Электронный коспект лекций (1162752), страница 4

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

Текст из файла (страница 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)Поясним на примере, как осуществляется эта коррекция.Логическое время без коррекции.коррекцией.06121824303642485460>-2432-<0816404856647280>--<Логическое время с010200612304018245060708090100303642487076>-2432-<081640486169778501020>--<30405060708090100Для целей упорядочения всех событий удобно потребовать, чтобыих времена никогда не совпадали.

Это можно сделать, добавляя вкачестве дробной части к времени уникальный номер процесса(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передаются коротковолновым передатчиком(FortCollins,Colorado) в начале каждой секунды UTC. Есть и другие службывремени.Алгоритмы синхронизации времени.Две проблемы - часы не должны ходить назад (надо ускорятьили замедлять их для проведения коррекции) и ненулевоевремя прохождения сообщения о времени (можно многократнозамерять время прохождения сообщений с показаниями часовтуда и обратно,и брать самую удачную попытку – сминимальным временем прохождения).4.2Выбор координатора.Многие распределенные алгоритмы требуют, чтобы один изпроцессов выполнял функции координатора, инициатора илинекоторуюдругую специальную роль.Выбортакогоспециального процесса будем называть выбором координатора.При этом очень часто бывает не важно, какой именно процессбудет выбран. Можно считать, что обычно выбирается процесс ссамым большим уникальным номером.Могут применятьсяразные алгоритмы, имеющие одну цель - если процедура выборовначалась, то она должна закончиться согласием всех процессовотносительно нового координатора.Алгоритм «задиры».Если процесс обнаружит, что координатор очень долго неотвечает, то инициирует выборы.

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

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

После получения от всех разрешения, он входитв критическую секцию.Поведение процесса при приеме запросаКогда процесс получает сообщение-запрос, в зависимости отсвоего состояния по отношению к указанной критическойсекции он действует одним из следующих способов.1) Если получатель не находится внутри критической секции ине запрашивал разрешение на вход в нее, то он посылаетотправителю сообщение «OK».2) Если получатель находится внутри критической секции, тоон не отвечает, а запоминает запрос.3) Если получатель выдал запрос на вхождение в эту секцию,но еще не вошел в нее, то он сравнивает временные меткисвоего запроса и чужого. Побеждает тот, чья метка меньше.Если чужой запрос победил, то процесс посылает сообщение«OK».

Если у чужого запроса метка больше, то ответ непосылается, а чужой запрос запоминается.Выход из критической секцииПосле выхода из секции он посылает сообщение «OK» всемпроцессам, запросы от которых он запомнил, а затем стирает всезапомненные запросы.Количество сообщений на одно прохождение секции - 2(n-1), где n- число процессов.Кроме того, одна критическая точка заменилась на n точек (есликакой-то процесс перестанет функционировать, то отсутствиеразрешения от него всех остановит).И, наконец, если в централизованном алгоритме есть опасностьперегрузки координатора, то в этом алгоритме перегрузкалюбого процесса приведет к тем же последствиям.Некоторые улучшения алгоритма (например, ждать разрешенияне от всех, а от большинства) требуют наличия неделимыхшироковещательных рассылок сообщений.Следующие три алгоритма – маркерные.

Их основное отличие отдвух первых заключается в том, что процессы получаютразрешение на вход в критическую секцию только при наличиимаркера. В каждом алгоритме используется свой метод получениямаркера.Алгоритм с круговым маркером.Все процессы составляют логическое кольцо, когда каждыйзнает, кто следует за ним. По кольцу циркулирует маркер, дающийправо на вход в критическуюсекцию.Получивмаркер(посредством сообщения точка-точка) процесс либо входит вкритическую секцию (если он ждал разрешения)либопереправляет маркер дальше. После выхода из критическойсекции маркер переправляется дальше, повторный вход всекцию при том же маркере не разрешается.Алгоритм широковещательный маркерный (Suzuki-Kasami).Маркер содержит: очередь запросов; массив LN[1...N] с номерами последних удовлетворенныхзапросов.Вход в критическую секцию1) Если процесс Pk, запрашивающий критическую секцию, неимеет маркера, то он увеличивает порядковый номер своихзапросов RNk[k] и посылает широковещательно сообщение«ЗАПРОС»,содержащееномер процесса (k) и номерзапроса (Sn = RNk[k]).2) Процесс Pk выполняет критическую секцию, если имеет(или когда получит) маркер.Поведение процесса при приеме запроса1) Когда процесс Pj получит сообщение-запрос от процессаPk, он устанавливает RNj[k]=max(RNj[k],Sn).

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

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