13

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

команда testandset

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

Testandset (a, b)

• читает значение логической переменной b,

• копирует его в a,

• устанавливает для b значение "истина"

и все это в рамках одной непрерываемой операции.

Пример использования команды проверки и установки для реализации взаимоисключения:

program примерtestandset

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;

Рис. 4.8 Реализация взаимоисключения

при помощи команды testandsef (ПРОВЕРИТЬ И УСТАНОВИТЬ)

Переменная "активный" логического типа имеет значение "исти­на", когда любой из процессов находится в своем критическом участ­ке, и значение "ложь" в противном случае.

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

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

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