Обобщенная задача взаимного исключения
2.2. Обобщенная задача взаимного исключения
Задача из ¬2.1 допускает естественное обобщение: даны N циклических процессов, каждый со своим критическим интервалом; можем ли мы так построить их, чтобы в любой момент самое большее один процесс находился в критическом интервале? Предположим, что в нашем распоряжении имеются те же самые средства связи, т. е. набор переменных общего доступа. Кроме того, наше решение должно удовлетворять тем же требованиям, а именно: остановка процесса вне его критического интервала не может никаким образом ограничивать продвижение других процессов, если более чем один процесс находится перед входом в свой критический интервал, то должно быть выполнено требование о невозможности подобрать для них такие конечные скорости, при которых решение о том, какому из них первому войти в свой критический интервал, откладывается до бесконечности.
Чтобы записать решение на языке АЛГОЛ-60, необходимо ввести понятие массива. В ¬2.1 мы вводили для каждого из процессов свои "с" с помощью описания
integer cl, с2
Вместо прямого перечисления величин, мы можем использовать (в предположении, что "N" имеет соответствующее положительное значение) следующее описание:
integer array с[1 : N]
которое означает, что мы вводим N целых переменных, к которым обращаются по именам
с[индекс],
где "индекс" может принимать значения 1, 2, . . ., N.
Следующей конструкцией языка АЛГОЛ-60, которую мы используем, является так называемый оператор цикла:
for j:=l step 1 until N do оператор S;
Он дает нам возможность очень удобно задать повторение "оператора S". В принципе эта конструкция означает, что "оператор S" будет выполнен N раз с "j", принимающим последовательно значения, равные 1, 2, . . ., N. (Мы добавили "в принципе", так как с помощью оператора goto, являющегося частью оператора S и передающего управление вне оператора S, повторное выполнение может быть прекращено раньше.)
Наконец, нам нужна логическая операция, которая в пределах этой главы будет обозначаться "and".
Мы уже встречали условное предложение в форме:
if условие then оператор
Теперь мы будем использовать такую форму:
if условие 1 and условие 2 then оператор
которая означает, что оператор S будет выполнен, если только "условие 1" и "условие 2" удовлетворяются оба. (Хотелось бы еще раз подчеркнуть, что эта глава не является руководством по программированию на АЛГОЛе и приведенные выше (нестрогие!) объяснения элементов АЛГОЛа даются только для того, чтобы сделать излагаемый материал возможно более самостоятельным.) С помощью только что бегло очерченных изобразительных средств мы можем записать наше решение для фиксированного значения N следующим образом:
begin integer array b, с[0 : N], integer очередь; for очередь := 0 step 1 until N do
begin b[очередь] := 1; с[очередь] :=1 end; очередь := 0; parbegin
процесс 1: begin ............... end; процесс 2: begin ............... end; . . . процесс N: begin ............... end; parend
end
В первой строчке вводится два массива с N + 1 элементом каждый; во второй вводится простая переменная "очередь". При выполнении следующего далее цикла переменная "очередь" принимает последовательно значения 0, 1, 2, 3, ..., N, так что элементы обоих массивов получают начальные значения, равные "1". Затем "очередь" устанавливается в "0" (т. е. ни один из процессов, пронумерованных от 1 до N, не поставлен в особые условия). После этого все N процессов начинают одновременно выполняться.
Все N процессов подобны. Структура i-го процесса такова (1
i N) :процесс i: begin integer 3; Ai: b[i] := 0; Li: if очередь
i thenbegin с[i] := 1; if b[очередь] = 1 then очередь := i; goto Li end; c[i] :=0; for j:= 1 step 1 until N do
begin if j=/=1 and с[j] = 0 then goto Li end; критический интервал i; очередь :=0; с[i]:=1; b[i]:=l; остаток цикла i; goto Ai end
