Модуль 2 ⏱ ~41 мин чтения 📐 4 Mermaid диаграмм

34. Deadlock, Livelock, Starvation

Введение: Три состояния паралича конкурентности

В мире многопоточного программирования разработчики привыкли больше всего опасаться состояния гонки (race condition). И это понятно: гонки данных коварны, но они хотя бы заявляют о себе явно — бросают паники рантайма, приводят к повреждению памяти или отлавливаются встроенным детектором go run -race.

Куда более опасными и разрушительными для реальных производственных систем являются три «тихих убийцы» распределенных и параллельных программ: deadlock, livlock и starvation. Они не роняют процесс с громким crash dump. Вместо этого они парализуют систему: сервис перестает отвечать на запросы, деградирует по задержкам или превращается в «зомби», потребляя 100% мощности процессора без единого байта полезной работы.

flowchart TD
    subgraph Pathologies["Три патологии конкурентности"]
        direction TB
        DL["Deadlock (Взаимная блокировка)<br/>CPU: 0% | Прогресс: 0%<br/>Горутины спят навсегда"]
        LL["Livelock (Ложная активность)<br/>CPU: 100% | Прогресс: 0%<br/>Потоки бешено меняют состояние"]
        ST["Starvation (Голодание)<br/>CPU: 100% | Прогресс: избирательный<br/>Одни работают, другие ждут вечно"]
    end

    classDef dl fill:#450a0a,stroke:#f43f5e,stroke-width:2px,color:#f8fafc;
    classDef ll fill:#78350f,stroke:#f59e0b,stroke-width:2px,color:#f8fafc;
    classDef st fill:#1e1b4b,stroke:#6366f1,stroke-width:2px,color:#f8fafc;

    class DL dl;
    class LL ll;
    class ST st;

Для инженера, пишущего на Go, глубокое понимание этих явлений особенно критично: Go runtime не защищает вас от логических ошибок архитектуры синхронизации. Вы оперируете легковесными горутинами (g), которых при блокировке паркует планировщик Go (обычно без всякого системного вызова), и средой исполнения, которая жонглирует системными тредами (m) и логическими процессорами (p). Любой архитектурный просчет моментально масштабируется: взрывная нагрузка на планировщик при раздувании GOMAXPROCS, шторм кэш-промахов и истощение системных ресурсов.

Deadlock (Взаимная блокировка)

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

Классическая житейская аналогия: два предельно вежливых господина подошли к узкому мостику с противоположных сторон. Каждый настаивает: «Только после вас!». Ни один не делает шага вперед, пока не пройдет второй. Оба застывают на мосту навсегда.

В коде на Go deadlock чаще всего вызывают:

  • Несогласованный порядок захвата примитивов sync.Mutex и sync.RWMutex.
  • Небуферизованные каналы с размером буфера 0.
  • Ожидание в конструкции select без секции default.
  • Захват блокировки повторно из той же горутины (нереентерабельность sync.Mutex).
flowchart LR
    subgraph DeadlockCycle["Цикл взаимного ожидания (Resource Allocation Graph)"]
        direction LR
        G1["Горутина 1"]
        M1["Мьютекс A"]
        G2["Горутина 2"]
        M2["Мьютекс B"]
    end

    G1 -->|"Удерживает"| M1
    M1 -.->|"Пытается захватить"| G2
    G2 -->|"Удерживает"| M2
    M2 -.->|"Пытается захватить"| G1

    classDef g fill:#1e293b,stroke:#38bdf8,stroke-width:2px,color:#f8fafc;
    classDef m fill:#450a0a,stroke:#f43f5e,stroke-width:2px,color:#f8fafc;

    class G1,G2 g;
    class M1,M2 m;

Под капотом: как Go блокирует горутину

Когда горутина вызывает mutex.Lock(), рантайм Go выполняет трехфазную процедуру захвата:

  1. Spin phase: Рантайм пытается захватить мьютекс атомарно с помощью инструкции atomic.CompareAndSwapInt32. Если мьютекс свободен, горутина остается в состоянии Grunning, а мьютекс помечается как захваченный за десяток наносекунд.
  2. Парковка: Если мьютекс занят и короткий цикл активного ожидания не дал результата, горутина вызывает внутреннюю функцию runtime_SemacquireMutex. Это обертка над семафорами рантайма: горутина ставится в очередь ожидания и паркуется (gopark), системный вызов futex для этого не нужен. Планировщик Go переводит текущую g в состояние Gwaiting, извлекает ее из очереди выполнения и не выделяет CPU. Системный поток ОС m освобождается и берет на исполнение другую горутину.
  3. Wake-up: Когда текущий владелец вызывает Unlock(), рантайм вызывает runtime_Semrelease, который будит одну из ожидающих горутин (Gwaiting -> Grunnable) тоже без обращения к ядру.

Если цикл ожидания замкнут (Горутина 1 ждет Горутину 2, а та ждет Горутину 1), обе горутины будут спать вечно. С точки зрения ядра Linux всё абсолютно законно: оно про эти горутины ничего не знает, а потоки m просто простаивают в ожидании работы.

Как предотвращать и детектить

Для предотвращения deadlock необходимо разрушить хотя бы одно из четырех условий Коффмана (Coffman conditions):

  1. Фиксированный порядок захвата (Lock Ordering): Если нескольким горутинам требуются мьютексы A и B, абсолютно весь код в кодовой базе обязан захватывать их в строгой последовательности: всегда сначала A, затем B. Это гарантированно ломает цикл ожидания.
  2. Таймауты и контекст: Никогда не блокируйтесь бесконечно. Используйте context.WithTimeout и select для ограничения времени ожидания.
  3. Инструменты диагностики:
    • go tool pprof http://host/debug/pprof/goroutine (или curl 'http://host/debug/pprof/goroutine?debug=2') — снимок всех горутин покажет точные строки кода, где они застряли в sync.runtime_Semacquire.
    • Асинхронная преэмпция (рантайм прерывает сигналом горутину, зациклившуюся без точек вытеснения) включена по умолчанию, отключить её можно через GODEBUG=asyncpreemptoff=1; логические дедлоки она не лечит.
Go 
// Захват мьютекса с таймаутом: опрос TryLock (Go 1.18+) до истечения контекста.
// Наивный вариант «горутина делает mu.Lock() и закрывает канал» опасен: после таймаута
// такая горутина всё равно захватит мьютекс, как только его отпустят, и никто его не освободит.
func acquireWithTimeout(ctx context.Context, mu *sync.Mutex) error {
    for {
        if mu.TryLock() {
            return nil // Успех: мьютекс захвачен
        }
        select {
        case <-ctx.Done():
            // Мьютекс не захвачен вовремя; Unlock() вызывать не нужно, мы его не взяли
            return ctx.Err()
        case <-time.After(time.Millisecond):
        }
    }
}

Livelock (Ложная активная блокировка)

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

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

Механика и отличие от deadlock

В отличие от deadlock, при лайвлоке горутины не запаркованы в ожидании блокировки. Горутины бодрствуют, находятся в статусе Grunning или Grunnable, выполняют машинные команды, делают yield планировщику или непрерывно перезапускают логику обработки.

В Go лайвлок чаще всего провоцируют:

  • Неаккуратные циклы повторных попыток (retry loops), где несколько горутин пытаются захватить ресурс, при неудаче синхронно отступают, ждут фиксированный интервал времени и одновременно набрасываются на него снова.
  • Конструкции select с небуферизованными каналами, где отправители и получатели непрерывно «подталкивают» друг друга.
  • Бесконечные CAS-циклы (Compare-And-Swap), в которых десятки параллельных ядер непрерывно затирают атомарный указатель, заставляя друг друга начинать заново.

Под капотом: Cache Coherence (MESI) и стоимость спина

Когда несколько горутин, запущенных на разных логических процессорах (p), непрерывно читают и модифицируют одни и те же общие переменные (например, разделяемый флаг или указатель в CAS-цикле), на аппаратном уровне включается протокол когерентности кэшей MESI (Modified, Exclusive, Shared, Invalidated):

sequenceDiagram
    autonumber
    participant CPU1 as Ядро 1 (L1d кэш)
    participant Bus as Межъядерная шина (UPI / Ring Bus)
    participant CPU2 as Ядро 2 (L1d кэш)

    CPU1->>Bus: Атомарная запись (LOCK CMPXCHG)
    Bus->>CPU2: Запрос инвалидации кэш-линии (MESI: Invalid)
    Note over CPU2: Кэш-линия сброшена в Invalid!
    CPU2->>Bus: Попытка записи (LOCK CMPXCHG) -> Cache Miss
    Bus->>CPU1: Запрос на выталкивание свежих данных
    Note over CPU1: Кэш-линия CPU1 переходит в Invalid!
    Note over CPU1,CPU2: Cache Line Bounce: тераватты энергии и сотни тактов впустую!
  1. Ядро CPU1 модифицирует кэш-линию данных (L1d), переводя ее в состояние Modified.
  2. Через шину межъядерного взаимодействия (QPI/UPI на Intel или Infinity Fabric на AMD) ядро рассылает широковещательный запрос и инвалидирует копию в кэше CPU2.
  3. При следующем чтении с CPU2 немедленно возникает Cache Miss, и ядро вынуждено по шине запрашивать актуальные данные из L1 CPU1.
  4. Стоимость катастрофы: феномен Cache Line Bounce съедает от 20 до 50 тактов CPU на каждый раунд согласования шины. В плотном цикле активного спина это нагревает процессор и парализует пропускную способность шины памяти быстрее, чем любой «тяжелый» syscall.

Как предотвращать

  1. Exponential Backoff with Jitter: Добавление случайного разброса задержки (Random Jitter через rand.Intn()) гарантированно ломает синхронность ретраев между конкурирующими узлами или потоками.
  2. Yield без busy-wait: Вызов runtime.Gosched() отдает текущий квант времени планировщику Go. Это позволяет другим горутинам продвинуться вперед, не перегружая системные ядра ОС.
  3. Балансировка нагрузки: Убедитесь, что переменная GOMAXPROCS соответствует доступным физическим ядрам машины, чтобы планировщик мог эффективно распределять логические процессоры p.
Go 
// Паттерн безопасного retry с экспоненциальным бэкоффом и jitter
func retryWithJitter(ctx context.Context, maxRetries int, fn func() error) error {
    var err error
    for i := 0; i < maxRetries; i++ {
        err = fn()
        if err == nil {
            return nil
        }
        // Jitter предотвращает синхронный ретрай всех инстансов
        delay := time.Duration(rand.Intn(100)) * time.Millisecond
        select {
        case <-ctx.Done():
            return ctx.Err()
        case <-time.After(delay):
            // Ждем, не блокируя тред ОС полностью
        }
    }
    return fmt.Errorf("max retries reached: %w", err)
}

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

Starvation — патологическое состояние, при котором одна или несколько горутин технически готовы к исполнению, но хронически не могут получить доступ к необходимому ресурсу (квантам CPU или разделяемому мьютексу), потому что другие, более «наглые» горутины непрерывно монополизируют этот ресурс.

В Go различают два основных типа голодания:

  1. CPU Starvation: Горутина не получает квант процессорного времени из-за монопольных вычислений других задач или отсутствия точек кооперативной преэмпции.
  2. Lock Starvation: Горутина бесконечно простаивает в очереди к sync.Mutex, потому что вновь прибывающие горутины перехватывают мьютекс прямо у нее перед носом (эффект конвоя блокировок — convoy effect).

Под капотом: Work-Stealing и режим голодания мьютекса

Планировщик Go построен на алгоритме Work-Stealing. Каждый логический процессор p владеет локальной очередью готовых горутин (runq на 256 элементов). Если p опустошает свою очередь, он пытается «украсть» половину горутин из очереди соседнего процессора p. Это обеспечивает великолепную общую утилизацию ядер, но само по себе не дает математических гарантий абсолютной справедливости (fairness).

Чтобы защитить долго ждущие горутины от вечного голодания, начиная с Go 1.9 в структуру sync.Mutex был добавлен инновационный Starvation Mode (режим голодания):

flowchart TD
    subgraph NormalMode["Обычный режим (Normal Mode)"]
        direction TB
        WaitQ["Очередь ожидания FIFO (waiters)"]
        NewG["Новая горутина (Running на CPU)"]
        MutexObj["sync.Mutex"]
        NewG -->|"Спиннинг: перехватывает лок на лету!"| MutexObj
        WaitQ -.->|"Проигрывает в скорости"| MutexObj
    end

    subgraph StarveMode["Режим голодания (Starvation Mode, wait > 1ms)"]
        direction TB
        StarveWaitQ["Очередь ожидания FIFO"]
        StarveNewG["Новая горутина"]
        StarveMutex["sync.Mutex"]
        StarveMutex ==>|"Владение передается строго голове очереди!"| StarveWaitQ
        StarveNewG -->|"Спиннинг ЗАПРЕЩЕН: идет в хвост очереди"| StarveWaitQ
    end

    classDef norm fill:#1e293b,stroke:#38bdf8,stroke-width:2px,color:#f8fafc;
    classDef starv fill:#450a0a,stroke:#f43f5e,stroke-width:2px,color:#f8fafc;

    class NormalMode,WaitQ,NewG,MutexObj norm;
    class StarveMode,StarveWaitQ,StarveNewG,StarveMutex starv;
  • Обычный режим: вновь пришедшая горутина исполняется на процессоре и уже держит в кэше L1 данные. Поэтому ей разрешено попытаться перехватить освобождающийся мьютекс через spinlock, опередив спящую горутину, которую рантайм только начал будить. Это дает максимальную общую пропускную способность, но может вызвать голодание.
  • Режим голодания: если горутина ожидает мьютекс дольше 1 миллисекунды, мьютекс принудительно переключается в режим Starvation.
  • В этом режиме вновь прибывающие горутины вообще не пытаются захватить лок и не крутятся в спинлоке: они сразу встают в хвост очереди ожидания. Право владения мьютексом передается строго по цепочке первой ожидающей g.
  • Мьютекс выходит из режима голодания только тогда, когда очередь ожидания полностью опустеет или разбуженная горутина ждала меньше 1 мс.

Как предотвращать

  1. Fair Scheduling: Используйте буферизованные каналы или примитивы sync.WaitGroup вместо самодельных spin-очередей.
  2. Context Preemption: Регулярно опрашивайте канал завершения context.WithCancel внутри вычислительных циклов.
  3. Профилирование: Используйте профилировщик pprof (pprof/mutex и pprof/block), чтобы увидеть реальное время ожидания горутин на блокировках.
Go 
// Идиоматичное предотвращение lock starvation через select + context
func fairLockAcquire(ctx context.Context, mu *sync.Mutex) error {
    for {
        if mu.TryLock() { // TryLock — публичный API с Go 1.18; пользоваться им стоит осознанно
            return nil
        }
        select {
        case <-ctx.Done():
            return ctx.Err()
        case <-time.After(1 * time.Millisecond):
            // Yield к планировщику, чтобы другие p могли украсть горутину
            runtime.Gosched()
        }
    }
}

Сравнение подходов: Go vs C++ vs Java vs PHP

Характеристика Go C++ / Java PHP
Блокировка sync.Mutex (futex + spin) std::mutex (OS pthread) / synchronized (Monitor) Отсутствует (до Swoole/ReactPHP)
Голодание мьютекса Встроенный режим (Go 1.9+) Зависит от реализации (POSIX PTHREAD_MUTEX_DEFAULT не гарантирует fairness) N/A
Планировщик М-н-1 / М-н-М, Work-Stealing, асинхронная преэмпция OS Thread Scheduler (N:M часто эмулируется) Single-threaded event loop (Swoole)
Ловушка GOMAXPROCS = 1 убивает конкурентность CPU-bound задач std::thread тяжелый (2MB stack). Deadlock детектируется слабо Livelock редок, но race condition в расширениях част

Ловушки и вопросы с собеседований

Итог

  1. Deadlock, Livelock и Starvation — три фундаментальных паралича параллельных систем. Deadlock усыпляет потоки навсегда (0% CPU), Livelock заставляет их метаться вхолостую (100% CPU), а Starvation оставляет одни потоки без ресурсов из-за эгоизма других.
  2. Под капотом Go опирается на семафоры рантайма и адаптивный спиннинг (futex ядра Linux нужен лишь для сна самих потоков m). Если мьютекс занят, горутина переводится в Gwaiting, освобождая поток ОС для полезной работы.
  3. Аппаратный протокол MESI наказывает за наивный lock-free спиннинг эффектом Cache Line Bouncing, расходуя полосу пропускания межъядерной шины.
  4. Встроенный Starvation Mode в sync.Mutex спасет от конвоя блокировок, гарантируя передачу лока ожидающей горутине, если задержка превысила 1 миллисекунду.
  5. Главная линия защиты инженера: строго фиксированный порядок захвата мьютексов (Lock Ordering), случайный Jitter при ретраях и профилирование блокировок через pprof.

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