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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м
Строка 15: Строка 15:
 
* При получении release от другого потока, его запрос удаляется из очереди
 
* При получении release от другого потока, его запрос удаляется из очереди
  
<tex>3*(N -1)</tex> messages.
+
Суммарно на каждую критическую секцию приходится <tex>3(N - 1)</tex> сообщение.

Версия 18:25, 19 июня 2013

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

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

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

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

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

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

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