Обобщенная задача взаимного исключения



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".




Начало  Назад  Вперед