3-4-MPI-Sync (В.А. Крюков, В.А. Бахтин - Распределенные системы), страница 2

Названия функций и параметры:

MPI_BARRIER(IN comm)

MPI_BCAST(IN/OUT buffer, IN cnt, IN type, IN root, IN comm)

MPI_GATHER(IN sendbuf, IN sendcnt, IN sendtype, OUT recvbuf,

IN recvcnt, IN recvtype, IN root, IN comm)

MPI_SCATTER(IN sendbuf, IN sendcnt, IN sendtype, OUT recvbuf,

IN recvcnt, IN recvtype, IN root, IN comm)

MPI_ALLGATHER(IN sendbuf, IN sendcnt, IN sendtype,

OUT recvbuf, IN recvcnt, IN recvtype, IN comm)

MPI_ALLTOALL(IN sendbuf, IN sendcnt, IN sendtype, OUT recvbuf,

IN recvcnt, IN recvtype, IN comm)

У последних 4-х функций есть векторные варианты, предназначенные для работы с неравномерным распределением данных по процессорам.

PVM (Parallel Virtual Machine).

Широко известная система PVM [5] была создана для объединения нескольких связанных сетью рабочих станций в единую виртуальную параллельную ЭВМ. Система представляет собой надстройку над операционной системой UNIX и используется в настоящее время на различных аппаратных платформах, включая и ЭВМ с массовым параллелизмом.

Задача пользователя представляет собой множество подзадач, которые динамически создаются на указанных процессорах распределенной системы и взаимодействуют между собой путем передачи и приема сообщений (а также посредством механизма сигналов).

Достоинства - простота, наличие наследованного от OS UNIX аппарата процессов и сигналов, а также возможность динамического добавления к группе вновь созданных процессов.

Недостатки - низкая производительность и функциональная ограниченность (например, имеется только один режим передачи сообщений - с буферизацией).

MPI-2 (1997 г.) http://www.mpi-forum.org

Развивает MPI в следующих направлениях:

• Динамическое создание и уничтожение процессов (важно для работы в сетях ЭВМ).

• Односторонние коммуникации и средства синхронизации для организации взаимодействия процессов через общую память (для эффективной работы на системах с непосредственным доступом процессоров к памяти других процессоров).

• Параллельные операции ввода-вывода (для эффективного использования существующих возможностей параллельного доступа многих процессоров к различным дисковым устройствам).

4 Синхронизация в распределенных системах

Обычно децентрализованные алгоритмы имеют следующие свойства:

(1) Относящаяся к делу информация распределена среди множества ЭВМ.

(2) Процессы принимают решение на основе только локальной информации.

(3) Не должно быть единственной критической точки, выход из строя которой приводил бы к краху алгоритма.

(4) Не существует общих часов или другого источника точного глобального времени.

Первые три пункта все говорят о недопустимости сбора всей информации для принятия решения в одно место. Обеспечение синхронизации без централизации требует подходов, отличных от используемых в традиционных ОС.

Последний пункт также очень важен - в распределенных системах достигнуть согласия относительно времени совсем непросто. Важность наличия единого времени можно оценить на примере программы make в ОС UNIX.

4.1 Синхронизация времени.

Аппаратные часы (скорее таймер - счетчик временных сигналов и регистр с начальным значением счетчика) основаны на кварцевом генераторе и могут в разных ЭВМ различаться по частоте.

В 1978 году Lamport показал, что синхронизация времени возможна, и предложил алгоритм для такой синхронизации. При этом он указал, что абсолютной синхронизации не требуется. Если два процесса не взаимодействуют, то единого времени им не требуется. Кроме того, в большинстве случаев согласованное время может не иметь ничего общего с астрономическим временем, которое объявляется по радио. В таких случаях можно говорить о логических часах.

Для синхронизации логических часов Lamport определил отношение «произошло до». Выражение a-->b читается как «a произошло до b» и означает, что все процессы согласны, что сначала произошло событие «a», а затем «b». Это отношение может в двух случаях быть очевидным:

(1) Если оба события произошли в одном процессе.

(2) Если событие «a» есть операция SEND в одном процессе, а событие «b» - прием этого сообщения другим процессом.

Отношение --> является транзитивным.

Если два события «x» и «y» случились в различных процессах, которые не обмениваются сообщениями, то отношения x-->y и y-->x являются неверными, а эти события называют одновременными.

Введем логическое время С таким образом, что если a-->b, то C(a) < C(b)

Алгоритм:

(1) Часы Ci увеличивают свое значение с каждым событием в процессе Pi:

Ci = Ci + d (d > 0, обычно равно 1)

(2) Если событие «a» есть посылка сообщения «m» процессом Pi, тогда в это сообщение вписывается временная метка tm=Ci(a). В момент получения этого сообщения процессом Pj его время корректируется следующим образом:

Cj = max(Cj,tm+d)

Поясним на примере, как осуществляется эта коррекция.

Логическое время без коррекции. Логическое время с коррекцией.

Для целей упорядочения всех событий удобно потребовать, чтобы их времена никогда не совпадали. Это можно сделать, добавляя в качестве дробной части к времени уникальный номер процесса (40.1, 40.2).

Однако логических часов недостаточно для многих применений (системы управления в реальном времени).

Физические часы.

После изобретения в 17 веке механических часов время измерялось астрономически. Интервал между двумя последовательными достижениями солнцем наивысшей точки на небе называется солнечным днем. Солнечная секунда равняется 1/86400(24*3600) части солнечного дня. В 1940-х годах было установлено, что период вращения земли не постоянен - земля замедляет вращение из-за приливов и атмосферы. Геологи считают, что 300 миллионов лет назад в году было 400 дней. Происходят и изменения длительности дня по другим причинам. Поэтому стали вычислять за длительный период среднюю солнечную секунду.

С изобретением в 1948 году атомных часов появилась возможность точно измерять время независимо от колебаний солнечного дня. В настоящее время 50 лабораторий в разных точках земли имеют часы, базирующиеся на частоте излучения Цезия-133. Среднее значение является международным атомным временем (TAI), исчисляемым с 1 июля 1958 года.

Отставание TAI от солнечного времени компенсируется добавлением секунды тогда, когда разница становится больше 800 мксек. Это скорректированное время, называеемое UTC (Universal Coordinated Time), заменило прежний стандарт (Среднее время по Гринвичу - астрономическое время). При объявлении о добавлении секунды к UTC электрические компании меняют частоту с 60 Hz на 61 Hz (c 50 на 51) на период времени в 60 (50) секунд. Для обеспечения точного времени сигналы WWV передаются коротковолновым передатчиком (Fort Collins, Colorado) в начале каждой секунды UTC. Есть и другие службы времени.

Алгоритмы синхронизации времени.

Две проблемы - часы не должны ходить назад (надо ускорять или замедлять их для проведения коррекции) и ненулевое время прохождения сообщения о времени (можно многократно замерять время прохождения сообщений с показаниями часов туда и обратно, и брать самую удачную попытку – с минимальным временем прохождения).

4.2 Выбор координатора.

Многие распределенные алгоритмы требуют, чтобы один из процессов выполнял функции координатора, инициатора или некоторую другую специальную роль. Выбор такого специального процесса будем называть выбором координатора. При этом очень часто бывает не важно, какой именно процесс будет выбран. Можно считать, что обычно выбирается процесс с самым большим уникальным номером. Могут применяться разные алгоритмы, имеющие одну цель - если процедура выборов началась, то она должна закончиться согласием всех процессов относительно нового координатора.

Алгоритм «задиры».

Если процесс обнаружит, что координатор очень долго не отвечает, то инициирует выборы. Процесс P проводит выборы следующим образом:

1. P посылает сообщение «ВЫБОРЫ» всем процессам с большими чем у него номерами.

2. Если нет ни одного ответа, то P считается победителем и становится координатором.

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

В любой момент процесс может получить сообщение «ВЫБОРЫ» от одного из коллег с меньшим номером. В этом случае он посылает ответ «OK», чтобы сообщить, что он жив и берет проведение выборов на себя, а затем начинает выборы (если к этому моменту он уже их не вел). Следовательно, все процессы прекратят выборы, кроме одного - нового координатора. Он извещает всех о своей победе и вступлении в должность сообщением «КООРДИНАТОР».

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

Круговой алгоритм.