Алгоритм Лампорта взаимного исключения — различия между версиями
| Строка 9: | Строка 9: | ||
# Ждет от них ответа (ok) | # Ждет от них ответа (ok) | ||
# Получив все ответы, ждет, когда он станет первым в своей очереди, и входит в критическую секцию | # Получив все ответы, ждет, когда он станет первым в своей очереди, и входит в критическую секцию | ||
| − | # Выйдя из критической секции, посылает всем сообщение о том, что вышел (rel) | + | # Выйдя из критической секции, удаляет свой запрос из своей очереди, посылает всем сообщение о том, что вышел (rel) |
Действия вне критической секции: | Действия вне критической секции: | ||
Версия 23:15, 8 апреля 2019
Алгоритм Лампорта -- алгоритм взаимного исключения, работающий в случае, если все сообщения идут FIFO и использующий логические часы Лампорта.
Каждый поток поддерживает очередь запросов на вход в критическую секцию. Приоритет – <временная метка, номер потока> (т.е при равенстве временных меток берем тот поток, чей номер меньше).
Когда поток хочет войти в критическую секцию, он:
- Добавляет свой запрос в свою очередь (т.е временную метку и номер потока)
- Посылает всем потокам запрос (req)
- Ждет от них ответа (ok)
- Получив все ответы, ждет, когда он станет первым в своей очереди, и входит в критическую секцию
- Выйдя из критической секции, удаляет свой запрос из своей очереди, посылает всем сообщение о том, что вышел (rel)
Действия вне критической секции:
- При получении запроса от другого потока, запрос добавляется в очередь и запрашивающему потоку посылается ответ
- При получении release от другого потока, его запрос удаляется из очереди
Суммарно на каждую критическую секцию приходится сообщение.
