Семафор как теоретическая конструкция
В информатике понятие семафор (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.
