CS Notes

scheduler

16 min read

Планировщик

← Файловые системы | Права доступа и capabilities →

Файловая система решила задачу хранения данных: программа вызывает write(fd, buf, size), а ядро превращает это в блоки на диске. Но остаётся открытый вопрос: если на машине 400 потоков и 4 ядра, кто решает, какой поток выполняется прямо сейчас?

Кажется, что CPU делится между потоками поровну — сколько потоков, во столько раз меньше доля каждого. На самом деле делится неравномерно по сложной формуле, и это оптимум при конфликте трёх целей: справедливости, латентности интерактивных задач и пропускной способности вычислительных. Планировщик принудительно забирает процессор у одной программы и передаёт другой, даже если та не хочет отдавать — именно эта формула определяет, у кого и когда. Какой поток из 400 выбрать? По какому принципу отмерять время?

Три конкурирующие цели

Планировщик процессов (process scheduler) распределяет процессорное время между потоками. У этой задачи три цели, и они конфликтуют друг с другом.

Справедливость (fairness): каждый поток должен получить процессорное время, пропорциональное его приоритету. Ни один поток не должен голодать — бесконечно ждать, пока другие используют CPU.

Латентность (latency): интерактивные потоки — терминал, GUI (Graphical User Interface), веб-сервер, ожидающий ввод пользователя — должны получать процессор быстро после пробуждения. Пользователь нажал клавишу — терминал обязан ответить за миллисекунды, а не ждать, пока 399 других потоков доработают свои кванты.

Пропускная способность (throughput): вычислительные задачи — компиляция, рендеринг, machine learning — хотят максимум процессорного времени без частых переключений, потому что каждое переключение — потерянные микросекунды.

Оптимизировать все три одновременно невозможно. Частое переключение улучшает латентность, но снижает пропускную способность из-за накладных расходов. Редкое переключение повышает throughput, но интерактивные задачи простаивают. Вся история планировщиков — поиск баланса между этими тремя силами.

Переключение контекста

Планировщик передаёт процессор от одного потока к другому через переключение контекста (context switch). Эта операция не бесплатна: переключение между потоками одного процесса занимает 1-3 мкс, между потоками разных процессов — 3-10 мкс. На машине с KPTI (защита от уязвимости Meltdown) добавляются дополнительные переключения таблиц страниц, что на тяжёлых syscall-нагрузках увеличивает стоимость на 20-30%; на современных процессорах с поддержкой PCID (идентификаторы пространств адресов) этот overhead существенно меньше.

Из чего складывается эта стоимость? Переключение — три шага.

Первый шаг — сохранение состояния текущего потока. Ядро помещает значения регистров общего назначения (rax, rbx, rcx, …, r15), указатель инструкций (rip), указатель стека (rsp), регистр флагов (rflags) и расширенные векторные регистры — FPU (Floating Point Unit), SSE (Streaming SIMD Extensions), AVX (Advanced Vector Extensions) — в структуру task_struct текущего потока. Эти регистры — расширенные регистровые файлы процессора для вещественной арифметики и SIMD-вычислений: на современных CPU они добавляют сотни байт к состоянию потока (а при включённом AVX-512 — ещё больше).

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

Третий шаг зависит от того, принадлежат ли потоки одному процессу. Если оба потока работают в одном адресном пространстве (флаг [[linux/foundations/threads#linux-потоков-не-существует|CLONE_VM]] при создании), переключение завершено — CR3 не меняется, таблица страниц остаётся прежней. Если потоки принадлежат разным процессам, ядро загружает новое значение в регистр CR3, указывая процессору на другую таблицу страниц. Смена CR3 сбрасывает TLB (Translation Lookaside Buffer) — кэш, хранящий трансляции виртуальных адресов в физические. После сброса каждый первый доступ к памяти проходит через полную аппаратную трансляцию (page walk), что стоит десятки наносекунд на каждое обращение.

переключение контекста:

поток A (выполняется)                     поток B (ожидает)
  rax, rbx, ..., rip                       task_struct B
         |                                     |
         v                                     |
  save -> task_struct A                        |
                                               |
  switch kernel stack:  A.stack -> B.stack     |
                                               |
  if (разные процессы):                        |
    CR3 = B.pgd  ---> TLB flush               |
                                               |
  restore <- task_struct B                     |
         |                                     v
         v
  поток B (выполняется)                   поток A (ожидает)

На сервере с 50 000 переключений контекста в секунду при средней стоимости 5 мкс на переключение накладные расходы составляют 250 мс процессорного времени в секунду — четверть одного ядра уходит только на переключения. Поэтому планировщик не может передавать процессор после каждой инструкции — нужен алгоритм, балансирующий между отзывчивостью и накладными расходами.

Когда происходит переключение

Планировщик забирает процессор у потока в двух ситуациях.

Добровольная уступка

Поток вызывает блокирующий системный вызов: read() на пустом сокете, sleep(), wait() для ожидания завершения дочернего процесса, futex_wait() для ожидания мьютекса. Ядро переводит поток в состояние SLEEPING и вызывает планировщик, чтобы тот выбрал следующий поток для выполнения. Когда данные в сокете появятся или таймер сработает — ядро разбудит поток и вернёт его в очередь на выполнение.

Большинство потоков на типичном сервере спят. Из 400 потоков на машине одновременно готовы к исполнению (runnable) обычно 5-20 — остальные ожидают сетевого ввода, таймеров или блокировок. Веб-сервер проводит в ожидании сети 99%+ времени.

Вытеснение

Аппаратный таймер (programmable interrupt timer) генерирует прерывание с частотой 250-1000 Гц (в зависимости от конфигурации ядра, параметр CONFIG_HZ). При каждом тике таймера процессор прерывает текущий поток и передаёт управление обработчику прерывания в ядре. Обработчик вызывает планировщик, который проверяет: стоит ли заменить текущий поток? Если да — происходит переключение контекста. Если нет — текущий поток продолжает работу.

Это и есть вытеснение (preemption): поток теряет процессор не потому, что сам решил отдать, а потому, что ядро забрало.

Вытесняющее и кооперативное планирование

До середины 90-х большинство ОС использовали кооперативное планирование (cooperative scheduling): поток работает, пока сам не вернёт управление — через блокирующий вызов или явный yield(). Одна зависшая программа блокировала всю систему, потому что ядро не могло отобрать процессор. Именно это регулярно случалось в ранних версиях Windows (до Windows 95) и Mac OS (до Mac OS X).

При вытесняющем планировании (preemptive scheduling) ядро прерывает поток принудительно через аппаратный таймер. Linux использует вытесняющую модель. Зависший поток получит свой тик таймера, ядро увидит, что он исчерпал отведённое время, и переключит на другой.

У вытеснения есть критическое следствие для программиста: поток может быть прерван между любыми двумя инструкциями. Не между вызовами функций, не между строками исходного кода — между любыми двумя машинными инструкциями. Операция x += 1 на уровне машинного кода — это три инструкции: mov (загрузить значение из памяти в регистр), add (прибавить единицу), mov (записать результат обратно). Планировщик может прервать поток после чтения, но до записи. Если другой поток в этот момент изменит ту же переменную — результат непредсказуем. Именно поэтому существуют гонки данных (race conditions) и именно поэтому нужны примитивы синхронизации: мьютексы (mutual exclusion — механизм, не дающий двум потокам одновременно исполнять критический участок кода), атомарные операции, барьеры памяти — весь пласт инструментов для защиты от непредсказуемых прерываний в произвольный момент.

Наивный подход: round-robin

Простейший алгоритм — круговой обход (round-robin): каждый поток получает фиксированный квант времени (time slice), например 10 мс, после чего процессор передаётся следующему в очереди.

На 4 ядрах с 400 потоками арифметика неутешительна: 400 потоков / 4 ядра = 100 потоков на ядро. Один полный круг: 100 * 10 мс = 1000 мс. Поток нажатия клавиши в терминале, пробудившись после ожидания ввода, встаёт в конец очереди из 99 потоков. В худшем случае он ждёт 990 мс — почти секунду — прежде чем получит процессор. Терминал, который реагирует на нажатие клавиши через секунду, непригоден для работы.

Уменьшить квант? При кванте 1 мс полный круг — 100 мс, латентность терпимая. Но переключение контекста стоит 1-10 мкс, и при кванте 1 мс накладные расходы составляют 0.1-1% процессорного времени. При 0.1 мс — уже 1-10%. Вычислительные задачи теряют ощутимую долю производительности на переключениях.

Round-robin не может дать и справедливость, и низкую латентность, и высокий throughput. Фиксированный квант — слишком грубый инструмент. Нужна идея, которая убирает квант как таковой и ставит вопрос иначе: не «сколько времени следующему потоку?», а «кто из всех потоков получил меньше всего?».

CFS: Completely Fair Scheduler

С версии ядра 2.6.23 (2007, автор Ingo Molnar) до версии 6.5 включительно Linux использовал CFS (Completely Fair Scheduler, полностью справедливый планировщик). В ядре 6.6 (октябрь 2023) CFS заменён на EEVDF — об этом ниже. Но принципы CFS остаются фундаментом: EEVDF развивает ту же идею виртуального времени, добавляя к ней дедлайны. Сама эта идея виртуального времени и рождается в CFS.

Идея CFS — отказаться от фиксированных квантов и вместо этого отслеживать, сколько процессорного времени каждый поток уже получил.

vruntime: виртуальное время выполнения

Центральное понятие CFS — vruntime (virtual runtime, виртуальное время выполнения). Это число наносекунд, которое поток «считает» за собой как использованное процессорное время. Для потока с обычным приоритетом vruntime растёт с той же скоростью, что и реальное время: 1 мс на процессоре = +1 мс к vruntime.

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

Пока поток выполняется — его vruntime растёт. Пока поток спит (ожидает I/O, таймер, блокировку) — vruntime не изменяется. Это создаёт разрыв: вычислительный поток, непрерывно работающий на CPU, накапливает высокий vruntime. Интерактивный поток, проводящий 99% времени в ожидании ввода, сохраняет низкий vruntime.

Красно-чёрное дерево

CFS хранит все готовые к исполнению (runnable) потоки в красно-чёрном дереве (BST, самобалансирующийся вариант), упорядоченном по vruntime. Поток с минимальным vruntime находится в самом левом узле дерева. Ядро кеширует указатель на этот узел — поэтому выбор следующего потока занимает O(1), без обхода дерева. Добавление и удаление потока стоят O(log n).

            vruntime
              |
     +--------+--------+
     |                  |
  [vrt=50]          [vrt=120]
   /    \            /     \
[vrt=30] [vrt=70] [vrt=100] [vrt=200]
  ^
  |
  самый левый -- следующий на выполнение

При 400 потоках на машине runnable в каждый момент обычно 5-20. Дерево из 20 элементов — высота 4-5, операции над ним занимают десятки наносекунд. Стоимость решения планировщика пренебрежимо мала по сравнению со стоимостью самого переключения контекста.

Когда переключать

CFS не переключает поток после фиксированного кванта. Вместо этого при каждом тике таймера (или при пробуждении потока) CFS сравнивает vruntime текущего потока с vruntime самого «обделённого» потока в дереве. Если разница превышает порог — происходит переключение.

Порог определяется двумя параметрами: sched_latency и sched_min_granularity (эти параметры действуют в ядрах до 6.5; в EEVDF они заменены на base_slice — см. раздел ниже). Параметр sched_latency (типичное значение 6-24 мс в зависимости от дистрибутива и конфигурации) задаёт целевой период, за который каждый runnable-поток должен получить хотя бы один квант процессора. Идеальный квант: sched_latency / число_runnable_потоков.

4 runnable-потока + sched_latency 6 мс = квант ~1.5 мс на каждый. 8 потоков — ~0.75 мс. Но при 100 runnable-потоках квант стал бы 0.06 мс (60 мкс) — слишком мало, накладные расходы на переключение сожрут полезное время. Поэтому существует sched_min_granularity (mainline default 0.75 мс, встречаются значения до 4 мс у тюнинг-профилей дистрибутивов) — минимальный квант, ниже которого CFS не переключает. При 100 runnable-потоках каждый получит этот минимум, а полный «круг» растянется соответственно.

В ядрах до 6.5 текущие значения этих параметров на конкретной машине можно посмотреть в /proc/sys/kernel/sched_latency_ns и /proc/sys/kernel/sched_min_granularity_ns.

Интерактивная отзывчивость

Представим сценарий: на сервере параллельно идёт компиляция ядра Linux (make -j4, 4 потока, каждый непрерывно потребляет CPU) и открыт терминал, в котором пользователь набирает команды.

Поток терминала спит в системном вызове read(), ожидая ввода с клавиатуры. Его vruntime не растёт. Четыре потока компиляции работают непрерывно, их vruntime увеличивается каждую наносекунду.

Пользователь нажимает клавишу. Контроллер клавиатуры генерирует аппаратное прерывание. Ядро обрабатывает прерывание, помещает символ в буфер терминала, будит поток терминала — переводит его из SLEEPING в RUNNING и вставляет в красно-чёрное дерево планировщика. vruntime этого потока значительно ниже, чем у любого из потоков компиляции — он спал секунды, пока они работали.

CFS видит: в дереве появился поток с vruntime намного меньше, чем у текущего. Разница превышает порог. CFS немедленно вытесняет текущий поток компиляции и передаёт процессор терминалу. На практике время от прерывания клавиатуры до начала исполнения потока терминала составляет единицы микросекунд.

Терминал обрабатывает символ, отправляет echo на экран и снова вызывает read() — засыпает. CFS возвращает процессор потокам компиляции. Весь эпизод занял десятки микросекунд — потоки компиляции потеряли ничтожную долю времени, а пользователь получил мгновенную реакцию.

Именно поэтому терминал остаётся отзывчивым во время тяжёлой компиляции. CFS не назначает интерактивным потокам специальный приоритет — механизм vruntime делает это автоматически: кто мало работал, тот получает процессор первым.

При пробуждении после длительного сна vruntime потока может оказаться настолько низким, что поток получит непропорционально большой квант. Чтобы этого избежать, CFS ограничивает vruntime при пробуждении: устанавливает его не ниже min_vruntime текущей очереди минус sched_latency. Поток получает приоритет, но не бесконечный.

Приоритеты: nice и весовые коэффициенты

Не все потоки равнозначны. Фоновая индексация файлов не должна забирать столько же CPU, сколько веб-сервер, обслуживающий клиентов. В Unix-системах приоритет обычных (не реального времени) потоков задаётся значением nice — целым числом от -20 (высший приоритет) до +19 (низший).

Название отражает «вежливость»: поток с nice +19 максимально «вежлив» и уступает процессор остальным. Поток с nice -20 «невежлив» и берёт максимум. Значение по умолчанию — 0.

CFS преобразует nice в весовые коэффициенты (weights). Каждое значение nice соответствует числовому весу из таблицы ядра sched_prio_to_weight. Ключевое соотношение: каждый шаг nice отличается примерно в 1.25 раза. nice 0 соответствует вес 1024, nice -1 — примерно 1277, nice +1 — примерно 820.

Вес влияет на скорость роста vruntime. Для потока с весом w вычисление vruntime выглядит так:

delta_vruntime = delta_exec * (NICE_0_WEIGHT / weight)

где delta_exec — реально проведённое на CPU время, а NICE_0_WEIGHT = 1024 (вес nice 0). Поток с высоким весом (низкий nice, высокий приоритет) накапливает vruntime медленнее, поэтому дольше остаётся «обделённым» в глазах CFS и получает больше процессорного времени.

Конкретный пример: два потока, один с nice 0 (вес 1024), другой с nice +5 (вес ~335). Отношение весов: 1024 / 335 = ~3.06. CFS распределит процессорное время в соотношении примерно 3:1 — первый поток получит ~75% CPU, второй ~25%. При этом оба потока считают, что система «справедлива»: каждый получает время пропорционально своему весу.

Только root может устанавливать отрицательные значения nice (повышать приоритет). Обычный пользователь может только увеличивать nice (понижать приоритет) своих процессов. Утилита nice задаёт приоритет при запуске: nice -n 15 make -j4 запустит компиляцию с пониженным приоритетом. Утилита renice меняет nice работающего процесса: renice -n 10 -p 1234.

EEVDF: наследник CFS

У CFS есть слабое место: единственный критерий выбора — vruntime. Коротким интерактивным задачам и длинным вычислительным задачам назначался квант одинаковой природы, а настройки справедливости и латентности задавались эвристиками (sched_latency, sched_min_granularity). На смешанной нагрузке эти эвристики подводят — либо интерактивность страдает, либо вычислительные задачи теряют в пропускной способности.

EEVDF (Earliest Eligible Virtual Deadline First, выбор по ближайшему допустимому виртуальному дедлайну) — ответ на эту проблему. Сохраняет ключевую идею CFS — виртуальное время выполнения и красно-чёрное дерево — но добавляет к vruntime второе измерение: виртуальный дедлайн (virtual deadline). Вместо эвристик ядро вычисляет для каждого потока VD = eligible_time + slice (оба слагаемых — в единицах виртуального времени, где вес уже учтён через vruntime) и выбирает поток с наименьшим VD среди допустимых (eligible) — тех, чей vruntime не опережает справедливое значение. Модель «nice → weight → vruntime» остаётся основой; меняется способ выбора следующего runnable-потока и latency knobs, которыми эта справедливость настраивается. В ядрах с 6.6 планировщик обычных задач (SCHED_NORMAL) — именно EEVDF.

Ключевое отличие: поток с коротким slice получает более ранний дедлайн и обслуживается раньше — без специальных эвристик для интерактивности. Откуда у интерактивного потока берётся приоритет автоматически? Пока поток спал в ожидании ввода, его vruntime не рос, и к моменту пробуждения он отстал от справедливого значения — накопил отрицательный lag. Это даёт ему более раннее eligible_time: он становится допустимым раньше прочих, и его виртуальный дедлайн VD = eligible_time + slice оказывается раньше, чем у непрерывно работавшего вычислительного потока. Тот же механизм «кто мало работал, тот идёт первым», что давал низкий vruntime в CFS, здесь выражается через раннее eligible_time. Дефолтная длина кванта одинакова для всех: параметр base_slice (по умолчанию 3 мс) заменяет sched_min_granularity. Короткий персональный slice поток получает не сам собой, а запросив его у ядра через системный вызов sched_setattr().

На практике для большинства серверных и десктопных нагрузок поведение EEVDF близко к CFS. Разница заметна на нагрузках со смешанными латентными и вычислительными задачами, где EEVDF обеспечивает более предсказуемую латентность без ручной настройки.

Политики реального времени

SCHED_NORMAL оптимизирует среднее время ожидания. Но аудиопоток, заполняющий аппаратный буфер каждые 5 мс, или контроллер мотора, реагирующий на датчик за сотни микросекунд, живут по наихудшему случаю — джиттер в 1-2 мс даёт глич в звуке или сорванное управление. Для таких задач Linux предоставляет отдельный класс: SCHED_FIFO и SCHED_RR. Приоритет — 1-99 (требует root), строго выше любого SCHED_NORMAL: поток SCHED_FIFO с приоритетом 1 вытеснит поток SCHED_NORMAL даже с nice -20. SCHED_FIFO не уступает CPU, пока сам не заблокируется; SCHED_RR — round-robin с квантом ~100 мс в пределах одного приоритета. Ошибка в RT-потоке опасна: бесконечный цикл блокирует ядро полностью, поэтому ядро резервирует 5% CPU для не-RT задач (sched_rt_runtime_us / sched_rt_period_us = 950000/1000000 по умолчанию — RT может использовать 95% ядра).

Многоядерность и привязка

На N-ядерной машине планировщик держит N runqueue — по одной на ядро, без глобальной блокировки. Балансировщик ядра периодически (~каждые 4 мс и при уходе ядра в idle) выравнивает длины очередей, но с учётом cache affinity: поток, недавно работавший на ядре 0, предпочитается тому же ядру — миграция стоит холодного L1/L2 кеша (в 10-50 раз медленнее на первых обращениях). На NUMA-системах (Non-Uniform Memory Access — несколько сокетов, у каждого своя RAM, ~80 нс local vs ~140 нс remote) ядро старается держать поток рядом с его памятью. Ручная привязка — taskset -c 0,1 ./worker или sched_setaffinity(); для многопроцессных нагрузок вроде PostgreSQL часто эффективнее numactl --interleave=all.

Наблюдение

Состояние и статистика — /proc/<pid>/status (счётчики voluntary_ctxt_switches vs nonvoluntary_ctxt_switches: I/O-bound vs CPU-bound), /proc/<pid>/sched (детали vruntime и текущая очередь). vmstat 1 показывает общий темп переключений. Для разбора проблем — perf sched record && perf sched latency: распределение латентности пробуждения, где видно, если поток регулярно мигрирует между NUMA-узлами или стоит в очереди дольше ожидаемого.

См. также

  • Ruby GVL timer thread — внутренний timer thread устанавливает флаг каждые ~100мс, заставляя текущий Ruby-поток освободить GVL и позволить другому получить CPU

Sources

← Файловые системы | Права доступа и capabilities →

Graph View

Backlinks