Заметки о программировании

       

Типичное использование общего семафора



4.1. Типичное использование общего семафора

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

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

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


Если, однако, природа вычислительного процесса такова, что после одной или двух секунд энергичных вычислений вырабатывается от 4 до 8 образов карт сразу, то безбуферная связь приведет к тому, что за периодом времени, в течение которого перфоратор будет простаивать (из-за отсутствия информации), последует период, когда должен будет стоять вычислительный процесс, потому что он не сможет избавиться от следующего произведенного образа карты, прежде чем предыдущий не будет отперфорирован. Такая нестабильность в скорости выработки образов карт может быть, однако, сглажена с помощью буфера надлежащего размера. Вот почему такое приспособление с очередью получило название "буфер".)

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

Опуская во внешнем блоке все связанные с буфером описания, мы можем теперь построить два процесса с помощью единственного общего семафора, названного "число порций в буфере".

begin integer число порций в буфере; число порций в буфере := 0; parbegin

производитель: begin

снова 1: производство новой порции; добавление порции к буферу; V(число порций в буфере); goto снова 1 end; потребитель: begin

снова 2: P(число порций в буфере); взятие порции из буфера; обработка взятой порции; goto снова 2 end; parend





end

Вторая строка части программы производителя представляет процесс формирования следующей порции информации; подразумевается полная независимость от буфера, для которого предназначена эта порция; когда этот оператор выполнен, очередная порция окончательно образована и ее вид больше не зависит от каких-либо неупомянутых здесь обстоятельств. Третья строка программы производителя описывает добавление сформированной порции к буферу, но так, что потребитель еще не знает об этом. V-операция окончательно подтверждает ее наличие, т. е. сообщает об этом потребителю. Чрезвычайно существенным является то, что V-операции предшествует окончательное добавление порции. О структуре потребителя можно сделать аналогичные замечания.

Операции "добавление порции к буферу" и "взятие порции из буфера", работающие с общей управляющей информацией о состоянии буфера, особенно в случае организации буфера в виде цепи, могут мешать друг другу, если только мы не позаботимся о том, чтобы они взаимно исключали друг друга во время выполнения. Этого можно добиться с помощью двоичного семафора, названного "работа с буфером", который принимает следующие значения:


  • =0: имеет место добавление к буферу или взятие из буфера;
  • =1: ни добавление, ни взятие не имеют места.


Программа становится такой:

begin integer число порций в буфере, работа с буфером; число порций в буфере := 0; работа с буфером := 1; parbegin

производитель: begin

снова 1: производство новой порции; P(работа с буфером); добавление порции к буферу; V(работа с буфером); V (число порций в буфере); goto снова 1 end; потребитель: begin

снова 2: P(число порций в буфере); P(работа с буфером); взятие порции из буфера; V(работа с буфером); обработка взятой порции; goto снова 2 end

parend

end

Читателю предоставляется убедиться самостоятельно в следующем:

а) порядок двух V-операций в производителе несуществен;

  б) порядок двух P-операций в потребителе существен.


Содержание раздела