Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Алгоритм Лампорта




Логические часы. Алгоритм Лампорта

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

В 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)

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

 

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

Общая последовательность событий в системе будет соблюдаться, если сможем гарантировать, что сдвиг частоты не вызовет нарушения ограничений. Предположим, что процесс X включает в отправляемое процессу Y сообщение отметку времени (отправка (m, tx)). Когда процесс Y получает это сообщение (получение (m, tx)), его собственные часы показывают ty (рис.5.2).

-Если Ty > Tx, то все в порядке

-Если Ty < Tx, то имеет место нарушение ограничения на порядок событий.

Процесс Y может установить на своих часах время tx+ 1, и все будет в порядке, хотя системное время будет все больше и больше расходиться с реальным. Главное, что порядок событий в системе будет соблюдаться.

9. Выбор координатора. Алгоритм «задиры». Кольцевой алгоритм без маркера

Координатор – один из процессов, который должен выполнить специальные функции по инициации, координации.

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

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

  1. P посылает сообщение "ВЫБОРЫ" всем процессам с большими, чем у него номерами.
  2. Если нет ни одного ответа, то P считается победителем и становится координатором.
  3. Если один из процессов с большим номером ответит, то он берет на себя проведение выборов. Участие процесса P в выборах заканчивается.

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

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

 




Поделиться с друзьями:


Дата добавления: 2015-04-23; Просмотров: 3205; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.009 сек.