Применение семафоров для решения задачи взаимного исключения

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

1. Вводятся специальные целочисленные общие переменные, называемые семафорами.

2. Добавляются к набору действия, из которых состоят процессы, два новых примитива: p-операция и v-операция.

(p – proberen(проверка); v – verhogen(увеличение))

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

s1 – семафор,

p(s1) или v(s1) – запись операций над семафором.

V-операция – операция с одним аргументом, который должен быть семафором. Ее назначение – увеличение аргумента на единицу. Это действие рассматривается как неделимая операция.

Имеется достаточно принципиальное различие между семафорными и обычными операциями сложения. Если двумя параллельно-развивающимися процессами выполнена семафорная операция v(s1) над общим семафором s1, получим увеличение семафора s1 на два, так как операция v неделимая. А выполнение операции сложения s1 с единицой параллельными процессами может привести к увеличению значения s1 на единицу.

П1 П2

S1 := S1+1 S1 := S1+1

П1 П2

v(S1) v(S1)

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

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

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

Begin integer свободно;

свободно := 1;

Parbegin

процесс 1: begin … end;

процесс 2: begin … end;

…

процесс N: begin … end;

Parend;

End;

процесс i:

Begin

Li: P(свободно);

Критический интервал i;

V(свободно);

Остаток цикла i;

Goto Li;

End;

Задача “производитель-потребитель”

Общие семафоры

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

ЧПБ – число порций в буфере.

РБ – работа с буфером

Begin integer ЧПБ;

ЧПБ := 0;

Parbegin

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

П1: производство новой порции;