Семафор (информатика)

Семафор — это абстрактный тип данных (или примитив синхронизации), используемый в параллельном программировании и операционных системах для управления доступом к общим ресурсам (например, данным, устройствам ввода-вывода, участкам кода) несколькими потоками или процессами. Семафор представляет собой целочисленную переменную, над которой определены две атомарные (неделимые) операции: ожидание (P, wait, down, acquire) и сигнализация (V, signal, up, release). Основная функция семафора — предотвращение состояний гонки (race conditions) и обеспечение взаимного исключения (mutual exclusion) при доступе к критическим секциям, а также координация выполнения процессов по принципу «производитель-потребитель» или «читатели-писатели».

История

Концепция семафора была предложена нидерландским учёным Эдсгером Дейкстрой в 1965 году. Дейкстра разработал этот механизм в рамках работы над операционной системой THE (Technische Hogeschool Eindhoven). Термин был заимствован из железнодорожной сигнализации (семафор), где сигнал указывает, можно ли поезду въезжать на участок пути. Первоначально семафоры реализовывались на аппаратном уровне с помощью специальных инструкций процессора (например, Test-and-Set), но впоследствии стали частью программных библиотек и ядер операционных систем.

Определение и основные операции

Семафор (обозначается как S) — это целочисленная переменная, которая инициализируется неотрицательным значением. Над ней выполняются две операции:

• P (Proberen — «проверить», по-нидерландски), также известная как wait, down, acquire, decrement: уменьшает значение семафора на 1. Если новое значение становится отрицательным, поток (или процесс), выполнивший операцию, блокируется и помещается в очередь ожидания.
• V (Verhogen — «увеличить», по-нидерландски), также известная как signal, up, release, increment: увеличивает значение семафора на 1. Если после увеличения значение семафора становится неотрицательным, один из заблокированных потоков (если они есть) пробуждается и может продолжить выполнение.

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

Классификация семафоров

Семафоры делятся на два основных типа:

Двоичный семафор (Binary Semaphore)

Двоичный семафор может принимать только два значения: 0 и 1. Он используется исключительно для реализации взаимного исключения (mutex). Когда поток входит в критическую секцию, он выполняет P-операцию, устанавливая семафор в 0, и выходит, выполняя V-операцию, возвращая семафор в 1. Если другой поток пытается войти в критическую секцию, когда семафор равен 0, он блокируется.

Счётный семафор (Counting Semaphore)

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

Реализация и использование

В операционных системах

В современных операционных системах (Linux, Windows, macOS) семафоры реализуются как системные вызовы или функции библиотек. Например:

• В Linux семафоры реализованы в виде системных вызовов semget, semop, semctl (System V IPC) или через функции sem_init, sem_wait, sem_post (POSIX).
• В Windows используются объекты ядра Semaphore, создаваемые функцией CreateSemaphore, и операции WaitForSingleObject (P) и ReleaseSemaphore (V).
• В Java семафоры представлены классом java.util.concurrent.Semaphore.

Пример использования (псевдокод)

``` // Инициализация семафора с начальным значением 1 (двоичный) Semaphore mutex = new Semaphore(1);

// Критическая секция void threadFunction() { mutex.acquire(); // P-операция // Доступ к общему ресурсу mutex.release(); // V-операция } ```

В языках программирования

• C/C++: POSIX threads (pthreads) предоставляют семафоры через библиотеку <semaphore.h>.
• Python: модуль threading.Semaphore в стандартной библиотеке.
• C#: класс Semaphore из пространства имён System.Threading.
• Go: семафоры не являются встроенной конструкцией, но могут быть реализованы с помощью каналов (channels).

Проблемы и ограничения

Взаимные блокировки (Deadlocks)

Неправильное использование семафоров может привести к взаимной блокировке (deadlock), когда два или более потока ожидают освобождения ресурсов, захваченных друг другом. Например, поток A захватывает семафор S1 и ожидает S2, а поток B захватывает S2 и ожидает S1.

Голодание (Starvation)

Если реализация очереди ожидания не является справедливой (например, не используется FIFO), некоторые потоки могут никогда не получить доступ к ресурсу, если другие потоки постоянно его захватывают.

Инверсия приоритета (Priority Inversion)

В системах с приоритетами высокоприоритетный поток может быть заблокирован низкоприоритетным, если последний удерживает семафор. Эта проблема была одной из причин сбоя марсианского аппарата Mars Pathfinder в 1997 году. Для её решения используются протоколы наследования приоритета (priority inheritance).

Альтернативы семафорам

В современных системах семафоры часто заменяются более высокоуровневыми примитивами синхронизации:

• Мьютексы (Mutexes) — специализированный двоичный семафор, который может быть освобождён только тем потоком, который его захватил (в отличие от семафора, который может быть освобождён любым потоком). Мьютексы обычно проще и безопаснее в использовании.
• Мониторы (Monitors) — высокоуровневые конструкции, объединяющие мьютекс и условные переменные (condition variables). Широко используются в Java (синхронизированные методы) и C# (lock-блоки).
• Спинлоки (Spinlocks) — примитивы, при которых поток в ожидании не блокируется, а циклически проверяет флаг (spin). Эффективны на многопроцессорных системах при коротких критических секциях.
• Атомарные операции (Atomic operations) — операции, выполняемые за один такт процессора (например, compare-and-swap), позволяющие реализовать синхронизацию без блокировок (lock-free программирование).

Примеры применения

• Управление пулом потоков: счётный семафор ограничивает количество одновременно выполняющихся потоков.
• Буферизация данных (производитель-потребитель): два семафора — один для пустых ячеек буфера, другой для заполненных.
• Доступ к файлам: семафор предотвращает одновременную запись в один файл несколькими процессами.
• Синхронизация в играх: семафоры используются для координации потоков рендеринга, физики и искусственного интеллекта.

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

• Название операции P (Proberen) и V (Verhogen) происходит от нидерландских слов, что было данью уважения Дейкстры к своей alma mater.
• В некоторых учебниках операцию P называют «down» (опустить), а V — «up» (поднять), что визуально соответствует изменению уровня семафора.
• Первоначально семафоры Дейкстры предполагали, что процессы не могут быть прерваны во время выполнения P или V, что было реализовано на ранних однопроцессорных системах путём отключения прерываний.

Источники

• Дейкстра, Э. «Co-operating sequential processes» (1965).
• Таненбаум, Э. «Современные операционные системы» (4-е издание, 2015).
• Сильбершац, А., Гэлвин, П., Гэгн, Г. «Операционные системы: концепции» (9-е издание, 2012).
• Документация POSIX по семафорам (IEEE Std 1003.1-2017).
• Кнут, Д. «Искусство программирования», том 1 (раздел о синхронизации).