Алгоритм Лампорта взаимного исключения — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 9: Строка 9:
 
# Ждет от них ответа (ok)
 
# Ждет от них ответа (ok)
 
# Получив все ответы, ждет, когда он станет первым в своей очереди, и входит в критическую секцию
 
# Получив все ответы, ждет, когда он станет первым в своей очереди, и входит в критическую секцию
# Выйдя из критической секции, посылает всем сообщение о том, что вышел (rel)
+
# Выйдя из критической секции, удаляет свой запрос из своей очереди, посылает всем сообщение о том, что вышел (rel)
  
 
Действия вне критической секции:
 
Действия вне критической секции:

Версия 23:15, 8 апреля 2019

Алгоритм Лампорта -- алгоритм взаимного исключения, работающий в случае, если все сообщения идут FIFO и использующий логические часы Лампорта.

Каждый поток поддерживает очередь запросов на вход в критическую секцию. Приоритет – <временная метка, номер потока> (т.е при равенстве временных меток берем тот поток, чей номер меньше).

Когда поток хочет войти в критическую секцию, он:

  1. Добавляет свой запрос в свою очередь (т.е временную метку и номер потока)
  2. Посылает всем потокам запрос (req)
  3. Ждет от них ответа (ok)
  4. Получив все ответы, ждет, когда он станет первым в своей очереди, и входит в критическую секцию
  5. Выйдя из критической секции, удаляет свой запрос из своей очереди, посылает всем сообщение о том, что вышел (rel)

Действия вне критической секции:

  • При получении запроса от другого потока, запрос добавляется в очередь и запрашивающему потоку посылается ответ
  • При получении release от другого потока, его запрос удаляется из очереди

Суммарно на каждую критическую секцию приходится [math]3(N - 1)[/math] сообщение.