Деревянко А.С., Солощук М.Н. Операционные системы.Часть I. Построение и функционирование операционных систем
Подождите немного. Документ загружается.
301
55
56
57
< обработка порции в work>
}
}
Каждый производитель получает "билет" со своим номером в
очереди на запись в буфер (строка 22). Затем он ожидает, когда до него
дойдет очередь (строка 24), ожидает освобождения места в буфере (строка
27), записывает информацию (строки 29, 30) и наращивает счетчик
производств (строка 32). Увеличение счетчика событий inCnt является
сигналом к разблокированию как для потребителя, получившего "билет"
на выборку этой порции и ожидающего в строке 46, так и для
производителя, получившего "билет" на запись следующей порции и
ожидающего в строке 27. Полученный процессом "билет" определяет и
адрес в буфере той секции, с которой будет работать процесс. Хотя
каждый процесс работает со своей секцией в буфере, одновременный
доступ к буферу однотипных процессов исключается ожиданием в строке
24 или 46. Если разрешить одновременный доступ к буферу двух,
например, производителей, то процесс, получивший "билет" на запись
порции в n-ю секцию буфера может закончить запись раньше, чем
процесс, пишущий порцию в n-1-ю секцию, даже если последний начал
запись раньше. Процесс, закончивший запись, увеличит счетчик inCnt и
выйдет из ожидания потребитель, имеющий билет на n-1-ю секцию,
запись в которую еще не закончена.
8.11. Рандеву
Модель взаимодействия процессов, названная рандеву,
рассматривает синхронизацию и передачу данных как единую
302
деятельность. Когда процесс A намерен передать данные процессу B, оба
процесса должны объявить о своей готовности установить связь, выдав
запросы на передачу и прием данных соответственно. Если процесс A
выдает заявку на передачу прежде, чем процесс B выдал заявку на прием,
то процесс A приостанавливается до выдачи заявки процессом B. И
наоборот: если процесс B выдал заявку на прием раньше, чем процесс A на
передачу, то приостанавливается процесс B. Таким образом, процессы
взаимодействуют только при встрече (рандеву) их заявок на передачу и
прием.
В абстрактной записи взаимодействие между процессами
записывается так:
1
2
3
4
5
6
7
8
9
10
11
12
processA {
объявление локальной переменной x;
. . .
B!x;
. . .
}
processB {
объявление локальной переменной y;
. . .
A?y;
. . .
}
Нотация B!x в строке 4 означает, что процесс A передает процессу B
значение своей переменной x. A?y в строке 10 означает, что процесс B
принимает значение, переданное процессом A, и записывает его в свою
переменную y.
303
Эта запись отражает так называемую синхронную модель рандеву.
Запись асинхронной модели мы можем получить, заменив строку 10 на:
10 ?y;
В синхронной модели оба процесса должны указывать в операторах
приема или передачи имя процесса-корреспондента. В асинхронной
модели только процесс-передатчик указывает имя процесса-приемника.
"Безадресный" оператор приема соответствует идеям структуризации
данных и программирования "снизу вверх", развивавшимся автором
моделей рандеву и мониторов – К.Хоаром [10]. Асинхронная модель
делает возможным разработку библиотечных процессов, которые, во-
первых, могут использоваться в разных разработках, а во-вторых, играть
роль процессов-серверов, обрабатывающих запросы от разных,
параллельно выполняющихся процессов-клиентов.
Асинхронная модель рандеву лежит в основе взаимодействия
процессов в языке ADA [6]. Мы не имеем возможности привести здесь
полное описание языка (его синтаксис во многом подобен синтаксису
языка Pascal) и ограничимся только средствами, интересующими нас в
первую очередь. Во всех последующих примерах ключевые слова языка
ADA записаны строчными буквами.
Процесс в языке ADA называется задачей и описание задачи состоит
из спецификаций задачи и ее тела. Спецификация имеет структуру:
task ИМЯ_ЗАДАЧИ is
< описания входных точек >
end;
Тело имеет структуру:
304
task body ИМЯ_ЗАДАЧИ is
< переменные и операторы >
end ИМЯ_ЗАДАЧИ;
В спецификации указываются точки входа задачи для рандеву. Их
описания идентичны описаниям процедур: имя и параметры с указанием
направления передачи параметров: in, out или inout. В задаче,
обращающейся к входной точке, обращение выглядит точно так же, как
обращение к процедуре. Однако, выполняется такое обращение иначе. В
задаче-приемнике такое обращение обрабатывается оператором приема. В
простейшем случае такой оператор имеет вид:
accept ИМЯ_ВХОДА ( < параметры > ) do
< операторы >
end;
Оператор приема входит в структуру последовательно выполняемых
операторов тела задачи. Если при обращении к данному входу выполнение
задачи-приемника еще не дошло до оператора приема, то задача-
передатчик блокируется. Если выполнение дошло до оператора приема, но
обращения к данному входу не было, блокируется задача-приемник.
В ряде случаев неизвестно заранее, в какой последовательности
будут поступать запросы. Для недетерминированного выбора из
нескольких возможных запросов используется оператор отбора:
select
< оператор accept >
< другие операторы >
305
or
< оператор accept >
< другие операторы >
or
. . .
else
< другие операторы >
end;
Когда выполнение приемника доходит до оператора отбора,
приемник готов выполнить любой из операторов приема, перечисленных
среди альтернатив отбора. Если к этому моменту уже поступили
обращения к нескольким входам, включенным в отбор, принимается одно
из обращений (какое именно – правила языка не определяют). Если
обращений нет, то либо выполняется альтернатива else, либо (если эта
альтернатива не задана) процесс-приемник ожидает.
Операторы accept, составляющие альтернативы отбора, могут быть
"защищены" условиями. Заголовок оператора в этом случае выглядит так:
when <логическое выражение > =>
accept
...
Защищенный оператор приема включается в число альтернатив
отбора только в том случае, если логическое выражение имеет значение
"истина".
Наше краткое описание средств языка само по себе, видимо,
недостаточно для его понимания, поэтому проиллюстрируем его примером
– все той же задачей производителей–потребителей:
306
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
PROD_CONS: declare;
/* пустая спецификация производителя */
task PRODUCER is
end;
/* тело производителя */
task body PRODUCER is
/* рабочая область для порции */
WORK : PORTION;
begin
loop /* цикл производства */
< производство порции в WORK >
/* запись порции */
PUTPORTION(WORK);
/* конец цикла производства */
end loop;
/* конец тела производителя */
end PRODUCER;
/* пустая спецификация потребителя */
task CONSUMER is
end;
/* тело потребителя */
task body CONSUMER is
/* рабочая область для порции */
WORK : PORTION;
begin
loop /* цикл потребления */
/* выборка порции */
GETPORTION ( WORK );
307
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
< обработка порции в WORK >
/* конец цикла потребления */
end loop;
/* конец тела потребителя */
end CONSUMER;
/* спецификация задачи-сервера */
task SERVER is
/* описание входных точек сервера */
entry GETPORTION(PORT : out PORTION);
entry PUTPORTION(PORT : in PORTION);
end;
/* тело сервера */
task body SERVER is
/* буфер */
BUFFER : array [1..BSIZE] of PORTION;
/* индексы для чтения и записи */
INCNT, OUTCNT :
INTEGER range 1..BSIZE := 1;
/* счетчик порций в буфере */
PORTCNT :
INTEGER range 0..BSIZE := 0;
begin
loop /* цикл обслуживания */
/* выбор из наступивших событий */
select when PORTCNT < BSIZE =>
/* если буфер не полон,
обслуживается запись */
accept
PUTPORTION(PORT:in PORTION) do
308
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
/* запись */
BUFFER[INCNT] := PORT;
end;
/* модификация счетчиков */
INCNT := INCNT mod BSIZE + 1;
PORTCNT := PORTCNT + 1;
or
/* или если буфер не пуст,
обслуживается выборка */
accept
GETPORTION(PORT:out PORTION) do
/* выборка */
PORT := BUFFER[OUTCNT];
end;
/* модификация счетчиков */
OUTCNT := OUTCNT mod BSIZE + 1;
PORTCNT := PORTCNT - 1;
end select; /* конец выбора */
/* конец цикла обслуживания */
end loop;
/* конец тела сервера */
end SERVER;
/* главная процедура */
begin
/* запуск всех задач */
initiate SERVER, PRODUCER, CONSUMER;
end.
В нашу программу входят:
309
• главная процедура (строки 80 - 84);
• задача-производитель (строки 2 - 17);
• задача-потребитель (строки 18 - 33);
• задача-сервер (строки 34 - 79), обеспечивающая обмен
производителя и потребителя с буфером.
Главная процедура запускает три другие задачи оператором
initiate (строка 83) и переходит в ожидание. Она завершится, когда
завершатся все запущенные ею задачи. Задачи PRODUCER и CONSUMER не
имеют операторов приема, поэтому их спецификации (строки 2 - 4 и 18 -
20) вырожденные – пустые. Тела этих задач содержат простые
бесконечные циклы (loop), в которых выполняется подготовка или
обработка порции и обращение к соответствующей входной точке сервера.
Задача SERVER является аналогом монитора. В ее спецификации (строки
34 - 39) описаны две входные точки: GETPORTION и PUTPORTION. Сам
буфер является локальным в теле сервера (строка 43), также локальны и
индексы чтения и записи (строки 45, 46) и счетчик порций (строки 48 - 49).
Выполнение сервера представляет собой бесконечный цикл (строки 51 -
77), в каждой итерации которого обрабатывается одно обращение.
Оператор select (строки 52 - 75) обеспечивает выбор из обращений:
GETPORTION или PUTPORTION. В зависимости от значения счетчика
PORTCNT из числа альтернатив может исключаться GETPORTION – если
буфер пуст или PUTPORTION – если он полон. Если к началу очередной
итерации обращений нет или есть обращение, которое не позволяет
принять защита when, сервер ожидает. Обратите внимание на
операторные скобки do ... end, следующие за операторами accept
(строки 57 - 60 и 68 - 71). Они ограничивают критическую секцию.
Выполнение процесса-передатчика не возобновится до тех пор, пока
процесс-приемник не выйдет из критической секции. Мы включили в
310
критические секции приемов только операторы, непосредственно
работающие с параметрами вызовов, так как основное предназначение
этой секции – защита параметров от преждевременного их изменения.
Остальные операторы, выполняемые в ходе обработки вызовов
(модификация индексов и счетчика), выполняются уже вне критической
секции.
В нашем примере мы запустили по одному производителю и
потребителю. В языке, однако, имеется возможность запускать любое
число однотипных задач: как полностью идентичных, так и
различающихся по значениям параметров.
Модель рандеву как достаточно универсальный метод
взаимодействия позволяет легко реализовать и примитивы взаимного
исключения и синхронизации. Двоичный семафор, например, выглядит
так:
task SEMAPHORE is
entry P;
entry V;
end;
task body SEMAPHORE is
begin
loop
accept P;
accept V;
end loop;
end SEMAPHOR;
В этой задаче операторы приема не являются альтернативными, а
выполняются строго последовательно. Если какая-либо внешняя задача