VARS - Virtual- And Real-time Scheduler.
1. Введение: проблема трёх классов задач
Современные операционные системы вынуждены одновременно обслуживать рабочие нагрузки трёх принципиально разных типов:
Интерактивные задачи (графический интерфейс, терминалы, ввод/вывод) — требуют минимальной задержки отклика (латентность не более 10–20 мс) и стабильной плавности.
Фоновые задачи (компиляция, архивация, научные расчёты) — потребляют много процессорного времени, но не критичны к задержкам; важно лишь, чтобы они не голодали.
Задачи реального времени (аудио/видео обработка, управление оборудованием, робототехника) — должны выполняться строго в заданные временные рамки (дедлайны).
Традиционные планировщики обычно решают одну из этих проблем хорошо, но не все сразу. Например, справедливые планировщики (CFS) дают отличную пропорциональность и низкую задержку для интерактивных задач, но не гарантируют жёстких дедлайнов при перегрузке. Специализированные RT-расширения (как SCHED_DEADLINE) обеспечивают временные гарантии, но сложны в интеграции с обычными процессами и часто требуют ручного выделения ресурсов.
Возникает естественный вопрос: можно ли построить единый планировщик, который естественным образом совмещает все три класса, не требуя сложной настройки? Оказывается, да. Для этого достаточно объединить два хорошо известных подхода: EEVDF (Earliest Eligible Virtual Deadline First) и приоритетную очередь реального времени с абсолютными дедлайнами. Гибридное решение оказывается удивительно простым, предсказуемым и эффективным.
2. Общая архитектура
Планировщик построен по принципу независимых очередей на каждое ядро процессора (per‑CPU runqueue). Это позволяет избкжать глобальной блокировки и обеспечивает хорошее масштабирование на многоядерных системах.
Каждая очередь содержит:
Хранилище всех задач, включая спящие.
Две отдельные структуры для выбора:
Очередь реального времени — задачи с абсолютными дедлайнами, отсортированные по времени, до которого они должны быть выполнены.
EEVDF-очередь — обычные задачи, отсортированные по паре (виртуальный дедлайн, виртуальное время выполнения).
Текущую задачу, исполняемую на данном ядре.
Минимальное виртуальное время (
min_vruntime) среди всех задач очереди — ключевой параметр для компенсации лагов.
Активация планировщика происходит либо по прерыванию от таймера (каждые 10 мс), либо по добровольному вызову yield от задачи. На каждом таком событии планировщик обновляет параметры текущей задачи, выбирает следующую и, при необходимости, переключает контекст выполнения.
3. EEVDF: справедливость через виртуальное время
EEVDF является развитием классического подхода виртуального времени, который используется в современных справедливых планировщиках. В отличие от них, EEVDF вводит понятие дедлайна для каждой задачи, что позволяет выбирать не просто задачу с наименьшим виртуальным временем, а ту, которая должна быть выполнена в ближайшее время для сохранения пропорциональности.
3.1. Приоритет и вес
Каждая задача получает приоритет (обычно выражаемый числом «nice» в диапазоне от -20 до 19). Этому приоритету соответствует вес — положительное целое число, определяющее долю процессорного вркмени, которую задача получит за один цикл планирования. Чем выше приоритет (меньше nice), тем больше вес.
Используется стандартная таблица весов, где веса растут примерно экспоненциально при повышении приоритета. Базовый вес (для nice=0) принимается равным w₀ = 1024.
3.2. Виртуальное время (vruntime)
Виртуальное время — это абстрактная метрика, которая увеличивается тем медленнее, чем выше вес задачи. За каждый реальный интервал времени Δt (измеряемый в миллисекундах) приращение виртуального времени для задачи i вычисляется по формуле:
Δvruntime_i = (Δt × w₀) / w_iгде w_i — вес задачи. Таким образом, задача с весом 2048 получит прирост vruntime вдвое меньше, чем задача с весом 1024, за тот же реальный отрезок. Это означает, что она будет «опережать» в виртуальном времени и получать больше реального CPU.
3.3. Дедлайн и квант (slice)
Каждая задача при первом появлении или после пробуждения получает квант (slice) — фиксированное значение в единицах vruntime (обычно порядка 10000). Её виртуальный дедлайн вычисляется как:
deadline_i = vruntime_i + sliceДедлайн — это момент в виртуальном времени, до которого задача должна получить свой квант, чтобы сохранить пропорциональность. Задачи с меньшим дедлайном имеют приоритет при выборе.
3.4. Алгоритм выбора в EEVDF
На каждом шаге планировщик выполняет следующие действия:
Находит текущее минимальное виртуальное время среди всех задач очереди —
min_vruntime.Выделяет подмножество догоняющих (eligible) задач, для которых выполняется условие
vruntime_i ≤ min_vruntime. Это задачи, которые «отстают» от графика и должны быть выполнены в первую очередь.Среди догоняющих задач выбирает ту, у которой наименьший дедлайн.
Если догоняющих задач нет (что бывает редко), выбирается задача с наименьшим vruntime среди всех.
Это правило гарантирует, что:
Ни одна задача не голодает — даже с маленьким весом она рано или поздно станет догоняющей и будет выбрана.
Задачи с высоким весом получают больше процессорного времени, поскольку их vruntime растёт медленнее и они чаще оказываются догоняющими.
Внутри одного весового класса задачи получают время примерно пропорционально их дедлайнам, что улучшает справедливость и снижает максимальную задержку.
4. Задачи реального времени: безусловный приоритет
В предложенном гибридном подходе задачи ркального времени обрабатываются совершенно отдельно. Каждая RT-задача имеет абсолютный дедлайн — время в миллисекундах от старта системы, до которого она должна быть выполнена.
4.1. Очередь реального времени
Все RT-задачи помещаются в специальную очередь, которая поддерживается отсортированной по абсолютному дедлайну (от наименьшего к наибольшему). На каждом шаге планировщик в первую очередь проверяет эту очередь:
Если в ней есть задачи с дедлайном, ещё не наступившим (т.е.
deadline > текущее_время), выбирается задача с наименьшим дедлайном (самая срочная).Только если RT-очередь пуста или все её задачи уже пропустили свои дедлайны, планировщик переходит к EEVDF.
Такая иерархия гарантирует, что RT-задачи всегда вытесняют любые обычные задачи, даже если у тех нулевое виртуальное время. Это даёт жёсткую гарантию выполнения в срок (при условии, что суммарная нагрузка RT-задач не превышает пропускной способности системы).
4.2. Обработка конфликтов и перегрузки
Если несколько RT-задач требуют больше процессорного времени, чем доступно, они неизбежно будут конфликтовать. В этом случае планировщик выбирает задачу с наименьшим дедлайном, тем самым минимизируя максимальную задержку. Задачи, пропустившие свой дедлайн, не отбрасываются — они продолжают выполняться, но в журнал системы записывается предупреждение. Такой подход (жёсткий приоритет с логированием) приемлем для большинства практических приложений: редкие пропуски допустимы, но задержки из-за фоновых задач — нет.
5. Обеспечение плавности интерактивных задач
Интерактивные задачи (графические серверы, терминалы, обработчики ввода) должны обладать очень малой задержкой отклика. В гибридном планировщике это достигается за счёт двух механизмов.
5.1. Высокий приоритет через вес или RT-статус
Интерактивные задачи могут запускаться с высоким приоритетом (маленьким nice), что даёт им большой вес в EEVDF. Это заставляет их vruntime расти медленно, и они будут выбираться чаще. Альтернативно, можно явно назначить им статус RT-задач с небольшим дедлайном (например, 5 мс). Тогда они будут вытеснять любые фоновые вычисления при пробуждении.
5.2. Компенсация лагов при пробуждении
Когда спящая задача просыпается (например, после нажатия клавиши), её vruntime может сильно отставать от min_vruntime очереди, поскольку она долго не выполнялась. Если просто поместить её в очередь с этим старым значением, она получит нкоправданно высокий приоритет и может монополизировать CPU, нарушая справедливость.
Чтобы избежать этого, применяется компенсация лага. Пусть lag = min_vruntime - vruntime_проснувшейся. Тогда скорректированное vruntime вычисляется как:
new_vruntime = min_vruntime - min( lag/2 , slice )То есть vruntime подтягивается к min_vruntime, но не полностью, а с учётом половины лага (и не более чем на величину кванта). Это даёт проснувшейся задаче небольшое преимущество (чтобы быстро отреагировать на событие), но не позволяет ей «съесть» всё время. В результате интерактивность сохраняется, а долговременная справедливость не страдает.
5.3. Период таймера
Планировщик обычно активируется по прерыванию таймера с периодом 10 мс. Это максимальная задержка, с которой задача может получить процессор, если она готова. Для интерактивных задач 10 мс — это вполне приемлемо: человек не замечает задержек менее 20–30 мс. При необходимости период можно уменьшить (например, до 1 мс), но это увеличит накладные расходы на переключения контекста.
6. Балансировка нагрузки на многоядерных системах
На системах с несколькими CPU важно, чтобы нагрузка распределялась равномерно, иначе одно ядро может быть перегружено, а другое простаивать, что приведёт к ухудшению общей отзывчивости.
Планировщик периодически (например, каждые 100 мс) запускает на одном из ядер процедуру глобальной балансировки:
Для каждого CPU вычисляется суммарный вес всех готовых задач (показатель загрузки).
Определяются CPU с максимальной и минимальной загрузкой.
Если разница превышает пороговое значение (например, вес одной типовой задачи), то с перегруженного ядра «воруется» одна задача (не текущая, не RT, и с учётом привязки к ядру, если она задана).
Задача переносится на менее загруженное ядро. При этом её vruntime корректируется, чтобы сохранить относительную справедливость:
new_vruntime = old_vruntime - old_queue_min_vruntime + new_queue_min_vruntimeТакой перенос обеспечивает пропорциональность времени выполнения даже после миграции. 5. Если целевое ядро отличается от текущего, ему отправляется межпроцессорное прерывание (IPI) для немедленного перепланирования.
Этот механизм предотвращает ситуации, когда одно ядро занято тяжёлыми вычислениями, а другое простаивает, хотя есть интерактивная задача, готовая к выполнению.
7. Сравнение с существующими подходами
Для наглядности сведём основные характеристики в таблицу.
Характеристика | Классический справедливый (CFS) | Специализированный RT (SCHED_DEADLINE) | Гибридный EEVDF+RT |
|---|---|---|---|
Справедливость для фоновых задач | Отличная | Не предусмотрена | Отличная (EEVDF) |
Интерактивная отзывчивость | Хорошая, но при перегрузке может страдать | Только для RT-задач | Отличная |
Поддержка реального времени | Нет | Жёсткие дедлайны | Жёсткие дедлайны |
Единый механизм управления | Да | Нет (отдельная политика) | Да (иерархия RT → EEVDF) |
Сложность настройки | Средняя | Высокая | Низкая |
Главное отличие гибридного подхода — он не требует разделения задач на классы с разными алгоритмами планирования. Вместо этого строится простая иерархия: сначала обслуживаются RT-задачи, затем оставшееся время распределяется по EEVDF. Это упрощает реализацию, делает поведение системы предсказуемым и позволяет легко управлять приоритетами через стандартные механизмы (задание nice и дедлайнов).
8. Практические сценарии работы
Рассмотрим несколько типичных ситуаций, чтобы понять, как поведёт себя планировщик.
Сценарий 1: Компиляция большого проекта и активная работа в терминале.
Компилятор запущен с обычным приоритетом (nice=0), использует все ядра. Терминал (или графическая оболочка) работает как RT-задача с дедлайном 10 мс. При каждом нажатии клавиши терминал пробуждается, немедленно вытксняет компилятор, обрабатывает ввод и снова засыпает. Задержка не превышает 10 мс, пользователь не замечает тормозов. Компиляция продолжается в фоне.
Сценарий 2: Воспроизведение видео и параллельное архивирование файлов.
Видеоплеер — RT-задача с дедлайном 33 мс (соответствует частоте 30 кадров/с). Архивирование — несколько фоновых процессов с минимальным приоритетом (nice=19). Планировщик выделяет плееру процессор строго по расписанию, архивация заполняет все оставшиеся слоты времени. Видео идёт плавно, без пропусков кадров.
Сценарий 3: Перегрузка RT-задачами.
Запущено 10 независимых RT-задач, каждая требует 2 мс процессора каждые 10 мс. Суммарная потребность — 20 мс на 10-мс интервал, что физически невозможно. Планировщик выбирает на каждом шаге задачу с наименьшим дедлайном, часть задач пропускает свои сроки (в журнал пишется предупреждение). Система не зависает, обычные задачи получают остатки времени. Такой компромисс неизбежен при перегрузке, но поведение детерминировано и предсказуемо.
9. Заключение
Представленный гибридный планировщик успешно решает задачу совмещения трёх классов нагрузок в единой модели. Благодаря простой иерархии (RT -> EEVDF) он не требует сложной настройки, а его поведение легко предсказать даже в экстремальных условиях.
Ключевые математические идеи — виртуальное время с дедлайнами и безусловный приоритет RT-задач — позволяют одновременно достичь:
Справедливости для фоновых вычислений,
Низкой латентности для интерактивных задач,
Гарантированных дедлайнов для задач реального времени.
Возможные направления для дальнейшего развития включают поддержку групп задач (для изоляции контейнеров), динамическую подстройку весов на основе истории загрузки и интеграцию с энергосберегающими режимами. Однако и в текущем виде планировщик уже готов к использованию в системах общего назначения, где важна как производительность, так и отзывчивость.
Математика и архитектура, описанные здесь, не привязаны к конкретной реализации и могут быть воспроизведены в любой операционной системе. Надеюсь, этот материал поможет разработчикам лучше понять возможности современных гибридных подходов к планированию.