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

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

¶История

Концепция семафоров была предложена Эдсгером Дейкстрой в 1965 году в работе «Cooperating Sequential Processes» (в русском переводе — «Взаимодействующие последовательные процессы»). Дейкстра ввёл термины P (от нидерл. proberen — пробовать) и V (от нидерл. verhogen — увеличивать) для обозначения операций. Изначально семафоры разрабатывались для операционной системы THE (Technische Hogeschool Eindhoven), создававшейся под руководством Дейкстры. Счётный семафор стал естественным расширением двоичного, позволившим эффективно решать задачи, требующие учёта количества доступных ресурсов (например, пулы соединений с базой данных, буферы ограниченного размера).

¶Принцип работы

Счётный семафор представляет собой целочисленную переменную S, которая инициализируется неотрицательным значением, равным количеству доступных ресурсов. Две основные операции определены следующим образом:

• P(S) (или wait, acquire, down): если S > 0, то значение S уменьшается на 1, и поток (или процесс) продолжает выполнение. Если S == 0, то поток блокируется и помещается в очередь ожидания, пока другой поток не выполнит операцию V.
• V(S) (или signal, release, up): значение S увеличивается на 1. Если в очереди ожидания есть заблокированные потоки, один из них (обычно первый в очереди) разблокируется и может продолжить выполнение.

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

¶Классификация

¶По значению

• Двоичный семафор (или мьютекс) — принимает только значения 0 и 1. Используется для взаимного исключения (mutual exclusion) — когда только один поток может одновременно владеть ресурсом.
• Счётный семафор — может принимать любое неотрицательное целое значение. Используется для управления доступом к конечному числу идентичных ресурсов (например, 5 принтеров, 10 соединений с сервером).

¶По типу очереди

• Справедливый семафор — гарантирует, что потоки разблокируются в порядке постановки в очередь (FIFO). Предотвращает «голодание» (starvation) — ситуацию, когда один поток никогда не получает доступ к ресурсу.
• Несправедливый семафор — может разблокировать любой ожидающий поток, не обязательно первый. Обеспечивает более высокую производительность за счёт меньших накладных расходов на поддержание порядка, но может приводить к недетерминированному поведению.

¶Реализация

¶Аппаратная поддержка

На современных процессорах атомарность операций P и V обеспечивается с помощью специальных инструкций, таких как test-and-set, compare-and-swap (CAS) или load-link/store-conditional (LL/SC). Эти инструкции позволяют выполнить проверку и изменение значения семафора за одну неделимую операцию.

¶Программная реализация

В операционных системах счётные семафоры реализуются на уровне ядра. Например, в Linux семафоры предоставляются системным вызовом semop (часть System V IPC) или через POSIX-семафоры (функции sem_init, sem_wait, sem_post). В пользовательском пространстве семафоры могут быть реализованы с помощью блокировок (например, pthread_mutex_t) и условных переменных (pthread_cond_t), но это менее эффективно.

¶Пример на C (POSIX)

```c

¶include <semaphore.h>

¶include <pthread.h>

¶include <stdio.h>

sem_t sem;

void worker(void arg) { sem_wait(&sem); // P(S) printf("Поток %ld получил доступ к ресурсу\n", (long)arg); // ... работа с ресурсом ... sem_post(&sem); // V(S) return NULL; }

int main() { sem_init(&sem, 0, 3); // 3 доступных ресурса pthread_t threads[10]; for (long i = 0; i < 10; i++) pthread_create(&threads[i], NULL, worker, (void*)i); for (int i = 0; i < 10; i++) pthread_join(threads[i], NULL); sem_destroy(&sem); return 0; } ```

¶Применение

¶Управление пулами ресурсов

Счётные семафоры широко применяются в системах, где имеется ограниченное количество однотипных ресурсов: пулы потоков (thread pools), пулы соединений с базами данных, пулы сетевых сокетов. Инициализация семафора числом ресурсов позволяет потокам запрашивать ресурс через операцию P, а освобождать — через V.

¶Решение задачи «производитель-потребитель»

В классической задаче синхронизации, где один или несколько потоков (производители) помещают данные в буфер ограниченного размера, а другие (потребители) извлекают их, используются два счётных семафора:

• empty — количество свободных мест в буфере (инициализируется размером буфера).
• full — количество занятых мест (инициализируется 0).

Производитель выполняет P(empty) перед записью и V(full) после; потребитель — P(full) перед чтением и V(empty) после.

¶Ограничение параллелизма

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

¶Взаимное исключение с несколькими ресурсами

В отличие от двоичного семафора (мьютекса), счётный семафор позволяет нескольким потокам одновременно работать с разными экземплярами одного типа ресурса, но не допускает превышения заданного лимита.

¶Критика и ограничения

• Инверсия приоритетов — ситуация, когда низкоприоритетный поток удерживает семафор, необходимый высокоприоритетному, что может привести к задержкам. В современных ОС эта проблема решается с помощью механизма наследования приоритета (priority inheritance).
• Отсутствие автоматического освобождения — если поток завершается аварийно, удерживая семафор, ресурс может остаться заблокированным навсегда. Для предотвращения этого используются механизмы тайм-аутов или автоматического освобождения при завершении потока.
• Сложность отладки — ошибки, связанные с неправильным использованием семафоров (например, пропуск операции V), могут приводить к взаимоблокировкам (deadlocks) или «голоданию», которые трудно воспроизвести и диагностировать.
• Производительность — операции с семафорами требуют переключения контекста при блокировке, что может быть дорогостоящим. В высокопроизводительных системах предпочитают использовать неблокирующие алгоритмы (lock-free) или более лёгкие примитивы, такие как спин-блокировки (spinlocks) для коротких критических секций.

¶Альтернативы

• Мьютекс — специализированный двоичный семафор, часто с дополнительными свойствами (например, рекурсивность, владение потоком). В отличие от счётного семафора, мьютекс может быть разблокирован только тем потоком, который его захватил.
• Условные переменные — позволяют потокам ожидать выполнения определённого условия, а не просто освобождения ресурса. Часто используются в комбинации с мьютексами.
• Семафоры-счётчики (в некоторых реализациях, например, в Java Semaphore) — предоставляют дополнительные методы, такие как tryAcquire (попытка захвата без блокировки) и drainPermits (получение всех доступных разрешений).

¶Интересные факты

• Названия операций P и V происходят от нидерландских слов, выбранных Дейкстрой: proberen (пробовать) и verhogen (увеличивать). В англоязычной литературе чаще используются wait/signal или acquire/release.
• В операционной системе THE, где впервые были применены семафоры, Дейкстра использовал их для синхронизации процессов, работающих с магнитными лентами — одним из первых устройств с ограниченным числом экземпляров.
• В стандарте POSIX определены именованные и неименованные семафоры. Именованные семафоры могут использоваться для синхронизации между разными процессами, а не только между потоками одного процесса.
• В языке Go семафоры не являются частью стандартной библиотеки, но их функциональность может быть реализована с помощью каналов (channels) — например, буферизированный канал ёмкостью N эквивалентен счётному семафору с начальным значением N.