program Version1;
var ProcessNum:integer;
procedure Process1;
begin
while true do
begin
while ProcessNum=2 do;
CriticalPoint1;
ProcessNum:=2;
OtherIOOperators;
end;
end;
procedure Process2;
begin
while true do
begin
while ProcessNum=1 do;
CriticalPoint2;
ProcessNum:=1;
OtherIOOperators;
end;
end;
begin
ProcessNum:=1;
parbegin
Process1; Process2;
parend
end;
В этой версии программной реализации взаимоисключения имеется только одна глобальная переменная и, таким образом, возникает проблема жесткой синхронизации. Поэтому существует вторая версия, в которой используются две переменные “п1внутри” и “п2внутри”, которые имеют истинное значение, если “процесс1” и ”процесс2” соответственно находятся в своих критических участках. Есть еще более сложные реализации, которые позволяют исключить некоторые нюансы. Вот как выглядит конечный вариант алгоритма Деккера.
program DekkerAlgorithm;
var currentprocess:(first,second);
p1wanttoenter,p2wanttoenter:boolean;
procedure process1;
begin
while true do
begin
p1wanttoenter := true;
while p2wanttoenter do
if currentprocess = second then
begin
p1wanttoenter:=false;
while currentprocess = second do;
p1wanttoenter := true;
end;
criticalpoint1;
currentprocess := second;
p1wanttoenter := false;
otheroperators1;
end;
end;
procedure process2;
begin
while true do
begin
p2wanttoenter := true;
while p1wanttoenter do
if currentprocess = first then
begin
p2wanttoenter:=false;
while currentprocess = first do;
p2wanttoenter := true;
end;
criticalpoint2;
currentprocess := first;
p2wanttoenter := false;
otheroperators2;
end;
end;
begin
p1wanttoenter := false;
p2wanttoenter := false;
currentprocess := first;
parbegin
process1; process2;
parend;
end.
Алгоритм Деккера исключает возможность бесконечного откладывания процессов.
Программное решение проблемы реализации примитивов взаимоисключения для n процессов первым предложил Дейкстра. Затем Кнут усовершенствовал алгоритм Дейкстры, исключив возможность бесконечного откладывания процессов, однако в варианте Кнута некоторый процесс по-прежнему мог испытывать (потенциально) длительную задержку. В связи с этим многие ученые начали искать алгоритмы, обеспечивающие более короткие задержки. Так, Эйзенберг и Макгайр предложили решение, гарантирующее, что процесс будет входить в свой критический участок не более чем за n-1 попыток. Лэмпорт разработал алгоритм, применимый, в частности, для распределенных систем обработки данных. Алгоритм Лэмпорта предусматривает “предварительное получение номерка”, подобно тому, как это делается в модных кондитерских, и поэтому получил наименование алгоритма кондитера (Bakery Algorithm). Бринк Хансен также предложил возможные варианты управления парралельными распределенными процессами.
Кроме программных, существуют и аппаратные реализации взаимоисключения, которые получили большое применение в современных мультипроцессорных системах, поскольку аппаратное управление взаимоисключением выполняется значительно быстрее.
Семафоры
Все рассмотренные нами ключевые понятия, относящиеся к взаимоисключению, Дейкстра суммировал в своей концепции семафоров. Семафор - это защищенная переменная, значение которой можно опрашивать и менять только при помощи специальных операций P и V и операции инициализации, которую будем называть “инициализация семафора”. Двоичные семафоры могут принимать только значения 0 и 1. считающие семафоры (семафоры со счетчиками) могут принимать неотрицательные целые значения. Операция P над семафором записывается как P(S) и выполняется следующим образом:
если S > 0
то S := S - 1
иначе (ожидать на S)
Операция V над семафором S записывается как V(S) и выполняется следующим образом:
если (один или более процессов ожидают на S)
то (разрешить одному из этих процессов продолжить работу)
иначе S := S + 1
Будем предполагать, что очередь процессов, ожидающих на S, обслуживается в соответствии с дисциплиной FIFO.
Операции P и V являются неделимыми. Участки взаимоисключения по семафору S в процессах обрамляются операциями P(S) и V(S). Если одновременно несколько процессов пытаются выполнить операцию P(S), это будет разрешено только одному из них, а остальным придется ждать. Семафоры и операции над ними могут быть реализованы как программно так и аппаратно. Как правило они реализуются в ядре операционной системы, где осуществляется управление сменой состояния процессов.
(Вывод)
Таким образом, при помощи алгоритма Деккера и/или аппаратной команды проверки, если она предусмотрена в машине, можно достаточно просто реализовать операции P и V с циклом активного ожидания. Однако активное ожидание может приводить к потере эффективности. Чтобы избежать режима активного ожидания операции над семафорами можно также реализовать в ядре операционной системы. Семафор реализуется как защищенная переменная и очередь, в которой процессы могут ожидать выполнения V-операций. Когда некоторый процесс пытается выполнить P-операцию для семафора, имеющего нулевое текущее значение, этот процесс освобождает процессор и блокирует себя в ожидании V-операции для данного семафора. При этом ядро операционной системы включает PCB процесса в очередь процессов, ожидающих разрешающего значения данного семафора. Затем ядро предоставляет центральный процессор следующему процессу, готовому к выполнению. Процесс, находящийся в очереди данного семафора, со временем становится первым в этой очереди. Затем при выполнении следующей V-операции этот процесс переходит из очереди семафора в список готовых к выполнению. Для процессов, пытающихся одновременно выполнить операции
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.
