Синхронизация процессов с помощью семафоров

Дейкстра для решения проблемы взаимного исключения предложил концепцию семафоров.

Семафор - это защищенная переменная, значение которой можно опрашивать и менять только при помощи специальных операций (семафорных примитивов) P и V и операции инициализации.

Двоичные (бинарные) семафоры могут принимать только значения 0 или 1 (true или false), то есть могут находиться в двух состояниях: закрыт и открыт. Считающие семафоры (семафоры со счетчиками) могут принимать целые значения. Считающий семафор открыт, если значение счетчика больше 0.

Операции P и V - это семафорные примитивы (неделимые операции), во время выполнения которых процессом к переменной-семафору нет доступа для других процессов. Если одновременно несколько процессов запрашивают выполнение операций P и/или V над одним и тем же семафором, то эти операции будут выполняться последовательно, в произвольном порядке.

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

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

В зависимости от ограничений, установленных для значения счетчика считающего семафора, изменяется смысл семафорной переменной и алгоритм выполнения семафорных примитивов.

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

Если счетчик может принимать и отрицательные целые значения, то отрицательное значение семафора означает длину очереди процессов, попытавшихся пройти через семафор (запросивших соответствующий ему ресурс).

Операции выборки значения семафорной переменной S, ее изменения и сохранения не могут быть прерваны. Во время выполнения последовательности этих операций в процедурах P и V, вызванных одним процессом, над каким-либо семафором он недоступен для других процессов. Операция hold(S) означает перевод процесса в состояние ожидания на семафоре S и выход из P. Это ожидание не должно быть “занятым” (то есть нельзя зациклить процедуру P на проверке состояния семафора, так как в этом случае ни один другой процесс не смог бы получить доступ к этой защищенной переменной даже для выполнения операции открытия этого семафора). Для устранения занятого ожидания с каждым семафором связывается список блокирования (список процессов, ожидающих открытия семафора). Процесс, который не может продолжиться после выполнения P(S), будет заблокирован с сохранением его состояния в соответствующем S списке блокирования. Операция release(S) - выполняет проверку списка блокирования, связанного с семафором S, если этот список не пуст, то активизируется некоторый процесс из этого списка, пропускается через семафор, а значение семафора изменяется при этом соответствующим образом (бинарный семафор снова закрывается, а для семафора со счетчиком возвращенная процессом, выполнившем операцию V(S), единица ресурса передается очередному процессу из списка).

Ниже приведено описание семафорных примитивов для бинарных и считающих семафоров. Алгоритмы выполнения семафорных операций можно представить так:

S	Бинарный семафор	Считающий семафор с неотрицательными значениями счетчика	Общий считающий семафор
P(S)	if S = 0 then Hold(S) else S:= 0	if S = 0 then Hold(S) else S:= S - 1	S:= S - 1; if S < 0 then Hold(S)
V(S)	if not Empty(S) then Release (S) else S:= 1;	if not Empty(S) then Release (S) else S:= S + 1;	S:= S + 1; if S<= 0 then Release (S)

Рассмотрите приведенные ниже варианты примитивов. Нет ли в их текстах ошибок? Все ли свойства примитивов выполняются?

S	Бинарный семафор	Считающий семафор с неотрицательными значениями счетчика	Общий считающий семафор
P(S)	if S = 0 then hold(S); S:= 0	if S = 0 then hold(S); S:= S - 1	S:= S - 1; if S < 0 then hold(S)
V(S)	S:= 1; release (S)	S:= S + 1; release (S)	S:= S + 1; release (S)

Использование семафоров значительно упрощает решение проблемы взаимного исключения. Для синхронизации процессов, рассматривавшихся выше, с помощью семафоров следует выполнить следующие изменения в соответствующих программах:

Процедура инициализации	Первый процесс	Второй процесс
procedure INIT; binary semaphore B ; begin B:= 1; {Открыт} start(P1); start(P2) end INIT .	process P1 ; binary semaphore B ; begin while true do begin BEFORE1 ; P(B); CS1 ; V(B); AFTER1 ; end end P1 .	process P2 ; binary semaphore B ; begin while true do begin BEFORE2 ; P(B); CS2 ; V(B); AFTER2 ; end end P2 .

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

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

Семафоры могут использоваться не только для решения проблемы взаимного исключения, но и как средство синхронизации выполнения процессов, определенные функции которых должны быть согласованы, упорядочены во времени. Например, существуют два процесса P₁ и P_2.. Первый процесс должен выполнить процедуру BEFORE до того как второй процесс сможет выполнить процедуру AFTER. Если второй процесс подойдет к выполнению процедуры AFTER раньше, чем первый процесс завершит выполнение процедуры BEFORE, он должен ждать ее завершения.

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

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

Процедура инициализации	Первый процесс	Второй процесс
procedure INIT; binary semaphore B ; begin B:= 0; {Закрыт} start(P1); start(P2) end INIT .	process P1 ; binary semaphore B ; begin ... BEFORE; V(B); {Разрешение для P2 } {выполнить AFTER} ... end P1 .	process P2 ; binary semaphore B ; begin ... P(B); {Ожидание от P1} {разрешения на выполнение} AFTER; ... end P2 .

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

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

Пусть процесс P₁ является “производителем”, который вырабатывает информацию и помещает новые записи в буфер. Параллельно с этим процессом в ВС существует процесс-“потребитель” информации P₂, считывающий информацию из буфера. Процесс-“писатель” не должен вносить информацию в переполненный буфер и затирать еще не прочитанные “читателем” записи, а процесс-“читатель” не может читать информацию из пустого буфера или повторять чтение уже прочитанных записей.

Пусть емкость буфера составляет N записей.

Для процесса P₁ ресурсом являются незаполненные записи в буфере, для их учета можно использовать считающий семафор E, а для процесса P₂ необходимым для работы ресурсом являются сформированные процессом P₁ записи, для учета их числа можно также использовать считающий семафор F. Кроме того, выполнение операций с буфером, который является разделяемым ресурсом, требует обычно взаимного исключения (последовательность операций над данными в буфере - критическая секция), для реализации которого можно использовать бинарный семафор.

Описание процедуры инициализации и программ, соответствующих процессам P₁ и P₂, приведено ниже.

Процедура инициализации	Процесс-производитель	Процесс-потребитель
procedure INIT; binary semaphore B ; integer semaphore E, F; begin B:= 1; {Буфер открыт} E:= N; {Все записи} {в буфере пусты} F:= 0; {В буфере нет} {ни одной записи} start(P1); start(P2) end INIT .	process P1 ; binary semaphore B ; integer semaphore E, F; begin while true do begin ... produce_next_record; P(E); P(B); write_record_to_buffer; V(B); V(F); ... end end P1 .	process P2 ; binary semaphore B ; integer semaphore E, F; begin while true do begin ... P(F); P(B); read_record_from_buffer; V(B); V(E); process_new_record; ... end end P2 .

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

Можно ли в приведенных процедурах поменять местами вызовы процедур P(F) и P(B) и P(E) и P(B)?

Рассмотрите варианты процедур для случаев, когда есть несколько процессов-писателей и несколько процессов-читателей, по одному процессу. Как можно сделать процедуры более эффективными?

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