Зачем отдельная глава про много ядер

В главах scheduling и proportional-scheduling мы считали, что ядро (процессор, который реально крутит инструкции) одно: задачи выстраиваются в очередь, планировщик выбирает следующую. Но твой ноут и любой сервер в проде — это 8, 16, 64 ядра. И тут возникают проблемы, которых на одном ядре просто не было.

Главных новых сложностей три:

1. Кэш-аффинность — задаче выгодно возвращаться на «своё» ядро.
2. Где хранить очередь задач — одна общая на всех или по одной на ядро.
3. Балансировка — что делать, когда одни ядра завалены, а другие простаивают.

Разберём по порядку, а в конце увидим, что планировщик Go (GMP) решает ровно эти же задачи — слово в слово.

Кэш и аффинность: почему ядру важно «своё» ядро

Сначала про кэш (cache) — это маленькая сверхбыстрая память прямо внутри ядра. Оперативка (RAM) по меркам процессора медленная: сходить в неё — это сотни тактов. Кэш в десятки раз быстрее, но и крошечный. Когда задача работает, ядро постепенно затаскивает её данные в свой кэш — кэш «нагревается».

Бытовая аналогия: повар (ядро) готовит блюдо (задача). Все нужные продукты он разложил на своём столе под рукой (кэш). Пока он на этом столе — всё быстро.

   Ядро 0                         RAM (медленно, ~200 тактов)
 ┌──────────┐                  ┌────────────────────────────┐
 │  CPU     │   <--- быстро    │  все данные процесса A      │
 │  ┌────┐  │   (~3 такта)     │  ............................│
 │  │кэш │◄─┼──── горячие ─────┼─ копии нужных строк        │
 │  │ A  │  │     данные A     │                            │
 │  └────┘  │                  └────────────────────────────┘
 └──────────┘

Что нарисовано: ядро 0 гоняло задачу A и набило свой кэш её данными. Доступ к кэшу — единицы тактов, к RAM — сотни. Пока A на ядре 0, она летает.

Теперь планировщик решает перекинуть A на ядро 1. Кэш ядра 1 про A ничего не знает — он «холодный». A снова полезет в медленную RAM и будет тормозить, пока не нагреет новый кэш. Это потеря кэш-аффинности (cache affinity) — свойства задачи быстрее работать на том ядре, где её данные уже в кэше.

   Ядро 0 (кэш A горячий)        Ядро 1 (кэш про A пустой)
 ┌──────────┐                  ┌──────────┐
 │  ┌────┐  │   миграция A     │  ┌────┐  │
 │  │ A  │  │ ───────────────► │  │ ?? │  │  ← снова бежим в RAM,
 │  └────┘  │   кэш потерян    │  └────┘  │    всё тормозит
 └──────────┘                  └──────────┘

Что нарисовано: перенос задачи на другое ядро обнуляет выгоду от прогретого кэша. Вывод простой: по возможности возвращай задачу на то же ядро.

Одна общая очередь vs очередь на каждое ядро

Где держать список готовых к запуску задач? Два подхода.

Single Queue (SQMS, общая очередь). Одна очередь на всю систему, все ядра тянут задачи из неё.

                 ┌───────────────────────────────┐
                 │   ОБЩАЯ ОЧЕРЕДЬ (один lock)    │
                 │   [ A ][ B ][ C ][ D ][ E ]    │
                 └───┬───────┬───────┬───────┬────┘
                     │       │       │       │
                 ┌───▼──┐ ┌──▼───┐ ┌─▼────┐ ┌▼─────┐
                 │Ядро0 │ │Ядро1 │ │Ядро2 │ │Ядро3 │
                 └──────┘ └──────┘ └──────┘ └──────┘

Что нарисовано: все 4 ядра лезут в одну очередь. Плюс — простота и автоматическая балансировка (свободное ядро просто берёт следующую задачу). Минусы серьёзные:

• Блокировка (lock). Очередь — общий ресурс, её надо защищать мьютексом (про это в locks-hardware). Чем больше ядер, тем сильнее они дерутся за один замок. Это плохая масштабируемость: добавил ядер — выигрыша почти нет, все стоят в очереди за локом.
• Cache bouncing (метание кэша). Задача A в этот раз досталась ядру 0, в следующий — ядру 2, потом ядру 1. Аффинность не сохраняется, кэш постоянно холодный.

  Шаг 1:  A → Ядро0      Шаг 2:  A → Ядро2      Шаг 3:  A → Ядро1
  кэш греется на 0       кэш на 0 выброшен,     опять холодный старт
                         греем заново на 2
  ── задача A «скачет» по ядрам, кэш всё время теряется → cache bouncing

Что нарисовано: при общей очереди одна и та же задача каждый раз попадает на случайное ядро и нигде не успевает прогреть кэш.

Multi Queue (MQMS, очередь на ядро). У каждого ядра — своя локальная runqueue (очередь готовых задач) со своим локом.

 ┌──────────┐  ┌──────────┐  ┌──────────┐  ┌──────────┐
 │ Ядро 0   │  │ Ядро 1   │  │ Ядро 2   │  │ Ядро 3   │
 │ ┌──────┐ │  │ ┌──────┐ │  │ ┌──────┐ │  │ ┌──────┐ │
 │ │[A][C]│ │  │ │[B][E]│ │  │ │[D]   │ │  │ │      │ │
 │ └──────┘ │  │ └──────┘ │  │ └──────┘ │  │ └──────┘ │
 │ свой lock│  │ свой lock│  │ свой lock│  │ свой lock│
 └──────────┘  └──────────┘  └──────────┘  └──────────┘

Что нарисовано: задачи закреплены за ядрами, каждое ядро работает со своей очередью и своим локом. Драки за общий замок нет → масштабируется отлично. И аффинность сохраняется: A всё время крутится на ядре 0, кэш горячий. Почти все современные планировщики (включая Linux CFS) — multi-queue.

Балансировка и work-stealing

У multi-queue есть своя плата: очереди могут перекоситься. Одно ядро завалено задачами, другое доделало все свои и простаивает. А простой ядра — это потеря пропорциональности и пропускной способности.

Решение — балансировка нагрузки (load balancing). Самый ходовой механизм — work-stealing (кража работы): простаивающее ядро не сидит без дела, а заглядывает в очередь к занятому соседу и крадёт часть его задач.

 ДО:
 ┌──────────┐                         ┌──────────┐
 │ Ядро 0   │                         │ Ядро 1   │
 │[A][B][C] │   ← завалено            │  (пусто) │ ← простаивает
 │[D]       │                         │          │
 └──────────┘                         └──────────┘
 
 Ядро 1 видит, что у него пусто, и КРАДЁТ половину очереди ядра 0:
 
 ПОСЛЕ (work-stealing):
 ┌──────────┐         украли          ┌──────────┐
 │ Ядро 0   │   ───────────────►      │ Ядро 1   │
 │[A][B]    │   половину задач         │[C][D]    │
 └──────────┘                         └──────────┘

Что нарисовано: пустое ядро 1 само пошло и забрало половину задач у перегруженного ядра 0. Теперь оба заняты. Важная деталь: крадут обычно половину (или хотя бы несколько задач), а не одну — иначе ядро будет бегать за работой слишком часто и снова упрётся в локи. И крадёт именно простаивающий: пока задачи есть, лезть к соседу незачем (это бьёт по аффинности). Баланс: красть слишком часто — дорого и рушит кэш; слишком редко — ядра простаивают.

Мост в Go: планировщик GMP

Тут начинается самое интересное для backend-инженера. Рантайм Go реализует ровно эту схему у себя в userspace. Его модель называется GMP:

• G (goroutine) — горутина, твоя дешёвая «задача». Это аналог задачи/процесса из этой главы. Их могут быть миллионы. Подробно — в goroutines.
• M (machine) — поток ОС (OS thread). Именно M реально исполняется на ядре процессора. Это «рабочий».
• P (processor) — логический процессор Go, абстрактный «слот» на право выполнять код. Их количество = GOMAXPROCS (по умолчанию число ядер). У каждого P есть своя локальная очередь горутин — это и есть наша per-CPU runqueue.

Чтобы M (поток) исполнял горутины, ему нужно захватить P. Грубо: P — это «руки», M — «мышцы», G — «работа».

   P0 (лок. очередь)      P1 (лок. очередь)      Глобальная очередь G
   [G1][G2][G3]           [G4][G5]               [G99][G100]...
       │                      │                  (общий запас, как SQMS,
   ┌───▼───┐              ┌───▼───┐               берут когда локальная пуста)
   │  M0   │              │  M1   │
   └───┬───┘              └───┬───┘
   ┌───▼───┐              ┌───▼───┐
   │Ядро 0 │              │Ядро 1 │
   └───────┘              └───────┘

Что нарисовано: каждый P держит локальную очередь горутин (как MQMS), M исполняет их на реальном ядре. Плюс есть одна глобальная очередь — резервный «общий котёл».

А теперь — узнавание: что делает P, у которого локальная очередь опустела?

 P1 опустошил свою очередь. Алгоритм поиска работы:
   1) заглянуть в ГЛОБАЛЬНУЮ очередь
   2) проверить сеть (netpoller) — готовые с I/O горутины
   3) WORK-STEALING: украсть ПОЛОВИНУ горутин у случайного другого P
 
   P0:[G1][G2][G3][G4]                    P1:(пусто)
                       \  украли половину  /
   P0:[G1][G2]   ─────────────────────►   P1:[G3][G4]

Что нарисовано: голодный P крадёт половину очереди у соседа — буквально тот же work-stealing, что и в ядре ОС. Go даже использует то же правило «забираем половину».

То есть планировщик Go — это многоядерный планировщик в миниатюре, живущий внутри твоего процесса: локальные очереди на P (аффинность + масштабируемость), глобальная очередь как страховка, work-stealing для балансировки. Глубокий разбор — в scheduler-deep.

Итог

На многих ядрах планировщик решает не только «кого пускать», но и «где». Общая очередь проста, но не масштабируется и теряет кэш; очереди на ядро масштабируются и хранят аффинность, но требуют балансировки через work-stealing. Ровно эту конструкцию ты используешь каждый день, запуская горутины: Go-рантайм — это многоядерный планировщик у тебя в процессе.

Что спрашивают на собесе

• Что такое кэш-аффинность и почему миграция задачи между ядрами стоит дорого.
• Чем плоха одна общая очередь на много ядер (драка за lock, cache bouncing) и почему современные планировщики используют per-CPU очереди.
• Что такое work-stealing, кто у кого крадёт и почему обычно крадут именно половину очереди.
• Расшифруй GMP: что такое G, M, P и зачем у каждого P своя локальная очередь.
• Как Go-рантайм балансирует горутины: локальная очередь → глобальная → кража у соседнего P.
• Связь с метриками из scheduling: почему простаивающее ядро бьёт по пропускной способности.