--- title: "Пропорциональное планирование и CFS" description: "В главах про метрики и MLFQ планировщик гнался за оборотом и откликом. Теперь цель другая: поделить процессор в заданной пропорции. Например, на одной машине работают сервис A…" canonical: https://graphlms.ru/os/book/proportional-scheduling course: "Операционные системы" updated: 2026-10-12 lang: ru publisher: GraphLMS --- # Пропорциональное планирование и CFS > Источник: https://graphlms.ru/os/book/proportional-scheduling — курс «Операционные системы», GraphLMS. ## Другая постановка задачи В главах про [метрики](/os/book/scheduling) и [MLFQ](/os/book/mlfq) планировщик гнался за оборотом и откликом. Теперь цель другая: **поделить процессор в заданной пропорции**. Например, на одной машине работают сервис A, сервис B и фоновые джобы C, и вы хотите, чтобы при полной загрузке A получал 50 % процессорного времени, B — 30 %, C — 20 %. Кто закончит первым, здесь вторично. Такой подход называют **пропорциональным** (proportional share) или **справедливым** (fair share) планированием. Бэкендеру эта глава нужна ради одного практического вопроса: как Linux делит процессор между контейнерами и почему контейнер с лимитом «1 CPU» иногда отвечает с задержкой в сотню миллисекунд при полупустой ноде. Чтобы до него дойти, разберём три механизма от простого к реальному: lottery, stride и планировщик Linux. ## Lottery: розыгрыш билетов Каждой задаче выдаём **билеты** (tickets) пропорционально желаемой доле. На каждом тике планировщик вытягивает случайный билет, и его владелец работает этот квант. ```text Всего 100 билетов: A: номера 0..49 (50 билетов) B: номера 50..79 (30 билетов) C: номера 80..99 (20 билетов) тик: 1 2 3 4 5 6 7 8 9 10 случ.: 63 12 85 41 07 77 90 33 58 21 победил: B A C A A B C A B A ``` За 10 тиков A получила 5 квантов, B — 3, C — 2, ровно 50/30/20. Это повезло: на коротком отрезке вполне могло выйти 7/2/1. Чем длиннее интервал, тем ближе фактические доли к заданным (закон больших чисел), но на коротких интервалах разброс заметный. Достоинства lottery: планировщик почти не хранит состояния (только число билетов), новую задачу добавить легко, а у любой задачи хотя бы с одним билетом есть шанс получить процессор. Недостаток — та самая случайность: за конкретную секунду задача с половиной билетов может получить и 35 %. ## Stride: то же без случайности **Stride scheduling** заменяет розыгрыш расчётом. Каждой задаче назначают **шаг** (stride), обратно пропорциональный числу билетов: ```text stride = БОЛЬШОЕ_ЧИСЛО / tickets ``` У каждой задачи есть счётчик **pass**, сначала 0. На каждом тике: 1. выбрать задачу с минимальным pass (при равенстве — любую, здесь берём по алфавиту); 2. дать ей квант; 3. прибавить к её pass её stride. Пусть у A 100 билетов, у B 50, у C 25, большое число 10 000. Тогда stride у A равен 100, у B 200, у C 400. ```text тик │ выбрали │ pass A │ pass B │ pass C (значения ПОСЛЕ тика) ────┼─────────┼────────┼────────┼──────── 0 │ A │ 100 │ 0 │ 0 1 │ B │ 100 │ 200 │ 0 2 │ C │ 100 │ 200 │ 400 3 │ A │ 200 │ 200 │ 400 4 │ A │ 300 │ 200 │ 400 (A и B по 200, взяли A) 5 │ B │ 300 │ 400 │ 400 6 │ A │ 400 │ 400 │ 400 ────┴─────────┴────────┴────────┴──────── За 7 тиков: A = 4, B = 2, C = 1, то есть 4 : 2 : 1 = 100 : 50 : 25 ``` После тика 6 все pass снова равны, и цикл повторяется. Доли точные на каждом таком цикле, без всякой случайности. У stride есть цена: глобальное состояние. Какой pass дать новой задаче? Если 0, она надолго монополизирует процессор, пока не догонит остальных. Поэтому новой задаче дают текущий минимальный pass в системе. Ровно эту идею использует планировщик Linux. ## Планировщик Linux: vruntime С 2007 по 2023 год в Linux по умолчанию работал **CFS** (Completely Fair Scheduler). В версии ядра 6.6 (конец 2023 года) его алгоритм выбора задачи заменили на **EEVDF**, о нём ниже. Учёт времени в обоих одинаковый, и начать проще с CFS. Вместо pass у каждой задачи есть **vruntime** (виртуальное время выполнения): сколько процессорного времени она получила, пересчитанное с учётом её веса. Основное правило CFS: ```text Запускай задачу с наименьшим vruntime. ``` Это прямой родственник stride: vruntime играет роль pass, «вес» играет роль билетов. ### Вес и nice Приоритет обычного процесса в Linux задаётся числом **nice** от −20 до +19. Чем меньше nice, тем процесс «наглее» и тем больше процессора получает. Ядро переводит nice в **вес** по фиксированной таблице. Несколько значений: | nice | вес | |---|---| | −5 | 3121 | | 0 | 1024 | | 1 | 820 | | 5 | 335 | | 19 | 15 | Соседние значения nice отличаются по весу примерно в 1,25 раза. Пока задача работает, её vruntime растёт так: ```text Δvruntime = Δреальное_время × 1024 / вес ``` У задачи с nice 0 vruntime растёт со скоростью реального времени. У задачи с большим весом медленнее, поэтому она чаще оказывается минимальной и чаще запускается. **Пример.** На одном ядре CPU две вычислительные задачи: A с nice 0 (вес 1024) и B с nice 5 (вес 335). Доли процессора пропорциональны весам: ```text A: 1024 / (1024 + 335) ≈ 75 % B: 335 / (1024 + 335) ≈ 25 % ``` Проверим через vruntime. За 30 мс работы vruntime A вырастет на 30 мс. Задаче B, чтобы её vruntime вырос на те же 30 мс, хватит 30 × 335 / 1024 ≈ 9,8 мс реального времени. Планировщик держит vruntime обеих примерно равными, значит, на каждые 30 мс работы A приходится около 10 мс работы B: те же 75 на 25. Для эксперимента на Linux: `nice -n 5 ./worker` запускает процесс с nice 5, `renice` меняет nice работающего процесса, а `top` показывает значение в колонке `NI`. ### Как выбирается задача с минимумом Задачи, готовые к запуску, CFS хранит в **красно-чёрном дереве** (сбалансированном дереве поиска), упорядоченном по vruntime. Самый левый узел — минимум. ```text (150) / \ (145) (210) / (120) ← самый левый: запустить следующим ``` Вставка и удаление стоят O(log n), а самый левый узел ядро держит в кэше. Задача поработала, её vruntime вырос, её вставляют обратно правее, а левым становится кто-то другой. Так vruntime всех задач держатся рядом, отсюда «completely fair». Задача, которая долго спала (ждала сеть), не должна потом монополизировать процессор из-за маленького vruntime. Поэтому при пробуждении её vruntime подтягивают к текущему минимуму в дереве: та же идея, что со стартовым pass в stride. ### EEVDF: что изменилось в Linux 6.6 CFS хорошо делил процессор, но плохо управлял **задержкой**: задача, которой нужно поработать 1 мс, но как можно скорее (обработчик звука, сетевой обработчик), не могла об этом сообщить. Её «наказывали» эвристиками и ручными настройками. **EEVDF** (Earliest Eligible Virtual Deadline First) сохраняет vruntime и веса, а выбор задачи делает в два шага: 1. **Право на запуск** (eligible). Ядро считает средневзвешенный vruntime всех готовых задач. Задача имеет право работать, если она недополучила процессор, то есть её vruntime не больше среднего. Задача, которая уже обогнала остальных, ждёт. 2. **Виртуальный дедлайн**. Каждая задача просит квант (slice), по умолчанию несколько миллисекунд. Дедлайн = vruntime + slice × 1024 / вес. Из задач с правом на запуск выбирается та, у которой дедлайн самый ранний. Задача с коротким slice получает ранний дедлайн и запускается раньше, но работает меньше за раз, поэтому её долю в целом это не увеличивает. Доли по-прежнему определяют веса, а задержкой теперь можно управлять отдельно. С ядра 6.12 задача может запросить свой slice через системный вызов `sched_setattr`. Код этого планировщика в ядре по-прежнему называется fair scheduler, и на собеседованиях почти всегда говорят «CFS». Отвечайте про vruntime и веса, а затем уточните, что в ядрах с 6.6 выбор задачи делает EEVDF. Это показывает, что вы знаете актуальное состояние. ## Связь с многоядерностью На машине с несколькими ядрами CPU у каждого ядра своя очередь (своё дерево), и задачи между ними время от времени перекладываются. Почему так и как это делают, разберём в главе [планирование на многоядерных](/os/book/multiprocessor-scheduling). ## Контейнеры: вес и квота Контейнеры в Docker и Kubernetes ограничивают процессор через **cgroups** (control groups) — механизм ядра, который объединяет процессы в группу и управляет её ресурсами. Для процессора два независимых рычага. Имена файлов зависят от версии cgroups; почти все современные дистрибутивы используют cgroup v2. | Что | cgroup v2 | cgroup v1 | Когда действует | |---|---|---|---| | Вес (доля при конкуренции) | `cpu.weight`, 1–10000, по умолчанию 100 | `cpu.shares`, по умолчанию 1024 | только когда процессора не хватает всем | | Квота (потолок) | `cpu.max`: «квота период», например `150000 100000` | `cpu.cfs_quota_us` и `cpu.cfs_period_us` | всегда | **Вес** — это те же билеты, только для группы процессов. Если ядра CPU свободны, группа с маленьким весом берёт сколько хочет. Если не хватает всем, группы делят процессор пропорционально весам. Kubernetes выставляет вес из `requests.cpu`. **Квота** — жёсткий потолок: за каждый период группа может потратить не больше квоты процессорного времени, суммарно по всем ядрам. `cpu.max = 150000 100000` значит «150 мс процессора на каждые 100 мс», то есть 1,5 ядра. Kubernetes выставляет квоту из `limits.cpu`. Когда группа выбрала квоту до конца периода, все её потоки замораживаются до начала следующего. Это **троттлинг** (throttling). ### Троттлинг на числах Контейнер с лимитом 1 CPU: квота 100 мс на период 100 мс. Нода на 8 ядер, сервис на Go до версии 1.25, поэтому `GOMAXPROCS = 8`: рантайм готов исполнять код на 8 потоках одновременно. Приходит запрос, который параллельно обрабатывает 8 горутин, каждой нужно 15 мс процессора. ```text период 100 мс 0 мс 12,5 мс 100 мс |█ 8 потоков █|░░░░░░░░░░ троттлинг, все потоки стоят ░░░░|█ ... квота 100 мс выбрана за 12,5 мс (8 × 12,5 = 100) ``` За первые 12,5 мс восемь потоков потратили 8 × 12,5 = 100 мс процессора, то есть всю квоту. До конца периода группа стоит, хотя на ноде свободны другие ядра. Каждой горутине осталось досчитать 2,5 мс, они сделают это в начале следующего периода. Запрос, которому нужно 15 мс работы, ответил примерно через 103 мс. В метриках это выглядит как «пила» на p99 при низкой средней загрузке. Проверить, что дело в троттлинге, можно по файлу `cpu.stat` группы: поля `nr_throttled` (сколько периодов закончились троттлингом) и `throttled_usec` (сколько времени группа стояла). Лекарства: согласовать параллелизм с квотой (`GOMAXPROCS` не больше лимита), поднять лимит или убрать его, оставив только вес. С Go 1.25 рантайм на Linux делает первое сам: по умолчанию `GOMAXPROCS` равен меньшему из числа доступных ядер и квоты cgroup, округлённой вверх (но не меньше 2), и пересчитывается, если лимит поменяли. Это работает, если в `go.mod` указана версия Go 1.25 или новее и `GOMAXPROCS` не задан вручную. ## Сравнение механизмов | Критерий | Lottery | Stride | CFS / EEVDF (Linux) | |---|---|---|---| | Природа | случайная | детерминированная | детерминированная | | Ключ выбора | случайный билет | минимальный pass | минимальный vruntime / ранний дедлайн | | Структура | список | список или куча | красно-чёрное дерево | | Приоритет | билеты | билеты | nice → вес | | Точность доли | в среднем | точная | точная | | Где встретить | учебники | учебники | любой Linux-сервер | > Квиз по разделу: см. вопросы в конце документа или на https://graphlms.ru/os/book/proportional-scheduling ## Частые ошибки - Путать вес и квоту. Вес (`cpu.weight`, `requests`) работает только при нехватке процессора, квота (`cpu.max`, `limits`) режет всегда. - Считать, что лимит 2 CPU значит «процесс может использовать 2 ядра». Он значит «200 мс процессора за 100 мс», и эти 200 мс можно выбрать восемью потоками за 25 мс, после чего стоять. - Думать, что nice 19 полностью останавливает процесс. Он получает мало (вес 15 против 1024), но не ноль. - Говорить, что Linux «в любом ядре» использует CFS: с 6.6 выбор делает EEVDF. ## Проверьте себя 1. Lottery, у A 75 билетов, у B 25. Какую долю процессора получит A в среднем? 2. Stride: у A 200 билетов, у B 100, большое число 1000. Найдите stride и последовательность первых трёх запусков (при равенстве берём A). 3. Две задачи с nice 0 и nice 1. Какие доли процессора они получат? 4. `cpu.max = 50000 100000`. Сколько это ядер? Сколько миллисекунд в каждом периоде группа простоит, если её 4 потока непрерывно хотят считать? 5. Go 1.25, нода на 16 ядер, `cpu.max = 250000 100000`. Каким будет `GOMAXPROCS` по умолчанию? Ответы. (1) 75 %. (2) stride A = 5, stride B = 10; запуски A (pass A = 5), B (pass B = 10), A (pass A = 10). (3) 1024 / 1844 ≈ 56 % и 820 / 1844 ≈ 44 %. (4) 0,5 ядра; 4 потока выберут 50 мс за 12,5 мс и простоят 87,5 мс. (5) Квота 2,5 ядра, округление вверх даёт 3; это меньше 16, значит 3. ## Что спрашивают на собесе - Чем пропорциональное планирование отличается от SJF и MLFQ. - Lottery против stride: одинаковые средние доли, но разная точность на коротком интервале и разное состояние. - Что такое vruntime, как nice превращается в вес и как вес влияет на рост vruntime. - Почему CFS хранит задачи в красно-чёрном дереве. - Что изменил EEVDF в Linux 6.6 и зачем. - `cpu.weight`/`cpu.shares` против `cpu.max`/квоты; что такое троттлинг и как его увидеть и устранить; что поменялось в Go 1.25 с `GOMAXPROCS`. ## Вопросы для самопроверки **Квиз «Пропорциональное планирование и CFS»** 1. В чём главная цель пропорционального планирования (proportional-share)? - Минимизировать среднее время оборота - Гарантировать самый быстрый отклик интерактивным задачам - Поделить CPU между задачами в заданных долях по весу/билетам (верно) - Полностью исключить переключения контекста - Пояснение: Proportional-share не гонится за оборотом/откликом, а делит процессор в нужной пропорции: больше билетов/вес — больше доля CPU в среднем. 2. Главный недостаток lottery scheduling по сравнению со stride? - Голодание процессов с малым числом билетов - Дисперсия: на коротких интервалах реальная доля скачет из-за случайности (верно) - Требует красно-чёрного дерева - Невозможность задать приоритеты - Пояснение: Lottery вероятностный: доли сходятся только в среднем на длинном интервале, а на коротком возможен заметный перекос. Stride детерминирован и точен. 3. Как stride вычисляет шаг и кого запускает следующим? - stride обратно пропорционален билетам; запускаем минимальный pass (верно) - stride прямо пропорционален билетам; запускаем максимальный pass - stride случаен; запускаем по очереди - stride равен числу билетов; запускаем минимальный stride - Пояснение: stride = большое_число / tickets, поэтому у кого больше билетов — меньше шаг. На каждом тике берём процесс с минимальным pass и прибавляем ему его stride. 4. Что делает CFS на каждом решении о планировании? - Запускает задачу с наибольшим vruntime - Запускает задачу с наибольшим приоритетом nice - Запускает задачу с наименьшим vruntime (верно) - Случайно выбирает задачу из очереди - Пояснение: CFS всегда выбирает задачу с минимальным vruntime (самый левый узел красно-чёрного дерева). Это прямой аналог 'минимального pass' в stride. 5. Как значение nice влияет на долю CPU в CFS? (выберите верные) - nice влияет на размер кванта, но не на долю CPU - nice не влияет ни на что при использовании CFS - nice > 0 → меньше вес → vruntime растёт быстрее → меньше CPU (верно) - nice < 0 → больше вес → vruntime растёт медленнее → больше CPU (верно) - Пояснение: nice задаёт вес: отрицательный nice = больший вес = медленный рост vruntime = больше CPU; положительный nice — наоборот. 6. Контейнеру задали cpu.cfs_quota_us=200000 при cpu.cfs_period_us=100000. Сколько ядер CPU это даёт как потолок? - Ответ: 2 - Пояснение: quota/period = 200000/100000 = 2. За каждый период 100мс контейнер может потратить 200мс CPU-времени — то есть до 2 ядер. Превысил бюджет — throttling до нового периода.