2014-02-17
1261
Лекция №17
Распределенные вычисления
Модель распределенных систем/процессов
Процессы – последовательные, работающие параллельно, обменивающиеся друг с другом информацией посредством сообщений.
Существует 2 ограничения:
1. Время доставки сообщения существенно
2. Необходимо учитывать отказы (корректная работа одного процесса не должна зависеть от отказа других процессов, с которыми он работает)
Классификационные признаки:
· Тип топологии коммуникаций:
Ø Связность
§ Полносвязный (коммуникационный граф)
§ Неполносвязный
Ø Ориентированность
§ Ориентированный (по одному “линку” отправляет, по другому принимает)
§ Неориентированный
· Синхронность (наличие реального времени, времени, замеренного реальными часами)
Ø Асинхронные (в таких моделях не делается никаких предположений о способах измерения времени)
Ø Использующие таймеры (в таких моделях делаются предположения о верхних границах времени доставки сообщений, а таймер измеряет реальное время)
|
|
|
Ø Использующие часы (каждый процесс имеет измеритель времени, и показания этих измерителей расходятся не более чем на заданную погрешность. Использование часов позволяет сократить число передаваемых сообщений. Имеется специальный класс алгоритмов, которые позволяют строить систему на базе таймеров и часов)
Ø Полностью синхронные модели (в таких моделях вычисления похожи на многопроцессорные системы с использованием циклов)
· Отказы
Ø Отказы линков
§ Потеря связности коммуникационного графа
§ Потеря сообщения
Ø Отказы процессов
§ Византийский отказ (отказ процесса не влияет на несвязанные с ним линии, возможно любое поведение отказавшего процесса. Общий метод борьбы с византийским отказом – использование цифровой подписи)
§ Отказ-пропуск (поврежденный процесс не может посылать некоторые сообщения. Моделирует процесс перезагрузки системы)
§ Отказ-остановка (отказавший процесс не может послать никакие сообщения. Имитирует крах системы обнаруживаемый или необнаруживаемый)
· Буферизация
Ø Ограниченная
§ С ожиданием освобождения буфера
§ Со сбоем и специальным сообщением при переполнении
Ø Неограниченная
Ø С произвольным порядком
Ø FIFO (очередь. На физическом уровне всегда гарантирована FIFO буферизация. Существуют специальные алгоритмы, которые восстанавливают порядок сообщений)
Другие модели распределенных вычислений:
· CSP (модель Хоара, взаимодействующие последовательные процессы)
· Рандеву
· RPC (удаленный вызов процедур)
Рассмотрим следующие модели:
1. Глобальное распределение переменных
|
|
|
Ранняя модель параллельных вычислений. Операция чтения/записи состоит из двух сообщений: запроса и ответа. Для реализации такой модели требуется разместить переменную в процессе. Тогда каждая операция чтения/записи потребует посылки двух сообщений (запрос/прием и передача/подтверждение записи). Такая реализация не является отказоустойчивой. Отказоустойчивая реализация требует наличия нескольких копий переменной, а значит и большее количество пересылаемых сообщений.
2. Локальное распределение переменных
Для каждой переменной определяется “владение процессом”: только процесс, владеющий переменной, может изменять ее значение. Остальные процессы только читают переменные. Чтение переменной отказавшего процесса предполагает возврат предопределенного значения (признака ошибки).
3. CSP – взаимодействующие последовательные процессы (модель Хоара)
Синхронизация мониторами (Java).
Определены 2 специальные команды:!?
i: j! Y – в этой модели процесс i выполняет команду вывода значения Y, процесс j выполняет команду j! Y. В свою очередь, процесс j считывает значение, переданное i в переменную X, выполняя команду i? X. Причем обе команды выполняются одновременно.
Использовалась в транспьютерах фирмы InMos (MK, соединяемые друг с другом в матрицу).
В настоящее время используется для верификации:
P ↔ j! v | P – алгебраическая форма записи.
Во многих распределенных алгоритмах требуется чтобы процесс мог взаимодействовать с несколькими соседями, а фактически взаимодействовал только с одним.
Рассмотрим следующий граф взаимодействий процессов:
В
А С
В таком графе каждый процесс может взаимодействовать с каждым, однако, фактически выполняется только одно какое-то взаимодействие. А принятие решения какое именно, требует сложного распределенного алгоритма.
Данной проблемы можно избежать, если ввести ограничение: процесс, готовый выполнить операцию вывода, не может ожидать других взаимодействий, но по-прежнему процесс может ждать на любом количестве операций ввода. Однако такая реализация не является отказоустойчивой, т.к. процесс, ожидающий операцию вывода с отказавшим процессом, тоже приходит к отказу.
Произвольная модель «Рандеву» (в языке Ada). (WaitforMultipleObject, delegateThread).
4) RPC-удаленный вызов процедуры.
В модели RPC вызов выполняется в одном процессе, исполнение в другом.
DCOM (Microsoft), RMI(Java), CORBA
Впервые описаны в 1980г.
Основные алгоритмы
· Алгоритм с разделяемыми переменными:
– Задачи взаимного исключения:
§ Задача «о критической секции» (1965), Дейкстра
§ Задача «обедающие философы», Дейкстра
Иллюстрирует пользу семафоров (философ не приступает к столу, если оба его соседа едят).
§ Задача «писатели-читатели»
– Задача о кооперации
§ Задача “Поставщик-Потребитель”
§ Маркирование графа (сети Петри)
– Смешанные задачи
· Алгоритмы достижения соглашения
– «Задача о двух генералах»
Два генерала должны договориться между собой о времени общей атаки на неприятеля (поодиночке им его не одолеть), для чего должны использовать единственный доступный им способ передачи сообщений – посылать гонцов.
Решения задача не имеет. При наличии коммуникационного отказа, соглашение о времени атаки невозможно (ненадежная связь, линк).
– Выбор общего значения
На входах всех процессов находятся некоторые числа, по завершении алгоритма на выходе всех неотказавших процессов должно быть одно и то же число. Число – 1/3.
– Одновременное действие («о стрелках»)
– Синхронизация часов
– Распределенная транзакция
Имеется несколько процессов. Если все процессы согласны завершить транзакцию, то она завершится, иначе, если хотя бы один не согласен, происходит откат.
