17. Опишите и сравните различные программные методы решение проблемы взаимного исключения (использование логических переменных, счетчиков, задержек при выполнении процессов).

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

Процедура инициализации	Первый процесс	Второй процесс
procedure INIT; common integer N ; begin N := 1 ; start(P1) ; start(P2) end INIT .	process P1; common integer N ; begin while true do begin BEFORE1 ; while N = 2 do ; CS1 ; N := 2 ; AFTER1 ; end end P1 .	process P2; common integer N ; begin while true do begin BEFORE2 ; while N = 1 do ; CS2 ; N := 1 ; AFTER2 ; end end P2 .

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

Переменная N является разделяемой, но выполняемые над ней операции являются неделимыми.

Но в данном случае нарушается одно из требований, предъявляемых к организации критической секции: процесс, имеющий право на вход в свою критическую секцию, но пока не вошедший в нее (он может “задержаться” при выполнении действий, предшествующих входу в критическую секцию), блокирует вход в критические секции другим процессам, которые могут быть готовы к обработке общих данных, но не могут получить к ним доступ, так как установлена не их очередь.

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

Процедура инициализации	Первый процесс	Второй процесс
procedure INIT; common boolean C1,C2 ; begin C1 := false ; C2 := false ; start(P1) ; start(P2) end INIT .	process P1; common boolean C1,C2 ; begin while true do begin BEFORE1 ; while C2 do ; C1 := true ; CS1 ; C1 := false ; AFTER1 ; end end P1 .	process P2; common boolean C1,C2 ; begin while true do begin BEFORE2 ; while C1 do ; C2 := true ; CS2 ; C2 := false ; AFTER2 ; end end P2 .

Изменить значение своего флажка может только процесс, которому он соответствует. Определение значения флажка также не требует сложных вычислений и сводится к операции записи, которая по условию неделима. Однако в том случае, когда (хоть это и маловероятно) оба процесса одновременно подойдут к проверке значений флажков своих конкурентов перед входом в критическую секцию, они смогут пройти в нее одновременно. Таким образом, нарушается самое главное требование к реализации критической секции – требование взаимного исключения.

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

Процедура инициализации	Первый процесс	Второй процесс
procedure INIT; common boolean C1,C2 ; begin C1 := false ; C2 := false ; start(P1) ; start(P2) end INIT .	process P1; common boolean C1,C2 ; begin while true do begin BEFORE1 ; C1 := true ; while C2 do ; CS1 ; C1 := false ; AFTER1 ; end end P1 .	process P2; common boolean C1,C2 ; begin while true do begin BEFORE2 ; C2 := true ; while C1 do ; CS2 ; C2 := false ; AFTER2 ; end end P2 .

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

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

Процедура инициализации	Первый процесс	Второй процесс
procedure INIT; common boolean C1,C2 ; begin C1 := false ; C2 := false ; start(P1) ; start(P2) end INIT .	process P1; common boolean C1,C2 ; begin while true do begin BEFORE1 ; C1 := true ; while C2 do begin C1 := false ; delay(T1) ; C1 := true ; end ; CS1 ; C1 := false ; AFTER1 ; end end P1 .	process P2; common boolean C1,C2 ; begin while true do begin BEFORE2 ; C2 := true ; while C1 do begin C2 := false ; delay(T2) ; C2 := true ; end ; CS2 ; C2 := false ; AFTER2 ; end end P2 .

В последнем предложенном программном варианте организации критической секции процесс, получив сигнал о том, что есть конкурент на вход в критическую секцию, не ждет от него отказа, а уступает возможность получения доступа к разделяемым данным “добровольно”, сбросив свой флажок на некоторое время (delay(T) – это задержка на указанное время). Эти задержки выполнения процессов могут устанавливаться произвольно и даже случайным образом, что гарантирует невозможность взаимного блокирования.

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

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

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

Процедура инициализации	Первый процесс	Второй процесс
procedure INIT; common boolean C1,C2 ; common integer N ; begin C1 := false ; C2 := false ; N := 1 ; start(P1) ; start(P2) end INIT .	process P1; common boolean C1,C2 ; begin while true do begin BEFORE1 ; C1 := true ; while C2 do begin if N = 2 then begin C1 := false ; while N=2 do ; C1 := true ; end end ; CS1 ; C1 := false; N := 2; AFTER1 ; end end P1 .	process P2; common boolean C1,C2 ; begin while true do begin BEFORE2 ; C2 := true ; while C1 do begin if N = 1 then begin C2 := false ; while N=1 do ; C2 := true ; end end ; CS2 ; C2 := false; N:=1; AFTER2 ; end end P2 .

.

Для большего числа процессов при использовании этого алгоритма сложно установить очередь процесса, имеющего преимущественное право на вход в критическую секцию в конфликтной ситуации, – нужен специальный алгоритм для вычисления номера. Этот номер может устанавливаться, например, по максимальному числу попыток входа в критическую секцию, которые выполнил процесс.