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

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

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

Основные условия, которым удовлетворяют оба алгоритма:

• задача взаимоисключения решается чисто программным спо­собом;

• не делается никаких предположений об относительных скоро­стях выполнения процессов;

- процессы, находящиеся вне своих критических участков, не мо­ гут мешать другим процессам входить в их собственные критические участки;

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

Алгоритм Деккера был предложен в середине 1960 годов.

Листинг алгоритма Деккера

boolean flagO, flagl; int turn;

void P0() {

while(true){ flagO=true; while(flagl){ if(turn==l){ flagO=false; while(turn==l)

/* Ничего не делать */; flagO=true; } }

/* Критический участок */;

turn=l; flagO=false;

/* Остальной код */;

} }

void PI() -С

while(true){ flagl=true;

while (flagO)-C if(turn==0){ flagl=false; while(turn==0)

/* Ничего не делать */; f lagl=true; } }

/* Критический участок */;

turn=0; flagl=false;

/* Остальной код */;

} }

void main() {

flagO=false; flagl=false; turn=l;

parbegin(PO,Pl);

}

Алгоритм Деккера решает задачу взаимных исключений, но до­статочно сложным путём, корректность которого не так легко дока­зать. Петерсон предложил в 1981 г. простое и элегантное решение той же проблемы.

Листинг аглоритма Петерсона

boolean flag[2]; int turn;

void P0() {

while(true){ flag[0]=true;

turn=l;

while(flag[1] && turn==l) /* Ничего не делать */;

/* Критический участок */;

flag[0]=false;

/* Остальной код */;

} }

void PI()

■С

while(true){ flag[l]=true; turn=0;

while(flag[0] && turn==0) /* Ничего не делать */;

/* Критический участок */;

flag[l]=false;

/* Остальной код */;

} }

void main() {

flag[0]=false;

flag[l]=false;

parbegin(PO,Pl);

}

18. Семафоры и мьютексы

Семафор — специальная защищенная переменная в ОС. Под за­щищённостью понимается невозможность для прикладной програм­мы работать с этой переменной непосредственно. Для доступа к семафору программа должна использовать специальные системные вызовы ядра (примитивы):

• установить начальное значение семафора S;

• P(S) — если S>0, то S:=S — 1, иначе ожидать на S;

• V(S) — если один или более процессов ожидают на S, то поз­волить одному из них продолжить работу, иначе S:=S+1.

Обратите внимание, что вызов примитива P(S) может заблоки­ровать процесс до выполнения примитива V(S) другим процессом.

Все вызовы ядра для управления семафорами атомарны, то есть не могут быть прерваны другими процессами.

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

Семафоры, которые могут принимать только два значения: 0 и 1, — называются мьютексами. Такие семафоры чаще всего приме­няются для организации процедуры взаимоисключения.

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