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

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

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

Семафоры могут быть двоичными и вычислительными. Вычислительные семафоры могут принимать целочисленные неотрицательные значения и используются для работы с ресурсами, количество которых ограничено, либо участвуют в синхронизации параллельно исполняемых задач. Двоичные семафоры являются частным случаем вычислительного семафора и могут принимать только два значения: 0 и 1.

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

Понятие семафора

Понятие семафора было введено в 1953 году нидерландским учёным Дейкстра. Семафор представляет из себя счётчик, над которым можно выполнять две операции: увеличение на 1 (англ. up) и уменьшение на 1 (англ. down). При попытке уменьшения семафора, значение которого равно нулю, процесс, запросивший данное действие должен блокироваться до тех пор, пока не станет возможным уменьшение значения семафора до неотрицательного значения, то есть пока другой процесс не увеличит значение семафора. Основным назначением семафора является разрешение или временный запрет на выполнение каких-либо действий, поэтому если значение счётчика семафора больше нуля, то говорят, что он находится в сигнальном состоянии, если же значение равно нулю – в несигнальном состоянии. Уменьшение значения семафора также иногда называют захватом, а увеличение значения — отпусканием или освобождением, что позволяет сделать описание работы семафора более понятным в контексте контроля использования какого-либо ресурса или при использовании в критических секциях.

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

Иногда операции уменьшения и увеличения значения семафора обозначают буквами P (от нидерл. proberen — пытаться) и V (от нидерл. verhogen — поднимать выше) соответственно. Впервые данные обозначения появились в языке Алгол 68.

В общем виде семафор можно представить как объект, состоящий из:

• переменной-счётчика, хранящей текущее значение семафора;
• списка заблокированных задач;
• функций атомарного увеличения и уменьшения значения семафора.

Типовые алгоритмы использования

Критическая секция

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

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

Для разных ресурсов могут быть разные семафоры, отвечающие за критические секции. Таким образом, критические секции, обеспечивающие защиту разных ресурсов, могут работать параллельно.

Пример работы критической секции на основе семафора

Основной поток
Инициализировать семафор А (А ← 1)
Поток 1	Поток 2
Поток 1 первым получил процессорное время Захватить семафор А (А ← 0) Выполнить действия над ресурсом Отпустить семафор А (А ← 1) Разблокировка потока 2	А захвачен в потоке 1 Захватить семафор А (блокировка) Разблокировка, А ← 0 Выполнить действия над ресурсом Отпустить семафор А (А ← 1)

Условная переменная

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

Блокировки чтения и записи

Блокировки чтения и записи позволяют организовать раздельную блокировку ресурса на чтение и на запись, разрешая одновременное чтение, но запрещая одновременную запись. Запись также блокирует любое чтение. Механизм может строиться на основе комбинации мьютексов, условных переменных и семафоров, в зависимости от способа реализации алгоритма.

Кольцевой буфер

Кольцевой буфер представляет из себя участок памяти определённого размера, данные в который заносятся и обрабатываются в порядке очереди (FIFO). В однопоточном варианте исполнения достаточно 4-х ячеек памяти: общий размер очереди, количество занятых элементов очереди, индексы текущего и следующего элементов в очереди. В многопоточной реализации алгоритм усложняется необходимостью синхронизации потоков (или процессов). Для случая двух потоков (читающий поток и пишущий поток) можно ограничиться двумя семафорами: для разрешения чтения данных и для разрешения записи данных. Начальное значение семафора, отвечающего за чтение, устанавливается в 0, потому как очередь пуста. А значение семафора на запись выставляется равным общему размеру очереди, то есть вся очередь доступна для заполнения. Перед добавлением очередного элемента в очередь семафор на запись уменьшается на 1, резервируя очередной элемент очереди для записи данных, а после добавления — семафор на чтение увеличивается на 1, разрешая чтение добавленного в очередь элемента.

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

Основная статья: Взаимная блокировка

При неправильном использовании семафоров могут возникать взаимные блокировки – ситуации, когда две или более параллельных задач оказываются заблокированными, ожидая отпускания блокировки друг от друга. В такой ситуации задачи не смогут нормально продолжить своё исполнение и обычно завершаются принудительно. Взаимные блокировки могут быть как в результате ошибок работы с семафорами, так и вследствие состояния гонки, которое является более тяжёлым в отладке.

Типовым примером взаимной блокировки могут служить вложенные друг в друга критические секции, реализованные двумя семафорами А и Б, при условии обратной вложенности в одном из потоков. Ошибкой подобной реализации является состояние гонки, из-за которого программа может работать большую часть времени, но в случае параллельного входа потоков в критические секции высоки шансы на взаимную блокировку.

Пример взаимной блокировки с обратной вложенностью критических секций

Основной поток
Инициализировать семафор А (А ← 1) Инициализировать семафор Б (Б ← 1)
Поток 1	Поток 2
Захватить семафор А (А ← 0) Б захвачен в потоке 2 Захватить семафор Б (блокировка) Выполнить действия над ресурсом Отпустить семафор Б Отпустить семафор А	Захватить семафор Б (Б ← 0) А захвачен в потоке 1 Захватить семафор А (блокировка) Выполнить действия над ресурсом Отпустить семафор А Отпустить семафор Б

Прикладное программирование

Семафоры в POSIX

Стандарты POSIX на уровне операционных систем предоставляют API языка Си для работы с семафорами как на уровне потоков, так и на уровне процессов через разделяемую память. Стандарты определяют тип данных семафора sem_t и набор функций для работы с ним. Семафоры POSIX доступны в Linux, macOS, FreeBSD и других POSIX-совместимых операционных системах.

Функции для работы с семафорами POSIX из заголовочного файла semaphore.h

Функция	Описание
sem_init()	Инициализация семафора с заданием начального значения счётчика и флага использования на уровне процессов
sem_destroy()	Освобождение семафора
sem_open()	Создание нового или открытие существующего именованного семафора
sem_close()	Закрытие семафора после окончания работы с ним
sem_unlink()	Удаление имени у именованного семафора (не уничтожает его)
sem_wait()	Уменьшение значения семафора на 1
sem_timedwait()	Уменьшение значения семафора на 1 ограничением максимального времени блокировки
sem_post()	Увеличение значения семафора на 1
sem_getvalue()	Получение текущего значения семафора

Одним из недостатков семафоров POSIX является способствующая ошибкам спецификация функции sem_timedwait(), которая оперирует временем часов реального времени (CLOCK_REALTIME) вместо времени непрерывной работы системы (CLOCK_MONOTONIC), что может приводить к сбоям в работе программ при изменении системного времени. Другим недостатком является отсутствие поддержки ожидания одновременно нескольких семафоров или семафора и файлового дескриптора.

Семафоры в Windows

Ядро Windows также предоставляет API языка Си для работы с семафорами. Потоки, заблокированные по семафору, выстраиваются в очередь FIFO, но могут перейти в конец очереди в случае прерывания потока для обработки других событий.

Основные функции для работы с семафорами Windows API

Функция	Описание
CreateSemaphoreA()	Создание семафора с указанием начального значения счётчика, максимального значения и имени семафора
OpenSemaphoreW()	Получение доступа к семафору по его имени, если он уже существует
CloseHandle()	Закрытие семафора после окончания работы с ним
WaitForSingleObject() или WaitForMultipleObjects()	Уменьшение значения семафора на 1 с блокировкой в случае нулевого значения счётчика; позволяет ограничивать максимальное время блокировки
ReleaseSemaphore()	Увеличение значения семафора на указанную величину

Особенностями семафоров под Windows является возможность увеличивать семафор на произвольное число и ожидать его сигнального состояния вместе с блокирующим ожиданием других семафоров или объектов.

Поддержка в языках программирования

Семафоры обычно не поддерживаются на уровне языка программирования в явном виде, но часто предоставляются встроенными или сторонними библиотеками. В некоторых языках, таких как Ada и Go, семафоры легко реализуются средствами языка.

Семафоры в языках программирования

Язык	Модуль или библиотека	Тип данных
Си	pthread, rt	sem_t
C++	Boost	boost::interprocess::interprocess_semaphore
C#	System.Threading	Semaphore
D	core.sync.semaphore	Semaphore
Go	golang.org/x/sync/semaphore	Weighted
Java	java.util.concurrent	java.util.concurrent.Semaphore
Python	asyncio	asyncio.Semaphore

Примеры использования

Пример критической секции

Пример содержит примитив синхронизации для критической секции в виде структуры, функцию входа в критическую секцию и функцию выхода из неё.

Пример реализации простой критической секции на основе семафора на языке Си (POSIX)

#include <errno.h>
#include <semaphore.h>
#include <stdbool.h>
#include <stdio.h>

#ifndef __STDC_LIB_EXT1__
  typedef int errno_t;
#endif

struct guard_t {
    sem_t sem_guard;
};

errno_t guard_init(struct guard_t *guard, bool between_processes)
{
    int r;
    r = sem_init(&guard->sem_guard, between_processes, 1);
    if (r == -1) {
        return errno;
    }

    return 0;
}

void guard_free(struct guard_t *guard)
{
    sem_destroy(&guard->sem_guard);
}

errno_t guard_enter(struct guard_t *guard)
{
    int r;
    do {
        r = sem_wait(&guard->sem_guard);
    } while ((r == -1) && (errno == EINTR));
    if (r == -1) {
        return errno;
    }
    return 0;
}

errno_t guard_leave(struct guard_t *guard)
{
    int r;
    r = sem_post(&guard->sem_guard);
    if (r == -1) {
        return errno;
    }
    return 0;
}

Пример синхронизации кольцевого буфера

В примере приведены структура и основные функции, необходимые для синхронизации кольцевого буфера на языке Си, используя интерфейс POSIX. Данная реализация позволяет одному потоку циклически записывать данные в кольцевой буфер, а другому потоку – асинхронно циклически читать из него.

Пример реализации синхронизирующего примитива для кольцевого буфера на основе семафоров на языке Си (POSIX)

#include <errno.h>
#include <semaphore.h>
#include <stdio.h>

#ifndef __STDC_LIB_EXT1__
  typedef int errno_t;
#endif

struct ring_buffer_t {
    size_t length;
    size_t count;
    size_t w_index;
    size_t r_index;

    sem_t sem_r;
    sem_t sem_w;
};

errno_t ring_buffer_init(struct ring_buffer_t *rbuf, size_t length)
{
    rbuf->length = length;
    rbuf->count = 0;
    rbuf->r_index = 0;
    rbuf->w_index = 0;

    int r;
    r = sem_init(&rbuf->sem_r, 1, 0);
    if (r == -1) {
        return errno;
    }

    errno_t errnum;

    r = sem_init(&rbuf->sem_w, 1, length);
    if (r == -1) {
        errnum = errno;
        goto aborting_sem_r;
    }

    return 0;
    
aborting_sem_r:
    sem_destroy(&rbuf->sem_r);
    return errnum;
}

void ring_buffer_free(struct ring_buffer_t *rbuf)
{
    sem_destroy(&rbuf->sem_w);
    sem_destroy(&rbuf->sem_r);
}

errno_t ring_buffer_write_begin(struct ring_buffer_t *rbuf)
{
    int r;
    do {
        r = sem_wait(&rbuf->sem_w);
    } while ((r == -1) && (errno == EINTR));
    if (r == -1) {
        return errnum;
    }

    return 0;
}

errno_t ring_buffer_write_end(struct ring_buffer_t *rbuf)
{
    ++rbuf->count;
    ++rbuf->w_index;
    if (rbuf->w_index >= rbuf->length) {
        rbuf->w_index = 0;
    }

    int r;
    r = sem_post(&rbuf->sem_r);
    if (r == -1) {
        return errno;
    }

    return 0;
}

errno_t ring_buffer_read_begin(struct ring_buffer_t *rbuf)
{
    int r;
    do {
        r = sem_wait(&rbuf->sem_r);
    } while ((r == -1) && (errno == EINTR));
    if (r == -1) {
        return errno;
    }

    return 0;
}

errno_t ring_buffer_read_end(struct ring_buffer_t *rbuf)
{
    --rbuf->count;
    ++rbuf->r_index;
    if (rbuf->r_index >= rbuf->length) {
        rbuf->r_index = 0;
    }

    int r;
    r = sem_post(&rbuf->sem_w);
    if (r == -1) {
        return errno;
    }

    return 0;
}

Детали реализации

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

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

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

На уровне процессоров

В архитектурах x86 и x86_64

Для синхронизации работы процессоров в многопроцессорных системах существуют специальные инструкции, позволяющие защитить доступ к какой-либо ячейке. В архитектуру x86 компанией Intel для ряда инструкций процессора предусмотрен префикс LOCK, позволяющий выполнять атомарные операции над ячейками памяти. Операции над ячейкой, выполняемые с префиксом LOCK, блокируют доступ остальных процессоров к ячейке, что на примитивном уровне позволяет организовывать легковесные семафоры с активным циклом ожидания.

Атомарное уменьшение значения семафора на 1 может быть выполнено при помощи инструкции LOCK DECL, которая выставляет флаг знака CS в случае, если результирующее значение оказывается меньше нуля. Особенностью такого подхода является то, что значение семафора может оказываться меньше нуля, поэтому после уменьшения счётчика флаг CS может проверяться с помощью инструкции JNS, и, если знак отрицательный, то операционная система может заблокировать текущую задачу.

Для атомарного увеличения значения семафора на 1 может использоваться инструкция LOCK INCL. Если результирующее значение оказывается отрицательным либо равным нулю, то это означает наличие ожидающих задач, в таком случае операционная система может разблокировать очередную задачу. Для пропуска разблокировки процессов может использоваться инструкция JG, которая осуществляет переход к метке, если флаги нулевого результата операции (ZF) и знака результата (SF) сброшены в 0, то есть если значение больше 0.

Во время блокировки в случаях отсутствия текущих задач может использоваться инструкция HLT, предназначенная для перевода процессора в режим низкого энергопотребления с ожиданием прерываний, которые необходимо предварительно разрешать с помощью инструкции STI. Однако в современных процессорах более оптимальным может быть использование инструкций MWAIT и MONITOR. Инструкция MWAIT аналогична HLT, но позволяет пробудить процессор по записи в ячейку памяти по адресу, указанному в MONITOR. NWAIT можно использовать для мониторинга изменения ячейки семафора, однако в многозадачных операционных системах эта инструкция используется для мониторинга флага необходимости запустить планировщик задач на заданном ядре.

Снижение энергопотребления во время активного цикла ожидания может достигаться с помощью инструкции PAUSE.

В архитектуре ARM

В архитектуре ARMv7 для синхронизации памяти используются так называемые локальный и глобальный эксклюзивные мониторы, представляющие собой автоматы состояний, контролирующие атомарный доступ к ячейкам памяти. Атомарное чтение ячейки памяти может осуществляться с помощью инструкции LDREX, а атомарная запись — через инструкцию STREX, которая также возвращает флаг успеха операции.

Для уменьшения значения семафора необходимо дождаться, пока его счётчик не станет больше нуля. Ожидание может быть реализовано разными способами:

• цикл активного ожидания в случае легковесного семафора, при котором периодически считывается значение счётчика с помощью инструкции LDREX;
• блокировка с переводом процессора в энергосберегающий режим ожидания с помощью инструкций ожидания прерывания WFI или ожидания события WFE;
• переключение контекста на исполнение другой задачи вместо блокировки процессора.

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

Увеличение значения семафора может представлять из себя циклическое чтение текущего значения счётчика через инструкцию LDREX с последующим увеличением копии значения и попыткой записи обратно в ячейку счётчика с помощью инструкции STREX. При этом чтение может не являться цикличным в случае бинарного семафора, поскольку его увеличение всегда будет приводить к записи в счётчик одного и того же значения, а сама запись не обязана быть синхронизируемой. После успешной записи счётчика, если его изначальное значение было нулевым, требуется возобновить исполнение заблокированных задач, что в случае переключения контекста может решаться средствами операционных систем. Если процессор был заблокирован с помощью инструкции WFE, разблокировать его можно через инструкцию SEV, оповещающей о наличии какого-либо события. Также эта команда может использоваться для разблокировки процессора, если не используется переключение контекста.

После уменьшения или увеличения значения семафора выполняется инструкция DMB, обеспечивающую гарантию целостности памяти защищаемого семафором ресурса.

См. также

• Состояние гонки
• Монитор
• Разделяемая память

Литература

• Эндрю С. Таненбаум. Современные операционные системы = Modern Operating Systems. — 3-е издание. — СПб: Питер: Издательский дом «Питер», 2011. — С. 162–163. — 1117 с. — (Классика computer science). — ISBN 9785459007572.
• ARM. ARM Synchronization Primitives. Development Article  (неопр.). www.arm.com (2009).
• Daniel Pierre Bovet, Marco Cesati. Understanding the Linux Kernel. — "O'Reilly Media, Inc.", 2002. — С. 173—177. — 786 с. — ISBN 9780596002138.
• Камерон Хьюз, Трейси Хьюз. Параллельное и распределенное программирование с использованием С++. — Издательский дом Вильямс. — 667 с. — ISBN 9785845906861.