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

Материал из Викиконспекты
Версия от 19:59, 26 июня 2010; 192.168.0.2 (обсуждение) (Новая страница: «Категория: Параллельное программирование Модифицируем [[Алгоритм Лампорта взаимного и…»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Модифицируем алгоритм Лампорта взаимного исключения. Будем предполагать FIFO-порядок сообщений. Также будем предполагать, что сообщения транслируются всем процессам. Каждый процесс содержит логические часы и очередь отправленных сообщений.

Алгоритм действует по следующим правилам:

  1. Чтобы отправить сообщение процесс транслирует свое время всем остальных (шаг аналогичен запросу на вход в критическую секцию)
  2. При приеме сообщения оно сохраняется вместе со временем и отправляется подтверждение, также помеченное временем
  3. Сообщение может быть доставлено процессу, если от всех остальных потоков получены сообщения с большей временной меткой (шаг аналогичен работе критической секции)