Как процессор распределяет задачи между локальной и глобальной очередью?

Распределение задач между очередями в Go

В языке Go планировщик (scheduler) использует систему из двух типов очередей для эффективного распределения горутин (goroutines) между потоками ОС (M в модели GMP). Это позволяет балансировать нагрузку и минимизировать накладные расходы на синхронизацию.

Архитектура очередей

Локальная очередь (Local Run Queue)

• Каждому потоку ОС (M) присваивается локальная очередь (обычно реализована как кольцевой буфер на 256 элементов)
• При создании новой горутины она обычно помещается в локальную очередь текущего M
• При извлечении горутин планировщик сначала проверяет локальную очередь, что позволяет избежать блокировок

// Упрощенное представление структуры P (processor)
type p struct {
    runq    [256]guintptr  // Локальная очередь
    runqhead uint32
    runqtail uint32
}

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

• Общая очередь для всех потоков (реализована как linked list с мьютексом)
• Служит буфером при дисбалансе нагрузки между процессорами
• Используется когда локальные очереди переполнены или опустошены

Алгоритм распределения задач

1. Создание новых горутин

go func() {
    // Новая задача
}()

• При быстром пути (hot path) горутина помещается в локальную очередь текущего P
• При переполнении локальной очереди (более 256 ожидающих горутин), половина перемещается в глобальную очередь

2. Работа воркера (work stealing)

Когда поток завершает выполнение текущей горутины:

• Приоритет 1: Поиск в локальной очереди (60% проверок)
• Приоритет 2: Поиск в глобальной очереди (регулярные проверки каждые 61 такт)
• Приоритет 3: Work stealing - "кража" работы из очередей других процессоров

3. Балансировка нагрузки

// Псевдокод алгоритма балансировки
func balance() {
    if localQueue.IsEmpty() {
        // Пробуем забрать из глобальной очереди
        if g := globalQueue.Pop(); g != nil {
            execute(g)
        }
        // Пробуем украсть у соседнего процессора
        for i := 0; i < tryStealTimes; i++ {
            if g := stealFromRandomP(); g != nil {
                execute(g)
                break
            }
        }
    }
}

Ключевые механизмы

Периодические проверки (sysmon)

• Фоновая горутина sysmon проверяет состояние каждые 10ms
• При обнаружении простаивающих потоков и задач в глобальной очереди - инициирует перераспределение
• Отвечает за перемещение горутин из глобальной очереди в локальные

Пороговые значения и триггеры

• Заполнение локальной очереди > 90%: подготовка к перемещению в глобальную
• Длительное ожидание в глобальной очереди > 2ms: приоритетный разбор
• Более 50% простаивающих процессоров: активный work stealing

Пример распределения

package main

import (
    "fmt"
    "runtime"
    "time"
)

func worker(id int) {
    time.Sleep(time.Millisecond * 100)
    fmt.Printf("Worker %d on CPU %d\n", id, runtime.GetCPU())
}

func main() {
    runtime.GOMAXPROCS(4) // 4 процессора
    
    for i := 0; i < 1000; i++ {
        go worker(i) // Создание 1000 горутин
    }
    
    time.Sleep(time.Second * 2)
}

В этом примере:

1. Первые 4×256 горутин распределяются по локальным очередям
2. Остальные попадают в глобальную очередь
3. Планировщик балансирует нагрузку через work stealing

Оптимизации и особенности

Batch операции

• Перемещение горутин между очередями выполняется пачками для уменьшения contention
• Локальная очередь использует lock-free структуры где возможно

Приоритеты выполнения

1. Запущенные горутины с остатком кванта времени
2. Горутины из локальной очереди (FIFO)
3. Горутины из глобальной очереди
4. Сеть/IO готовые горутины из epoll/kqueue
5. Украденные горутины из других очередей

Проблемы и решения

Проблема: Конкуренция за глобальную очередь

Решение: Использование local run queues как первого уровня кэширования

Проблема: Голодание горутин в глобальной очереди

Решение: Периодические проверки sysmon и guaranteed execution time

Проблема: False sharing

Решение: Выравнивание структур данных по кэш-линиям

Настройка и мониторинг

# Трассировка планировщика
GODEBUG=schedtrace=1000 ./program
# Детальная трассировка
GODEBUG=scheddetail=1,schedtrace=1000 ./program

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