Лекционные материалы (1162669), страница 4

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

При этом пользователь может сам определитьглобальную операцию - функцию;Схема перемещения данных между 4 процессамиДанныеPr-0Pr-1Pr-2Pr-3A0Pr-0Pr-1Pr-2Pr-3A0A1A2A3Pr-0Pr-1Pr-2Pr-3A0A0A0A0A1A1A1A1A2A2A2A2A3A3A3A3Pr-0Pr-1Pr-2Pr-3A0B0C0D0A1B1C1D1A2B2C2D2A3B3C3D3BROADCASTA0A0A0A0SCATTERGATHERA0A1A2A3ALLGATHERA0A1A2A3ALLTOALLA0A1A2A3B0B1B2B3C0C1C2C3D0D1D2D316Названия функций и параметры: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 в следующих направлениях:Динамическое создание и уничтожение процессов (важно для работы в сетях ЭВМ).Односторонние коммуникации и средства синхронизации для организации взаимодействияпроцессов через общую память (для эффективной работы на системах с непосредственнымдоступом процессоров к памяти других процессоров).Параллельные операции ввода-вывода (для эффективного использования существующихвозможностей параллельного доступа многих процессоров к различным дисковымустройствам).174 Синхронизация в распределенных системахОбычно децентрализованные алгоритмы имеют следующие свойства:(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)18Поясним на примере, как осуществляется эта коррекция.Логическое время без коррекции.06121824303642485460>--<08162432404856647280>--<Логическое время с коррекцией.01020304050607080901000612182430364248707608 162432404861-< 697785>--0102030>- 4050-< 60708090100Для целей упорядочения всех событий удобно потребовать, чтобы их времена никогда несовпадали. Это можно сделать, добавляя в качестве дробной части к времени уникальныйномер процесса (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. Есть и другие службывремени.Алгоритмы синхронизации времени.Две проблемы - часы не должны ходить назад (надо ускорять или замедлять их дляпроведения коррекции) и ненулевое время прохождения сообщения о времени (можномногократно замерять время прохождения сообщений с показаниями часов туда иобратно, и брать самую удачную попытку – с минимальным временем прохождения).194.2Выбор координатора.Многие распределенные алгоритмы требуют, чтобы один из процессов выполнял функциикоординатора, инициатора или некоторую другую специальную роль.

Выбор такогоспециального процесса будем называть выбором координатора. При этом очень часто бываетне важно, какой именно процесс будет выбран. Можно считать, что обычно выбираетсяпроцесс с самым большим уникальным номером. Могут применяться разные алгоритмы,имеющие одну цель - если процедура выборов началась, то она должна закончитьсясогласием всех процессов относительно нового координатора.Алгоритм «задиры».Если процесс обнаружит, что координатор очень долго не отвечает, то инициируетвыборы. Процесс P проводит выборы следующим образом:1) P посылает сообщение «ВЫБОРЫ» всем процессам с большими чем у него номерами.2) Если нет ни одного ответа, то P считается победителем и становится координатором.3) Если один из процессов с большим номером ответит, то он берет на себя проведениевыборов.

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

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

Характеристики

Список файлов лекций