Задача производителя и потребителя

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

Проблемы возникают в тот момент, когда производителю требуется поместить новую запись в уже заполненный буфер. Решение заключается в блокировании производителя до тех пор, пока потребитель не извлечет как минимум одну запись. Также, если потребителю нужно извлечь запись из буфера и он видит, что буфер пуст, он блокируется до тех пор, пока производитель не поместит что-нибудь в буфер и не активизирует этого потребителя.

На первый взгляд этот подход выглядит довольно простым, но он приводит к той же разновидности состязательной ситуации, которая нам уже встречалась в примере с каталогом спулера. Для отслеживания количества записей в буфере нам потребуется переменная count. Если максимальное количество записей, которое может содержаться в буфере, равно N, то программа производителя должна сначала проверить, не имеет ли count значение N. Если переменная имеет такое значение, производитель должен заблокировать свое выполнение, а если не имеет, производитель должен добавить запись и увеличить показание счетчика count.

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

Чтобы выразить вызовы sleep и wakeup на языке C, мы покажем их в виде вызовов библиотечных процедур. Они не являются частью стандартной библиотеки C, но, по-видимому, были бы доступны на любой системе, имеющей эти системные вызовы.



Листинг 2.5.
Задача производителя и потребителя с фатальной состязательной ситуацией


Не показанные в листинге процедуры insert_item и remove_item занимаются помещением записей в буфер и извлечением их оттуда.

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

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

Суть возникшей проблемы заключается в утрате вызова wakeup в отношении процесса, который не находится в состоянии блокировки по собственной воле. Если бы этот вы
зов не утрачивался, то все бы работало должным образом. Быстро устранить проблему позволит изменение правил за счет добавления к картине событий бита ожидания активизации. Этот бит устанавливается, когда в отношении процесса, который не находится в состоянии бездействия, вызывается процедура wakeup. Затем, когда процесс попытается заблокироваться при установленном бите ожидания активизации, этот бит снимается, но процесс не блокируется. Бит ожидания активизации становится своеобразной копилкой, хранящей сигналы активизации. Потребитель снимает бит ожидания активизации в каждой итерации цикла.

Хотя в нашем простом примере бит ожидания активизации спасает положение, нетрудно создать такие примеры, где фигурируют три и более процесса, для которых одного бита ожидания активизации явно недостаточно. Можно внести другие правки и добавить второй бит ожидания активизации, а может быть, 8 или 32 таких бита, но, в принципе, проблема останется нерешенной.

2.3.4.

<< | >>
Источник: Э. ТАНЕНБАУМ Х. БОС. СОВРЕМЕННЫЕ ОПЕРАЦИОННЫЕ СИСТЕМ Ы 4-е ИЗДАНИЕ. 2015

Еще по теме Задача производителя и потребителя:

  1. 3. Права производителей фонограмм.
  2. 5. Права производителя фонограммы
  3. § 6. Исключительные права на средства индивидуализации товаров и их производителей
  4. 1. Понятие потребителя
  5. 3. Договоры о передаче исключительных прав производителя фонограммы
  6. Ориентация организации на потребителя.
  7. 3. Право потребителей на информацию
  8. 5. 3ащита прав потребителей
  9. Глава 31. Патентное право, права на средства индивидуализации товаров и их производителей («промышленная собственность»)
  10. 5. Договоры о передаче прав на средства индивидуализации товаров и их производителей
  11. Аудитория как потребитель продукции СМИ
  12. Аудитория как потребитель продукции СМИ
  13. § 2. Гражданско-правовая защита потребителей в обязательствах розничной купли-продажи
  14. 2. Права граждан-потребителей и особенности их гражданско-правовой защиты
  15. § 1. Гражданско-правовое регулирование отношений, связанных с интеллектуальной деятельностью, ее результатами, средствами индивидуализации товаров и их производителей
  16. 3. Последствия продажи покупателю (потребителю) товара ненадлежащего качества