Монитороподобные средства синхронизации
Введение
Основной концепцией таких средств является организация контроля правильности установления взаимосвязи между процессами.
Считается, что данные средства синхронизации имеют большую наглядность, чем семафорная техника, что достигается за счет структурирования.
Концепция монитороподобных средств основана на языковом обособлении или локализации средств взаимодействия. Это не только выделение особых языковых конструкций, но и сосредоточение в их составе информации о разделяемых ресурсах, о переменных состояния, характеризующих эти ресурсы, а также допустимые действия над этими ресурсами.
3.1.12.2 Механизм типа «критическая область»
Как следует из названия, это механизм, ориентированный на решение задачи взаимного исключения.
Для построения критической области используется две языковые конструкции. Одна из них VAR V: SHARED T; предназначена для описания критического ресурса, и её используют в начале текста программы в области описания типов переменных. Вторая описывает доступ к ресурсу в тексте программы REGION V DO S.
VAR R: SHARED T1;
Q: SHARED T2;
Begin
Parbegin
процесс 1: . . . L1: REGION R DO S1; . . .
процесс 2: . . . L2: REGION Q DO S2; . . .
. . . . . . . . . . .
процесс i: . . . Li: REGION R DO S3; . . .
Parend;
End.
Процессы 1-ый и i-ый взаимно разделяют ресурс R и при выполнении программы будет выполнятся только одна из областей.
Описание переменной V: SHARED T означает, что определяется ресурс с именем V, как некоторая переменная, доступная параллельным процессам. Тип ресурса задаётся его описанием T.
Для осуществления доступа к ресурсу V в тексте программы процесса требуется использовать конструкцию вида REGION V DO S. Такая конструкция описывает отдельную критическую область относительно критического ресурса V и определяет действия S, которые будут осуществлены над ресурсом. Такие конструкции при исполнении исключают друг друга относительно критического ресурса.
Основные допущения при построении такого механизма синхронизации заключаются в том, что недопустима обработка переменной, описанной как «разделяемая» в каких-либо языковых конструкциях в программе, отличных от конструкций типа REGION. Попытка сделать это – заведомая ошибка в использовании критического ресурса – может быть выявлена на этапе компиляции программы.
TYPE T = ARRAY 1..100 OF INTEGER;
VAR M: SHARED T;
Begin
Parbegin
Процесс 1: L1: <действие процесса>
REGION M DO <обработка массива M>;
GOTO L1;
. . . . . . . . . . . . . . . . . .
Процесс N: Ln: <действие процесса>
REGION M DO <обработка массива M>;
GOTO Ln;
Parend;
End.
Механизм типа «условная критическая область»
Данный механизм является модификацией механизма «критическая область». Но здесь вводится возможность производить работу с критическим ресурсом только тогда, когда он пребывает в определенном состоянии или выполнено условие, допускающее возможность работы с критическим ресурсом.
Для проверки условия и состояния вводится специальный примитив AWAIT. Он может выполняться только в пределах языковой конструкции REGION. В качестве параметра этого примитива используется логическое выражение. Предполагается, что значения компонентов логического выражения могут изменяться другими параллельными процессами, но обязательно в области REGION. Если при выполнении AWAIT окажется, что логическое выражение истинно, то данный процесс временно покидает критическую область. Это даёт возможность одному из других параллельных процессов войти в критическую область и изменить параметры логического выражения. При повторном входе приостановленного процесса в критическую область логическое условие может стать ложным, и процесс получит возможность работать с критическим ресурсом.
Для организации временного выхода из критической области и повторного входа в неё по отношению к критическому ресурсу выстраиваются две очереди:
- в первую или главную очередь попадают те процессы, которые готовы войти в критическую область, и конкурируют за право получить доступ к ресурсу;
- в другую очередь, называемую событийной, попадают процессы, которые, находясь в критической области, обнаружили с помощью примитива AWAIT невозможность обработки критического ресурса.
Процессы, находящиеся в событийной очереди, переносятся в главную очередь после каждого нормального выхода какого-либо из процессов из его критической области по отношению к какому-либо ресурсу.
TYPE T = ARRAY 1..100 OF INTEGER;
VAR M: SHARED T;
СЧИТЫВАНИЕ : BOOLEAN;
BEGIN
СЧИТЫВАНИЕ :=TRUE;
PARBEGIN процесс 1 : begin
m1: <некоторые действия>
Region m do begin
Await(считывание);
<считать информацию из М>
считывание := true;
End;
Goto m1;
End;
процесс 2 : begin
m2: <некоторые действия>
Region m do begin
<запись информации в М>
считывание := false;
End;
Goto m2;
End;
Parend;
End.
Такие действия могут быть реализованы компилятором путём применения двоичного семафора, единственного в отношении каждого критического ресурса.
Процесс-читатель может выполнить действия только в том случае, если информация в массив записана.
Особенностью данного средства синхронизации является сокрытие от пользователей механизма повторного входа в критические области. Этот механизм является механизмом активного ожидания, поэтому его использование целесообразно, когда обращение к критическим ресурсам происходит редко.
Вторая модификация механизма «критическая область»
(модификация второго рода)
Сущность модификации второго рода состоит в том, что в составе функции 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. Такой подход позволяет разделить процесс проектирования алгоритма на два класса. В одном проектируются средства доступа к ресурсам или система распределения ресурса, а второй – это непосредственно разработка программы, реализующей определённую задачу.
Таким образом, создаётся централизованная схема распределения критических ресурсов. Такая схема называется монитороподобной.
Ресурсы