Планирование на многоядерных

Что меняется, когда ядер много

До сих пор планировщик выбирал задачу для одного ядра CPU. Ноутбук, на котором вы это читаете, имеет 8 или больше ядер, сервер в проде — 32, 64, 128. Появляется второй вопрос: не только кого запускать, но и где.

Вместе с ним приходят три проблемы, которых на одном ядре не было:

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

В конце главы окажется, что планировщик горутин в Go решает ровно эти три задачи теми же приёмами.

Кэш и аффинность

У каждого ядра CPU есть свой кэш — маленькая быстрая память рядом с вычислительным блоком. Порядок цен: обращение к кэшу первого уровня занимает несколько тактов, к оперативной памяти — сотни. Пока задача работает на ядре, её данные постепенно оседают в кэше этого ядра, и она ускоряется. Говорят, что кэш «прогрелся».

   Ядро 0                            RAM (сотни тактов)
 ┌───────────┐                   ┌──────────────────────┐
 │  CPU      │                   │  все данные задачи A  │
 │  ┌─────┐  │  несколько тактов │                      │
 │  │кэш  │◄─┼───── горячие ─────┼─ копии нужных строк   │
 │  │ A   │  │     данные A      │                      │
 │  └─────┘  │                   └──────────────────────┘
 └───────────┘

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

Одна очередь на всех

Первый вариант: одна общая очередь готовых задач на всю систему (в литературе SQMS, single-queue multiprocessor scheduling). Освободилось ядро — взяло следующую задачу из очереди.

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

Плюс — простота и автоматическая балансировка: свободное ядро само берёт работу. Минусов два.

Замок. Очередь — общая структура данных, и чтобы два ядра не испортили её одновременными изменениями, её защищают блокировкой (подробно в главе как устроен лок). Чем больше ядер, тем дольше они ждут друг друга у этого замка. Добавили ядер, а производительность почти не выросла.

Потеря аффинности. Задача A в этот раз досталась ядру 0, в следующий — ядру 2, потом ядру 1. Кэш каждый раз холодный.

  Шаг 1: A → Ядро 0     Шаг 2: A → Ядро 2      Шаг 3: A → Ядро 1
  кэш греется на 0      прогрев на 0 пропал    снова холодный старт

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

Второй вариант: у каждого ядра своя очередь (runqueue) со своим замком (MQMS, multi-queue multiprocessor scheduling). Новая задача попадает в одну из очередей и дальше обычно живёт на этом ядре.

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

Ядра не спорят за общий замок, и задачи остаются на своих ядрах с горячим кэшем. Так устроены почти все современные планировщики, включая планировщик Linux.

Перекос нагрузки: пример

У очередей на ядро своя беда. Два ядра, три одинаковые вычислительные задачи A, B, C. Планировщик положил A на ядро 0, а B и C на ядро 1:

  Ядро 0: [ A  A  A  A  A  A  A  A ]   A получает 100 % ядра
  Ядро 1: [ B  C  B  C  B  C  B  C ]   B и C получают по 50 %

Задачи одинаковые, а A работает вдвое быстрее. Если бы задач было две, а одна закончилась, одно ядро вообще простаивало бы, пока у второго есть очередь. Это прямая потеря пропускной способности.

Лекарство — миграция: время от времени переносить задачи между очередями. Для трёх задач на двух ядрах выход — переносить задачу по кругу: какое-то время A делит ядро с B, потом с C, и в среднем каждая получает по 2/3 ядра.

Распространённый способ миграции — кража работы (work stealing). Ядро, у которого очередь опустела, само заглядывает в очередь к соседу и забирает часть его задач.

 ДО:
 Ядро 0: [A][B][C][D]  ← перегружено      Ядро 1: (пусто) ← простаивает
 
 ПОСЛЕ кражи половины:
 Ядро 0: [A][B]                           Ядро 1: [C][D]

Обычно крадут не одну задачу, а несколько, например половину: если красть по одной, придётся ходить к соседу слишком часто, а каждый поход — это его замок и холодный кэш для перенесённой задачи. Красть слишком часто дорого, слишком редко — ядра простаивают.

Как это сделано в Linux. Балансировкой занимается планировщик ядра ОС по двум сценариям. Периодически каждое ядро сравнивает свою загрузку с соседями и, если перекос велик, перетягивает задачи к себе. Кроме того, ядро, которое вот-вот уйдёт в простой, сначала пытается забрать работу у загруженного соседа. Соседей перебирают по иерархии: сначала логические ядра одного физического, потом ядра одного процессорного сокета, потом другие сокеты. Переносить задачу на другой сокет дороже всего: у сокета своя память (это называется NUMA), и после переезда задача будет ходить за своими данными в «чужую» память.

Управление размещением вручную

Иногда ОС мешать не нужно, а нужно закрепить процесс за ядрами:

• taskset -c 2,3 ./server запускает процесс только на ядрах 2 и 3 (системный вызов sched_setaffinity);
• в Kubernetes статическая политика CPU manager выдаёт подам класса Guaranteed с целым числом CPU эксклюзивные ядра;
• базы данных и обработчики сетевых пакетов часто закрепляют потоки за ядрами, чтобы не терять кэш и не ходить в чужую NUMA-память.

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

Рантайм Go планирует горутины по той же схеме, но в пространстве пользователя. Модель называется GMP:

• G (goroutine) — горутина, единица работы. Их могут быть сотни тысяч.
• M (machine) — поток ОС. Именно M исполняется на ядре CPU, и именно его планирует ядро ОС.
• P (processor) — логический процессор Go: право исполнять Go-код плюс локальная очередь готовых горутин. Число P равно GOMAXPROCS.

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

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

Локальные очереди P — это очереди на ядро из этой главы: каждый P берёт горутины из своей очереди без общего замка. Глобальная очередь — общий запас; чтобы горутины в ней не голодали, P заглядывает туда регулярно, раз в 61 итерацию планирования, даже если локальная очередь не пуста.

Когда локальная очередь P опустела, он ищет работу так:

  1) глобальная очередь
  2) сеть (netpoller): горутины, чьи сокеты стали готовы
  3) кража: случайный другой P, забрать ПОЛОВИНУ его очереди
 
   P0: [G1][G2][G3][G4]             P1: (пусто)
   P0: [G1][G2]          ──────►    P1: [G3][G4]

Это то самое правило «кради половину». Подробнее о внутреннем устройстве — в курсе Go: горутины и планировщик изнутри.

Сколько P по умолчанию

Обычно GOMAXPROCS равен числу логических ядер, доступных процессу. Начиная с Go 1.25, на Linux рантайм учитывает ещё и CPU-квоту контейнера (cgroup): если у контейнера лимит 4 CPU на ноде с 64 ядрами, GOMAXPROCS будет 4, а не 64. Зачем это нужно и что было раньше — в главе пропорциональное планирование, в разделе про троттлинг.

Частые ошибки

• Считать, что больше ядер автоматически значит быстрее. Если все ядра борются за один замок, выигрыша почти нет.
• Думать, что миграция бесплатна. Перенесённая задача теряет прогретый кэш, а при переезде между сокетами — ещё и близость к своей памяти.
• Ставить GOMAXPROCS больше лимита CPU контейнера «для параллелизма». Это приводит к троттлингу.

Проверьте себя

1. Почему общая очередь плохо масштабируется на 64 ядрах?
2. Два ядра, четыре одинаковые задачи, распределены 3 и 1. Какую долю ядра получает каждая задача? Как это исправить?
3. Зачем красть сразу половину очереди, а не одну задачу?
4. Какой будет GOMAXPROCS у Go 1.25 на 8-ядерной машине без контейнерных лимитов? А в контейнере с лимитом 1,5 CPU?

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

• Что такое кэш-аффинность и почему миграция задачи между ядрами стоит дорого.
• Общая очередь против очереди на ядро: масштабируемость, аффинность, балансировка.
• Что такое work stealing и почему крадут половину.
• Расшифруйте GMP: что такое G, M, P и зачем у P своя очередь.
• Как Go-рантайм ищет работу для простаивающего P.
• Как GOMAXPROCS связан с CPU-лимитом контейнера.