8.3.3. Семафоры Семафор как теоретическая конструкция

В информатике понятие семафор (semaphore) был впервые введено голландским теоретиком Э.В. Дейкстрой (E.W. Dijkstra) для решения задач синхронизации процессов. Семафор sem может рассматриваться как целочисленная переменная, для которой определены следующие операции:

р(sem) или wait (sem)

if sem<>0 then

уменьшить sem на единицу

else

ждать, пока sem не станет ненулевым, затем вычесть единицу

v(sem) или signal(sem)

увеличить sem на единицу

if очередь ожидающих процессов не пуста then

продолжить выполнение первого процесса в очереди ожидания

Обратите внимание, что обозначения р и v происходят от голландских терминов для понятий ожидания (wait) и сигнализации (signal), причем последнее понятие не следует путать с обычными сигналами UNIX.

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

Формально удобство семафоров заключается в том, что утверждение

(начальное значение семафора

+ число операций v

- число завершившихся операций р) >= 0

всегда истинно. Это – инвариант семафора (semaphore invariant). Теоретикам нравятся такие инварианты, так как они делают возможным систематическое и строгое доказательство правильности программ.

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

p(sem);

какие-либо действия

v(sem);

Предположим далее, что начальное значение семафора sem равно единице. Из инварианта семафора можно увидеть, что:

(число завершенных операций р -

число завершенных операций v) <= начального значения семафора

или:

(число завершенных операций р -

число завершенных операций v) <= 1

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

Реализация семафоров в ОС UNIX основана на этой теоретической идее, хотя в действительности предлагаемые средства являются более общими (и, возможно, чрезмерно сложными). Вначале рассмотрим процедуры semget и semctl.

Системный вызов semget Описание

uses ipc;

Function semget(key:Tkey; nsems:longint; permflags:longint):longint;

Вызов semget аналогичен вызову msgget. Дополнительный параметр nsems задает требуемое число семафоров в наборе семафоров; это важный момент – семафорные операции в System V IPC приспособлены для работы с наборами семафоров, а не с отдельными объектами семафоров. На рис. 8.2 показан набор семафоров. Ниже увидим, что использование целого набора семафоров усложняет интерфейс процедур работы с семафорами.

	Индекс 0	Индекс 1	Индекс 2	Индекс 3
semid	semval = 2	semval = 4	semval = 1	semval = 3
		nsems=4

Рис.8.2. Набор семафоров

Значение, возвращаемое в результате успешного вызова semget, является идентификатором набора семафоров (semaphore set identifier), который ведет себя почти так же, как идентификатор очереди сообщений. Идентификатор набора семафоров обозначен на рис. 8.2 как semid. Следуя обычной практике, индекс семафора в наборе может принимать значения от 0 до nsems-1.

С каждым семафором в наборе связаны следующие значения:

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

sempid Идентификатор процесса, который последним работал с семафором

semcnt Число процессов, ожидающих увеличения значения семафора

semzcnt Число процессов, ожидающих обнуления значения семафора