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

Механизм работы планировщика Go с глобальной очередью

В планировщике Go (Goroutine Scheduler) для забора горутин из глобальной очереди (global runqueue) используется механизм work-stealing (кража задач) в сочетании с периодической загрузкой задач (load balancing). Это ключевой аспект многопоточного выполнения в Go, обеспечивающий эффективное распределение работы между потоками операционной системы (OS threads), за которыми закреплены логические процессоры (P — Processors).

Структура очередей в планировщике

Планировщик Go организован по модели M:P:G, где:

• M (Machine) — поток ОС, который выполняет код.
• P (Processor) — логический процессор, который управляет локальной очередью горутин для потока M.
• G (Goroutine) — горутина, единица планирования.

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

Механизм забора из глобальной очереди

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

1. Периодическая проверка (каждые 61 такт планировщика)
   Каждый P ведет счетчик schedtick. При вызове планировщика (например, при завершении горутины или системном вызове) tick увеличивается. Каждые 61 тик P проверяет глобальную очередь перед локальной, чтобы обеспечить балансировку нагрузки. Это предотвращает ситуацию, когда одни P перегружены, а другие простаивают.

   Пример логики (упрощенно):

   // Псевдокод логики планировщика
   func schedule() {
       // ...
       if gp == nil {
           // Каждые 61 тик проверяем глобальную очередь
           if schedtick%61 == 0 && checkGlobalQueue() {
               gp = dequeueGlobal()
           }
           // Иначе работаем с локальной очередью
       }
       // ...
   }
   

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

   • Сначала проверяется локальная очередь текущего P.
   • Если она пуста, проверяется глобальная очередь.
   • Если глобальная очередь тоже пуста, P пытается украсть половину горутин из локальной очереди другого случайного P.

   Это реализовано в функции findrunnable() в runtime планировщика:

   // Фрагмент логики (адаптировано из исходного кода Go)
   func findrunnable() (gp *g) {
       // 1. Проверка локальной очереди
       gp = runqget(_p_)
       if gp != nil {
           return gp
       }
       
       // 2. Проверка глобальной очереди
       if sched.runqsize > 0 {
           lock(&sched.lock)
           gp = globrunqget(_p_, 0)
           unlock(&sched.lock)
           if gp != nil {
               return gp
           }
       }
       
       // 3. Попытка кражи у других P
       // ...
   }
   

Важные детали реализации

• Блокировки: Доступ к глобальной очереди защищен глобальной блокировкой планировщика (sched.lock), поэтому частые обращения к ней могут стать узким местом. Именно поэтому предпочтение отдается локальным очередям.
• Количество забираемых горутин: При обращении к глобальной очереди P забирает не одну горутину, а min(len(global_queue)/GOMAXPROCS + 1, len(global_queue)). Это позволяет более равномерно распределить нагрузку.
• Приоритеты: У планировщика нет приоритетов горутин — используется FIFO (First-In-First-Out) в пределах очереди, но с учетом описанных механизмов балансировки.

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

Рассмотрим сценарий, когда несколько горутин создаются из главного потока:

package main

import (
    "fmt"
    "time"
)

func worker(id int) {
    fmt.Printf("Горутина %d выполняется\n", id)
}

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

Здесь, при создании 1000 горутин, локальная очередь P главного потока может переполниться, и часть горутин будет перемещена в глобальную очередь. Затем другие P (если GOMAXPROCS > 1) через механизм work-stealing или периодическую проверку заберут эти горутины из глобальной очереди для параллельного выполнения.

Таким образом, механизм work-stealing и периодическая проверка каждые 61 такт — это основные способы, позволяющие планировщику Go забирать горутины из глобальной очереди, обеспечивая балансировку нагрузки и эффективное использование ресурсов CPU в многопоточных приложениях.