loop
D := Буфер.Прочитать; Обработка(D);
end loop;
Parbegin Поставщик; Потребитель; Parend.
По определению, в каждый конкретный момент времени процедура Записать или процедура Прочитать может использоваться только одной задачей; например, в случае, если «Поставщик» выполняет запись в буфер посредством вызова Буфер.Записать(D) и в это время «Потребитель» выполняет вызов Буфер.Прочитать, то «Потребитель» будет заблокирован и поставлен в очередь доступа. Таким образом, одновременное выполнение действий чтения и записи невозможно, т. е. выполняется третье условие задачи.
Однако для полноценного решения обеспечения только взаимного исключения будет недостаточно. При написании многозадачных приложений часто возникают ситуации, когда необходимо сделать так, чтобы одна из задач ожидала выполнения некоторого условия, которое должно измениться другой задачей.
При определении монитора Хоаром был предложен механизм условной переменной, который является его неотъемлемой частью. В мониторе предоставляется возможность определять переменную типа condition, над которой возможны 3 операции: wait(cond), signal(cond), check(cond), где cond
– переменная типа condition. Действие wait(cond) блокирует вызвавшую задачу и ставит ее в очередь, связанную с переменной cond; действие signal(cond) выбирает из этой очереди первую задачу (предполагается, что дисциплина обслуживания очереди – FIFO) и позволяет ей продолжить работу; операция check(cond) возвращает количество задач, находящихся в этой очереди. Тип данных condition отличается от традиционного представления типа данных в языках программирования как определения множества значений переменной и множества допустимых операций над этими значениями.
Какие же очереди создаются при определении монитора? Во-первых – это очередь доступа к монитору. В нее попадают все задачи, которые блокируются при попытке получить доступ к ресурсам монитора, если он уже занят какой-то задачей. Далее, при определении в мониторе условной переменной с ней связывается очередь задач, которые могут блокироваться
11
действием wait над этой переменной. Таких очередей будет столько, сколько переменных определено в мониторе.
Приведем пример монитора, с помощью которого еще раз реализуем решение задачи «Поставщик – Потребитель»:
monitor Буфер;
СамБуфер array[1..ДлинаБуфера] : Данное; СчетчикЗаписей : integer;
НеПуст, НеПолон : condition; procedure Записать(d : Данное);
begin
if (СчетчикЗаписей >= ДлинаБуфера) then wait(НеПолон);
Записать_в_буфер; СчетчикЗаписей := СчетчикЗаписей + 1; signal(НеПуст);
end;
function Прочитать : Данное; begin
if (СчетчикЗаписей = 0) then wait(НеПуст);
Прочитать_из_буфера; СчетчикЗаписей := СчетчикЗаписей – 1; signal(НеПолон);
end;
begin
СчетчикЗаписей := 0; end Буфер;
Поставщик: loop
D := Производство;
Буфер.Записать(D); end loop;
Потребитель: loop
D := Буфер.Прочитать; Обработка(D);
12
end loop;
Parbegin Поставщик; Потребитель; Parend.
В приведенном мониторе выполняются все 3 условия задачи «Поставщик – Потребитель» в ее «классической интерпретации». Однако одна особенность заслуживает более тщательного рассмотрения.
Обратимся к примеру монитора, в котором описана одна условная condпеременная и две процедуры P1 и P2:
monitor Х;
cond : condition; procedure P1;
. . .
if (условие) then wait(cond);
. . .
end; procedure P2;
. . .
signal(cond);
. . .
операция Y;
. . .
end; end X.
Пусть некоторая задача R1 вызвала процедуру P1 при значении «условие» = «истина». Задача R1 блокируется и ставится в очередь, связанную с переменной cond, монитор освобождается, и его процедуры становятся доступными для других задач. Пусть теперь некоторая задача R2 устанавливает «условие» в значение «ложь» и вызывает процедуру P2. При этом действие операции signal(cond) должно немедленно активизировать задачу R1, гарантируя, что за время активизации значение условия «условие» не изменилось. Предполагается, что такая особенность, известная как «семантика Хоара», свойственна монитору Хоара.
Однако на практике реализация такого свойства оказывается сложной и не совместимой с вытесняющей многозадачностью, когда любая задача может быть приостановлена в произвольный момент. В реальной ситуации действие signal(cond) не прерывает задачу R2, а просто переводит R1 из
13
очереди заблокированных в очередь задач, готовых к выполнению, а задача R2 «держит» монитор до окончания выполнения процедуры P2. Такая реализация известна под названием «семантика Mesa». Заметим, что при этом нет никаких ограничений на то, что в приведенном примере действие «операция Y» снова не изменит значение «условие» на «истина». Кроме того за время, прошедшее между освобождением монитора задачей R2 и возобновлением работы R1 с действия, следующего за wait(cond), какая-то третья задача могла изменить значение «условие» на «истина». Таким образом, в «семантике Mesa», которая и реализуется на практике, может возникнуть ситуация, когда задача R1 будет продолжать работу при недопустимом значении условия. Во избежание этого условие блокировки задачи должно перепроверяться, и вместо конструкции «if (условие) then wait(cond);» необходимо использовать конструкцию «while (условие) wait(cond);».
Пример: задача «Читатели – Писатели»
В качестве примера использования монитора, предложенного Хоаром, рассмотрим еще одну задачу синхронизации, ставшую уже классической.
Пусть имеется некоторый «Информационный фонд», предназначенный для хранения определенных данных. Пусть имеется N задач – Писателей, которые могут записывать данные в этот Информационный фонд, и М задач
– Читателей, которые могут читать данные. Как Читатели, так и Писатели могут работать с фондом ограниченное время, но на скорость их работы ограничений не накладывается. Другими словами, какой-то Читатель может читать «очень быстро» и «недолго», а какой-то очень «медленно» и «долго». Аналогично и Писатели. Следует организовать работу Читателей и Писателей таким образом, чтобы выполнялись следующие условия:
1.В каждый момент времени может работать только один Писатель.
2.В каждый момент времени количество работающих Читателей может быть от 0 до М.
3.Ни Читатель, ни Писатель не должны ждать доступа к Фонду бесконечно долго.
Решить задачу можно с помощью монитора по следующей схеме: monitor ЧитателиПисатели;
МожноЧитать, МожноПисать : condition; КтоТоПишет : boolean;
14
Читатели : 0..M; procedure НачалоЧтения; procedure КонецЧтения; procedure НачалоЗаписи; procedure КонецЗаписи; begin
КтоТоПишет := false; Читатели := 0;
end ЧитателиПисатели.
Каждый Читатель начинает свое взаимодействие с Информационным фондом с вызова процедуры ЧитателиПисатели.НачалоЧтения и заканчивает вызовом ЧитателиПисатели.КонецЧтения:
Читатель: loop
ЧитателиПисатели.НачалоЧтения; РаботаСФондомЧ; ЧитателиПисатели.КонецЧтения; РазноеЧ;
end loop;
Аналогично, каждый Писатель выполняет подобные действия перед началом и концом записи:
Писатель: loop
ЧитателиПисатели.НачалоЗаписи; РаботаСФондомП; ЧитателиПисатели.КонецЗаписи; РазноеП;
end loop;
Таким образом, осталось определить 4 процедуры монитора, но сделать это так, чтобы выполнялись условия задачи. Начнем с процедуры НачалоЧтения:
procedure НачалоЧтения; begin
if (КтоТоПишет) or (check(МожноПисать) > 0) then
wait(МожноЧитать); |
// * |
Читатели := Читатели + 1; |
|
15