![]() КАТЕГОРИИ: Архитектура-(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". Это отношение может в двух случаях быть очевидным:
Отношение -> является транзитивным. Если два события x и y случились в различных процессах, которые не обмениваются сообщениями, то отношения x->y и y->x являются неверными, а эти события называют одновременными. Введем логическое время С таким образом, что если a->b, то C(a) < C(b) Алгоритм:
Сначала рассмотрим поведение данной системы безотносительно физического времени. Процесс X взаимодействует с процессом Y (например, направив ему сообщение). Можно утверждать, что отправка сообщения процессом X происходит до его получения процессом Y. Затем процесс Y взаимодействует с процессом Z.
Теперь предположим, что у каждого процесса имеются локальные часы, показания которых, могут расходиться. Для записи времени событий в каждом отдельном процессе можно использовать локальные часы, но при этом нужно выработать определенные соглашения о том, какое из событий побеждает (то есть происходит первым) при совпадении отметок времени. Например, для этого отметку времени можно дополнять идентификатором процесса. Общая последовательность событий в системе будет соблюдаться, если сможем гарантировать, что сдвиг частоты не вызовет нарушения ограничений. Предположим, что процесс X включает в отправляемое процессу Y сообщение отметку времени (отправка (m, tx)). Когда процесс Y получает это сообщение (получение (m, tx)), его собственные часы показывают ty (рис.5.2). -Если Ty > Tx, то все в порядке -Если Ty < Tx, то имеет место нарушение ограничения на порядок событий. Процесс Y может установить на своих часах время tx+ 1, и все будет в порядке, хотя системное время будет все больше и больше расходиться с реальным. Главное, что порядок событий в системе будет соблюдаться. 9. Выбор координатора. Алгоритм «задиры». Кольцевой алгоритм без маркера Координатор – один из процессов, который должен выполнить специальные функции по инициации, координации. Многие распределенные алгоритмы требуют, чтобы один из процессов выполнял функции координатора, инициатора или некоторую другую специальную роль. Выбор такого специального процесса будем называть выбором координатора. При этом очень часто бывает не важно, какой именно процесс будет выбран. Можно считать, что обычно выбирается процесс с самым большим уникальным номером. Могут применяться разные алгоритмы, имеющие одну цель - если процедура выборов началась, то она должна закончиться согласием всех процессов относительно нового координатора. Алгоритм "задиры"
В любой момент процесс может получить сообщение "ВЫБОРЫ" от одного из коллег с меньшим номером. В этом случае он посылает ответ "OK", чтобы сообщить, что он жив и берет проведение выборов на себя, а затем начинает выборы (если к этому моменту он уже их не вел). Следовательно, все процессы прекратят выборы, кроме одного - нового координатора. Он извещает всех о своей победе и вступлении в должность сообщением "КООРДИНАТОР". Если процесс выключился из работы, а затем захотел восстановить свое участие, то он проводит выборы (отсюда и название алгоритма).
Дата добавления: 2015-04-23; Просмотров: 3287; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |