Деревянко А.С., Солощук М.Н. Операционные системы.Часть I. Построение и функционирование операционных систем
Подождите немного. Документ загружается.
291
неохраняемые процедуры. Для того, чтобы процесс получил возможность
доступа к неохраняемой процедуре, он должен быть членом группы, за
которой право такого доступа закреплено. Группы формируются
динамически. Для прикрепления к группе процесс должен обратиться к
охраняемой процедуре. Если в данный момент прикрепление к группе
возможно, эта процедура прикрепит процесс к группе, если нет –
заблокирует процесс до появления такой возможности. После окончания
доступа процесс должен вызвать также охраняемую процедуру
открепления от группы. Для задачи "читатели–писатели" предполагается
такой порядок доступа процессов к данным:
• для читателей:
startRead ( proc );
read( proc, ... );
endRead ( proc );
• для писателей:
startWrite ( proc );
write ( proc, ... );
endWrite ( proc );
где proc – идентификатор процесса.
Структура самого монитора в общих чертах следующая:
1
2
3
4
5
6
7
/* счетчик читателей /*
int rdCnt = 0;
/* признак активности записи */
char wrFlag = 0;
/* списки - писателей и читателей */
process *wrCrowd=NULL, *rdrowd=NULL;
/* события:
292
8
9
10
11
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
МОЖНО_ЧИТАТЬ, МОЖНО_ПИСАТЬ */
event mayRead, mayWrite;
/* процедура регистрации читателя */
void guard startRead ( process *p ) {
rdCnt++; /* подсчет читателей */
/* если идет запись -
ожидать МОЖНО_ЧИТАТЬ */
if ( wrFlag ) wait (mayRead);
/* дублирование сигнала
для другого читателя */
signal (mayRead);
/* включение в список читателей */
inCrowd ( rdCrowd, p );
}
/* процедура открепления читателя */
void guard endRead ( process *p ) {
/* исключение из списка читателей */
fromCrowd ( rdCrowd, p );
/* уменьшение числа читателей,
если читателей больше нет -
сигнализация МОЖНО_ПИСАТЬ */
if ( --rdCnt==0 ) signal(mayWrite);
}
/* процедура регистрации писателя */
void guard startWrite ( process *p ) {
/* если есть другие читатели
или писатели - ждать */
if ( wrFlag||rdCnt ) wait(mayWrite);
/* установка признака записи */
293
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
wrFlag = 1;
/* писатель включается в оба списка*/
inCrowd ( rdCrowd, p );
inCrowd ( wrCrowd, p );
}
/* процедура открепления писателя */
void guard endWrite ( process *p ) {
wrFlag=0; /* сброс признака записи */
/* исключение из списков */
fromCrowd ( rdCrowd, p );
fromCrowd ( wdCrowd, p );
/* если есть претенденты-читатели -
разрешение им */
if ( rdCnt ) signal (mayRead);
/* иначе - разрешение на запись */
else signal (mayWrite);
}
/* процедура чтения */
void read ( process *p,
< другие параметры > ) {
/* если процесс не зарегистрирован
читателем - отказ */
if (!checkCrowd(rdCrowd, p)) <отказ>;
else < чтение данных >;
}
/* процедура записи */
void write ( process *p,
< другие параметры > ) {
/* если процесс не зарегистрирован
294
66
67
68
69
писателем - отказ */
if (!checkCrowd(wrCrowd,p)) <отказ>;
else < запись данных >;
}
Прежде чем процесс получит доступ к данным, он должен
зарегистрироваться как читатель или как писатель. В нашем примере
переменные rdCrowd и wrCrowd (строка 6) являются указателями на
списки читателей и писателей соответственно, хотя можно интегрировать
процессы в группы и любым другим способом. Используемые (но не
определенные) нами функции inCrowd и fromCrowd обеспечивают
включение процесса в группу и исключение из группы, а функция
checkCrowd возвращает 1, если указанный процесс входит в группу
(иначе – 0). Процедура read выполняется только для процессов,
включенных в группу читателей (строки 59, 60), а write – только для
включенных в группу писателей (строки 67, 68). Переменная rdCnt (строка
2) – счетчик текущего числа читателей, переменная wrFlag (строка 4) –
счетчик писателей (или признак наличия писателя, так как писателей не
может быть более одного). События mayRead и mayWrite (строка 9)
являются разрешениями читать и писать соответственно.
Входная точка startRead (строка 11) выполняет регистрацию
читателя. Это охраняемая процедура. Она наращивает счетчик
читателей, но если в данный момент работает писатель, то
потенциальный читатель блокируется до наступления события mayRead
(строка 15). После того, как процесс будет разблокирован (или если он
не блокировался вообще), он выдает сигнал mayRead (строка 18),
который предназначается для другого читателя, возможно, также
ждущего разрешения на чтение (можно сказать, что процесс этим
295
восстанавливает потребленный им ресурс), и включается в список
читателей. После завершения доступа читатель обращается к входной
точке endRead (строка 23). Эта процедура исключает процесс из списка
читателей, уменьшает счетчик читателей и, если читателей больше не
осталось, сигнализирует разрешение на запись.
Писатель регистрируется/разрегистрируется через входные точки
startWrite/endWrite (строки 32/43). При регистрации
потенциальный писатель может быть заблокирован, если в настоящий
момент зарегистрирован другой писатель или хотя бы один читатель
(строка 35). Сигнал mayWrite разблокирует писателя, и он включается в
обе группы (строки 39, 40), так как имеет право и читать, и писать. При
откреплении писатель исключается из групп. Если за время его работы
попытался зарегистрироваться хотя бы один читатель, выдается
разрешение на чтение (строка 50), в противном случае – разрешение на
запись для другого писателя, возможно, ждущего своей очереди (строка
52).
8.10. Примитивы синхронизации в языках
программирования
До сих пор мы рассматривали методы, которые обеспечивают и
взаимное исключение, и синхронизацию. Целый ряд прикладных задач,
однако, требует только синхронизации без взаимного исключения. Отказ
от последнего, если это не мешает решению задачи, всегда оправдан, так
как взаимное исключение усложняет решение и может снижать уровень
мультипрограммирования.
Один из возможных примитивов, обеспечивающих синхронизацию
без взаимного исключения, называется счетчиком событий. Счетчик
296
событий – тип данных, представляемый неуменьшающимся целым числом
с начальным значением 0. Его значение в любой момент времени – число
событий определенного типа, происшедших от некоторой точки начала
отсчета. Над этим типом данных возможны следующие операции:
• advance(E) – увеличение значения счетчика событий E на 1,
атомарная операция;
• eread(E) – возвращает текущее значение счетчика E, эта
операция не взаимоисключающая с advance, так что к моменту,
когда значение попадет в читающий его процесс, текущее
значение счетчика может быть уже изменено;
• await(E,value) – ждать – ожидание (блокировка процесса),
пока значение счетчика E не станет большим, чем value, или
равным ему.
Существенно, что из перечисленных операций только advance
является взаимоисключающей, остальные могут выполняться параллельно
друг с другом и с advance.
Вот как решается с помощью счетчиков событий задача для одного
производителя и одного потребителя:
1
2
3
4
5
6
7
8
9
/* тип данных - счетчик событий */
typedef unsigned int eventcounter
/* счетчики для чтения и записи */
static eventcounter inCnt = 0,
outCnt = 0;
/* буфер */
static portion buffer [BUFSIZE];
/* процесс-потребитель */
void consumer ( void ) {
297
10
11
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
int portNum; /* номер порции */
/* рабочая область порции */
portion work;
/* цикл потребления */
for ( portNum = 1; ; portNum++ ) {
/* ожидание доступности порции
по номеру */
await (inCnt, portNum);
/* выборка из буфера */
memcpy (&work,
buffer + portNum % BSIZE,
sizeof(portion) );
/* продвижение счетчика записи */
advance (outCnt);
< обработка порции в work>
}
}
/* процесс-производитель */
void producer ( void ) {
int portNum; /* номер порции */
/* рабочая область для порции */
portion work;
/* цикл производства */
for ( portNum = 1; ; portNum++ ) {
< производство порции в work >
/* ожидание доступности порции
по номеру */
await (outCnt, portNum - BSIZE);
/* запись в буфер */
298
39
40
41
42
43
44
memcpy (buffer + portNum % BSIZE,
&work, sizeof(portion) );
/* продвижение счетчика чтения */
advance (inCnt);
}
}
Как мы уже отмечали выше, производитель и потребитель работают
с разными секциями буфера и взаимное исключение для них не требуется.
Процессы – производитель и потребитель – могут перекрываться в любых
своих фазах, кроме операций advance (строки 23 и 42). Переменные
inCnt и outCnt являются счетчиками событий – производства порции и
потребления порции соответственно. Кроме того, каждый процесс хранит в
собственной локальной переменной portNum номер порции, с которой
ему предстоит работать (счет начинается с 1). Потребитель ждет, пока
счетчик производств не достигнет номера очередной его порции, затем
выбирает порцию из буфера и увеличивает счетчик потреблений.
Производитель работает симметрично. Обратите внимание на второй
параметр операции await в производителе (строка 37). Он задается таким,
чтобы обеспечить отсутствие ожидания при наличии хотя бы одной
свободной секции в буфере.
Другой механизм синхронизации носит название секвенсоров
(sequencer). Буквальный перевод этого слова – "упорядочиватель"; так
называются средства, которые выстраивают неупорядоченные события в
определенном порядке. Как и счетчик событий, секвенсор представляется
целым числом, над которым выполняется единственная операция:
ticket. Операция ticket(S) возвращает текущее значение секвенсора
и увеличивает его на 1. Операция является атомарной. Начальное значение
секвенсора – 0.
299
Имея в своем распоряжении секвенсоры, мы можем так записать
решение задачи производителей–потребителей для произвольного числа
процессов:
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
/* типы данных - счетчик событий
и секвенсор */
typedef unsigned int eventcounter;
typedef unsigned int sequencer;
/* счетчики для чтения и записи */
static eventcounter inCnt = 0,
outCnt = 0;
/* секвенсоры для чтения и записи */
static sequencer inSeq = 0, outSeq = 0;
/* буфер */
static portion buffer [BUFSIZE];
/* процесс-производитель */
void producer ( void ) {
int portNum; /* номер порции */
/* рабочая область для порции */
portion work;
/* цикл производства */
while (1) {
< производство порции в work >
/* получение "билета"
на запись порции */
portNum = ticket (inSeq);
/* ожидание номера порции */
await (inCnt, portNum);
/* ожидание свободного места
300
26
27
28
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
в буфере */
await (outCnt, portNum - BSIZE+1);
/* запись в буфер */
memcpy (buffer + portNum % BSIZE,
&work, sizeof(portion) );
/* продвижение счетчика чтения */
advance (inCnt);
}
}
/* процесс-потребитель */
void consumer ( void ) {
int portNum; /* номер порции */
/* рабочая область для порции */
portion work;
/* цикл потребления */
while (1) {
/* получение "билета"
на выборку порции */
portNum = ticket (outSeq);
/* ожидание номера порции */
await (outCnt, portNum);
/* ожидание появления в буфере */
await (inCnt, portNum+1);
/* выборка порции */
memcpy (&work,
buffer + portNum % BSIZE,
sizeof(portion) );
/* продвижение счетчика записи */
advance (outCnt);