Синхронизация параллельных процессов на низком уровне

Блокировка памяти

Взаимоисключения могут быть реализованы аппаратно, если сделать операции над памятью неделимыми. То есть, если каждый из процессов пытается поместить какие-либо значения в одну и ту же ячейку, то спор разрешается аппаратурой: если одному процессу разрешается выполнить операцию засылки немедленно, то другому приходится ждать пока первый не закончит операцию - такое разрешение спора и называется блокировкой памяти( storage interlock).

Попытаемся решить проблему критического участка для двух процессов X и Y с помощью некоторой переменной ключ, которая будет принимать значение true, когда процесс находится в своем критическом участке, и значение false - в противном случае. Прежде, чем войти в критический участок, процесс X проверяет ключ_Y другого процесса, чтобы убедится, что можно войти безопасно. Затем он включает свой собственный ключ_X и пользуется критическим участком.

var ключ_X, ключ_Y: boolean;

procedure процесс_Х;

begin

while (true) do

begin

while (ключ_Y) do;{ожидание, пока процесс Y не выйдет из критического участки}

ключ_X:=true;

{Критический участок Х}

ключ_X:=false;{признак выхода процесса X из критического участка}

{Оставшаяся часть процесса Х}

end;

end;

procedure процесс_Y;

begin

while (true) do

begin

while (ключ_X) do;{ожидание пока процесс X не выйдет из критического участка}

ключ_Y:=true;

{Критический участок Y}

ключ_Y:=false;{признак выхода процесса Y из критического участка}

{Оставшаяся часть процесса Y}

end;

end;

begin

ключ_X:=false;

ключ_Y:=false;

Parbegin

процесс_Х;

процесс_Y

Parend

end.

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

Алгоритм Деккера (Dekker’s Algorithm)

программную реализацию механизма взаимоисключения предложил голландский математик Деккер.

var C1,C2,очередь:integer;

procedure процесс_Х;

begin

C1:=1;

while (C2=1) do

begin

if очередь=2 then

begin

C1:=0;

while (очередь=2) do;

C1:=1;

end;

end;

{Критический участок процесса Х}

C1:=0;

очередь:=2;

{Оставшаяся часть процесса Х}

end;

procedure процесс_Y;

begin

C2:=1;

while (C1=1) do

begin

if очередь=1 then

begin

C2:=0;

while (очередь=1) do;

C2:=1

end;

end;

{Критический участок процесса Y}

C2:=0;

очередь:=1;

{Оставшаяся часть процесса Y}

end;

Begin

C1:=0;

C2:=0;

очередь:=1;

Parbegin

процесс_X;

процесс_Y

Parend

end.

В этом решении С1=1, когда процесс_Х хочет войти в свой критический участок. С2=1, когда процесс_Y хочет войти в свой критический участок, а переменная очередь указывает, чья очередь попытаться войти, при условии, когда оба процесса хотят выполнить свои критические участки.

Аппаратная реализация взаимоисключения: команда “проверка и установка” (testandset)

Рассмотрим вариант аппаратного решения данной проблемы. Наличие аппаратной команды testandset, которая осуществляет чтение переменной; запись ее значения в область сохранения и установку конкретного значения этой переменной, причем выполняет эти действия до конца без прерывания, значительно упрощает решение проблемы критического участка посредством блокировки памяти.

Рассмотрим выполнение команды testandset с параметрами общий и локальный. Операция читает значение параметра общий и присваивает его переменной локальный, а затем устанавливает в переменной общий значение 1.

Переменная общий разделяется между процессами, которые подлежат синхронизации по отношению к некоторому критическому ресурсу. У каждого процесса есть своя собственная переменная локальный_Х и локальный_Y.

Рассмотрим решение проблемы взаимоисключения с помощью операции testandset.

var общий: integer;

procedure процесс_Х;

var локальный_Х: integer;

begin

while (true) do

begin

локальный_Х:=1;

while (локальный_Х =1) do

testandset(локальный_Х, общий);

{Критический участок процесса Х}

общий:=0;

{Оставшаяся часть процесса Х}

end;

end;

procedure процесс_Y;

var локальный_Y: integer;

begin

while (true) do

begin

локальный_Y:=1;

while (локальный_Y =1) do

testandset(локальный_Y, общий);

{Критический участок процесса Y}

общий:=0;

{Оставшаяся часть процесса Y}

end;

end;

begin

общий:=0;

Parbegin

процесс_Х;

процесс_Y

Parend;

end.