Алгоритм Деккера

Алгоритм Деккера основан на использовании трех переменных (листинг 6.4): перекл1, перекл2 и ОЧЕРЕДЬ. Пусть по-прежнему переменная перекл1=true тогда, ког­да процесс ПР1 хочет войти в свой критический интервал (для ПР2 аналогич­но), а значение переменной ОЧЕРЕДЬ указывает, чье сейчас право сделать попытку входа, при условии, что оба процесса хотят выполнить свои критические интер­валы.

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

label 1, 2;

var перекл1, перекл2: boolean;

ОЧЕРЕДЬ: integer;

begin пepeкл1:=false;

перекл2:=false;

ОЧЕРЕДЬ:=1;

parbegin

while true do

begin перекл1:=true;

1: if перекл2=true then

if ОЧЕРЕДЬ=1 then go to 1

else begin перекл1:=false;

while ОЧЕРЕДЬ=2 do

begin end

end

else begin

CS1; { Критический интервал ПР1 }

ОЧЕРЕДЬ:=2;

перекл1:=faIse;

end

end

and

while true do

begin перекл2:=true;

2: if перекл1=truе then

if ОЧЕРЕДЬ=2 then go to 2

else begin перекл2:=false;

while ОЧЕРЕДЬ=1 do

begin end

end

else begin

CS2; { Критический интервал ПР2 }

ОЧЕРЕДЬ:=1;

перекл2:=false

end

end

parend

end.

Если перекл2=true и перекл1=false, то выполняется критический интервал про­цесса ПР2 независимо от значения переменной ОЧЕРЕДЬ. Аналогично для случая перекл2=false и перекл1=tгue.

Если же оба процесса хотят выполнить свои критические интервалы, то есть перекл2=true и перекл1=true, то выполняется критический интервал того процесса, на который указывало значение переменной ОЧЕРЕДЬ, независимо от скоростей развития обоих процессов. Использование переменной ОЧЕРЕДЬ совместно с перекл1 и перекл2 в алгоритме Деккера позволяет гарантированно решать проблему кри­тических интервалов. Переменные перекл1 и перекл2 обеспечивают, что взаимное выполнение не может иметь места; переменная ОЧЕРЕДЬ гарантирует от взаимного блокирования. Взаимное блокирование невозможно, так как переменная не из­меняет своего значения во время выполнения программы принятия решения о том, кому же сейчас проходить свой критический интервал.

Тем не менее, реализация критических интервалов на основе описанного алго­ритма практически не используется из-за чрезмерной сложности, особенно в случаях, когда алгоритм Деккера обобщается с двух до N процессов.

Синхронизация процессов посредством операции «ПРОВЕРКА И УСТАНОВКА»

Операция «ПРОВЕРКА И УСТАНОВКА» является, как и блокировка памяти, одним из аппаратных средств решения задачи критического интервала. Данная операция реализована на многих компьютерах. Так, в знаменитой IBM 360 (370) эта команда называлась TS (test and set). Команда TS является двухадресной (двухоперандной). Ее действие заключается в том, что процессор присваивает значение второго операнда первому, после чего второму операнду присваивается значение, равное единице. Команда TS является неделимой операцией, то есть между ее началом и концом не могут выполняться никакие другие команды.

Чтобы использовать команду TS для решения проблемы критического интерва­ла, свяжем с ней переменную common, которая будет общей для всех процессов, использующих некоторый критический ресурс. Данная переменная будет при­нимать единичное значение, если какой-либо из взаимодействующих процессов находится в своем критическом интервале. С каждым процессом связана своя локальная переменная, которая принимает значение, равное единице, если дан­ный процесс хочет войти в свой критический интервал. Операция TS будет при­сваивать значение common локальной переменной и устанавливать common в единицу. Программа решения проблемы критического интервала на примере двух парал­лельных процессов приведена в листинге 6.5.

Листинг 6.5. Взаимное исключение с помощью операции «ПРОВЕРКА И УСТАНОВКА»

var common, local1. local2: integer;

begin

common:=0;

parbegin

ПР1: while true do

begin

local1:=1;

while local1=l do TS(local1, common);

CS1; { Критический интервал npoueca ПР1 }

common:=0:

PR1; { ПР1 после критического интервала }

end

and

ПР2: while true do

begin

local2:=l;

while local2=l do TS(local2, common);

CS2; { Критический интервал процеса ПР2 }

common:=0;

PR2; { ПР2 после критического интервала }

end

parend

end.

Предположим, что первым захочет войти в свой критический интервал процесс ПР1. В этом случае значение local1 сначала установится в единицу, а после цик­ла проверки с помощью команды TS(local1, common) — в ноль. При этом значение common станет равным единице. Процесс ПР1 войдет в свой критический интервал. После выполнения этого критического интервала common примет значение, равное нулю, что даст возможность второму процессу ПР2 войти в свой критический интервал.

Безусловно, мы предполагаем, что в компьютере предусмотрена блокировка па­мяти, то есть операция common:=0 неделима. Команда «ПРОВЕРКА И УСТАНОВ­КА» значительно упрощает решение проблемы критических интервалов. Глав­ное свойство этой команды — ее неделимость.

Основной недостаток использования операций типа «ПРОВЕРКА И УСТАНОВ­КА» состоит в следующем: находясь в цикле проверки переменной common, про­цессы впустую потребляют время центрального процессора и другие ресурсы. Действительно, если предположить, что произошло прерывание процесса ПР1 во время выполнения своего критического интервала в соответствии с некото­рой дисциплиной обслуживания и начал выполняться процесс ПР2, то он войдет в цикл проверки, впустую тратя процессорное время. В этом случае до тех пор, пока диспетчер супервизора не поставит на выполнение процесс ПР1 и не даст ему закончиться, процесс ПР2 не сможет войти в свой критический интервал.

В микропроцессорах i80386 и старше, с которыми мы теперь сталкиваемся по­стоянно, есть специальные команды: ВТС, BTS, ВТК, которые как раз и являют­ся вариантами реализации команды типа «ПРОВЕРКА И УСТАНОВКА».

Несмотря на то, что и алгоритм Деккера, основанный только на блокировке памяти, и операция «ПРОВЕРКА И УСТАНОВКА» пригодны для реализации взаимного исключения, оба эти приема очень неэффективны. Всякий раз, когда один из процессов выполняет свой критический интервал, любой другой про­цесс, который пытается войти в свою критическую секцию, попадает в цикл про­верки соответствующих переменных-флагов, регламентирующих доступ к кри­тическим переменным. При таком неопределенном пребывании в цикле, которое называется активным ожиданием, напрасно расходуется процессорное время, поскольку процесс имеет доступ к тем общим переменным, которые и определя­ют возможность или невозможность входа в критическую секцию. При этом процесс занимает ценное время центрального процессора, на самом деле ничего реально не выполняя. Как результат, мы имеем общее замедление вычислитель­ной системы процессами, которые реально не выполняют никакой полезной ра­боты.

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

Вместо того чтобы связывать с каждым процессом свою собственную перемен­ную, как это было в рассмотренных нами решениях, можно со всем множеством конкурирующих критических секций связать одну переменную, которую и рас­сматривать как некоторый ключ. Вначале доступ к критической секции открыт. Однако перед входом в свой критический интервал процесс забирает «ключ» и тем самым блокирует другие процессы. Покидая критическую секцию, процесс открывает доступ, возвращая «ключ» на место. Если процесс, который хочет войти в свою критическую секцию, обнаруживает, что ключ «отсутствует», то он должен быть переведен в состояние блокирования до тех пор, пока процесс, имеющий ключ, не вернет его. Таким образом, каждый процесс, входящий в кри­тический интервал, должен вначале проверить, доступен ли ключ, и если это так, то сделать его недоступным для других процессов. Причем самым главным явля­ется то, что эти два действия должны быть неделимыми, чтобы два или более процессов не могли одновременно получить доступ к ключу. Более того, провер­ку того, можно ли войти в критический интервал, лучше всего выполнять не са­мим конкурирующим процессам, так как это приводит к активному ожиданию, а возложить эту функцию на операционную систему. Таким образом, мы подо­шли к одному из самых главных механизмов решения проблемы взаимного ис­ключения — семафорам Дейкстры.