10 Алгоритмы синхронизации процессов. Примитивы взаимоисключения.

1.Взаимоисключение для n процессов

 

Программное решение проблемы реализации примитивов взаимо­исключения для п процессов первым предложил Дейкстра. Затем Кнут усовершенствовал алгоритм Дейкстры, исклю­чив возможность бесконечного откладывания процессов, однако в варианте Кнута некоторый процесс по-прежнему мог испытывать (потенциально) длительную задержку. В связи с этим многие уче­ные начали искать алгоритмы, обеспечивающие более короткие за­держки. Так, Эйзенберг и Макгайр  предложили решение, гарантирующее, что процесс будет входить в свой критический учас­ток не более чем за п—1 попыток. Лэмпорт разработал алгоритм, применимый, в частности, для распределенных систем об­работки данных. Алгоритм Лэмпорта предусматривает «предвари­тельное получение номерка», подобно тому как это делается в мод­ных кондитерских, и поэтому подучил наименованиеалгоритма кондитера (Bakery Algorithm). Бринк Хансен также предлагает возможные варианты управления параллельными распределенны­ми процессами.

 

2. Аппаратная реализация взаимоисключения: команда testandset

 

Алгоритм Деккера — это программное решение проблемы взаи­моисключения. В данном разделе мы приводим аппаратное решение данной проблемы.

Главным фактором, обеспечивающим успех в этом случае, является наличие одной аппаратной команды, которая осуществляет чтение переменной, запись ее значения в область сохранения и установку нужного конкретного значения этой переменной. Подоб­ная команда, обычно называемая testandset (проверить-и-установить), после запуска выполняет все эти действия до конца без пре­рывания. Неделимая команда

testandset (а, b)

читает значение логической переменной b, копирует его в а, а затем устанавливает для b значение «истина» — и все это в рамках одной непрерываемой операции. Пример использования команды проверки и установки для реализации взаимоисключения приведен на рис. 1.

 

program npимeptestandset var активный: логический;

procedure процессодин;

    var первомувходитьнельзя: логический;

begin

while истина do

begin

первомувходитьнельзя : = истина;

while первомувходитьнельзя do

testandset (первомувходитьнельзя, активный);

                        критическийучастокодин;

активный : = ложь;

прочиеоператорыодин

end

end;

procedure процессдва;

    var второмувходитьнельзя: логический;

begin

while истина do

begin

второмувходитьнельзя : = истина;

while второмувходитьнельзя do

testandset (второмувходитьнельзя, активный);

критическийучастокдва;

активный : = ложь;

прочиеоператорыдва

             end

end;

begin

активный : = ложь;

parbegin

процессодин;

           процессдва parend

end;

 

Рис. 1. Реализация взаимоисключения при помощи команды testandsef

            (ПРОВЕРИТЬ И УСТАНОВИТЬ).

 

Переменная «активный» логического типа имеет значение «исти­на», когда любой из процессов находится в своем критическом участ­ке, и значение «ложь» в противном случае. «Процессодин» прини­мает решение о входе в критический участок в зависимости от значения своей локальной логической переменной «первомувходитьнельзя». Он устанавливает для переменной «первомувходитьнельзя» значение «истина», а затем многократно выполняет команду про­верки и установки для глобальной логической переменной «актив­ный». Если «процессдва» находится вне критического участка, пере­менная «активный» будет иметь значение «ложь». Команда проверки и установки запишет это значение в «первомувходитьнельзя» и ус­тановит] значение «истина» для переменной «активный». При про­верке в цикле while будет получен результат «ложь», и «процессодин» войдет в свой критический участок. Поскольку для перемен­ной «активный» установлено значение «истина», «процессдва» в свой критический участок войти не может.

Предположим теперь, что «процессдва» уже находится в своем критическом участке, когда «процессодин» хочет войти в критиче­ский участок. «Процессодин» устанавливает значение «истина» для переменной «первомувходитьнельзя», а затем многократно прове­ряет значение переменной «активный» по команде testandset. По­скольку «процессдва» находится в своем критическом участке, это значение остается истинным. Каждая команда проверки и установки обнаруживает, что «активный» имеет значение «истина», и устанавливает это значение для переменных «первомувходитьнельзя» и «активный». Таким образом, «процессодин» продолжает нахо­диться в цикле активного ожидания, пока «процессдва» в конце кон­цов не выйдет из своего критического участка и не установит зна­чение «ложь» для переменной «активный». В этот момент команда проверки и установки, обнаружив это значение переменной «ак­тивный» (и установив для нее истинное значение, чтобы «процессдва» не мог больше войти в свой критический участок), установит значе­ние «ложь» для переменной «первомувходитьнельзя», что позволит, чтобы «процессодин» вошел в свой критический участок.

Этот способ реализации взаимоисключения не исключает бес­конечного откладывания, однако здесь вероятность такой ситуации весьма мала, особенно если в системе имеется несколько процессо­ров. Когда процесс, выходя из своего критического участка, уста­навливает значение «ложь» переменной «активный», команда про­верки и установки testandset другого процесса, вероятнее всего, сможет «перехватить» переменную «активный» (установив для нее значение «истина») до того, как первый процесс успеет пройти цикл, чтобы снова установить значение «истина» для этой переменной.