4.2. Общий семафор как средство событийной синхронизации

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

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

Над семафором выполняются две операции, которые называются P- и V-операциями.

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

Дадим формальное объектно-ориентированное описание семафора.

Class TSemaphore {

int Count;

TList* List;

TSemaphore(int count);

~TSemaphore();

void P();

void V();

}

TSemaphore::TSemaphore(int count)

{

Count = count;

List = new TList();

}

TSemaphore::~TSemaphore()

{

delete List;

}

void TSemaphore::P()

{

Запрет_Прерываний;

Count--;

if (Count < 0) {

List->Insert(Текущий_процесс);

ПЕРЕНАЗНАЧИТЬ_ПРОЦЕССОР;

}

Разрешение_Прерываний;

}

void TSemaphore::V()

{

Запрет_Прерываний;

Count++;

if (Count <= 0) {

List->Remove(Первый_процесс);

Очередь_готовых->Insert(Текущий_процесс);

ПЕРЕДАТЬ_УПРАВЛЕНИЕ(Текущий_процесс,Первый_процесс);

}

Разрешение_Прерываний;

}

int main()

{

TSemaphore* Semaphore;

Semaphore = new PSemaphore(1);

...

delete Semaphore

}

Процесс:

Semaphore->P();

Критический участок;

Semaphore->V();

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

Функционирование семафора

Два класса задач могут быть решены с использованием семафора.

1. Безразлично, какой из процессов первым подойдет к критическому участку. Примеры мы рассматривали. Все равно, какой процесс первым инкрементирует переменную N в примере предыдущей лекции.

2. Небезразлично, какой из процессов первым подойдет к критическому участку.

Пример с обменом данными через ячейку памяти.

Процесс 1: Процесс 2:

... ...

Запись в ЯП; Чтение из ЯП;

... ...

Ясно, что операцию чтения можно проводить только после операции записи.

Рассмотрим сначала первую задачу.

S = new TSemaphore(1);

Процесс 1 Процесс 2 Процесс 3

... ... ...

S->P(); S->P(); S->P();

Кр. уч-к; Кр. уч-к; Кр. уч-к;

S->V(); S->V(); S->V();

... ... ...

delete (S;

Пусть П1 первым подошел к критическому участку. Count = 1.

Count--; Count = 0;

Входит в критический участок, т. к. условие блокировки Count < 0.

Пусть П2 вторым подошел к критическому участку. Count = 0.

Count--; Count = -1;

Встает в очередь семафора, т.к. выполняется условие блокировки.

Пусть П3 третьим подошел к критическому участку. Count = -1.

Count--; Count = -2;

Встает в очередь семафора за П2, т. к. выполняется условие блокировки.

Теперь П1 выходит из критического участка. Count = -2.

Count++; Count = -1;

Активизирует процесс П2, как первый в очереди, т. к. выполняется условие активизации

Count <= 0.

Процесс П2 входит в критический участок.

Теперь П2 выходит из критического участка. Count = -1.

Count++; Count = 0;

Активизирует процесс П3, как первый в очереди, т. к. выполняется условие активизации

Count <= 0.

Процесс П3 входит в критический участок.

Теперь П3 выходит из критического участка. Count = 0.

Count++; Count = 1;

Активизировать некого и не выполняется условие активизации Count <= 0.

Семафор приходит в исходное состояние.

Рассмотрим теперь вторую задачу.

Рассматривая вторую задачу, мы подбираемся к изучению методов обмена сообщениями в ядре.

Общая схема взаимодействия двух процессов при обмене данными выглядит следующим образом.

Процесс 1 Процесс 2

... ...

Записать в ЯП; Если не записано, то ЖДАТЬ;

Сообщить, что записал; Прочитать из ЯП;

... ...

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

Инициализируем семафор S в 0, т.е. S->Count = 0.

П1 П2

... ...

Записать в ЯП; S->P();

S->V(); Прочитать из ЯП;

... ...

Пусть процесс П1 записал в ЯП данные и первым подошел к выполнению операции S->V().

Count++; Count = 1;

Т.к. условие активизации процессов в операции S->V() - Count <= 0, то активизировать некого.

Пусть теперь к выполнению операции S->P() подошел процесс П2.

Count--; Count = 0;

Т.к. условие блокировки в операции S->P() - Сount < 0, то процесс П2 не блокируется и переходит к чтению ЯП.

Таким образом, чтение произошло после записи.

Пусть теперь первым подошел к выполнению операции S->P() процесс П2.

Count--; Count = -1;

Выполняется условие блокировки и процесс П2 встает в очередь, не прочитав ячейку памяти.

Теперь процесс П1 пишет в ЯП и подходит к выполнению операции S->V().

Count++; Count = 0;

Т.к. условие активизации Count <= 0 выполняется, то происходит активизация процесса П2 и чтение ЯП.

Таким образом, чтение опять произошло после записи.

Для решения данной задачи в современных ОС используются семафоры событий.

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

пока процесс П2 не подошел к операции чтения, процесс П1 может выполнить несколько операций записи, возвращаясь к ней в цикле. Т. е. может произойти потеря данных.

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

Следующая схема позволяет это сделать.

П1 П2

while (1) { while (1) {

... ...

Запись в ЯП; S->P();

S->V(); Чтение из ЯП;

A->P(); A->V();

... ...

} }

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

Активизация П1 выполняется процессом П2 после чтения ЯП. Первый семафор используется как подтверждение записи, а второй - как подтверждение чтения.

Последний пример фактически является примером буфера на одну ячейку.

Замечания

1. Наличие очереди в семафоре - это, вообще говоря, вопрос реализации. Вместо очереди может быть организовано «активное ожидание».

2. При описании структуры семафора мы немного отступили от типовой структуры примитива ядра.

3. Свойство семафора: для первой задачи имеет место свойство: Если Count < 0, то |Сount| равен числу процессов, стоящих в очереди семафора.