Семафоры: синхронизация процессов и потоков

Когда несколько процессов или потоков работают с общими данными одновременно, возникает гонка: результат зависит от того, кто успел раньше. Семафор - это классический примитив синхронизации, предложенный Дейкстрой в 1965 году, который наводит порядок в таком хаосе. Он хранит целочисленный счётчик и две атомарные операции над ним, и через этот счётчик процессы договариваются, кому сейчас можно входить в критическую секцию, а кому - ждать. Ниже разберём, как устроены операции P и V, чем счётный семафор отличается от бинарного, как на семафорах строится классическая задача producer-consumer и где обычно ломается синхронизация.

Что такое семафор

Семафор $S$ - это защищённая переменная-счётчик с двумя атомарными операциями. Значение счётчика показывает, сколько ещё процессов могут получить доступ к ресурсу прямо сейчас. Атомарность здесь принципиальна: проверка значения и его изменение происходят как единое неделимое действие, которое нельзя прервать в середине, иначе вся защита рассыпется.

Дейкстра назвал операции голландскими словами: $P$ (от proberen - «пробовать», она же wait или down) и $V$ (от verhogen - «увеличивать», она же signal или up). В современных API они называются по-разному: sem_wait/sem_post в POSIX, WaitForSingleObject/ReleaseSemaphore в Windows, acquire/release в Java и Python, - но семантика везде одна.

Рассчитать для своей задачи

Операции P и V

Формально две операции определяются так. Операция $P(S)$ уменьшает счётчик; если он стал отрицательным, процесс блокируется и встаёт в очередь:

$$P(S):\quad S \leftarrow S - 1;\ \text{если}\ S < 0,\ \text{то заблокировать процесс}$$

Операция $V(S)$ увеличивает счётчик; если есть ожидающие, один из них пробуждается:

$$V(S):\quad S \leftarrow S + 1;\ \text{если}\ S \le 0,\ \text{то разбудить один процесс}$$

При такой записи модуль отрицательного значения $|S|$ равен числу заблокированных процессов в очереди. Существует и эквивалентная запись, где счётчик не уходит ниже нуля, а $P$ перед уменьшением ждёт, пока $S > 0$. Обе формулировки описывают одно поведение; важно, что между проверкой и изменением счётчика никто не может вклиниться.

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

Счётный и бинарный семафор

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

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

Бинарный семафор ограничен значениями $0$ и $1$ и работает как замок: либо ресурс свободен, либо занят. Бинарный семафор с начальным значением $1$ - это, по сути, мьютекс для защиты критической секции. Тонкое отличие от мьютекса в том, что мьютекс имеет владельца - освободить его может только захвативший поток, тогда как семафор может «открыть» любой процесс. Для двух потоков взаимное исключение можно построить и без семафоров - программным алгоритмом Петерсона, но семафор масштабируется на любое число процессов.

Рассчитать для своей задачи

Взаимное исключение на семафоре

Самое частое применение - защита критической секции, то есть участка кода, который нельзя выполнять одновременно нескольким процессам. Берём бинарный семафор $mutex$ с начальным значением $1$ и оборачиваем секцию:

$$\begin{aligned} &P(mutex) \\ &\quad \text{критическая секция} \\ &V(mutex) \end{aligned}$$

Первый процесс делает $P$, счётчик становится $0$, секция занята. Любой второй процесс на $P$ блокируется, пока первый не сделает $V$ и не вернёт счётчик к $1$. Так гарантируется взаимное исключение: внутри секции в каждый момент времени ровно один процесс.

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

Задача producer-consumer

Классическая задача, на которой проверяют любой механизм синхронизации, - «производитель-потребитель» с ограниченным буфером. Один процесс кладёт элементы в буфер размера $N$, другой их забирает. Нужно, чтобы производитель не писал в полный буфер, а потребитель не читал из пустого.

Решение использует три семафора:

$$\begin{aligned} empty &= N \quad (\text{число свободных ячеек}) \\ full &= 0 \quad (\text{число занятых ячеек}) \\ mutex &= 1 \quad (\text{защита буфера}) \end{aligned}$$

Производитель перед записью делает $P(empty)$ - ждёт свободную ячейку, затем $P(mutex)$, кладёт элемент, $V(mutex)$ и $V(full)$ - сигналит, что появился элемент. Потребитель симметрично: $P(full)$, $P(mutex)$, забирает, $V(mutex)$, $V(empty)$.

Семафоры $empty$ и $full$ синхронизируют скорости двух процессов, а $mutex$ защищает сам буфер от одновременного доступа. Калькулятор выше показывает, как меняется заполнение буфера при разных скоростях производителя и потребителя.

Семафоры между процессами

Внутри одной программы семафор - это переменная в общей памяти потоков. Между разными процессами память не разделяется, поэтому используют именованные семафоры ядра: sem_open в POSIX создаёт семафор с именем в файловой системе, к которому подключаются независимые процессы. Исторически в System V для этого служил механизм semget/semop, работающий с массивами семафоров и набором операций за один вызов.

Семафор ядра переживает завершение создавшего его процесса и снимается явно (sem_unlink) - если про это забыть, в системе накапливаются «осиротевшие» семафоры, которые видны через ipcs.

Цена межпроцессной синхронизации выше внутрипоточной: каждая операция $P$/$V$ на именованном семафоре - это системный вызов с переключением в режим ядра, тогда как в однопроцессной программе быстрый путь семафора часто разруливается в пространстве пользователя без обращения к ядру. Поэтому для горячих участков кода внутри одной программы предпочитают облегчённые примитивы, а тяжёлые семафоры ядра берут там, где нужна именно межпроцессная координация.

Семафоры и deadlock

Сам по себе семафор не спасает от взаимной блокировки - наоборот, неаккуратное использование её создаёт. Классический сценарий: два процесса захватывают два семафора $A$ и $B$ в противоположном порядке. Первый делает $P(A)$, второй - $P(B)$, после чего первый ждёт $B$, а второй ждёт $A$, и оба зависают навсегда. Возникают все четыре условия Коффмана: взаимное исключение, удержание с ожиданием, отсутствие вытеснения и круговое ожидание.

Надёжная профилактика - единый глобальный порядок захвата: если все процессы всегда берут семафоры в одном и том же порядке (сначала $A$, потом $B$), круговое ожидание становится невозможным. Отсюда и правило в задаче producer-consumer: сначала $P$ на счётный семафор условия, и только потом $P(mutex)$.

Частые ошибки

• Перепутанный порядок P-операций. Захват $mutex$ до проверки условия ($full$/$empty$) приводит к взаимной блокировке: процесс держит замок и спит на счётном семафоре, не давая никому войти.
• Пропущенный V. Выход из критической секции по исключению или return без $V(mutex)$ оставляет семафор закрытым - это самый частый источник зависаний.
• Лишний V. Сигнал семафору, для которого не было парного $P$, искусственно завышает счётчик и пускает в секцию больше процессов, чем разрешено, ломая взаимное исключение.
• Неатомарная самодельная реализация. Попытка собрать семафор из обычной переменной и if без атомарных инструкций или отключения прерываний создаёт ту же гонку, от которой семафор должен защищать.
• Busy-waiting вместо блокировки. Опрос счётчика в цикле (спинлок) на однопроцессорной системе бессмысленно жжёт CPU; настоящий семафор снимает процесс с выполнения и будит по $V$.

FAQ

Чем семафор отличается от мьютекса? Мьютекс - это бинарный замок с владельцем: освободить его может только захвативший поток, и он предназначен строго для взаимного исключения. Семафор - счётчик без понятия владельца: его может увеличить любой процесс, и он годится не только для замка, но и для подсчёта ресурсов и сигнализации между процессами.

Может ли семафор вызвать deadlock? Да. Если два процесса захватывают два семафора в разном порядке (один $A$ потом $B$, другой $B$ потом $A$), каждый ждёт ресурс, удерживаемый другим, - возникает классический взаимоблок. Лечится единым глобальным порядком захвата семафоров.

Что значит начальное значение семафора? Это число процессов, которые могут пройти через $P$ без блокировки. Для взаимного исключения берут $1$, для пула из $N$ одинаковых ресурсов - $N$, а для сигнализации «событие ещё не произошло» - $0$.

Коротко

Семафор - это атомарный счётчик с операциями $P$ (ждать) и $V$ (сигналить), через который процессы договариваются о доступе к общему ресурсу. Бинарный семафор реализует взаимное исключение в критической секции, счётный - управляет пулом из $N$ ресурсов, а связка из трёх семафоров решает задачу producer-consumer. Главное - соблюдать порядок P-операций, всегда выполнять парный $V$ и помнить про атомарность: на этих трёх правилах держится вся синхронизация.