9.2. Абстрактные семафоры

Общий подход к монополизации ресурсов с помощью специальных системных операций предложил голландский математик Е. Дейкстра (E. Dijkstra). Этот подход состоит в построении и использовании семафоров. Семафор – это защищенная от прямого доступа переменная, значения которой можно опрашивать и изменять только с помощью специальных операций P и V; кроме того, в самом начале к семафору применяется операция инициализации.

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

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

Операция P(S) выполняет действия: если S равно 1, то занести в S значение 0, иначе БЛОКИРОВАТЬ нить по семафору S, и если очередь готовых задач не пуста, то УСТАНОВИТЬ на процессор задачу из этой очереди.

Операция V(S) выполняет действия: если список задач, заблокированных по семафору S, не пуст, то ДЕБЛОКИРОВАТЬ задачу из этой очереди (т.е. перевести ее в очередь готовых задач), иначе занести в S значение 1.

Инициализация семафора – это установка значения семафора в 0 или в 1.

Для двоичных семафоров значение семафора 1 обозначает, что ресурс, защищаемый семафором, свободен, а значение семафора 0 – что ресурс занят. Операции P(S) и V(S) предназначены для использования в качестве конструкций пролог и эпилог критических интервалов. В начале критического интервала ставится операция P(S), а в конце критического интервала - операция V(S), иначе говоря операции P и V – это ограничители критического интервала, его "операторные скобки". Семафоры – не просто логические ключи, проверка значений которых позволяет продолжить или нет текущую задачу, они путем операций P и V глубоко связаны с внутренними действиями ОС над задачами. Для понимания существа операций P и V в них следует видеть две стороны: монополизацию ресурсов для избежания состязаний и управление внутренними очередями состояния задач.

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

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

Reader Writer

P(S)		P(W)
N  N + 1		Запись
если N=1, то P(W)		V(W)
V(S)		END
Чтение
P(S)
N  N - 1
если N=0, то V(W)
V(S)
END

Рис. 9.1. Схемы программ "читателя" и "писателя"

Перед началом работы программ для всех читателей и писателей должна быть выполнена инициализация

S  0 , N  0, W  1.

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

P(S) : если S > 0, то S  S - 1, иначе WAIT(S);

V(S) : если список задач, заблокированных по семафору S, не пуст, то ДЕБЛОКИРОВАТЬ задачу из этой очереди (т.е. перевести ее в очередь готовых задач), иначе S  S +1,

где системная функция WAIT(S) определяет ожидание освобождения семафора S, т.е. БЛОКИРОВАТЬ задачу по семафору S, и если очередь готовых задач не пуста, то УСТАНОВИТЬ на процессор задачу из этой очереди, иначе ждать освобождение семафора S.

Эта форма семафоров обусловила название операций: P – proberen (проверить), V – verholen (увеличить) на голландском языке. Считающий семафор показывает число единиц свободного ресурса.

Считающий семафор может быть обобщен путем распространения его значений на отрицательные числа следующим определением операций P и V:

P(S) : S  S - 1; если S < 0, то WAIT(S);

V(S) : S  S +1; если S  0, то ДЕБЛОКИРОВАТЬ задачу из этой очереди (т.е. перевести ее в очередь готовых задач).

Обобщенный считающий семафор своим значением равен разности между числом единиц наличного ресурса и числом запросов на них. При S  0 значение такого семафора показывает число свободных единиц ресурса, при S < 0 – число задач, заблокированных по семафору S.

Использование считающих семафоров демонстрирует задача ПРОИЗВОДИТЕЛЬ – ПОТРЕБИТЕЛЬ, к виду которой относится, в частности, управление буферным пулом. Решение этой задачи, рассматриваемое для процессов P_пр и P_потр, использует два семафора S1 и S2, причем перед запуском процессов P_пр и P_потр должна происходить инициализация:

S1  число_свободных_мест,

S2  0 (нуль элементов для использования).

Неотрицательные значения семафора S1 дают число свободных мест на складе (в буфере), а неотрицательные значения семафора S2 – число элементов, готовых для использования на складе (в буфере).

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

Процесс – производитель P_пр

Процесс – потребитель P_потр

Рис. 9.2. Схема программ процессов производителя и потребителя

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

Таблица 9.1

События во взаимодействии процессов P_пр и P_потр

Событие	Pпр	Pпотр	S1	S2
0	-	-	2	0
1		P(S2) блокир.	2	-1
2	P(S1)		1	-1
3	V(S2) деблок.		1	0
4	P(S1)		0	0
5		V(S1)	1	0
6	V(S2)		1	1
7	P(S1)		0	1
8	V(S2)		0	2
9	P(S1) блокир.		-1	2
10		P(S2)	-1	1
11		V(S1) деблок.	0	1

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

Семафор – вовсе не идеальное средство для организации взаимодействия параллельных процессов (хотя лучшего не известно). Если при использовании двоичных семафоров S1, S2 в программах встретятся последовательности

Процесс A Процесс B

P(S1)		P(S2)
P(S2)		P(S1)
.		.
.		.
.		.
V(S2)		V(S1)
V(S1)		V(S2)

то при следующей последовательности выполнения шагов этих процессов :

P(S1)-процесса A,

затем переключение на выполнение процесса B,

P(S2)-процесса B

возникает взаимное блокирование процессов. При этом процесс A ждет освобождения семафора S2 процессом B, а процесс B – освобождения семафора S1 процессом A и это ожидание может продолжаться сколько угодно. Такая взаимная блокировка процессов называется тупиком, клинчем или дедлоком (от английского слова deadlock).