В.А. Крюков - Операционные системы распределенных вычислительных систем (1158860), страница 4
Текст из файла (страница 4)
Если места в буфере нет - ошибка программы(но есть возможность определить свой буфер). Операция локальная.В синхронном режиме последовательность выдачи операций произвольна, но операцияsend завершается только после выдачи и начала выполнения операции receive. Для этогопосылающая сторона запрашивает у принимающей стороны подтверждение выдачи операцииreceive. Операция нелокальная.В режиме готовности операция send может быть выдана толькопосле выдачисоответствующей операции receive, иначе программа считается ошибочной и результат ееработы не определен. Операция нелокальная.15Во всех четырех режимах операция receive завершается после получения сообщения взаданный пользователем буфер приема.Неблокирующие операции не приостанавливают процесс до своего завершения, авозвращают ссылку на коммуникационный объект, позволяющий опрашивать состояниеоперации или дожидаться ее окончания.Имеются операции проверки поступающих процессу сообщений, без чтения их в буфер(например, для определения длины сообщения и запроса затем памяти под него).Имеется возможность аварийно завершать выданные неблокирующие операции, и поэтомупредоставлены возможности проверки, хорошо ли завершились операции.Имеется составная операция send-receive, позволяющая избежать трудностей с порядкомвыдачи отдельных операций в обменивающихся между собой процессах.
Для частного случаяобмена данными одного типа и длины предлагается специальная операция (send-receivereplace), в которой для посылки и приема сообщения используется один буфер.(8) Коллективные коммуникации.Для обеспечения коллективных коммуникаций введены следующие функции:барьер для всех членов группы (BARRIER);передача сообщения всем членам группы от одного (BROADCAST);сбор данных от всех членов группы для одного (GATHER);рассылка данных всем членам группы от одного (SCATTER);сбор данных от всех членов группы для всех (ALLGATHER);рассылка данных всем членам группы от всех (ALLTOALL);глобальные операции (сумма, максимум, и т.п.), когда результат сообщается всемчленам группы или только одному. При этом пользователь может сам определитьглобальную операцию - функцию;Схема перемещения данных между 4 процессамиДанныеPr-0Pr-1Pr-2Pr-3A0Pr-0Pr-1Pr-2Pr-3A0A1A2A3Pr-0Pr-1Pr-2Pr-3A0A0A0A0A1A1A1A1A2A2A2A2A3A3A3A3Pr-0Pr-1Pr-2Pr-3A0B0C0D0A1B1C1D1A2B2C2D2A3B3C3D3BROADCASTA0A0A0A0SCATTERGATHERA0A1A2A3ALLGATHERA0A1A2A3ALLTOALLA0A1A2A3B0B1B2B3C0C1C2C3D0D1D2D316Названия функций и параметры: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-< 697785>--0102030>- 4050-< 60708090100Для целей упорядочения всех событий удобно потребовать, чтобы их времена никогда несовпадали. Это можно сделать, добавляя в качестве дробной части к времени уникальныйномер процесса (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) Если один из процессов с большим номером ответит, то он берет на себя проведениевыборов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
