Введение в распределенные

Оптимизация алгоритма Лэмпорта. В алгоритме Лэмпорта в некоторых ситуациях нет необходимости посылать ответные сообщения REPLY. А именно, если процесс Р_j получит запрос REQUEST(L_i, i) от процесса Р_i после того, как он сам отправил процессу Р_i некоторое сообщение с отметкой времени (L_j, j) > (L_i, i) (таким сообщением, например, может быть сообщение REQUEST(L_j, j), если Р_j соберется входить в КС практически одновременно с Р_i), то Р_j нет необходимости отправлять P_i ответное сообщение. Действительно, благодаря свойству FIFO канала связи между Р_j и Р_i поступление такого сообщения к процессу Р_i будет гарантировать, что ему от P_j больше не поступит запросов с отметкой времени меньшей, чем (L_i, i). К примеру, на рис. 4.2ж процесс P₁ получает от процесса P₃ запрос с отметкой времени (1, 3) уже после того, как сам отправил запрос с отметкой времени (4, 1) – см. рис. 4.2д. Поэтому показанное на рис. 4.2з ответное сообщение из процесса P₁ в процесс P₃ с отметкой времени (11, 1) можно было не пересылать.
С учетом представленной оптимизации число сообщений, необходимых для обеспечения взаимного исключения в алгоритме Лэмпорта, будет варьироваться от 2(N – 1) до 3(N – 1).

2. Алгоритм Рикарта-Агравала

Рассмотренный выше алгоритм Лэмпорта явным образом выстраивает запросы на доступ к КС в очередь в порядке возрастания их отметок времени. Еще раз обратим внимание на роль сообщений REPLY и RELEASE в этом алгоритме. Ответные сообщения REPLY используются исключительно для информирования процесса, запрашивающего вход в КС, о том, что в каналах не осталось ни одного другого запроса, который мог бы встать перед его запросом в его локальной очереди. Роль сообщения RELEASE сводится к удалению обслуженного запроса из всех локальных очередей для предоставления другим процессам возможности войти в КС. Отсюда видно, что отметки логического времени, переносимые этими сообщениями, не играют существенной роли в функционировании алгоритма и могут быть опущены. В этом случае при проверке второго условия входа в КС процесс будет опираться не на время получаемых сообщений, а на число поступивших сообщений REPLY: второе условие входа в КС в алгоритме Лэмпорта будет выполнено, когда процесс, запрашивающий доступ к КС, получит все сообщения REPLY от всех остальных процессов.
В работе Г. Рикарта и А. Агравала предпринята попытка оптимизировать алгоритм Лэмпорта, исключив из него сообщения RELEASE за счет объединения функций сообщений RELEASE и REPLY в одном сообщений. Более того, алгоритм Рикарта-Агравала не требует, чтобы каналы связи обладали свойством FIFO. Основная идея этого алгоритма заключается в том, что для входа в КС процессу требуется собрать разрешения от всех других процессов распределенной системы. Для этого процесс, желающий получить доступ к КС, рассылает свой запрос REQUEST всем остальным процессам и ожидает от них поступления разрешений в виде сообщений REPLY. Условия, при которых процессы дают свое разрешение на вход в КС, сформулированы таким образом, чтобы удовлетворить требованиям безопасности и живучести. А именно, если все остальные процессы находятся в состоянии выполнения вне КС, они немедленно отправляют процессу, запрашивающему доступ к КС, сообщения REPLY. Если же один из процессов выполняется в КС, то он откладывает отправку своего разрешения до тех пор, пока сам не покинет КС, тем самым не позволяя двум процессам выполняться в КС одновременно. Если же несколько процессов запрашивают разрешение на вход в КС в одно и то же время, то, как и в алгоритме Лэмпорта, для разрешения конфликта доступа к КС используются линейно упорядоченные отметки времени запросов (L_i, i), где L_i – скалярное время процесса P_i на момент формирования запроса, i – идентификатор процесса P_i. Процесс, запрос которого имеет наименьшую отметку времени, получит право войти в КС первым. Это достигается за счет того, что каждый находящийся в состоянии запроса на вход в КС процесс P_i при получении запроса от другого процесса P_j сравнивает отметку времени (L_i, i) своего запроса с отметкой времени (L_j, j) поступившего запроса, и откладывает отправку REPLY, если (L_i, i) < (L_j, j). Если же (L_i, i) > (L_j, j), то процесс P_i отправляет сообщение REPLY процессу P_j немедленно. Поэтому процесс с наименьшей отметкой времени запроса получит ответные сообщения от всех остальных процессов и сможет войти в КС.
Для реализации алгоритма Рикарта-Агравала каждый процесс P_i поддерживает работу с массивом DR_i[1..N], содержащим признаки отложенного ответа (от англ. deferred reply). Если процесс P_i откладывает отправку ответного сообщения процессу P_j, он устанавливает DR_i[j] = 1; после отправки сообщения REPLY элемент DR_i[j] сбрасывается в ноль. Все элементы DR_i[k] инициализируется нулем, 1 ≤ k ≤ N. С учетом этого массива алгоритм Рикарта-Агравала будет определяться следующими правилами.

1.