Решение проблемы производителя и потребителя с помощью семафоров

Как показано в листинге 2.4, проблему потерянных сигналов запуска можно ре­шить с помощью семафоров. Очень важно, чтобы они были реализованы недели­мым образом. Стандартным способом является реализация операций down и up в виде системных запросов, с запретом операционной системой всех прерываний на период проверки семафора, изменения его значения и возможного перевода процесса в состояние ожидания. Поскольку для выполнения всех этих действий требуется всего лишь несколько команд процессора, запрет прерываний не приносит никакого вреда. Если используются несколько процессоров, каждый сема­фор необходимо защитить переменной блокировки посредством команды tsl, чтобы гарантировать одновременное обращение к семафору только одного про­цессора. Необходимо понимать, что использование команды tsl принципиально отличается от активного ожидания, при котором производитель или потреби­тель ждут наполнения или опустошения буфера. Операция с семафором займет несколько микросекунд, тогда как активное ожидание может затянуться на су­щественно больший промежуток времени.

В представленном решении используются три семафора: один для подсчета заполненных сегментов буфера (full), другой для подсчета пустых сегментов (empty), а третий предназначен для исключения одновременного доступа произ­водителя и потребителя (mutex) к буферу. Значение счетчика full исходно равно нулю, счетчик empty равен числу сегментов в буфере, a mutex равен 1. Семафоры, исходное значение которых установлено в 1, предназначенные для исключения одновременного нахождения в критической области двух процессов, называются двоичными семафорами. Взаимное исключение обеспечивается, если каждый процесс выполняет операцию down перед входом в критическую область и up — после выхода из нее.

Теперь, когда у нас есть примитивы межпроцессного взаимодействия, вер­немся к последовательности обработки прерываний, показанной в конце разде­ла 2.1.2. В системах, использующих семафоры, естественным способом скрыть прерывание будет связать с каждым устройством ввода/вывода семафор, изна­чально равный нулю. Сразу после включения устройства ввода/вывода управ­ляющий процесс выполняет операцию down на соответствующем семафоре, тем самым входя в состояние блокировки. В случае прерывания обработчик преры­вания выполняет up на соответствующем семафоре, переводя процесс в состоя­ние готовности. В такой модели пятый шаг в алгоритме из раздела 2.1.2 заключа­ется в выполнении up на семафоре устройства, чтобы следующим шагом планировщик смог запустить программу, управляющую устройством. Разумеет­ся, если в этот момент несколько процессов находятся в состоянии готовности, планировщик вправе выбрать другой, более значимый процесс. Мы рассмотрим некоторые алгоритмы планирования позже в этой главе.

В примере, представленном в листинге 2.4, семафоры использовались двояко. Это различие достаточно ощутимо, чтобы сказать о нем особо. Семафор mutex предназначен для реализации взаимного исключения, то есть для исключения одновременного обращения к буферу и к связанным переменным двух процес­сов. Мы уже рассмотрели взаимное исключение и методы его реализации в пре­дыдущем разделе.

Остальные семафоры введены с целью синхронизации. Семафоры full и empty необходимы, чтобы гарантировать, что определенные последовательности собы­тий происходят или не происходят. В нашем случае они дают гарантию, что про­изводитель прекращает работу, когда буфер полон, а потребитель прекращает ее, когда буфер пуст.

Мониторы

Межпроцессное взаимодействие с применением семафоров выглядит довольно просто, не правда ли? Эта простота кажущаяся. Взгляните внимательнее на по­рядок выполнения процедур down перед помещением или удалением элементов из буфера в листинге 2.4. Представьте себе, что две процедуры down в программе производителя поменялись местами, так что значение mutex было уменьшено раньше, чем empty. Если буфер был заполнен, производитель блокируется, сбро­сив mutex в 0. Соответственно, в следующий раз, когда потребитель обратится к буферу, он выполнит down с переменной mutex, равной 0, и тоже заблокируется. Оба процесса заблокированы навсегда. Эта неприятная ситуация называется взаимоблокировкой, и мы вернемся к ней в главе 3.

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

Чтобы упростить написание программ, в 1974 году Хоар (Ноаге) [43] и Бринч Хансен (Brinch Hansen) предложили примитив синхронизации более высокого уровня, называемый монитором. Их предложения несколько отличались друг от друга, как мы увидим дальше. Монитор — набор процедур, переменных и других структур данных, объединенных в особый модуль или пакет. Процессы могут вызывать процедуры монитора, но у процедур, объявленных вне монитора, нет прямого доступа к внутренним структурам данных монитора. В листинге 2.5 представлен монитор, написанный на воображаемом языке, некоем «местечко­вом диалекте» — «пиджин» Pascal.

Листинг 2.5. Монитор

monitor example

integer i:

condition с:

procedure producerO;

...

end:

procedure consumerO;

end;

end monitor;

Реализации взаимных исключений способствует важное свойство монитора: при обращении к монитору в любой момент времени активным может быть толь­ко один процесс. Мониторы являются структурным компонентом языка про­граммирования, поэтому компилятор знает, что обрабатывать вызовы процедур монитора следует иначе, чем вызовы остальных процедур. Обычно при вызове процедуры монитора первые несколько команд процедуры проверяют, нет ли в мониторе активного процесса. Если таковой есть, вызывающему процессу при­дется подождать, в противном случае запрос удовлетворяется.

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

Хотя мониторы предоставляют простой способ реализации взаимного исклю­чения, этого недостаточно. Необходим также способ блокировки процессов, ко­торые не могут продолжать свою деятельность. В случае проблемы производителя и потребителя достаточно просто поместить все проверки буфера на не-пустоту и пустоту в процедуры монитора, но как процесс заблокируется, обнаружив пол­ный буфер?

Решение заключается в переменных состояния и двух операциях, wait и signal. Когда процедура монитора обнаруживает, что она не в состоянии продолжать работу (например, производитель выясняет, что буфер заполнен), она выполняет операцию wait на какой-либо переменной состояния, скажем, full. Это приводит к блокировке вызывающего процесса и позволяет другому процессу войти в мо­нитор.

Другой процесс, в нашем примере потребитель, может активизировать ожи­дающего напарника, например, выполнив операцию signal на той переменной со­стояния, на которой он был заблокирован. Чтобы в мониторе не оказалось двух активных процессов одновременно, нам необходимо правило, определяющее по­следствия операции signal. Xoap предложил запуск «разбуженного» процесса и остановку второго. Бринч Хансен придумал другое решение: процесс, выполнив­ший signal, должен немедленно покинуть монитор. Иными словами, операция signal выполняется только в самом конце процедуры монитора. Мы будем ис­пользовать это решение, поскольку оно в принципе проще и к тому же легче в реализации. Если операция signal выполнена на переменной, с которой связаны несколько заблокированных процессов, планировщик выбирает и «оживляет» только один из них.

Кроме этого, существует третье решение, не основывающееся на предположе­ниях Хоара и Хансена: позволить процессу, выполнившему signal, продолжать работу и запустить ждущий процесс только после того, как первый процесс по­кинет монитор.

Переменные состояния не являются счетчиками. В отличие от семафоров они не аккумулируют сигналы, чтобы впоследствии воспользоваться ими. Это озна­чает, что в случае выполнения операции signal на переменной состояния, с кото­рой не связано ни одного блокированного процесса, сигнал будет утерян. Проще говоря, операция wait должна выполняться прежде, чем signal. Последнее прави­ло существенно упрощает реализацию. На практике оно не создает проблем, по­скольку отслеживать состояния процессов при необходимости не очень трудно. Процесс, который собирается выполнить signal, может оценить необходимость этого действия по значениям переменных.

В листинге 2.6 представлена схема решения проблемы производителя и по­требителя с применением мониторов, написанная на «пиджин» Pascal. В данной ситуации этот суррогат языка удобен своей простотой, а также тем, что он позво­ляет в точности следовать моделям Хоара и Хансена. В каждый момент времени активна только одна процедура монитора. Буфер состоит из N сегментов.

Листинг 2.6. Схема решения проблемы производителя и потребителя с применением мониторов

monitor Producer-Consumer

condition full. empty:

integer count;

procedure insert(item: integer);

begin

if count = N then wait(full):

insert_item(item):

count;= count+1;

if count = 1 then signal(empty)

end;

function remove: integer;

begin

if count = 0 then wait(empty);

remove = remove_item;

count:= count-1:

if count = N-l then signal(full)

end;

count:= 0;

end monitor:

procedure producer:

begin

while true do

begin

item = produce_item;

ProducerConsumer.i nsert(i tern)

end

end:

procedure consumer;

begin

while true do

begin

item = ProducerConsumer.remove;

consume_item(item)

end

end:

Можно подумать, что операции wait и signal похожи на sleep и wakeup, кото­рые приводили к неустранимым состояниям конкуренции. Они действительно похожи, но с одним существенным отличием: неудачи применения операций sleep и wakeup были связаны с тем, что один процесс пытался уйти в состояние ожидания, в то время как другой процесс предпринимал попытки активизиро­вать его. С мониторами такого произойти не может. Автоматическое взаимное исключение, реализуемое процедурами монитора, гарантирует: если производи­тель, находящийся в мониторе, обнаружит полный буфер и решит выполнить операцию wait, можно не опасаться, что планировщик передаст управление потребителю раньше, чем операция wait будет завершена. Потребитель даже не сумеет попасть в монитор, пока операция wait не будет выполнена и производи­тель не прекратит работу.

Благодаря автоматизации взаимного исключения применение мониторов сде­лало параллельное программирование значительно менее подверженным ошиб­кам, в отличие от применения семафоров. Но и у мониторов тоже есть свои недостатки. Недаром два примера мониторов, которые мы рассмотрели, были на­писаны на «пиджин» Pascal, а не на С, как все остальные примеры этой книги. Как мы уже говорили, мониторы являются структурным компонентом языка программирования, и компилятор должен их распознавать и организовывать взаимное исключение. В Pascal, С и многих других языках нет мониторов, поэто­му странно было бы ожидать от их компиляторов выполнения правил взаимного исключения. И в самом деле, как отличить компилятор процедуры монитора от остальных?

Другая проблема, связанная с мониторами и семафорами, состоит в том, что они были разработаны для решения задачи взаимного исключения в системе с одним или несколькими процессорами, имеющими доступ к общей памяти. По­мещение семафоров в разделенную память с защитой в виде команд TSL может исключить состояния состязания. Эти примитивы будут неприменимы в распре­деленной системе, состоящей из нескольких процессоров с собственной памятью у каждого, связанных локальной сетью. Вывод из всего вышесказанного следую­щий: семафоры являются примитивами слишком низкого уровня, а мониторы применимы только в некоторых языках программирования. Примитивы не под­ходят и для реализации обмена информацией между компьютерами — нужно что-то другое.

Передача сообщений

В роли чего-то другого выступает передача сообщений. Межпроцессное взаимо­действие такого рода строится на двух примитивах: send и receive, которые ско­рее являются системными вызовами, нежели структурными компонентами язы­ка (что отличает их от мониторов и делает похожим на семафоры). Поэтому их легко можно инкапсулировать в библиотечные процедуры, например:

send(destination. &message):

receive(source. &message):

Первый запрос посылает сообщение заданному адресату, а второй получает сообщение от указанного источника (или от любого источника, если это не име­ет значения). Если сообщения нет, второй запрос блокируется до поступления сообщения либо немедленно возвращает код ошибки.