Вторая модификация механизма «критическая область»

(модификация второго рода)

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

Для описания этой переменной используется конструкция

VAR E: EVENT R.

Это значит, что Е – событийная по отношению к критическому ресурсу R.

Переменная Е является структурированной и представляет собой одномерный массив. В этот массив как в очередь попадают процессы, при работе которых был выполнен примитив AWAIT.

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

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

Пример.

Распределяется ресурс R, который состоит из M однотипных единиц. Любому процессу должна быть предоставлена возможность при каждом разовом обращении к системе получить из состава R одну единицу. Если в момент обращения нет ни одной свободной единицы, то процесс должен перейти в состояние ожидания до тех пор, пока не появится хотя бы одна свободная единица. После использования единицы ресурса процесс обязан её возвратить в состав ресурса R. О таком возвращении должны быть оповещены все процессы, ожидающие единицу ресурса.

BEGIN

TYPE RES = 1..M, P = 1..N;

VAR INF: SHARED RECORD

свобод_ресурс: sequence of res;

требование: queue of p;

оч_событий: array p of event r;

end;

procedure reserve(процесс: p; var ресурс: res)

begin

region inf do begin

while empty(свобод_ресурс) do

begin

enter(процесс, требование);

await(оч_событий(процесс));

end;

GET (ресурс, свобод_ресурс);

end;

procedure release(ресурс: res)

begin

var процесс: р;

region inf do

begin

put(ресурс, свобод_ресурс);

if (not empty(требование)) then

begin

remove(процесс, требование);

couse(оч_событий(процесс));

end;

end;

end;

parbegin

процесс M1: begin

VAR R1:RES;

m1: <некоторые действия>

Reserve(1, var r1);

<использовать единицу ресурса из r с номером,

равным значению r1>

release(r1);

goto m1;

end;

...

процесс MN: begin

VAR RN:RES;

m1: <некоторые действия>

Reserve(N, var rN);

<использовать единицу ресурса из r с номером,

равным значению rN>

release(r1);

goto mN;

end;

parend;

end.

В рассматриваемом примере под критическим ресурсом понимается не ресурс R, который даже не описан, а некоторая совокупность информации, описывающая состояние ресурса и системы процессов, выдавших заявки на получение ресурсов. Для этого объявлена переменная INF, которую можно отнести к типу запись, состоящую из трёх поименованных элементов разного типа. Элемент с именем СВОБОД_РЕСУРС – это переменная типа SEQUENCE (последовательность), состоящая из непоименованных элементов типа RES. Эта переменная предназначена для хранения информации о нераспределённых в текущий момент единицах ресурсов. Все единицы ресурса пронумерованы от 1 до M. Такие элементы можно обрабатывать с помощью примитивов GET и PUT.

GET присваивает значение переменной (1-ый аргумент) одному из элементов переменной типа SEQUENCE по правилу FIFO;

PUT – обратная по смыслу операции GET. При выполнении PUT по правилу FIFO выбирается элемент из переменной типа SEQUENCE и присваивается переменной, указанной первым аргументом.

Второе поле записи – ТРЕБОВАНИЕ. Это переменная типа QUEUE (очередь). Она содержит непоименованные элементы, каждый из которых может принимать значения от 1 до N, где N – максимальное число процессов, которые могут претендовать на использование ресурсов.

Элемент ТРЕБОВАНИЕ используется для хранения заявок, поступающих от процессов на приобретение единиц ресурсов. Заявка – это номер процесса. Все процессы пронумерованы от 1 до N, причём каждый процесс знает о своём номере. Занесение номера процесса в очередь и извлечение номера процесса из очереди осуществляется с помощью примитивов ENTER и REMOVE. Занесение и извлечение необязательно производятся по правилу FIFO, а в соответствие с некоторой дисциплиной обслуживания.

В отношении переменной ТРЕБОВАНИЕ используется процедура EMPTY, значение которой всегда будет истинным при отсутствии элементов в очереди ТРЕБОВАНИЕ.

Элемент ОЧ_СОБЫТИЙ – это массив событийных переменных, каждая из которых указывает явно на один и тот же ресурс. Процессу с номером i соответствует i-ый элемент этого массива.

Для упрощения решения задачи используются процедуры RESERVE (для выделения единицы ресурса) и RELEASE (для возврата использованного ресурса в переменную СВОБОД_РЕСУРС).

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

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

В каждой процедуре имеется критическая область в отношении ресурса INF, и только в её пределах происходит обращение к ресурсам.

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

Если процесс, который вошёл в критическую область, при выполнении процедуры резервирования обнаружил, что ни одной свободной единицы ресурса нет, то он временно покидает критическую область с помощью примитива AWAIT и переходит в состояние ожидания на собственной событийной переменной в массиве ОЧ_СОБЫТИЙ.

Если процесс, находясь в критической области, обнаружил хотя бы одну свободную единицу ресурса, он узнаёт её номер и производит её захват. При этом корректируется значение переменной СВОБОД_РЕСУРС. Полученной единицей ресурса процесс владеет монопольно, после чего осуществляется выход из критической области, и, следовательно, в неё может войти какой-либо из других процессов.

При выполнении процессом процедуры освобождения указанная им единица ресурса становится свободной, и соответствующая информация заносится в переменную СВОБОД_РЕСУРС. В ходе выполнения этой процедуры также проверяется необходимость реактивации процессов, которые временно вышли из критической области. Эта проверка проводится путём анализа переменной ТРЕБОВАНИЕ, и если в этой переменной имеются запросы, то осуществляется перевод одного из процессов из переменной ОЧ_СОБЫТИЙ в главную очередь.

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

Таким образом, создаётся централизованная схема распределения критических ресурсов. Такая схема называется монитороподобной.