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

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

 

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

Аппаратная реализация взаимоисключения: команда 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 другого процесса, вероятнее всего, сможет «перехватить» переменную «активный» (установив для нее значение «истина») до того, как первый процесс успеет пройти цикл, чтобы снова установить значение «истина» для этой переменной.

Семафоры

 

Все описанные выше ключевые понятия, относящиеся к взаимо­исключению, Дейкстра суммировал в своей концепции семафоров (Di65). Семафор — это защищенная переменная, значение которой можно опрашивать и менять только при помощи специальных опе­раций Р и V и операции инициализации, которую мы будем назы­вать «инициализациясемафора». Двоичные семафоры могут прини­мать только значения 0 и 1. Считающие семафоры (семафоры со счетчиками) могут принимать неотрицательные целые значения.

Операция Р над семафором записывается как P(S) и выполняется следующим образом:

если S > О

то S: =S— 1

иначе (ожидать на S)

 

Операция V над семафором S записывается как V(S) и выпол­няется следующим образом;

если (один или более процессов ожидают на S)

то (разрешить одному из этих процессов продолжить работу)

иначе S: = S + 1

 

Будем предполагать, что очередь процессов, ожидающихна обслуживается в соответствии с дисциплиной «первый пришедший обслуживается первым» (FIFO).

Подобно операции проверки и установки testandset, операции Р и V являются неделимыми. Участки взаимоисключения по сема­фору S в процессах обрамляются операциями P(S) и V(S). Если одновременно несколько процессов попытаются выполнить операцию P(S), это будет разрешено только одному из них, а остальным придется ждать.

Семафоры и операции над ними могут быть реализованы как программно, так и аппаратно. Как правило, они реализуются в ядре операционной системы, где осуществляется управление сме­ной состояния процессов.

На рис. 2 приводится пример того, каким образом можно обеспечить взаимоисключение при помощи семафоров. Здесь при­митив Р (активный) — эквивалент для «входвзаимоисключения», а примитив V (активный) — для «выходвзаимоисключения».

program примерсемафораодин;

var активный: семафор;

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

Begin

while истина do begin

предшествующиеоператорыодин;

Р(активный);

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

V(активный);

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

end

end;

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

Begin

while истина do begin

предшествующиеоператорыдва Р(активный);

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

V(активный);

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

еnd

end;

Begin

инициализациясемафора(активный,1);

Parbegin

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

процессдва parend

end;

Рис. 2. Обеспечение взаимоисключения при помощи семафора и примитивов Р и V.