Деревянко А.С., Солощук М.Н. Операционные системы.Часть I. Построение и функционирование операционных систем
Подождите немного. Документ загружается.
271
разблокируется какой-либо процесс, то значение семафора так и остается
нулевым, если же очередь ожидающих пуста, то значение семафора
увеличивается на 1.
Укажем еще вот на какую особенность. После того, как процесс
разблокирован, он включается в список готовых. Может случиться так, что
этот процесс будет выбран планировщиком и активизирован даже раньше,
чем процесс, освободивший ресурс, закончит свою V-операцию.
Поскольку разблокированный процесс восстанавливается в контексте
своей P-операции, то получится, что два процесса одновременно
выполняют семафорные операции. В данном случае ничего страшного в
этом нет, потому что для разблокированного процесса уже снято взаимное
исключение (это было сделано при его блокировании), и этот процесс
после разблокирования уже не изменяет значения семафора. Запомним,
однако, эту особенность, которая в других примитивах взаимного
исключения может приобретать более серьезный характер.
Итак, общие свойства решения задачи взаимного исключения с
помощью семафоров таковы:
• дисциплина либеральна по тем же соображениям, что и
предыдущая;
• метод справедлив для любого числа процессов и процессоров;
• когда процесс блокируется, он не расходует процессорное время
на занятое ожидание;
• возможность бесконечного откладывания зависит от принятой
дисциплины обслуживания очереди ожидающих процессов, при
дисциплине FCFS бесконечное откладывание исключается;
• сами семафоры (но не защищаемые ими ресурсы) представляют
собой монопольно используемые ресурсы, следовательно, могут
порождать тупики; для борьбы с тупиками возможно применение
272
любого из известных нам методов, предпочтителен –
иерархический;
• как и все методы, рассмотренные выше, семафоры требуют от
программиста корректного применения "скобок", в роли которых
выступают P- и V-операции.
Для решения задачи взаимного исключения достаточно двоичных
семафоров. Мы, однако, описали тип поля value как целое число. В
приведенном нами выше определении Дейкстры речь тоже идет о
целочисленном, а не о двоичном значении. Семафор, который может
принимать неотрицательные значения, большие, чем 1, называется общим
семафором. Такой семафор может быть очень удобен, например, при
управлении не единичным ресурсом, а классом ресурсов. Начальное
значение поля value для такого семафора устанавливается равным числу
единиц ресурса в классе. Каждое выделение единицы ресурса процессу
сопровождается P-операцией, уменьшающей значение семафора. Семафор,
таким образом, играет роль счетчика свободных единиц ресурса. Когда
этот счетчик достигнет нулевого значения, процесс, выдавший следующий
запрос на ресурс, будет заблокирован в своей P-операции. Освобождение
ресурса сопровождается V-операцией, которая разблокирует процесс,
ожидающий ресурс или наращивает счетчик ресурсов.
Общие семафоры могут быть использованы и для простого решения
задачи синхронизации. В этом случае семафор связывается с каким-либо
событием и имеет начальное значение 0. (Событие может рассматриваться
как ресурс, и до наступления события этот ресурс недоступен). Процесс,
ожидающий события, выполняет P-операцию и блокируется до установки
семафора в 1. Процесс, сигнализирующий о событии, выполняет над
семафором V-операцию. Для графа синхронизации, например, показанного
на рисунке 8.1, мы свяжем с каждым действием графа одноименный
273
семафор. Тогда каждое действие (например, E) должно быть оформлено
следующим образом:
procE () {
/*ожидание событий B и D*/
P(B); P(D);
. . .
/* сигнализация о событии E для двух
ожидающих его действий (F и H) */
V(E); V(E);
}
Ниже мы рассмотрим применение семафоров для более сложного
варианта задачи синхронизации.
8.6. "Производители–потребители"
Пусть мы имеем два циклических процесса, которые мы назовем
"производитель" и "потребитель". Производитель в каждой итерации
своего цикла вырабатывает (производит) порцию информации, которую он
помещает в общий для обоих процессов буфер. Предположим для начала,
что емкость буфера неограничена. Потребитель в каждой итерации своего
цикла выбирает из буфера порцию информации, выработанную
производителем, и обрабатывает (потребляет) ее. Потребитель не должен
начинать обработку порции, пока ее производство не будет закончено.
Задача состоит в синхронизации действий производителя и потребителя
таким образом, чтобы не допустить потерь и искажений информации, во-
первых, и голодания процессов, во-вторых.
274
Решение достигается при помощи единственного общего семафора,
играющего роль счетчика числа порций в буфере (здесь и далее мы
предполагаем структуру семафора, определенную в предыдущем разделе):
1
2
3
4
5
6
7
8
9
10
11
12
12
14
15
16
17
18
19
static semaphore *portCnt =
{ 0, 0, NULL };
static ... buffer ...;
/* процесс-производитель */
void producer ( void ) {
while (1) {
< производство порции >
< добавление порции в буфер >
V(portCnt);
}
}
/* процесс-потребитель */
void consumer ( void ) {
while (1) {
P(portCnt)
< выборка порции из буфера >
< обработка порции >
}
}
Исходное значение семафора portCnt – 0. Производитель каждую
итерацию своего цикла заканчивает V-операцией, увеличивающей
значение счетчика. Потребитель каждую свою итерацию начинает P-
операцией. Если буфер пуст, то потребитель задержится в своей P-
операции до появления в буфере очередной порции. Таким образом, если
275
потребитель работает быстрее производителя, он будет время от времени
простаивать, если производитель работает быстрее – в буфере будут
накапливаться порции.
В реальных задачах такого рода (например, кольцевой буферизации,
рассмотренной нами в главе 6) буфер всегда имеет некоторую конечную
емкость. Если производитель работает быстрее, то при заполнении буфера
он должен приостанавливаться, ожидая освобождения места в буфере. Это
легко обеспечить, введя новый семафор freeCnt, выполняющий роль
счетчика свободных мест в буфере:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
static semaphore *portCnt =
{ 0, 0, NULL },
*freeCnt = { BSIZE, 0, NULL },
static ... buffer [BSIZE];
/* процесс-производитель */
void producer ( void ) {
while (1) {
< производство порции >
P(freeCnt);
< добавление порции в буфер >
V(portCnt);
}
}
/* процесс-потребитель */
void consumer ( void ) {
while (1) {
P(portCnt)
< выборка порции из буфера >
V(freeCnt);
276
20
21
22
< обработка порции >
}
}
Попытаемся теперь обобщить решение для произвольного числа
производителей и потребителей. Но в таком обобщении мы сталкиваемся с
еще одной существенной особенностью. В приведенных выше решениях
мы допускали одновременное выполнение операций <добавление порции в
буфер> и <выборка порции из буфера>. Очевидно, что при любой
организации буфера производитель и потребитель могут одновременно
работать только с разными порциями информации. Иначе обстоит дело с
многочисленными производителями и потребителями. Два производителя
могут попытаться одновременно добавить порцию в буфер и выбрать для
этого одно и то же место в буфере. Аналогично два потребителя могут
попытаться выбрать из буфера одну и ту же порцию. В следующем
примере мы для наглядности представляем буфер в виде кольцевой
очереди с элементами (порциями) одинакового размера:
1
2
3
4
5
6
7
8
9
10
11
typedef ... portion; /* порция информации */
static portion buffer [BSIZE];
static int wIndex = 0, rIndex = 0;
static semaphore *portCnt = { 0, 0, NULL },
*freeCnt = { BSIZE, 0, NULL },
*rAccess = { 1, 0, NULL },
*wAccess = { 1, 0, NULL };
/* имеется NP
аналогичных процессов-производителей */
void producer ( void ) {
portion work;
277
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
while (1) {
< производство порции в work >
P(wAccess);
P(freeCnt);
/* добавление порции в буфер */
memcpy(buffer+wIndex,&work,
sizeof(portion) );
if ( ++wIndex == BSIZE ) w_index = 0;
V(portCnt);
V(wAccess);
}
}
/* имеется NC
аналогичных процессов-потребителей */
void consumer ( void ) {
portion work;
while (1) {
P(rAccess);
P(portCnt)
/* выборка порции из буфера */
memcpy(&work, buffer+rIndex,
sizeof(portion) );
if ( ++rIndex == BSIZE ) rIndex = 0;
V(freeCnt);
V(rAaccess);
< обработка порции в work>
}
}
278
Мы оформляем обращения к буферу как критические секции,
защищая их семафорами rAccess и wAccess. Поскольку конфликтовать
(пытаться работать с одной и той же порцией в буфере) могут только
однотипные процессы, мы рассматриваем буфер как два ресурса: ресурс
для чтения и ресурс для записи, и каждый такой ресурс защищается своим
семафором. Таким образом, запрещается одновременный доступ к буферу
двух производителей или двух потребителей, но разрешается
одновременный доступ одного производителя и одного потребителя.
8.7. Конструкции критических секций в языках
программирования
Семафоры являются удобными и эффективными примитивами, при
помощи которых решаются задачи взаимного исключения и
синхронизации, поэтому они широко используются во многих ОС. API
ОС, обеспечивающий для пользователя работу с семафорами, мы
рассмотрим в следующей главе, а здесь остановимся на некоторых
возможных расширенных механизмах в системном программном
обеспечении (прежде всего – в системах программирования), которые
будут использовать семафоры в скрытой от пользователя форме.
Некоторые неудобства использования критических секций могут
быть преодолены введением специальных конструкций в язык
программирования. Например, если у нас в программе есть разделяемая
переменная x, то удобно защитить ее конструкцией типа:
shared int x;
. . .
section ( x ) {
279
< операторы, работающие с переменной x >
}
Конструкция section определяет критическую секцию. Вместо
специальных "скобок критической секции" используется заголовок
section и обычные операторные скобки. Последнее дает возможность
проверять правильность оформления критической секции на
синтаксическом уровне – на этапе трансляции программы, а не ее
выполнения, – и предупреждает возможность появления самой
распространенной ошибки программистов – непарных скобок.
Определение переменной x со специальным описателем shared
позволяет выявить (опять на этапе компиляции) все попытки доступа к ней
вне критической секции.
Реализация этой конструкции очевидна: переменная x защищается
скрытым семафором, над которым производится P-операция при входе в
секцию и V-операция – при выходе из нее.
Отчасти такая конструкция позволяет решить и проблему тупиков.
Если описать в программе иерархию разделяемых переменных, то можно
спокойно разрешить программисту делать вложенные критические секции
и проверять правильность вложения на этапе компиляции. Этот метод,
однако, не универсален: если в критической секции есть обращение к
процедуре, а в последней – другая критическая секция, то правильность
такого вложения компилятор проверить не сможет. Другой путь –
запретить вложенные секции, но разрешить в заголовке секции указывать
не одну разделяемую переменную, а целый их список. Этот вариант более
прост и надежен, но он использует дисциплину залпового выделения
ресурсов и, следовательно, более консервативен.
Критические секции как языковые конструкции обеспечивают
взаимное исключение, но не синхронизацию процессов. Инструментом для
280
синхронизации может быть оператор типа await, операндом которого
является логическое выражение. Этим оператором процесс блокируется до
тех пор, пока операнд не примет значение "истина". Поскольку ожидание
связано с внешним событием, в логическом выражении должна
участвовать хотя бы одна разделяемая переменная, следовательно,
применение await может быть разрешено только в критической секции.
В качестве примера приведем решение задачи "производители–
потребители" для процессов, использующих буфер, организованный в виде
стека. Такая организация буфера диктует нам необходимость запретить
одновременный доступ к нему любых двух процессов.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
shared struct {
portion buffer [BSIZE];
int stPtr;
} stack = { {...}, 0 };
void producer ( void ) {
portion work;
while (1) {
< производство порции в work >
section ( stack ) {
await ( stack.stRtr < BSIZE );
memcpy ( stack.buffer +
stack.stPtr++,
&work, sizeof(portion) );
}
}
}
void consumer ( void ) {
portion work;