Всем привет! В статье расскажу про относительно новую возможность написания собственных CPU планировщиков для Linux с помощью BPF. Разберёмся, для чего это нужно, как работает, а также посмотрим на примеры уже написанных планировщиков.

Оглавление

Зачем это нужно
Что такое Extensibe CPU Scheduler (SCHED_EXT)
Внутреннее устройство SCHED_EXT
Планировщик в User Space
Примеры существующих

Зачем это нужно

Давайте перед тем, как говорить про BPF CPU Scheduler, немного обсудим имеющиеся во встроенном cpu планировщике линукс проблемы, из-за которых собственно и появилась идея создания возможности для разработчиков писать свои собственные шедулеры.

Первая проблема – каким бы "Completely Fair" не был дефолтный планировщик, он все равно останется планировщиком общего назначения, и поэтому никогда не будет покрывать специфичные кейсы (гейминг, некоторые highload web сервисы и так далее).

Вторая проблема – невероятная сложность устройства подсистемы CPU шедулинга в линукс. Если вам нужно внести туда какие-то свои правки или не дай бог написать какой-то дополнительную политику планирования, вам нужно полностью разбираться в этой системе, а она очень сложная и не то чтобы полностью задокументированная.

Третья проблема – достаточно медленная разработка. Если вы всё-таки решились вносить какие-то правки в kernel scheduler, сразу приготовьтесь, что для каждой проверки, для каждого фикса вам нужно будет пересобирать ядро и перезапускать систему, а на это нужно время.

Четвертая проблема – вероятно ваши правки, которые нужны только вам, в апстрим не попадут. Соответственно каждый раз, когда ядро будет обновляться, вам придется пулить изменения с апстрима в вашу ветку, и всегда есть большая вероятность, что придется править мердж конфликты, а когда мы говорим про ядро, это может быть достаточно нетривиально.

Что такое Extensibe CPU Scheduler (SCHED_EXT)

Extensible Scheduler – это функционал ядра линукс, который даёт возможность пользователям создавать свои собственные политики распределения CPU времени. Делается это посредством написания BPF приложения и его последующей загрузки в ядро. После этого контролировать выделение цпу времени всем процессам (или только процессам с классом SCHED_EXT, об этом подробнее ниже) будет ваш планировщик.

В linux есть ряд классов планирования помимо SCHED_EXT, о которых можно почитать в другой моей статье :). Касательно этой темы важно знать, что при запуске extensibe шедулера все SCHED_NORMAL, SCHED_IDLE и SCHED_EXT задачи перейдут под его контроль, если не передан флаг SCX_OPS_SWITCH_PARTIAL. Если же флаг всё-таки передали, то наш кастомный планировщик будет управлять только задачами, которым мы руками выставим класс планирования SCHED_EXT. Это не особо рекомендуется, потому что приоритет SCHED_EXT ниже SCHED_NORMAL и ваш планировщик просто не сможет в полной мере "показать себя", если ему будут мешать задачки, управляемые дефолтным планировщиком. Проверить, управляется ли запущенный процесс extensible планировщиком, можно, посмотрев его schedule параметры в файле /proc/$PID/sched. Если вы видите там строчку ext.enabled: 1, значит процессорное время ему выделяет запущенный SCHED_EXT планировщик.

Примечательно, что в отличие от бага в модуле или подсистеме ядра, баг в BPF программе SCHED_EXT не приведет к ~~апокалипсису~~ kernel panic и необходимости перезагрузки системы. Если внутри вашего планировщика происходит ошибка, то BPF приложение завершается, а все процессы, ранее им управляемые, переходят обратно на дефолтный планировщик.

Внутреннее устройство SCHED_EXT

Начнем с самой базы – Сore CPU планировщика (kernel/sched/core.c). Он определяет, какой класс планирования выставить потоку, вызывает функции шедулеров, принадлежащих конкретным классам планирования, реализует context switching и так далее. В мире ООП можно было бы назвать его родительским классом для всех остальных планировщиков.

Далее у нас идет код класса планирования SCHED_EXT (kernel/sched/ext.c). В нём реализуется полный набор функций, которые требуются для функционирования отдельного класса планирования. Посмотреть их можно в вызове вот этого макроса.

Если провалиться дальше в какую-нибудь функцию, например, в функцию enqueue_task_scx, которая отвечает за добавление задачи в очередь, можно увидеть некоторое количество базовой логики, которая будет выполняться для всех пользовательских планировщиков. И если в этой же функции провалиться ещё глубже, в функцию do_enqueue_task, то тут уже можно будет найти условие, которое определяет, выполнять кастомную логику или дефолтную.

/* Проверяется, реализована ли функция в вашем шедулере */
if (unlikely(!SCX_HAS_OP(sch, enqueue)))
    goto global;

/* Вызывается функция кастомного шедулера */
SCX_CALL_OP_TASK(sch, SCX_KF_ENQUEUE, enqueue, rq, p, enq_flags);

/* ... */

/* Дефолтная реализация, на случай, если функция enqueue не реализована в вашем планировщике */
global:
	touch_core_sched(rq, p);
	refill_task_slice_dfl(p);
	dispatch_enqueue(sch, find_global_dsq(p), p, enq_flags);

Подобные дефолтные реализации есть для каждой функции, поэтому когда вы пишете свой планировщик, у вас нет функций, которые вам нужно обязательно реализовать, иначе ничего работать не будет. Есть только одно обязательное поле для пользовательского планировщика - его имя :). Все остальные поля, которые вы можете реализовать, вы найдете в структуре sched_ext_ops.

В самом низу файла можно найти фрагмент регистрации bpf_struct_ops. "BPF Struct Ops" - это специальный тип BPF программ, позволяющий реализовывать отдельный функционал ядра. Работает это таким образом – вы пишите функции (программы), кладете ссылки на них в специальную структуру, а потом, на этапе загрузки приложения в ядро, эта структура вместе с программами кладётся в определённое место в памяти ядра. И далее уже эти функции могут в качестве call-back'ов вызываться подсистемами ядра, например, как это было показано выше макросом SCX_CALL_OP_TASK.

На уровне выше идёт код BPF программы собственно вашего планировщика. Примеры, как они могут выглядеть, можно посмотреть в этой папке. Вот самый простой из них - scx_simple.bpf.c.

Ну и ещё выше остается только программа, которая вызывала syscall bpf(), загрузив тем самым BPF программу шедулера. Так же прилагаю самый простой пример - программу scx_simple.c, запускающую планировщик scx_simple, на чей код уже была ссылка выше. Заметьте, что это единственная часть кода, которая запускается у нас в пространстве пользователя.

Планировщик в User Space

Вам может показаться, что единственное место, в котором вы можете описывать логику вашего шедулера - это код планировщика в пространстве ядра, но это не так. BPF приложение состоит из программ (считай функций), BPF Map (это может быть хеш-таблица, массив или более специфичные типы данных) и глобальных переменных, и последние два пункта доступны в том числе и из пространства пользователя. Поэтому у вас, например, может быть общая мапа, в которую BPF шедулер будет складывать задачи, запрашивающие процессорное время, а user-space шедулер будет решать, кому из этой мапы следующему дать доступ к процессору, и после этого перекладывать в другую мапу, из которой планировщик в ядре возьмёт задачу и сразу отправит выполняться. Примерно так поступили при реализации scx_userland.

Вы можете справедливо задаться вопросом: "если у меня все основные решения по планированию задач принимаются в пространстве пользователя, не получится ли так, что теперь планировщик будет планировать сам себя?". Если процесс вашего "userland" планировщика имеет параметр ext.enabled: 1 (как этот параметр получается описано выше в разделе "Что такое Extensibe CPU Scheduler"), то да, получается ваш планировщик сам себе выписывает процессорное время. Эту ситуацию можно обыграть следующим образом: прописать логику в BPF коде так, чтобы часть планировщика, загруженная в ядро, относилась к своей "userland" части по-особенному. Например, BPF часть может выдать ей бесконечный доступ к процессорному времени, пока она не разберётся с накопленной очередью задач и не определит, на каких CPU они должны выполняться. Такой подход применяется в scx_rustland_core, фреймворке для написания "userland" планировщиков на rust.

Примеры существующих

Примеров существующих SCHED_EXT планировщиков достаточно много, и почти со всеми вы можете ознакомиться в этом гит репозитории. Ниже я перечислю несколько, по моему мнению, самых интересных.

scx_rustland – планировщик, приоритезирующий интерактивные процессы над фоновыми и просчитывающий все решения планирования в пространстве пользователя. Хорошо себя показал на системе с запущенной Terraria, увеличив fps в игре с 30 кадров до 60. Весь код планировщика состоит из трёх частей: BPF код на C, выполняющийся в ядре, Rust фреймворк scx_rustland_core, о котором уже писал выше, и код на Rust, реализующий правила политики с помощью фреймворка.
scx_layered – планировщик, созданный в Meta (признана экстремистской и запрещена на территории РФ), позволяет делить процессы на "слои" и задавать каждому слою свою политику. Например, вы можете выделить все процессы в cgroup'е system.slice и указать, что процессам в ней выделяется от 1 до 4 ядер, и что выделение им новых ядер происходит только в случае высокой утилизации всех текущих. Подробнее можно почитать в этом исследовании и в этом мануале по конфигурации scx_layered. Утверждается, что в Meta (признана экстремистской и запрещена на территории РФ) этот планировщик используется для множества web сервисов, в которых важен точечный контроль над выделением CPU.
scx_lavd – планировщик, как говорят, разработанный специально для Steam Deck, и, как вы, наверное, уже поняли, для игр :). Код делится на BPF часть, написанную на С, и часть, написанную на Rust. Всё планирование задач происходит в C коде, а Rust предоставляет "высокоуровневую" информацию системе и загружает BPF код в ядро.

Спасибо за чтение!

BPF CPU Scheduler: не нравится стандартный планировщик в Linux? Напиши свой