Семафоры

Задача: не больше N одновременно

Сервис ходит в базу, у которой лимит 50 соединений. Если под нагрузкой тысяча горутин одновременно полезет в базу, половина получит ошибку «too many connections». Нужно пропускать не больше N горутин, а остальных держать в очереди. Мьютекс тут не годится, он пускает ровно одну.

Для этого есть семафор. Его придумал Эдсгер Дейкстра в 1960-х, и это самый старый из примитивов синхронизации, которые до сих пор в ходу.

Удобная картинка — парковка на N мест с табло «свободно: 5» на въезде. Машина въезжает — табло уменьшается. Мест 0 — шлагбаум закрыт, машины ждут в очереди. Кто-то выехал — табло увеличилось, и одна машина из очереди заезжает.

Формально семафор — это целочисленный счётчик и две атомарные операции:

• wait (у Дейкстры P, от голландского proberen, «пробовать»; встречается также как down и acquire): если счётчик больше нуля, уменьшить его и пройти; если ноль — уснуть, пока не станет больше;
• signal (у Дейкстры V, от verhogen, «увеличивать»; up, release): увеличить счётчик и, если кто-то спит, разбудить одного.

Атомарность здесь значит, что две горутины не могут одновременно увидеть «осталось одно место» и обе проехать.

Что означает начальное значение

Поведение семафора целиком задаётся начальным значением счётчика.

Двоичный семафор (init = 1). Первый wait уменьшает 1 → 0 и проходит. Второй видит 0 и засыпает. Первый закончил и сделал signal: 0 → 1, второй просыпается, уменьшает обратно до 0 и входит. Получился мьютекс.

Семафор-сигнал (init = 0). Главная горутина запустила фоновую и должна дождаться, пока та загрузит конфиг. Главная делает wait и засыпает (счётчик 0). Фоновая загрузила конфиг и делает signal. Если фоновая успела раньше, счётчик стал 1, и wait главной пройдёт сразу. Сигнал не потеряется, в этом отличие от условной переменной.

Две записи одного и того же

В учебниках встречаются две конвенции, и их легко спутать.

В исходном описании Дейкстры wait сначала уменьшает счётчик и засыпает, если тот стал отрицательным. Тогда отрицательное значение -K означает «K потоков спят в очереди». Например, семафор на 3 места и 6 воркеров: значения пройдут 3 → 2 → 1 → 0 → −1 → −2 → −3, и −3 говорит, что трое ждут.

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

Семафор из мьютекса и условной переменной

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

package main
 
import (
	"fmt"
	"sync"
	"time"
)
 
// Semaphore — счётчик + мьютекс + условная переменная.
type Semaphore struct {
	mu    sync.Mutex
	cond  *sync.Cond
	value int // сколько свободных единиц; не бывает меньше нуля
}
 
func NewSemaphore(n int) *Semaphore {
	s := &Semaphore{value: n}
	s.cond = sync.NewCond(&s.mu)
	return s
}
 
func (s *Semaphore) Acquire() { // P, wait
	s.mu.Lock()
	for s.value <= 0 {
		s.cond.Wait()
	}
	s.value--
	s.mu.Unlock()
}
 
func (s *Semaphore) Release() { // V, signal
	s.mu.Lock()
	s.value++
	s.cond.Signal()
	s.mu.Unlock()
}
 
func main() {
	sem := NewSemaphore(3) // не больше трёх «запросов к базе» одновременно
 
	var (
		mu      sync.Mutex
		running int // сколько воркеров сейчас внутри
		peak    int // максимум за всё время
		wg      sync.WaitGroup
	)
 
	for i := 1; i <= 8; i++ {
		wg.Add(1)
		go func(id int) {
			defer wg.Done()
			sem.Acquire()
			defer sem.Release()
 
			mu.Lock()
			running++
			if running > peak {
				peak = running
			}
			mu.Unlock()
 
			time.Sleep(20 * time.Millisecond) // «запрос к базе»
 
			mu.Lock()
			running--
			mu.Unlock()
		}(i)
	}
	wg.Wait()
	fmt.Println("воркеров: 8, пик одновременно:", peak)
}

воркеров: 8, пик одновременно: 3

Восемь воркеров, но внутри никогда не больше трёх: остальные спят в Acquire.

Частая ошибка при написании такого кода — сначала уменьшить, потом ждать отрицательного значения:

   Acquire:  value--;  while value < 0: wait     ← так нельзя
   Release:  value++;  signal

Прогоним с value = 0 и двумя ждущими A и B. A: value = −1, спит. B: value = −2, спит. Кто-то делает Release: value = −1, будит A. A проверяет value < 0 — да, −1 — и засыпает обратно. Единица ресурса освободилась, но её никто не взял, и при одном освобождении система встала. Цикл while проверяет то же, что и уменьшение, поэтому уменьшать надо после ожидания, как в коде выше.

А что на уровне ОС

В Linux POSIX-семафоры (sem_wait, sem_post) устроены по той же схеме, что мьютекс из главы про futex: счётчик лежит в памяти процесса, sem_wait при положительном счётчике уменьшает его атомарным CAS без системного вызова, а futex_wait вызывается, только когда надо уснуть.

Интересная деталь про Go: sync.Mutex в рантайме сам построен на семафоре. Когда горутина не смогла захватить мьютекс, она вызывает внутренний runtime_SemacquireMutex и паркуется в очереди семафора, а Unlock при наличии ждущих делает runtime_Semrelease. Мьютекс — частный случай семафора не только в теории.

Производитель и потребитель на семафорах

Ограниченный буфер на N мест из прошлой главы на семафорах пишется тремя семафорами:

   empty = N   — сколько свободных ячеек (их ждёт производитель)
   full  = 0   — сколько заполненных ячеек (их ждёт потребитель)
   mutex = 1   — защита самого массива
 
   ПРОИЗВОДИТЕЛЬ              ПОТРЕБИТЕЛЬ
   wait(empty)                wait(full)
   wait(mutex)                wait(mutex)
     положить элемент           взять элемент
   signal(mutex)              signal(mutex)
   signal(full)               signal(empty)

empty и full работают как два табло: производитель занимает свободную ячейку и объявляет заполненную, потребитель наоборот. В сумме они всегда дают N (если не считать момент внутри критической секции). Условие «буфер полон» нигде не проверяется явно — его проверяет сам счётчик empty.

Порядок захвата важен. Поменяем у производителя первые две строки: сначала wait(mutex), потом wait(empty). Буфер полон, производитель взял мьютекс и уснул на empty, не отпустив мьютекс. Потребитель, который мог бы освободить место, первым делом делает wait(mutex) и тоже засыпает. Оба ждут друг друга вечно — это взаимоблокировка. Правило: сначала семафор ресурса, потом мьютекс; внутри мьютекса не спать в ожидании.

Читатели и писатели

Ещё одна классическая задача. Есть общая структура (например, конфиг или кэш), которую часто читают и редко меняют. Читатели друг другу не мешают, им можно работать одновременно. Писатель должен быть один, и пока он пишет, читать нельзя.

Readers-writer lock (RW-лок) решает это так: первый вошедший читатель захватывает «семафор записи», последний вышедший его отпускает. Писатель захватывает тот же семафор и ждёт, пока читатели не разойдутся.

У простой версии есть ловушка: если читатели идут непрерывным потоком, счётчик читателей никогда не падает до нуля, и писатель голодает. Поэтому реальные реализации отдают приоритет писателю. В Go это sync.RWMutex: как только писатель вызвал Lock, новые RLock блокируются, пока писатель не отработает. Отсюда практическое следствие: RLock внутри RLock в одной горутине (например, рекурсивный вызов) может зависнуть, если между ними писатель встал в очередь.

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

Семафоры в Go

Отдельного типа «семафор» в стандартной библиотеке нет. Его роль выполняет буферизованный канал: ёмкость канала — это число мест.

sem := make(chan struct{}, 50) // не больше 50 одновременно
 
for _, req := range requests {
	sem <- struct{}{} // wait: занять место (блокируется, если 50 заняты)
	go func(r Request) {
		defer func() { <-sem }() // signal: освободить место
		handle(r)
	}(req)
}

struct{}{} — пустая структура размером 0 байт: важен сам факт занятого места, данные не нужны. Обратите внимание, что место занимается до go, а не внутри горутины. Иначе цикл мгновенно запустит тысячу горутин, и они будут ждать своей очереди, занимая память, — ограничено будет число работающих, но не созданных.

Если нужна отмена по context или разный «вес» задач (тяжёлый запрос занимает три места), есть golang.org/x/sync/semaphore:

sem := semaphore.NewWeighted(50)
 
if err := sem.Acquire(ctx, 1); err != nil {
	return err // контекст отменён, пока ждали
}
defer sem.Release(1)

Ещё короче для групп задач: errgroup.Group с методом SetLimit(n) из golang.org/x/sync/errgroup — внутри тот же семафор. Подробнее про этот приём — в Go-курсе: паттерны конкурентности, каналы.

Про «владельца» лока. В POSIX-мьютексе с проверкой ошибок отпустить лок может только тот поток, что его взял, а у семафора владельца нет: signal может сделать кто угодно, на этом построен семафор-сигнал. В Go sync.Mutex тоже не привязан к горутине — документация явно разрешает захватить его в одной горутине и отпустить в другой. Но так почти никогда не пишут: «кто взял, тот и отпускает» остаётся соглашением, которое делает код читаемым.

Частые ошибки

• Уменьшать счётчик до ожидания и ждать отрицательного значения — система встаёт при одном освобождении (разбор в главе).
• Захватывать мьютекс раньше семафора ресурса в producer/consumer — получается взаимоблокировка.
• Занимать место в канале-семафоре внутри горутины, а не до go: ограничено число работающих горутин, но не созданных.
• Вызывать RLock повторно в той же горутине у sync.RWMutex: если между вызовами в очередь встал писатель, горутина зависнет.
• Считать, что двоичный семафор и мьютекс одно и то же во всём: у семафора нет понятия владельца, и это используют для сигналов.

Проверьте себя

1. Чем семафор с начальным значением 0 полезен и почему сигнал не потеряется, если signal случится раньше wait?
2. Что означает значение −3 в конвенции Дейкстры?
3. Почему у производителя порядок wait(empty) → wait(mutex) нельзя менять?
4. Семафор на 2 места, пять горутин по очереди делают wait, потом первые две — signal. Выпишите значение счётчика после каждой операции в обеих конвенциях. Сколько горутин спит в конце?

Что спрашивают на собесе

• Чем семафор отличается от мьютекса? Счётчик может быть больше 1, значит внутрь пускается N потоков. Сигнал запоминается в счётчике. Отпустить семафор может кто угодно — на этом построен семафор-сигнал.
• Что означает отрицательное значение? В конвенции Дейкстры — сколько потоков спит в очереди. В большинстве реализаций счётчик не уходит ниже нуля.
• Как ограничить число одновременных запросов? Считающий семафор с init = N. В Go — канал chan struct{} ёмкости N, x/sync/semaphore или errgroup.SetLimit.
• Producer/consumer на семафорах. empty = N, full = 0, mutex = 1. Сначала семафор ресурса, потом мьютекс, иначе deadlock.
• Как семафор устроен внутри? Мьютекс + условная переменная, проверка в цикле; в Linux — атомарный счётчик в памяти и futex для сна.
• Что такое readers-writer lock и где его ловушка? Много читателей или один писатель. Без приоритета писателя тот голодает; в Go RWMutex отдаёт приоритет писателю, поэтому рекурсивный RLock опасен.