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

Отличный вопрос! Он касается фундаментальных механизмов планирования в Go, которые напрямую влияют на производительность многопоточных программ.

Основные принципы распределения горутин

Распределение горутин между глобальной очередью (Global Queue) и локальными очередями (Local Queues) процессоров (или, точнее, P — планировщиков) в Go — это ключевой элемент модели M:N планирования, где M горутин выполняется на N системных потоках (каждый поток представлен структурой M).

Стандартный ответ: горутина из глобальной очереди перемещается в локальную очередь планировщика (P) в момент, когда этот P освобождается и нуждается в новой работе. Однако "освобождение" может происходить по нескольким причинам.

Когда именно происходит перемещение из глобальной в локальную очередь?

Вот основные триггеры этого процесса:

1. Когда P завершил выполнение своей текущей горутины и его локальная очередь пуста

Это самый частый случай. Планировщик работает по схеме "работать, пока есть работа".

// Псевдо-алгоритм логики планировщика (очень упрощенный)
func schedule(p *P) {
    for {
        // 1. Попытаться взять горутину из локальной очереди P
        gp := p.runq.pop()
        if gp != nil {
            execute(gp)
            continue
        }
        
        // 2. Локальная очередь пуста -> попытаться взять из глобальной очереди
        gp = globrunqget(p, 1) // Забрать одну горутину
        if gp != nil {
            execute(gp)
            continue
        }
        
        // 3. Если и в глобальной ничего нет, планировщик может попытаться
        // "украсть" горутину из локальной очереди другого P
        gp = findrunnable() // Этот метод включает проверку глобальной очереди
        if gp != nil {
            execute(gp)
        }
    }
}

После выполнения горутины (gp), если в локальной очереди P больше нет задач, планировщик вызывает globrunqget, который переносит до n горутин из глобальной очереди в локальную очередь этого P (обычно старается взять половину от того, что есть в глобальной, чтобы распределить нагрузку).

2. При запуске новой горутины с помощью go

Когда вы создаете новую горутину командой go func() {...}(), она не всегда сразу попадает в локальную очередь текущего P. Алгоритм такой:

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

3. Когда планировщик выполняет "воровство" работы (work stealing)

Если все P заняты, но один из них завершил свою локальную очередь, он начинает алгоритм "воровства":

1. Проверяет глобальную очередь.
2. Если в глобальной нет задач, пытается "украсть" половину горутин из локальной очереди случайно выбранного другого P.

// Упрощенная логика воровства
func stealWork(p *P) *g {
    // Сначала попробовать взять из глобальной
    gp := globrunqget(p, 1)
    if gp != nil {
        return gp
    }
    
    // Выбрать случайного другого P
    otherP := randomP()
    // Попытаться забрать половину горутин из его локальной очереди
    gpList := otherP.runq.stealHalf()
    if len(gpList) > 0 {
        p.runq.pushAll(gpList) // Добавить украденные в свою локальную очередь
        return gpList[0] // Вернуть первую для выполнения
    }
    return nil
}

Таким образом, горутины, которые были "переполнением" из одной локальной очереди в глобальную, или горутины, созданные в контексте другого P, могут через глобальную очередь или прямое воровство переместиться в локальную очередь нуждающегося P.

4. При возврате из системного вызова

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

Почему это важно?

Распределение через глобальную очередь обеспечивает два ключевых свойства:

1. Балансировка нагрузки. Если один P перегружен (локальная очередь полна), а другой idle (без работы), глобальная очередь служит общим пулом задач, из которого idle P может получить работу. Это предотвращает ситуацию, когда часть ядер CPU простаивает, а другая часть перегружена.

2. Предотвращение задержек из-за переполнения. Локальные очереди ограничены размером (256 горутин). Перемещение переполнения в глобальную очередь предотвращает блокировки создания новых горутин. Глобальная очередь может расти значительно больше.

Пример в контексте программы

Рассмотрим программу, которая создает множество горутин:

package main

func worker(id int) {
    // Выполняет работу
}

func main() {
    for i := 0; i < 1000; i++ {
        go worker(i) // Создаем 1000 горутин
    }
    // Ждем завершения...
}

• Первые 256 горутин (i=0..255) будут помещены в локальную очередь P0 (на котором работает main()).
• При создании 257-й горутины, локальная очередь P0 переполняется. 128 горутин из нее перемещаются в глобальную очередь, освобождая место. Затем 257-я горутина идет в локальную очередь P0.
• Если в системе несколько ядер (и несколько P), другие P (например, P1, P2), которые могут быть idle или менее загруженными, будут периодически проверять глобальную очередь и забирать из нее горутины в свои локальные очереди при планировании (см. пункт 1 выше).
• Таким образом, 1000 горутин распределяются между несколькими локальными очередями через механизм переполнения и балансировки через глобальную очередь.

Заключение

Горутина распределяется из глобальной очереди в локальную очередь конкретного планировщика (P) динамически, в ответ на события планирования:

1. Когда P завершил текущую задачу и его локальная очередь пуста — основное время работы планировщика.
2. Как часть механизма "воровства работы" (work stealing) — для балансировки нагрузки между P.
3. Косвенно, при переполнении локальной очереди — горутины, перемещенные из локальной в глобальную очередь при переполнении, позже будут взяты другими P.

Эта система позволяет эффективно использовать многоядерные процессоры, минимизировать contention (конкуренцию) за локальные очереди (которые почти не требуют синхронизации), и обеспечивать справедливость распределения задач. Глобальная очередь выступает как буфер и механизм балансировки, а локальные очереди — как быстрые, низко-конкурентные списки задач для каждого ядра CPU.