Задача читатели писатели

При разработке синхронизации и параллельных вычислений зачастую полезно связать имеющуюся у вас задачу с уже известными и получить возможность проверить применимость вашего решения к известной задаче. В литературе довольно часто встречается рассмотрение таких "эталонных" задач, представляющих собой примеры часто возникающих перед разработчиком проблем. С одной из них — задачей производителя/потребителя — мы уже встречались; в этом разделе мы рассмотрим еще одну классическую задачу — читателей/писателей.

Определить ее можно следующим образом. Имеются данные, совместно используемые рядом процессов. Данные могут находиться в файле, в блоке основной памяти или даже в регистрах процессора. Имеется несколько процессов, которые только читают эти данные (читатели), и несколько других, которые только записывают данные (писатели). При этом должны удовлетворяться следующие условия.

• Любое число читателей могут одновременно читать файл.
• Записывать информацию в файл в определенный момент времени может
  только один писатель.
• Когда писатель записывает данные в файл, ни один читатель не может его
  читать.

Перед тем как приступить к работе, разделим эту задачу на две: обычную задачу взаимоисключений и задачу производителя/потребителя. В задаче читателей/писателей читатели не записывают данные, а писатели их не читают. Более общей является ситуация, когда каждый процесс может как читать, так и писать данные (и которая включает рассматриваемую задачу как частный случай). В таком случае мы можем объявить любую часть процесса, которая обращается к данным, критическим разделом и использовать простейшее решение на основе взаимоисключений. Причина, по которой мы рассматриваем частный случай более общей задачи, заключается в том, что общее решение значительно замедляет работу, в то время как для частного случая имеется гораздо более эффективное решение. Представим себе библиотечный каталог, в котором читатели могут искать нужную им литературу, а один или несколько работников библиотеки могут этот каталог обновлять. При общем решении читатели будут вынуждены входить в каталог по одному, что, конечно, приведет к неоправданным задержкам и очередям. Кроме того, работники библиотеки при внесении изменений не должны мешать друг другу, а также не должны допускать читателей к данным в момент их изменения, чтобы предотвратить получение читателем недостоверной информации.

Можно ли рассматривать задачу производителя/потребителя как частный случай задачи читателей/писателей с единственным писателем (производитель) и единственным читателем (потребитель)? Оказывается, нет. Производитель — не просто писатель. Он должен считывать значение указателя очереди, чтобы определять, куда следует вносить очередную порцию информации, и выяснять, не заполнен ли буфер. Аналогично и потребитель является не просто читателем, так как он изменяет значение указателя очереди, указывая, что элемент удален из буфера.

Теперь мы рассмотрим два решения поставленной задачи.

Приоритетное чтение

В листинге 5.19 приведено решение задачи с использованием семафоров для варианта, в котором имеются один читатель и один писатель (решение не требует изменений, если имеется много читателей и писателей). Процесс писателя очень прост. Для обеспечения взаимного исключения используется семафор wsem. Когда один писатель записывает данные, ни другие писатели, ни читатели не могут получить к ним доступ. Процесс читателя также использует семафор wsem для обеспечения взаимоисключений. Однако чтобы обеспечить возможность одновременной работы многих читателей, состояние семафора проверяет только читатель, входящий в критический раздел, в котором нет других читателей. Если в критическом разделе уже находится хоть один читатель, то другой читатель приступает к работе, не ожидая семафора wsem. Для отслеживания количества читателей в критическом разделе используется глобальная переменная readcount, а для гарантии корректного ее обновления — семафор х.

Листинг 5.19. Решение задачи читателей/писателей с использованием семафоров (приоритетное чтение)

int readcount;
semaphore x = 1, wsem = 1;
void reader ()
{
while(true)
{
wait(x);
readcount++;
if (readcount==l)
wait(wsem);
signal(x);
READUNITO;
wait(x);
readcount—;
if (readcount==0)
signal(wsem);
signal(x);
}
}
void writer ()
{
while(true)
{
wait(wsem);
WRITEUNITO;
signal(wsem);
}
}
void main ()
{
readcount = 0;
parbegin(reader, writer);
}

Приоритетная запись

В предыдущем решении приоритетной операцией являлось чтение данных. Если один читатель получил доступ к данным, то возможна ситуация, когда писатель в течение долгого времени не получит возможности внести изменения — пока хотя бы один из читателей будет находиться в критическом разделе.

В листинге 5.20 показано решение, обеспечивающее выполнение следующего условия: ни один читатель не сможет обратиться к данным, если хотя бы один писатель объявил о своем намерении произвести запись. Для этого к имеющимся в программе семафорам и переменным процесса писателя добавлены следующие:

семафор rsem, запрещающий вход читателей, если хотя бы один писатель объявил о намерении произвести запись;
переменная writecount, обеспечивающая корректность установки значения
rsem;
семафор у, гарантирующий корректность изменения переменной writecount.

Листинг 5.20. Решение задачи читателей/писателей с использованием семафоров (приоритетная запись)

int readcount, writecount;
semaphore x = 1, y=l, z=l,
rsem = 1, wsem = 1;
void reader()
{
while(true)
{
wait(z);
wait(rsem);
wait(x);
readcount++;
if (readcount==l)
wait(wsem);
signal(x);
signal(rsem);
signal(z);
READUNIT();
wait(x);
readcount--;
if (readcount==0)
signal(wsem);
signal (x);
}
}
void writer()
{
while(true)
{
wait(y);
writecount++;
if (writecount==l)
wait(rsem);
signal(y);
wait(wsem);
WRITEUNITO;
signal(wsem);
wait(y);
writecount—;
if (writecount==0)
signal(rsem); signal(y);
}
}
void main ()
{
readcount = writecount = 0;
parbegin(reader, writer);
}

В процессе читателя требуется один дополнительный семафор. На основании семафора rsem нельзя создавать длинную очередь, иначе сквозь нее не смогут "прорваться" писатели. Для осуществления ограничения, когда семафор rsem приостанавливает только один процесс чтения, служит семафор z, блокирующий остальных читателей. В табл. 5.5 приведены возможные ситуации в данной системе.

Таблица 5.5. Состояния очередей процессов в программе из листинга 5.20

В листинге 5.21 приведено еще одно решение задачи с приоритетной записью, реализованное с использованием системы передачи сообщений. В этом случае имеется управляющий процесс с правом доступа к совместно используемым данным. Прочие процессы запрашивают право доступа к данным, посылая сообщение управляющему процессу. Запрашивающий процесс получает право доступа посредством ответного сообщения "ОК", а после завершения работы сообщает об этом специальным сообщением finished. У управляющего процесса имеются три почтовых ящика, по одному для каждого типа получаемых им сообщений.

Листинг 5.21. Решение задачи читателей/писателей с использованием системы передачи сообщений

void reader(int i)
{
message rmsg;
while(true)
{
rmsg = i;
send(readrequest,rmsg);
receive(mbox[i],rmsg);
READUNIT();
rmsg = i;
send{finished,rmsg);
}
}
void writer(int j)
{
message rmsg;
while(true)
{
rmsg = i^-send (writerequest, rmsg);
receive(mbox[j],rmsg);
WRITEUNITO ;
rmsg = i;
send(finished,rmsg);
}
}
void controller()
{
while(true)
{
if (count > 0)
{
if (!empty(finished))
{
receive(finished,msg);
count++;
}
else if (!empty(writerequest))
{
receive(writerequest,msg);
writer_id = msg.id;
count = count - 100;
}
else if (!empty(readrequest) )
{
receive(readrequest,msg);
count--;
send(msg.id,"OK");
}
}
if (count == 0)
{
send(writer_id,"OK");
receive(finished,msg);
count = 100;
}
while(count < 0)
{
receive(finished,msg);
count++;
}
}
}

Первыми управляющий процесс обслужит запросы на запись, давая таким образом приоритет операции записи; кроме того, управляющий процесс обеспечивает выполнение взаимоисключений, для чего используется переменная count, инициализируемая неким числом, которое заведомо больше максимально возможного количества читателей. В нашем примере использовано значение 100. Действия управляющего процесса можно описать следующим образом.

Если count>0, значит, ожидающих писателей нет; активные читатели могут как присутствовать, так и отсутствовать. Управляющий процесс обслуживает сначала все сообщения типа finished, а затем запросы от писателей и читателей.
Если count=0, это означает, что у нас имеется только запрос на запись.Управляющий процесс дает писателю "добро" на выполнение своих действий и ожидает от него сообщения о завершении работы.

Если count<0, значит, писатель сделал запрос и ожидает завершения работы всех активных читателей, так что управляющий процесс при этом принимает только сообщения о завершении работы читателей.