Что такое механизм `work-stealing` в планировщике Go и как он работает?

Механизм work-stealing (воровство работы) — это фундаментальная стратегия планировщика Go для эффективной балансировки нагрузки и максимального использования процессорных ядер.

В основе планировщика лежит модель M:P:G:

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

Как работает work-stealing:

1. Локальная очередь: Когда процессор P выполняет горутины, он в первую очередь берет их из своей локальной очереди (LRQ).
2. Опустошение очереди: Если локальная очередь P пустеет, он не простаивает, а начинает искать работу.
3. Поиск работы: Поиск происходит в следующем порядке:
   • Сначала P пытается взять горутины из глобальной очереди (GRQ), где находятся горутины, которые еще не были przypisane do żadnego P.
   • Если глобальная очередь пуста, P становится "вором" и пытается украсть половину горутин из локальной очереди другого, случайным образом выбранного P.

Цель механизма:

• Максимальная утилизация CPU: Потоки ОС (M) не простаивают, пока есть готовые к выполнению горутины.
• Снижение задержек: Горутины выполняются быстрее, так как нагрузка равномерно распределяется по всем доступным процессорам P.
• Эффективность: Доступ к локальной очереди не требует блокировок, в отличие от глобальной, что делает основную работу очень быстрой. Блокировки используются только при доступе к глобальной очереди или в момент "воровства".