Алгоритм Рикарта-Агравалы — различия между версиями
Ulyantsev (обсуждение | вклад) |
Ulyantsev (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
[[Категория: Параллельное программирование]] | [[Категория: Параллельное программирование]] | ||
'''Алгоритм Рикарта-Агравалы''' взаимного исключения: | '''Алгоритм Рикарта-Агравалы''' взаимного исключения: | ||
| − | # Когда процесс <tex>P_i</tex> хочет войти в критический участок, то рассылает всем сообщение "запрос" с текущей временной меткой | + | # Когда процесс <tex>P_i</tex> хочет войти в критический участок, то рассылает всем сообщение "запрос" с текущей временной меткой. |
# Когда процесс <tex>P_k</tex> получает от <tex>P_j</tex> запрос войти в критический участок: | # Когда процесс <tex>P_k</tex> получает от <tex>P_j</tex> запрос войти в критический участок: | ||
| − | #* если он сам не посылал запрос, то посылает отклик | + | #* если он сам не посылал запрос, то посылает отклик; |
| − | #* если он послал свой запрос, он сравнивает временные метки этих двух запросов и посылает отклик только если у его собственного запроса метка позже (на самом деле, при равенстве меток, нужно проверять, у кого больше номер, т.е. для отсутствия блокировок нужно ввести приоритет на потоках) | + | #* если он послал свой запрос, он сравнивает временные метки этих двух запросов и посылает отклик только если у его собственного запроса метка позже (на самом деле, при равенстве меток, нужно проверять, у кого больше номер, т.е. для отсутствия блокировок нужно ввести приоритет на потоках); |
| − | #* в остальных случаях процесс <tex>P_k</tex> задерживает отправку отклика | + | #* в остальных случаях процесс <tex>P_k</tex> задерживает отправку отклика. |
| − | # Процесс может войти в критический участок только после получения откликов ото всех других узлов сети | + | # Процесс может войти в критический участок только после получения откликов ото всех других узлов сети. |
| − | # После выхода из него он рассылает задержанные отклики на все | + | # После выхода из него он рассылает задержанные отклики на все ожидающие запросы. |
| − | ожидающие запросы | ||
Starvation-free. <tex>2 \cdot (N-–1)</tex> messages. | Starvation-free. <tex>2 \cdot (N-–1)</tex> messages. | ||
Отказ любого узла приводит к зависанию. Решается проблема введением таймаутов. | Отказ любого узла приводит к зависанию. Решается проблема введением таймаутов. | ||
Версия 18:58, 26 июня 2010
Алгоритм Рикарта-Агравалы взаимного исключения:
- Когда процесс хочет войти в критический участок, то рассылает всем сообщение "запрос" с текущей временной меткой.
- Когда процесс получает от запрос войти в критический участок:
- если он сам не посылал запрос, то посылает отклик;
- если он послал свой запрос, он сравнивает временные метки этих двух запросов и посылает отклик только если у его собственного запроса метка позже (на самом деле, при равенстве меток, нужно проверять, у кого больше номер, т.е. для отсутствия блокировок нужно ввести приоритет на потоках);
- в остальных случаях процесс задерживает отправку отклика.
- Процесс может войти в критический участок только после получения откликов ото всех других узлов сети.
- После выхода из него он рассылает задержанные отклики на все ожидающие запросы.
Starvation-free. messages.
Отказ любого узла приводит к зависанию. Решается проблема введением таймаутов.
