Семафор (программирование)

Семафор — это абстрактный тип данных (или примитив синхронизации), используемый в многозадачных и многопоточных операционных системах для управления доступом к общим ресурсам (критическим секциям) и координации взаимодействия между процессами или потоками. Семафор представляет собой целочисленную переменную, над которой определены две атомарные (неделимые) операции: ожидание (P, от нидерл. proberen — «проверять») и сигнализация (V, от нидерл. verhogen — «увеличивать»). Ключевая особенность семафора заключается в том, что его значение не может стать отрицательным в результате операции P; если ресурс недоступен, поток блокируется до тех пор, пока другой поток не освободит ресурс.

История

Концепция семафора была предложена нидерландским учёным Эдсгером Дейкстрой в 1965 году. Дейкстра разработал эту модель для решения проблем синхронизации в операционной системе THE, создававшейся в Технологическом университете Эйндховена. До появления семафоров синхронизация осуществлялась с помощью аппаратных блокировок или более примитивных методов, таких как занятое ожидание (busy waiting), что приводило к неэффективному использованию процессорного времени. Дейкстра формализовал понятие семафора, введя строгие математические правила для операций P и V, что позволило доказывать корректность параллельных алгоритмов. Впоследствии семафоры стали одним из фундаментальных механизмов синхронизации в таких операционных системах, как Unix (включая Linux) и Windows.

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

Семафоры делятся на два основных типа в зависимости от начального значения и поведения.

Двоичный семафор

Двоичный семафор (или mutex, хотя это не одно и то же) может принимать только значения 0 или 1. Он используется для реализации взаимного исключения (mutual exclusion), когда только один процесс или поток может одновременно владеть ресурсом. Операция P уменьшает значение с 1 до 0, блокируя доступ, а операция V увеличивает его обратно до 1, освобождая ресурс. В отличие от мьютекса, двоичный семафор не обязательно должен быть освобождён тем же потоком, который его захватил, что делает его более гибким, но и более подверженным ошибкам.

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

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

Устройство и реализация

Семафор как абстрактный тип данных включает в себя:

• Целочисленную переменную (значение семафора), которая хранит количество доступных ресурсов.
• Очередь ожидания (список заблокированных процессов или потоков), которые ожидают освобождения ресурса.
• Атомарные операции: P (wait) и V (signal).

Реализация семафоров в операционных системах обычно опирается на аппаратную поддержку атомарных инструкций (например, compare-and-swap или test-and-set) и механизмы планировщика. Когда поток вызывает операцию P и значение семафора равно 0, планировщик переводит этот поток в состояние ожидания (sleep) и помещает его в очередь. При вызове операции V другим потоком планировщик пробуждает один из ожидающих потоков (если очередь не пуста). Это позволяет избежать занятого ожидания и эффективно использовать процессорное время.

Операции P и V

• P (proberen): атомарно уменьшает значение семафора на 1. Если новое значение меньше 0, поток блокируется и помещается в очередь ожидания.
• V (verhogen): атомарно увеличивает значение семафора на 1. Если значение было меньше или равно 0 (то есть в очереди есть ожидающие потоки), один из них пробуждается.

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

Применение

Семафоры широко используются в параллельном программировании и операционных системах для решения классических задач синхронизации.

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

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

Синхронизация событий

Семафоры могут использоваться для упорядочивания выполнения потоков. Например, семафор, инициализированный значением 0, позволяет одному потоку ждать, пока другой не выполнит определённое действие. Поток-производитель вызывает V после завершения работы, а поток-потребитель вызывает P для ожидания.

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

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

Задача «Производитель-Потребитель»

Классическая задача, в которой один или несколько потоков-производителей помещают данные в буфер, а потоки-потребители извлекают их. Для её решения используются два семафора: один (empty) отслеживает количество свободных мест в буфере, другой (full) — количество заполненных мест. Начальное значение empty равно размеру буфера, full — 0. Производитель выполняет P(empty) перед добавлением и V(full) после; потребитель — P(full) перед извлечением и V(empty) после.

Задача «Читатели-Писатели»

Эта задача регулирует доступ к данным, которые могут одновременно читать несколько потоков, но запись должна быть исключительной. Решение с использованием семафоров может быть реализовано с помощью одного двоичного семафора для защиты счётчика читателей и другого для защиты доступа к данным.

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

Несмотря на широкое распространение, семафоры имеют ряд недостатков. Основной из них — подверженность ошибкам программиста. Например, если поток забывает выполнить V после P, семафор может остаться заблокированным, что приведёт к взаимной блокировке (deadlock). Также семафоры не защищают от таких проблем, как инверсия приоритетов (priority inversion), когда высокоприоритетный поток ожидает ресурса, занятого низкоприоритетным, который, в свою очередь, вытесняется среднеприоритетным потоком. В современных системах для упрощения разработки и снижения вероятности ошибок часто используются более высокоуровневые примитивы синхронизации, такие как мьютексы, условные переменные (condition variables), семафоры POSIX, а также конструкции, предоставляемые языками программирования (например, мониторы в Java или async/await в C#).

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

POSIX

В Unix-подобных системах (включая Linux) семафоры реализованы в стандарте POSIX. Существуют два типа: именованные (для синхронизации между процессами) и неименованные (для синхронизации потоков одного процесса или процессов с общей памятью). Основные функции: sem_init, sem_wait, sem_post, sem_destroy, sem_open, sem_close, sem_unlink.

Windows

В Windows семафоры реализованы как объекты ядра и могут быть именованными или неименованными. Для работы с ними используются функции Win32 API: CreateSemaphore, OpenSemaphore, ReleaseSemaphore, WaitForSingleObject, CloseHandle. В отличие от POSIX, в Windows семафор может иметь максимальное значение, задаваемое при создании.

Другие системы

В некоторых операционных системах, таких как FreeRTOS (для встраиваемых систем), семафоры также являются ключевым механизмом синхронизации. В RTOS обычно поддерживаются как двоичные, так и счётные семафоры, а также мьютексы с наследованием приоритета для предотвращения инверсии приоритетов.

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

• Названия операций P и V происходят от нидерландских слов proberen («проверять») и verhogen («увеличивать»), которые использовал Дейкстра. В англоязычной литературе их часто называют wait и signal, или down и up.
• Семафоры являются одним из первых формальных инструментов для доказательства корректности параллельных алгоритмов. Дейкстра показал, что с помощью семафоров можно реализовать любую схему синхронизации, что делает их полными по Тьюрингу в контексте параллельных вычислений.
• В современных языках программирования, таких как Go, семафоры часто заменяются каналами (channels), которые предоставляют более безопасный и выразительный механизм синхронизации.

Источники

• Э. Дейкстра. «Cooperating Sequential Processes» (1965).
• Э. Таненбаум, Х. Бос. «Современные операционные системы» (4-е издание).
• У. Ричард Стивенс, Стивен А. Раго. «UNIX. Профессиональное программирование» (3-е издание).
• Документация Microsoft по объектам ядра Windows: семафоры.
• Стандарт POSIX.1-2008, раздел «Semaphores».