Алгоритм Лампорта взаимного исключения — различия между версиями
| Строка 1: | Строка 1: | ||
[[Категория: Параллельное программирование]] | [[Категория: Параллельное программирование]] | ||
| − | '''Алгоритм Лампорта''' взаимного исключения | + | '''Алгоритм Лампорта''' -- алгоритм взаимного исключения, работающий в случае, если все сообщения идут FIFO и использующий логические часы Лампорта. |
| − | + | Каждый поток поддерживает очередь запросов на вход в критическую секцию. Приоритет – <временная метка, номер потока> (т.е при равенстве временных меток берем тот поток, чей номер меньше). | |
Когда поток хочет войти в критическую секцию, он: | Когда поток хочет войти в критическую секцию, он: | ||
# Добавляет свой запрос в свою очередь (т.е временную метку и номер потока) | # Добавляет свой запрос в свою очередь (т.е временную метку и номер потока) | ||
| − | # Посылает всем потокам запрос | + | # Посылает всем потокам запрос (req) |
| − | # Ждет от них ответа | + | # Ждет от них ответа (ok) |
# Получив все ответы, ждет, когда он станет первым в своей очереди, и входит в критическую секцию | # Получив все ответы, ждет, когда он станет первым в своей очереди, и входит в критическую секцию | ||
| − | # Выйдя из критической секции, посылает всем сообщение | + | # Выйдя из критической секции, посылает всем сообщение о том, что вышел (rel) |
Действия вне критической секции: | Действия вне критической секции: | ||
| − | * При получении запроса от другого потока, запрос добавляется в очередь и запрашивающему потоку посылается ответ | + | * При получении запроса от другого потока, запрос добавляется в очередь и запрашивающему потоку посылается ответ |
* При получении release от другого потока, его запрос удаляется из очереди | * При получении release от другого потока, его запрос удаляется из очереди | ||
Суммарно на каждую критическую секцию приходится <tex>3(N - 1)</tex> сообщение. | Суммарно на каждую критическую секцию приходится <tex>3(N - 1)</tex> сообщение. | ||
Версия 19:04, 16 мая 2018
Алгоритм Лампорта -- алгоритм взаимного исключения, работающий в случае, если все сообщения идут FIFO и использующий логические часы Лампорта.
Каждый поток поддерживает очередь запросов на вход в критическую секцию. Приоритет – <временная метка, номер потока> (т.е при равенстве временных меток берем тот поток, чей номер меньше).
Когда поток хочет войти в критическую секцию, он:
- Добавляет свой запрос в свою очередь (т.е временную метку и номер потока)
- Посылает всем потокам запрос (req)
- Ждет от них ответа (ok)
- Получив все ответы, ждет, когда он станет первым в своей очереди, и входит в критическую секцию
- Выйдя из критической секции, посылает всем сообщение о том, что вышел (rel)
Действия вне критической секции:
- При получении запроса от другого потока, запрос добавляется в очередь и запрашивающему потоку посылается ответ
- При получении release от другого потока, его запрос удаляется из очереди
Суммарно на каждую критическую секцию приходится сообщение.
