Решение задачи «читатели — писатели»
Другой важной и часто встречающейся задачей, решение которой также требует синхронизации, является задача «читатели — писатели». Эта задача имеет много вариантов. Наиболее характерная область использования этой задачи — при построении систем управления файлами. Два класса процессов имеют доступ к некоторому ресурсу (области памяти, файлам). «Читатели» — это процессы, которые могут параллельно считывать информацию из некоторой общей области памяти, являющейся критическим ресурсом. «Писатели» — это процессы, записывающие информацию в эту область памяти, исключая при этом и друг друга, и процессы «читатели». Имеются различные варианты взаимодействия между «писателями» и «читателями». Наиболее широко распространены следующие условия.
Устанавливается приоритет в использование критического ресурса процессам «читатели». Это означает, что если хотя бы один «читатель» пользуется ресурсом, то он закрыт для использования всем «писателям» и доступен для использования всем «читателям». Во втором варианте, наоборот, больший приоритет у процессов «писатели». При появлении запроса от «писателя» необходимо закрыть дальнейший доступ всем тем процессам «читателям», которые выдадут запрос на критический ресурс после него.
Другим типичным примером для задачи «читатели — писатели» помимо систем управления файлами может служить система автоматизированной продажи билетов. Процессы «читатели» обеспечивают нас справочной информацией о наличии свободных билетов на тот или иной рейс. Процессы «писатели» запускаются с пульта кассира, когда он оформляет для нас тот или иной билет. Имеется большое количество как «читателей», так и «писателей».
Пример программы, реализующей решение данной задачи в первой постановке, представлен в листинге 6.13. Процессы «читатели» и «писатели» описаны в виде соответствующих процедур.
Листинг 6.13. Решение задачи «читатели — писатели» с приоритетом в доступе к критическому ресурсу «читателей»
varR. W: semaphore;
NR: integer: procedure ЧИТАТЕЛЬ: begin
Р(Ю:
Inc(NR); { NR:-NR +1 }
if NR - 1 then PCW):
VCR):
Read Data: { критический интервал } продолжение *?
Листинг 6.13 (продолжение)
Р(Ю: Dec(NR):
if NR = 0 then V(W); V(R) end:
procedure ПИСАТЕЛЬ: begin
P(W):
Write_Data: { критический интервал }
V(W) end
begi n NR:=0:
InitSem(S.l): InitSem(W.l): parbegin
.while true do ЧИТАТЕЛЬ and
while true do ЧИТАТЕЛЬ and
while true do ЧИТАТЕЛЬ and
while true do ПИСАТЕЛЬ and
while true do ПИСАТЕЛЬ and
while true do ПИСАТЕЛЬ pa rend end.
При решении данной задачи используются два семафора R и W и переменная NR, предназначенная для подсчета текущего числа процессов типа «читатели», находящихся в критическом интервале. Доступ к разделяемой области памяти осуществляется через семафор W. Семафор R используется для взаимоисключения процессов типа «читатели».
Если критический ресурс не используется, то первый появившийся процесс при входе в критический интервал выполнит операцию P(W) и закроет семафор. Если процесс является «читателем», то переменная NR будет увеличена на единицу и последующие «читатели» будут обращаться к ресурсу, не проверяя значение семафора W, что обеспечивает параллельность их доступа к памяти. Последний «читатель», покидающий критический интервал, является единственным, кто выполнит операцию V(W) и откроет семафор W. Семафор R предохраняет от некор-
ректного изменения значения NR, а также от выполнения «читателями» операций P(W) и V(W). Если в критическом интервале находится «писатель», то на семафоре W может быть заблокирован только один «читатель», все остальные будут блокироваться на семафоре R. Другие «писатели» блокируются на семафоре W.
Когда «писатель» выполняет операцию V(W), неясно, какого типа процесс войдет в критический интервал. Чтобы гарантировать получение процессами «читателями» наиболее свежей информации, необходимо при постановке в очередь готовности использовать дисциплину обслуживания, учитывающую более высокий приоритет «писателей». Однако этого оказывается недостаточно, ибо если в критическом интервале продолжает находиться, по крайней мере, один «читатель», то он не даст обновить данные, но и не воспрепятствует вновь приходящим процессам «читателям» войти свою критическую секцию. Необходим дополнительный семафор. Пример правильного решения этой задачи приведен в листинге 6.14.
Листинг 6.14. Решение задачи «читатели — писатели» с приоритетом в доступе к критическому ресурсу первых с дополнительным семафором
var S. W. R: semaphore:
NR: integer: procedure ЧИТАТЕЛЬ: begin
P(S): P(R):
Inc(NR):
if NR - 1 then P(W):
V(S): V(R):
Read_Data: { критический интервал }
P(R):
Dec(NR):
if NR = 0 then V(W);
V(R) end:
procedure ПИСАТЕЛЬ; begin
PCS): P(W):
Write_Data: { критический интервал }
V(S): V(W) end
begin NR:=0:
InitSem(S.l): InitSem(W.l): InitSem(R.l): parbegin
while true do ЧИТАТЕЛЬ and
while true do ЧИТАТЕЛЬ продолжение #
Листинг 6.14 (продолжение)
and
while true do ЧИТАТЕЛЬ and
while true do ПИСАТЕЛЬ and
while true do ПИСАТЕЛЬ and
while true do ПИСАТЕЛЬ parend end.
Как можно заметить, семафор S блокирует приход новых «читателей», если появился хотя бы один процесс «писатель». Обратите внимание, что в процедуре «читатель» использование семафора S имеет место только при входе в критический интервал. После выполнения чтения уже категорически нельзя использовать этот семафор, ибо он тут же заблокирует первого же «читателя», если хотя бы один «писатель» захотел войти в свою критическую секцию. И получится так называемая тупиковая ситуация, ибо «писатель» не сможет войти в критическую секцию, поскольку в ней уже находится процесс «читатель». А «читатель» не сможет покинуть критическую секцию, потому что процесс «писатель» желает войти в свой критический интервал.
Обычно программы, решающие проблему «читатели — писатели», используют как семафоры, так и мониторные схемы с взаимным исключением, то есть такие, которые блокируют доступ к критическим ресурсам для всех остальных процессов, если один из них модифицирует значения общих переменных. Взаимное исключение требует, чтобы «писатель» ждал завершения всех текущих операций чтения. При условии, что «писатель» имеет более высокий приоритет, чем «читатель», такое ожидание в ряде случаев весьма нежелательно. Кроме того, реализация принципа исключения в многопроцессорных системах может вызвать определенную избыточность. Поэтому ниже приводится схема, применяемая иногда для решения задачи «читатели — писатели», которая в случае одного «писателя» допускает одновременное выполнение операций чтения и записи (листинг 6.15). После чтения данных процесс «читатель» проверяет, мог ли он получить неправильное значение, некорректные данные (вследствие того, что параллельно с ним процесс «писатель» мог их изменить), и если обнаруживает, что это именно так, то операция чтения повторяется.
Листинг 6.15. Синхронизация процессов «читатели» и «писатель» без взаимного исключения
Var VI. V2: integer;
Procedure ПИСАТЕЛЬ: • Begin
Inc(Vl); Write_Data; V2:=V1 End;
Procedure ЧИТАТЕЛЬ; Var V: integer Begin
Repeat V.:- V2; Read_Data
Until VI • V End;
. Begin
VI:- 0: V2:- 0: Parbegin
while true do ЧИТАТЕЛЬ and
while true do ЧИТАТЕЛЬ and
while true do ЧИТАТЕЛЬ and
while true do ПИСАТЕЛЬ pa rend end.
Этот алгоритм использует для данных два номера версий, которым соответствуют переменные VI и V2. Перед записью порции новых данных процесс «писатель» увеличивает на 1 значение переменной VI, а после записи — переменную V2. «Читатель» обращается к V2 перед чтением данных, а к VI — после. Если при этом VI и V2 равны, то очевидно, что получена правильная версия данных. Если же данные обновлялись за время чтения, то операция повторяется. Данный алгоритм может быть использован в случае, если нежелательно заставлять процесс «писатель» ждать, пока «читатели» закончат операцию чтения, или если вероятность повторения операции чтения достаточно мала и обусловленное повторными операциями снижение эффективности системы меньше потерь, связанных с избыточностью решения при использовании взаимного исключения. Однако необходимо иметь в виду ненулевую вероятность зацикливания чтения при высокой интенсивности операций записи. Наконец, если само чтение представляет собой достаточно длительную операцию, то оператор V:=V2 для процесса «читатель» может быть заменен на оператор
Repeat V:- V2 Until VI - V
Это предотвратит выполнение «читателем» операции чтение, если «писатель» уже начал запись.
Дата добавления: 2015-01-18 | Просмотры: 1581 | Нарушение авторских прав
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 |
|