Какие знаешь очереди в планировщике Go?

Очереди в планировщике Go

В планировщике Go существуют несколько типов очередей, которые играют ключевую роль в управлении горутинами и распределении их по потокам операционной системы (OS threads). Архитектура планировщика Go основана на модели work-stealing и m:n scheduling, где множество горутин (m) распределяется по меньшему количеству потоков ОС (n). Вот основные очереди:

1. Локальные очереди (Local Queues)

Каждый поток ОС (M), связанный с логическим процессором (P), имеет свою локальную очередь (local runqueue). Это очередь из горутин, готовых к выполнению именно на этом P. Локальная очередь реализована как кольцевой буфер (кольцевая очередь) фиксированного размера (обычно на 256 элементов).

• Назначение: Минимизация конкуренции за блокировки, поскольку каждый P работает со своей очередью независимо.
• Пример структуры: В исходном коде Go (src/runtime/runtime2.go) она представлена как runq в структуре p.

type p struct {
    // ...
    runqhead uint32
    runqtail uint32
    runq     [256]guintptr
    // ...
}

2. Глобальная очередь (Global Queue)

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

• Назначение: Балансировка нагрузки между различными P, особенно когда некоторые P перегружены, а другие простаивают.
• Реализация: Обычно реализована как связанный список с защитой на мьютексе.

3. Очередь ожидания (Wait Queue) или очередь каналов

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

• Назначение: Управление блокированными горутинами, ожидающими коммуникации.
• Структура: В исходном коде представлена как sendq и recvq в структуре hchan.

type hchan struct {
    // ...
    recvq    waitq  // очередь ожидающих получателей
    sendq    waitq  // очередь ожидающих отправителей
    // ...
}

type waitq struct {
    first *sudog
    last  *sudog
}

4. Сетевой поллир (Netpoller) и его очередь

Планировщик интегрирован с netpoller — механизмом, который асинхронно обрабатывает операции ввода-вывода (особенно сетевые). Когда горутина выполняет блокирующую сетевую операцию, она регистрируется в netpoller, а не блокирует поток ОС.

• Назначение: Позволяет горутинам, ожидающим сетевых данных, освободить P, пока данные не готовы. Как только операция ввода-вывода завершается, соответствующая горутина помещается в очередь (часто в глобальную или локальную очередь своего P) для дальнейшего выполнения.

5. Очередь таймеров (Timers Heap)

Для планирования отложенного выполнения (например, через time.Sleep или time.After) используется приоритетная куча (heap) таймеров, привязанная к каждому P.

• Назначение: Эффективное управление таймерами и отложенными вызовами функций.
• Реализация: Минимальная куча, отсортированная по времени срабатывания.

Алгоритм работы и балансировки (Work-Stealing)

Планировщик использует стратегию кражи задач для балансировки нагрузки:

1. Локальный приоритет: P сначала выбирает горутину из своей локальной очереди.
2. Кража задач (Work-Stealing): Если локальная очередь пуста, P пытается "украсть" половину задач из локальной очереди другого случайного P.
3. Обращение к глобальной очереди: Если кража не удалась, P берет горутину из глобальной очереди (захватывая мьютекс).
4. Опрос сети: Если все очереди пусты, P может проверить netpoller на наличие готовых к выполнению горутин.

Ключевые термины и структуры

. M (Machine): Поток операционной системы. . P (Processor): Логический процессор, ресурс для выполнения горутин. У каждого P есть локальная очередь. . G (Goroutine): Сама горутина, единица планирования. . Global Sched: Глобальная структура планировщика (sched), содержащая глобальную очередь.

var sched struct {
    // ...
    runq     gQueue // глобальная очередь
    runqsize int32
    // ...
}

Вывод

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