Семафо́р (англ. semaphore) — примитив синхронизации[1] работы процессов и потоков, в основе которого лежит счётчик, над которым можно производить две атомарные операции: увеличение и уменьшение значения на единицу, при этом операция уменьшения для нулевого значения счётчика является блокирующейся[2]. Служит для построения более сложных механизмов синхронизации[1] и используется для синхронизации параллельно работающих задач, для защиты передачи данных через разделяемую память, для защиты критических секций, а также для управления доступом к аппаратному обеспечению.
Вычислительные семафоры используются для контроля над ограниченными ресурсами[3]. Двоичные семафоры обеспечивают взаимное исключение исполнения критических секций[4], а их упрощённой реализацией являются мьютексы, которые более ограничены в использовании[5]. Помимо взаимного исключения в общем случае семафоры и мьютексы могут использоваться во множестве других типовых алгоритмов, включая сигнализирование другим задачам[6], разрешение прохождения определённых контрольных точек только для одной задачи единовременно по аналогии с турникетом[7], задачу производителя и потребителя, подразумевающую передачу данных от одних задач другим[8], барьеры, позволяющие синхронизировать группы задач в определённых контрольных точках[9], условные переменные для оповещения других задач о каких-либо событиях[3] и блокировки чтения и записи, разрешающие одновременное чтение данных, но запрещающих их одновременное изменение[10].
Типовыми проблемами использования семафоров являются одновременное блокирование двух задач в ожидании друг друга[11] и ресурсное голодание, в результате чего ресурс может быть периодически недоступен для одних задач из-за его использования другими задачами[12]. При использовании в процессах с приоритетом реального времени может возникнуть инверсия приоритетов, которая может привести к неограниченной по времени блокировке процесса с более высоким приоритетом из-за захвата семафора процессом с более низким приоритетом, в то время как процессорное время отдаётся процессу со средним приоритетом[13], решением чего является наследование приоритетов[14].
Понятие семафора было введено в 1965 году нидерландским учёным Эдсгером Дейкстрой[15], а в 1968 году он предложил использовать два семафора для решения задачи производителя и потребителя[8].