Лекция №18

Лекция №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.

– Одновременное действие («о стрелках»)

– Синхронизация часов

– Распределенная транзакция

Имеется несколько процессов. Если все процессы согласны завершить транзакцию, то она завершится, иначе, если хотя бы один не согласен, происходит откат.

Дата добавления: 2014-12-07