Реализация общего семафора с помощью двоичных семафоров

Общий семафор может быть представлен тройкой из двух двоичных семафоров и целой переменной:

binary-semaphore S1 = 1;

binary-semaphore S2 = 0;

int C = начальное значение общего семафора S;

Операция wait:

wait (S1);

C--;

if (C < 0) {

signal (S1);

wait (S2);

}

signal (S1);

Операция signal:

wait (S1);

C++;

if (C >= 0) {

signal (S2);

};

signal (S1);

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

Решение классических задач синхронизации с помощью семафоров

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

· ограниченный буфер (bounded buffer problem)

· читатели – писатели (readers – writers problem)

· - обедающие философы (dining philosophers problem).

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

Будем использовать три общих семафора:

semaphore full = n;

semaphore empty = 0;

semaphore mutex = 1;

Семафор full сигнализирует о переполнении буфера, empty – об исчерпании буфера, mutex – используется для взаимного исключения действий над буфером.

Код процесса-производителя имеет вид:

do {

...

сгенерировать элемент в nextp

...

wait (full);

wait (mutex);

...

добавить nextp к буферу

...

signal (mutex);

signal (empty);

} while (1);

Код процесса-потребителя:

do {

wait (empty);

wait (mutex);

...

взять и удалить элемент из буфера в nextc

...

signal (mutex);

signal (full);

...

использовать элемент из nextc

...

} while (1);

Поясним использование семафоров. Семафор mutex используется "симметрично"; над ним выполняется пара операций: wait … signal – семафорные скобки. Его роль – чисто взаимное исключение критических секций. Семафор empty сигнализирует об исчерпании буфера. В начале он закрыт, так как элементов в буфере нет. Поэтому при закрытом семафоре empty потребитель вынужден ждать. Открывает семафор empty производитель, после того, как он записывает в буфер очередной элемент. Семафор full сигнализирует о переполнении буфера. В начале он равен n – максимальному числу элементов в буфере. Производитель перед записью элемента в буфер выполняет операцию wait (full), гарантируя, что, если буфер переполнен, записи нового элемента в буфер не будет. Открывает семафор full потребитель, после того, как он освободил очередной элемент буфера.

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

Решение с помощью семафоров задачи "читатели – писатели"

Суть задачи читатели-писатели в следующем: имеется общий ресурс и две группы процессов: читатели (которые могут только читать ресурс, но не изменяют его) и писатели (которые изменяют ресурс). В каждый момент работать с ресурсом может сразу несколько читателей (когда ресурс не изменяется писателями), но не более одного писателя. Необходимо синхронизировать их действия над ресурсом и обеспечить взаимное исключение соответствующих критических секций.

Будем использовать два семафора и целую переменную:

semaphore mutex = 1;

semaphore wrt = 1;

int readcount = 0;

Семафор mutex используется читателями для взаимного исключения операций над переменной readcount (счетчиком читателей). Семафор wrt используется для взаимного исключения писателей.

Реализация процесса-писателя особых комментариев не требует:

wait (wrt);

...

изменение ресурса

...

signal (wrt);

Реализация процесса-читателя несколько более сложна:

wait (mutex);

readcount++;

if (readcount == 1) {

wait (wrt);

}

signal (mutex);

...

чтение ресурса

...

wait (mutex);

readcount--;

if (readcount == 0) {

signal (wrt);

}

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

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

Суть задачи обедающие философы в следующем. Имеется круглый стол, за которым сидят пять философов (впрочем, их число принципиального значения не имеет – для другого числа философов решение будет аналогичным). Перед каждым из них лежит тарелка с едой, слева и справа от каждого – две китайские палочки. Философ может находиться в трех состояниях: проголодаться, думать и обедать. На голодный желудок философ думать не может. Но начать обедать он может, только если обе палочки слева и справа от него свободны. Требуется синхронизировать действия философов. В данном случае общим ресурсом являются палочки. Иллюстрацией условий задачи является рис. 12.1.

Рис. 12.1. Задача "обедающие философы".

Данная задача является одной из излюбленных задач профессора Ч. Хоара, который использовал ее как пример в своих работах по параллельному программированию.

При решении задачи будем использовать массив семафоров chopstick, описывающий текущее состояние палочек: chopstick[i] закрыт, если палочка занята, открыт – если свободна:

semaphore chopstick [5] = { 1, 1, 1, 1, 1};

Алгоритм реализации действий философа i имеет вид:

do {

wait (chopstick [i]); /* взять левую палочку */

wait (chopstick [(I + 1) % 5]); /* взять правую палочку */

...

обедать

...

signal (chopstick [i]); /* освободить левую палочку */

signal (chopstick [(i+1) % 5]); /* освободить правую палочку */

...

думать

...

while (1);

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

Дата добавления: 2014-01-20