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

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

Обозначим используемую для установления порядка входа процессов в критические секции переменную N. Начальное значение этой переменной должно быть установлено при инициализации системы (до запуска процессов P₁ и P₂). Предположим, что первым в критическую секцию должен быть допущен процесс P₁.

В этом случае процедуру инициализации системы и рассматриваемые процессы можно записать представленным ниже способом.

Процедура инициализации	Первый процесс	Второй процесс
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 .

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

Переменная N также является разделяемой, но выполняемые над ней операции являются неделимыми (для того, чтоб установить новое значение процесс не должен считывать значение переменной и выполнять над ним какие-либо действия: порядок передачи права на вход в критическую секцию жестко определен, поэтому каждый процесс “знает” номер того процесса, очередь которого он устанавливает, и может сохранить фиксированное значение переменной, выполнив всего одну операцию записи).

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

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

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

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

В этом случае процедуру инициализации системы и рассматриваемые процессы можно записать следующим образом:

Процедура инициализации	Первый процесс	Второй процесс
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 .

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

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

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

Процедура инициализации	Первый процесс	Второй процесс
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 .

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

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

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