Просмотр исходного текста страницы Алгоритм Рикарта-Агравалы

{| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
|+
|-align="center"
|'''НЕТ ВОЙНЕ'''
|-style="font-size: 16px;"
|
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.

Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.

Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.

Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.

''Антивоенный комитет России''
|-style="font-size: 16px;"
|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
|-style="font-size: 16px;"
|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
|}

[[Категория: Параллельное программирование]]
'''Алгоритм Рикарта-Агравалы''' — алгоритм взаимного исключения, являющийся оптимизацией [[Алгоритм Лампорта взаимного исключения|алгоритма Лампорта]].

Мы объединяем запросы rel и ok в один: вместо отправки ok сразу посылаем только если не хотим входить в критическую секцию или сразу как только выйдем из секции.

# Когда процесс <tex>P_i</tex> хочет войти в критический участок, то рассылает всем сообщение req с текущей временной меткой.
# Когда процесс <tex>P_k</tex> получает от <tex>P_j</tex> запрос войти в критический участок:
#* если он сам не посылал запрос, то посылает отклик;
#* если он послал свой запрос, он сравнивает временные метки этих двух запросов и посылает отклик только если у его собственного запроса метка позже (на самом деле, при равенстве меток, нужно проверять, у кого больше номер, т.е. для отсутствия блокировок нужно ввести приоритет на потоках);
#* в остальных случаях процесс <tex>P_k</tex> задерживает отправку отклика.
# Процесс может войти в критический участок только после получения откликов ото всех других узлов сети.
# После выхода из него он рассылает задержанные отклики на все ожидающие запросы.

В отличие от алгоритма Лапрота, нам не требуется ни третьего сообщения, ни хранить очередь запросов в каждом процессе.

[[Файл:mutex-distributed-ricart.png|400px]]

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

Отказ любого узла приводит к зависанию. Решается проблема введением таймаутов.