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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Типовые алгоритмы

Сигнализирование Сигнализирование, также называемое уведомлением, является базовым назначением семафоров, оно гарантирует исполнение участка кода одной задачи после исполнения участка кода другой задачи. Сигнальное использование семафора обычно предполагает установку его начального значения в 0, чтобы ожидающие сигнального состояния задачи могли блокироваться до наступления события. Сигнализирование выполняется через увеличение значения семафора, а ожидание — через уменьшение значения. +Пример сигнализирования семафоромОсновной поток Инициализировать семафор А (А ← 0)Поток 1Поток 2 Выполнить подготовку ресурса Сигнализировать семафором А (А ← 1)

Разблокировка потока 2 Действия над общим ресурсом Поток 2 первым получил процессорное время Ожидать сигнального состояния А (блокировка)

Разблокировка, А ← 0 Действия над общим ресурсом

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

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

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

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

Для разных ресурсов могут быть разные семафоры, отвечающие за критические секции. Таким образом, критические секции, защищённые разными семафорами, могут работать параллельно. + Пример работы критической секции на основе семафораОсновной поток Инициализировать семафор А (А ← 1)Поток 1Поток 2 Поток 1 первым получил процессорное время

Захватить семафор А (А ← 0) Выполнить действия над ресурсом Отпустить семафор А (А ← 1)

Разблокировка потока 2 А захвачен в потоке 1

Захватить семафор А (блокировка)

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

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

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

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

+ Инициализация Турникет Блокировка Разблокировка турникет = Семафор(1) захватить(турникет) отпустить(турникет) захватить(турникет) отпустить(турникет)

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

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