Изменения

'''Алгоритм Рикарта-Агравалы''' — алгоритм взаимного исключения, являющийся оптимизацией [[Алгоритм Лампорта взаимного исключения|алгоритма Лампорта]]. Мы объединяем запросы rel и ok в один:вместо отправки ok сразу посылаем только если не хотим входить в критическую секцию или сразу как только выйдем из секции. # Когда процесс <tex>Р_iP_i</tex> хочет войти в критический участок, то рассылает всем сообщение &quot;запрос&quot; req с текущей временной меткой.

#* если он сам не посылал запрос, то посылает отклик;#* если он послал свой запрос, он сравнивает временные метки этих двух запросов и посылает отклик только если у его собственного запроса метка позже (на самом деле, при равенстве меток, нужно проверять, у кого больше номер, т.е. для отсутствия блокировок нужно ввести приоритет на потоках);#* в остальных случаях процесс <tex>P_k</tex> задерживает отправку отклика.# Процесс может войти в критический участок только после получения откликов ото всех других узлов сети.# После выхода из него он рассылает задержанные отклики на всеожидающие запросы. В отличие от алгоритма Лапрота, нам не требуется ни третьего сообщения, ни хранить очередь запросов в каждом процессе. [[Файл:mutex-distributed-ricart.png|400px]]

StarvationАлгоритм является starvation-free. Суммарно на каждую критическую секцию приходится <tex>2*\cdot (N-–11)</tex> messagesсообщений.