| РЕФЕРАТ на тему: типовые задачи синхронизации "Читатели-писатели" | |
| Автор: drug | Категория: Прочее | Просмотров: | Комментирии: 0 | 17-04-2013 17:05 |
РЕФЕРАТ
на тему:
типовые задачи синхронизации "Читатели-писатели"
"Читатели-писатели" и групповые мониторы
Еще одна классическая задача синхронизации называется задачей "читателей-писателей" и формулируется следующим образом. Имеется произвольное число процессов-писателей и процессов-читателей, которые совместно используют какие-то данные (обычно имеется в виду файл). В любой момент процесс-читатель может потребовать прочитать данные. В любой момент процесс-писатель может потребовать прочитать или записать данные. Чтение и запись данных - операции длительные, но конечные. В то время, когда процесс записывает данные, никакие другие читатели или писатели не должны иметь доступа к данным. Любое число процессов может читать данные одновременно. Решение должно обеспечивать целостность данных и отсутствие бесконечного откладывания процессов.
Существенные отличия этой задачи от задачи производителей-потребителей состоят в следующем:
-процессы чтения и записи длительные;
-данные представляют собой повторно используемые ресурсы, а не потребляемые, как в предыдущей задаче;
-требуются различные режимы доступа для чтения и записи.
Нам не удастся решить эту задачу при помощи мониторов, описанных в предыдущем разделе, так как, если мы сделаем процедуры read и write охраняемыми, то, во-первых, у нас получатся слишком большие (длительные) критические секции, а во-вторых, мы исключим параллельное выполнение читателей.
Решение может быть получено при помощи, так называемого, группового монитора. В такой монитор входят как охраняемые, так и неохраняемые процедуры. Для того, чтобы процесс получил возможность доступа к неохраняемой процедуре, он должен быть членом группы, за которой право такого доступа закреплено. Группы формируются динамически. Для прикрепления к группе процесс должен обратиться к охраняемой процедуре. Если в данный момент прикрепление к группе возможно, эта процедура прикрепит процесс к группе, если нет - заблокирует процесс до появления такой возможности. После окончания доступа процесс должен вызвать также охраняемую процедуру открепления от группы. Для задачи "читатели-писатели" предполагается такой порядок доступа процессов к данным:
для читателей:
startRead ( proc );
read( proc, ... );
endRead ( proc );
для писателей:
startWrite ( proc );
write ( proc, ... );
endWrite ( proc );
где proc - идентификатор процесса.
Структура самого монитора в общих чертах следующая:
1 int rdCnt = 0; /* счетчик читателей */
2 char wrFlag = 0; /* признак активности записи */
3 /* списки - писателей и читателей */
4 process *wrCrowd=NULL, *rdrowd=NULL;
5 /* события: МОЖНО_ЧИТАТЬ, МОЖНО_ПИСАТЬ */
6 event mayRead, mayWrite;
7 /*== процедура регистрации читателя ==*/
8 void guard startRead ( process *p ) {
9 rdCnt++; /* подсчет читателей */
10 /* если идет запись - ожидать МОЖНО_ЧИТАТЬ */
11 if ( wrFlag ) wait (mayRead);
12 /* дублирование сигнала для другого читателя */
13 signal (mayRead);
14 /* включение в список читателей */
15 inCrowd ( rdCrowd, p );
16 }
17 /*== процедура открепления читателя ==*/
18 void guard endRead ( process *p ) {
19 /* исключение из списка читателей */
20 fromCrowd ( rdCrowd, p );
21 /* уменьшение числа читателей,
22 если читателей больше нет - сигнализация МОЖНО_ПИСАТЬ */
23 if ( --rdCnt==0 ) signal(mayWrite);
24 }
25 /*== процедура регистрации писателя ==*/
26 void guard startWrite ( process *p ) {
27 /* если есть другие читатели или писатели - ждать */
28 if ( wrFlag||rdCnt ) wait(mayWrite);
29 /* установка признака записи */
30 wrFlag = 1;
31 /* писатель включается в оба списка*/
32 inCrowd ( rdCrowd, p );
33 inCrowd ( wrCrowd, p );
34 }
35 /*== процедура открепления писателя ==*/
36 void guard endWrite ( process *p ) {
37 wrFlag=0; /* сброс признака записи */
38 /* исключение из списков */
39 fromCrowd ( rdCrowd, p );
40 fromCrowd ( wdCrowd, p );
41 /* если есть претенденты-читатели - разрешение им */
42 if ( rdCnt ) signal (mayRead);
43 /* иначе - разрешение на запись */
44 else signal (mayWrite);
45 }
46 /*== процедура чтения ==*/
47 void read ( process *p,
48 ) {
49 /* если процесс не зарегистрирован читателем - отказ */
50 if (!checkCrowd(rdCrowd, p)) ;
51 else ;
52 }
53 /*== процедура записи ==*/
54 void write ( process *p,
55 ) {
56 /* если процесс не зарегистрирован писателем - отказ */
57 if (!checkCrowd(wrCrowd,p)) ;
58 else ;
59 }
Прежде, чем процесс получит доступ к данным, он должен зарегистрироваться как читатель или как писатель. В нашем примере переменные rdCrowd и wrCrowd (строка 4) являются указателями на списки читателей и писателей соответственно, хотя можно интегрировать процессы в группы и любым другим способом. Используемые (но не определенные) нами функции inCrowd и fromCrowd обеспечивают включение процесса в группу и исключение из группы, а функция checkCrowd возвращает 1, если указанный процесс входит в группу (иначе - 0). Процедура read выполняется только для процессов, включенных в группу читателей (строки 50, 51), а write - только для включенных в группу писателей (строки 57, 58). Переменная rdCnt (строка 2) - счетчик текущего числа читателей, переменная wrFlag (строка 4) - счетчик писателей (или признак наличия писателя, так как писателей не может быть более одного). События mayRead и mayWrite (строка 9) являются разрешениями читать и писать соответственно.
Входная точка startRead (строка 8) выполняет регистрацию читателя. Это охраняемая процедура. Она наращивает счетчик читателей, но если в данный момент работает писатель, то потенциальный читатель блокируется до наступления события mayRead (строка 11). После того, как процесс будет разблокирован (или если он не блокировался вообще), он выдает сигнал mayRead (строка 13), который предназначается для другого читателя, возможно, также ждущего разрешения на чтение (можно сказать, что процесс этим восстанавливает потребленный им ресурс), и включается в список читателей. После завершения доступа читатель обращается к входной точке endRead (строка 18). Эта процедура исключает процесс из списка читателей, уменьшает счетчик читателей и, если читателей больше не осталось, сигнализирует разрешение на запись.
Писатель регистрируется/разрегистрируется через входные точки startWrite/endWrite (строки 26-36). При регистрации потенциальный писатель может быть заблокирован, если в настоящий момент зарегистрирован другой писатель или хотя бы один читатель (строка 28). Сигнал mayWrite разблокирует писателя, и он включается в обе группы (строки 32, 33), так как имеет право и читать, и писать. При откреплении писатель исключается из групп. Если за время его работы попытался зарегистрироваться хотя бы один читатель, выдается разрешение на чтение (строка 42), в противном случае - разрешение на запись для другого писателя, возможно, ждущего своей очереди (строка 44).