Куда пойдут потоки искать горутины, если их нет и в локальной, и в глобальной очередях?

План поиска работы для "безработной" горутины

Когда горутина пытается выполнить системный вызов, блокирующую операцию или просто завершает свою текущую работу, планировщик Go (scheduler) переводит её в состояние ожидания. Если в локальной очереди (Local Run Queue, LRQ) конкретного потока M и в глобальной очереди (Global Run Queue, GRQ) нет готовых к выполнению горутин, поток не просто "засыпает" — он запускает многоуровневый процесс поиска работы.

Алгоритм поиска работы (work-stealing algorithm)

Поток (M, machine) в такой ситуации выполняет следующий алгоритм:

1. Проверка локальной очереди (LRQ) — первичный и самый быстрый источник
2. Проверка глобальной очереди (GRQ) — воркстилер периодически забирает оттуда горутины
3. Опрос сети (netpoller) — проверка готовности сетевых операций
4. Воровство работы у других потоков (work stealing) — основной механизм балансировки
5. Поиск отложенных вызовов (timers) и сборщика мусора

Основной механизм в этом сценарии — воровство работы (work stealing). Давайте рассмотрим этапы подробнее:

Детальный разбор этапов

1. Локальная и глобальная очереди (уже пусты по условию)

// Локальная очередь — часть структуры P (processor)
type p struct {
    runqhead uint32
    runqtail uint32
    runq [256]guintptr // локальный буфер горутин
    
    runnext guintptr // специальная "следующая" горутина
}

2. Опрос сети (netpoller)

Перед тем как воровать работу, поток проверяет netpoller:

// Упрощённая логика (реализация в runtime/netpoll.go)
func netpoll(delay int64) gList {
    // Использует epoll/kqueue/IOCP для проверки готовности сокетов
    // Возвращает список горутин, ожидающих сетевого I/O
}

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

3. Воровство работы у других потоков

Когда локальные источники исчерпаны, поток пытается "украсть" горутины у других потоков:

// Алгоритм в runtime/proc.go (findrunnable())
func findrunnable() (gp *g, inheritTime bool) {
    // 1. Проверка локальной очереди
    // 2. Проверка глобальной очереди  
    // 3. Опрос сети
    // 4. Опрос таймеров
    // 5. Work stealing:
    for i := 0; i < 4; i++ {
        for enum := stealOrder.start(fastrand()); !enum.done(); enum.next() {
            if gp := runqsteal(pp, allp[enum.position()]); gp != nil {
                return gp, false
            }
        }
    }
}

Процесс воровства:

• Поток случайным образом выбирает "жертву" (другой поток)
• Забирает половину горутин из локальной очереди выбранного потока
• Ворует из runnext (особо приоритетная горутина, следующая к выполнению)

4. Системный вызов и ожидание

Если все механизмы поиска не дали результата:

// Финальные действия перед блокировкой
if gp == nil {
    // Освобождение P (processor) для других потоков
    pidleput(pp)
    
    // Блокировка потока до поступления работы
    stopm() // Останавливает текущий M
    
    // При пробуждении — снова поиск работы
    mstart()
}

Практический пример

Рассмотрим визуализацию процесса:

// Изначально у нас 4 потока (M) с привязанными процессорами (P)
// M1: LRQ пуста, GRQ пуста
// M2: LRQ содержит [G2, G3, G4, G5]
// M3: LRQ содержит [G6]
// M4: Работает системный вызов

// M1 начинает поиск:
// 1. LRQ пуста ❌
// 2. GRQ пуста ❌  
// 3. Netpoller: нет готовых горутин ❌
// 4. Воровство: выбирает M2, забирает половину:
//    Было в M2: [G2, G3, G4, G5] → забирает [G4, G5]
//    M2 остаётся: [G2, G3]
//    M1 получает: [G4, G5] и начинает выполнять G4

Критические аспекты реализации

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

• Воровать можно только у "активных" потоков (не находящихся в syscall)
• Предотвращение голодания (starvation) через периодическую проверку GRQ
• Кооперативная многозадачность — горутина должна добровольно отдать управление

Производительность:

• Локальные очереди — lock-free, используют атомарные операции
• Глобальная очередь — требует мьютексов, используется реже
• Work stealing минимизирует contention (состязание)

Итоговая схема поиска

Поток M ищет работу:
├── LRQ (локальная очередь) ❌
├── GRQ (глобальная очередь) ❌
├── Netpoller (сеть) ❌
├── Timers (таймеры) ❌
├── Work stealing (воровство у других M):
│   ├── Случайный выбор "жертвы"
│   ├── Попытка украсть половину LRQ
│   └── Попытка украсть runnext
└── Если ничего не найдено:
    ├── Отсоединение P (processor)
    └── Блокировка M до появления работы

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