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

Запрос на вход в КС. Когда процессу Р_i нужен доступ к КС, он переходит в состояние запроса на вход в КС, фиксируя показания своих скалярных часов L_i, и рассылает сообщение REQUEST(L_i, i) всем остальным процессам. Когда процесс Р_j получает запрос

REQUEST(L_i, i) от процесса Р_i, он отправляет процессу Р_i ответ REPLY в случае, если Р_j находится в состоянии выполнения вне КС, или в случае, если Р_j находится в состоянии запроса на вход в КС и отметка времени (L_j, j) его запроса больше отметки времени (L_i, i) запроса процесса Р_i. В противном случае Р_j откладывает отправку ответного сообщения REPLY и устанавливает DR_j[i] = 1.

2. 
   Вход в КС. Процесс Р_i может войти в КС, если он получил ответные сообщения REPLY от всех остальных процессов.
   
3. 
   Выход из КС. При выходе из КС процесс Р_i рассылает отложенные сообщения REPLY всем ожидающим процессам, т.е. всем процессам Р_j, для которых DR_i[j] = 1, и затем устанавливает DR_i[j] = 0.
   

Представленный алгоритм удовлетворяет требованиям безопасности и живучести для решения задачи взаимного исключения.

Докажем выполнение свойства безопасности от противного. Пусть два процесса P_i и Р_j выполняются в КС одновременно, и отметка времени запроса P_i меньше отметки времени запроса Р_j. Процесс Р_j может войти в КС, только когда он получит ответные сообщения от всех остальных процессов. При этом сообщение с запросом от Р_j достигло P_i после того, как P_i отправил свой запрос; в противном случае отметка времени запроса P_i должна была бы быть больше отметки времени запроса Р_j по правилам работы логических часов. По условиям алгоритма процесс P_i не может отослать ответное сообщение REPLY процессу Р_j, находясь в состоянии запроса на вход в КС и имея меньшее значение отметки времени своего запроса, до тех пор, пока P_i не выйдет из КС. Таким образом мы получаем противоречие с предположением, что Р_j получил ответные сообщения REPLY от всех процессов в системе, в том числе, от процесса P_i.
Покажем теперь, что алгоритм Рикарта-Агравала обладает свойством живучести. Процесс P_i не сможет получить доступ к КС, если он отправил свой запрос, но не получил необходимого ответа хотя бы от одного процесса P_j. В этом случае мы будем говорить, что P_i ждет P_j. Эта ситуация возможна, если процесс P_j находится либо в состоянии выполнения внутри КС, либо в состоянии запроса на вход в КС. При этом отметка времени запроса P_j должна быть меньше отметки времени запроса P_i. Если P_j выполняется внутри КС, то через ограниченное время он выйдет из КС и отправит ответное сообщение процессу P_i. Если же P_j находится в состоянии запроса на вход в КС, то либо он войдет в КС, либо должен существовать другой процесс P_k такой, что P_j ждет P_k. Продолжая эти рассуждения, мы построим цепь из процессов, ожидающих друг друга: P_i ждет P_j, P_j ждет P_k, P_k ждет P_m, и т.д. Важно отметить, что эта цепь имеет ограниченную длину и является ациклической: процессы располагаются в ней в порядке убывания отметок времени запросов. Последний процесс P_l
в этой цепи с наименьшим временем запроса либо выполняется в КС, либо получит разрешения от всех остальных процессов и сможет войти в КС. При выходе из КС P_l разошлет ответные сообщения всем ожидающим процессам, в том числе процессу, стоящему непосредственно слева от него, тем самым позволяя этому процессу войти в КС. Поэтому за ограниченное число шагов любой процесс окажется последним в цепи ожидающих процессов и сможет войти в КС.
Из этих рассуждений видно, что в алгоритме Рикарта-Агравала, также как и в алгоритме Лэмпорта, доступ к КС предоставляется строго в соответствии с отметками времени запросов по порядку, сохраняющему частичный причинно-следственный порядок →. Отсюда следует, что после получения сообщения REQUEST от процесса P_i всеми процессами ни один из них не сможет войти в КС более одного раза вперед P_i. Обратим также внимание, что в отличие от алгоритма Лэмпорта, в котором запросы на доступ КС явным образом выстраивались в очередь, в алгоритме Рикарта- Агравала процессы, желающие войти в КС, неявно упорядочиваются в ациклическую цепь, в которой каждый процесс ожидает поступления разрешений от процессов, стоящих справа от него.
Пример работы алгоритма Рикарта-Агравала приведен на рис. 4.3. Также как и в сценарии, представленном выше для алгоритма Лэмпорта, на рис. 4.3а процессы Р₂ и Р₃ запрашивают вход в КС приблизительно в одно и то же время. На рис. 4.3б процессы Р₁ и Р₃ получают запрос от Р₂ и отправляют ему ответные сообщения. В свою очередь процесс Р₂, получив запрос от Р₃, откладывает отправку ответного сообщения, т.к. Р₂ находится в состоянии запроса на вход в КС и отметка времени его запроса меньше отметки времени запроса Р₃. Соответствующий элемент массива DR₂ устанавливается в единицу. Поэтому процесс Р₃ не сможет получить доступ к КС до тех пор, пока Р₂ не войдет и не выйдет из нее. Далее в нашем сценарии процесс Р₁ переходит в состояние запроса на вход в КС и рассылает соответствующее сообщение остальным процессам, как показано на рис. 4.3б. Между тем, получив необходимые ответы от Р₁ и Р₃, процесс Р₂ входит в КС – см. рис. 4.3в. Затем запрос от процесса Р₁ достигает процессов Р₂ и Р₃. Обратим внимание, что при получении запроса от Р₁ процессы Р₂ и Р₃ не отправляют ответные сообщения, т.к. Р₂ находится в состоянии выполнения в КС, а Р₃ находится в состоянии запроса на вход в КС и отметка времени его запроса меньше отметки времени запроса Р₁. В итоге цепь ожидающих процессов будет выглядеть следующим образом: Р₁ ждет Р₃, Р₃ ждет Р₂. Эта ситуация проиллюстрирована на рис. 4.3в. Действительно, процесс Р₃ знает о том, что его ждет процесс Р₁, т.к. DR₃[1] = 1, а процесс Р₂ знает о том, что его ждут процессы Р₁ и Р₃, т.к. DR₂[1] = 1 и DR₂[3] = 1.

(а)

(б)

(в)

(г)

(д)

(е)

(ж)
Рис. 4.3. Пример работы алгоритма Рикарта-Агравала.

На рис. 4.3г процесс Р₂ выходит из КС и рассылает отложенные ответы ожидающим процессам Р₁ и Р₃. Теперь последним в цепи ожидающих процессов оказывается процесс Р₃, и он войдет в КС следующим. На рис. 4.3д запрос процесса Р₃ достигает процесса Р₁, и, несмотря на то, что сам Р₁ находится в состоянии запроса на вход в КС, он высылает Р₃ ответ, т.к. отметка времени запроса Р₁ больше отметки времени запроса Р₃. По получению необходимых ответов Р₃ входит в КС. Когда Р₃ выйдет из КС, он отправит Р₁ отложенный ответ, и Р₁ сможет войти в КС, как показано на рис. 4.3е. На рис. 4.3ж процесс Р₁ выходит из КС. При этом ему не требуется рассылать никаких сообщений.

Отметим, что в отличие от алгоритма Лэмпорта, алгоритм Рикарта- Агравала использует для работы с КС 2(N – 1) сообщений: (N – 1) сообщений требуется для входа в КС и (N – 1) сообщений требуется для выхода из КС.

3.