Никита Алексеев, Автор в Академия Selectel

Планировщик процессов — одна из важнейших подсистем ядра Linux. Именно он определяет, какой поток получит процессорное время в каждый конкретный момент. Несмотря на многоядерность современных компьютеров, количество одновременно выполняемых задач практически всегда значительно превышает доступные вычислительные ресурсы. Поэтому ядру необходимо постоянно принимать решения о распределении процессорного времени между задачами. Внутри Linux объектом планирования является не процесс как таковой, а задача, представленная структурой task_struct. Она может соответствовать как отдельному процессу, так и потоку выполнения. Все готовые к выполнению задачи помещаются в специальные очереди, из которых планировщик выбирает следующую. Рис. 1. Планировщик операционной системы. Для каждого процессорного ядра Linux поддерживает собственную очередь выполнения — runqueue. Такое решение позволяет ядрам независимо выбирать следующую задачу, что уменьшает конкуренцию за общие структуры данных и повышает масштабируемость системы. Если одно ядро оказывается перегружено, а другое простаивает, механизм балансировки нагрузки переносит задачи между очередями. За более чем тридцать лет развития Linux алгоритмы планирования неоднократно менялись. Каждое новое поколение стремилось устранить недостатки предыдущего. Сначала основное внимание уделялось скорости работы самого алгоритма, затем — справедливости распределения ресурсов. Сегодня важнейшей задачей становится минимизация задержек и повышение отзывчивости системы. Классы и политики планирования в Linux Планировщик Linux — не один алгоритм, а целая подсистема из нескольких классов планирования. Каждый из них предназначен для определенного типа задач и обладает собственной политикой выбора процесса. При планировании ядро последовательно проверяет классы в порядке их приоритета и выбирает задачу из первого класса, в котором есть готовые к выполнению процессы. Рассмотрим основные классы планирования. Stop Scheduler (stop_sched_class) — внутренний класс ядра с наивысшим приоритетом. Используется для выполнения критически важных операций ядра, требующих временной остановки выполнения обычных задач на одном или нескольких процессорах. Пользовательские процессы не могут выполняться в этом классе. Deadline Scheduler (SCHED_DEADLINE) — предназначен для задач реального времени с жесткими временны́ми ограничениями. Алгоритм стремится гарантировать выполнение задачи до заданного дедлайна. Real-Time Scheduler (SCHED_FIFO, SCHED_RR) — обслуживает задачи реального времени. Политика SCHED_FIFO выполняет процессы в порядке очереди до добровольной передачи процессора. Политика SCHED_RR дополнительно использует квант времени для справедливого распределения процессора между задачами с одинаковым приоритетом. Fair Scheduler (SCHED_NORMAL, SCHED_BATCH) — класс, в котором выполняется большинство пользовательских процессов. Именно здесь исторически применялись планировщики O(1), затем CFS, а в современных версиях ядра — и EEVDF. Idle Scheduler (SCHED_IDLE) — класс с минимальным приоритетом, предназначенный для фоновых задач, которые выполняются только при отсутствии более важных процессов. Таким образом, O(1), CFS и EEVDF не являются самостоятельными планировщиками всей операционной системы. Это различные алгоритмы реализации Fair Scheduler, отвечающего за выполнение обычных пользовательских процессов. Именно эволюции этого класса и посвящена данная статья. Эпоха O(1) Scheduler В начале 2000‑х годов в Linux появился планировщик O(1) Scheduler. Его название отражало ключевую особенность: время выбора следующей задачи оставалось постоянным независимо от количества процессов в системе, то есть выполнялось за O(1). До появления O(1) в Linux использовался алгоритм O(N) Scheduler. Он хранил все готовые к выполнению задачи в общей очереди. При каждом переключении контекста последовательно просматривал их, вычисляя для каждой значение функции goodness. Она учитывала несколько факторов, например: приоритет процесса, оставшийся промежуток времени выполнения и привязку к процессору. Задачу с наибольшим показателем goodness планировщик ставил на исполнение. Из‑за необходимости прохода по всем элементам очереди он и получил свое имя. Пока задач было мало, обход не создавал значительной нагрузки. Однако по мере увеличения числа одновременно выполняемых задач планировщик начинал тратить заметную часть процессорного времени на собственную работу, что стало одной из главных причин разработки O(1). В основе нового алгоритма лежали две очереди задач фиксированного размера: Active Queue — готовые к выполнению; Expired Queue — полностью использовавшие выделенный им квант процессорного времени. Рис. 2. Пример очередей. Каждая очередь представляла собой массив списков процессов, разделенных по уровням приоритета. Планировщик всегда выбирал первую задачу с наивысшим доступным приоритетом. После завершения временно́го кванта задача переносилась в очередь Expired Queue. Когда Active Queue пустела, очереди просто менялись местами, и цикл повторялся. Подобная организация позволяла избежать перебора всех процессов и обеспечивала очень высокую скорость работы даже при большом количестве задач. К достоинствам O(1) можно отнести: постоянное время выбора следующего процесса; хорошую масштабируемость; высокую производительность на серверных системах своего времени. Почему Linux понадобился новый планировщик Хотя O(1) отлично справлялся со своей основной задачей — быстрым выбором следующего процесса — его архитектура постепенно перестала соответствовать требованиям современных операционных систем. Главной проблемой оказалась зависимость алгоритма от большого количества эвристик. Планировщик пытался самостоятельно определить характер процесса (интерактивный он или вычислительный) — то есть насколько часто тот должен получать процессорное время и как следует изменять его приоритет. По мере накопления подобных правил код усложнялся, а возможные ошибки в классификации задач могли приводить к необоснованному повышению повышению приоритета фоновых потоков. Кроме того, распределение процессорного времени нельзя было назвать полностью справедливым. Некоторые процессы могли получать дополнительные преимущества благодаря особенностям своего поведения, тогда как другие ожидали выполнения значительно дольше. В связи с этим возникла необходимость заменить эвристический алгоритм новой математической моделью. Требовалось: справедливое распределение процессорного времени; высокая отзывчивость интерактивных приложений; простую и понятную архитектуру; хорошая масштабируемость на многоядерных системах. CFS – Completely Fair Scheduler В 2007 году в ядре Linux появился Completely Fair Scheduler, полностью изменивший подход к планированию задач. Для справедливого распределения ресурсов каждой задаче сопоставляется величина virtual runtime — виртуальное процессорное время. Оно отражает продолжительность периода, уже полученного задачей с учетом ее приоритета. Чем меньше значение vruntime, тем меньше процесс успел поработать, и тем выше вероятность его выбора на следующем шаге. Все задачи хранятся в красно-черном дереве, отсортированном по значению vruntime. Самый левый узел дерева всегда содержит процесс с минимальным виртуальным временем, поэтому выбор следующей задачи происходит очень быстро. Рис. 3. Красно-черное дерево задач. На рисунке 3 видно, что самая левая вершина имеет минимальное значение vruntime, поэтому на следующем шаге алгоритм выберет именно ее. Доступ к этой вершине можно получить за константное время благодаря поддержке указателя на нее. Однако перебалансировка дерева, добавление и удаление узлов занимает O(log N) времени. Подробнее ознакомиться со структурой дерева ядра можно на страничке документации. В отличие от предшественников, CFS работает не напрямую со структурой task_struct, а с вложенной в нее сущностью планирования — sched_entity. Именно в ней хранятся параметры, необходимые алгоритму: значение vruntime, вес задачи, узел красно-черного дерева и другая информация. Подобный подход позволяет CFS планировать ресурсы как для отдельных потоков, так и для групп задач — например, при использовании cgroups. При исполнении задачи, она получает гарантированный временной промежуток времени, длительность которого зависит от параметра NICE. Это значение показывает, насколько поток готов делиться процессорным временем с другими, и находится в интервале от -20 до 19. При этом vruntime увеличивается по формуле: Функция weight(NICE) аппроксимируется следующим образом: Однако в самом ядре для ускорения вычислений используются заранее рассчитанные табличные значения для каждого значения NICE. По сравнению с O(1) алгоритм CFS значительно упростил архитектуру подсистемы планирования. Вместо сложного набора эвристик появилась единая математическая модель справедливого распределения процессорного времени. Один из разработчиков O(1) в своем комментарии на простом примере показал, что CFS лучше распределяет задачи: Однако у CFS был существенный недостаток Процессам, остро нуждающимся в процессорном времени прямо сейчас, не всегда удавалось его оперативно выделить. Из‑за этого возникали задержки, особенно заметные в приложениях с графическим интерфейсом. Планировщик EEVDF В ядре Linux 6.6 основным алгоритмом планирования обычных процессов стал EEVDF (Earliest Eligible Virtual Deadline First) — дословно «первая из желательных с ближайшим крайним сроком» Как следует из названия, в нем учитывается не только фактическое время, но и момент, когда задача должна получить доступ к процессору. Новый планировщик стал логичным развитием CFS. Он по‑прежнему использует красно-черное дерево и концепцию виртуального времени, однако меняет сам принцип выбора следующей задачи. Главная проблема CFS заключалась в жесткой привязке исключительно к накопленному виртуальному процессорному времени. Для большинства задач этого было достаточно, однако приложения с высокой интерактивностью — графические оболочки, мультимедиа, игры — иногда получали процессор позже, чем требовалось для плавной работы. EEVDF вводит два новых понятия: Eligibility — право задачи быть выбранной для выполнения; Virtual Deadline — виртуальный дедлайн, к которому задача должна получить свою долю процессорного времени. Теперь планировщик сначала определяет пул задач, имеющих право на выполнение, а затем выбирает среди них процесс с наиболее ранним виртуальным дедлайном. Как именно определяется право на выполнение? Вводится величина lag (отставание) Она вычисляется как разность между временем, которое задача должна была получить, и тем, которое она фактически исполнялась. Если lag > 0, задача недополучила положенные ресурсы. Когда lag < 0, наоборот, израсходовала больше, чем должна. Задачи, которые получили меньше процессорного времени, чем предполагалось, считаются Eligibile (желательными). В свою очередь, величина Deadline вычисляется по формуле: В этом выражении slice обозначает квант времени, который процесс получит на исполнение, а weight — весовую функцию, зависящую от значения NICE. Такой подход позволяет как уменьшить задержки выполнения интерактивных приложений, так и сохранить справедливое распределение процессорного времени между задачами. По сути, алгоритм EEVDF перенял все сильные стороны CFS, успешно устранив часть его ограничений. Заключение Все три планировщика решают одну и ту же фундаментальную проблему — определяют, какая задача должна занять процессор следующей. Однако способы выбора кардинально различаются, что особенно заметно при сравнении O(1) и CFS. Алгоритм O(1) ориентирован прежде всего на собственную скорость работы. Благодаря очередям приоритетов выбор следующей задачи выполняется за постоянное время, однако поддержание справедливости требует большого количества эвристик. В свою очередь, CFS предложил строгую математическую модель справедливого распределения процессорного времени. Переход к виртуальному времени позволил значительно улучшить общее поведение системы. EEVDF развивает идеи CFS, дополняя их механизмом виртуальных дедлайнов. Вместо выбора процесса исключительно по минимальному времени работы, планировщик учитывает ожидаемое время исполнения задачи, благодаря чему уменьшаются задержки и улучшается работа интерактивных приложений. Таким образом, развитие планировщиков Linux демонстрирует постепенный переход от оптимизации скорости самого алгоритма к оптимизации распределения вычислительных ресурсов и улучшения отзывчивости интерактивных приложений.

Никита Алексеев

Материалы автора

Эволюция планировщиков ядра Linux — от O(1) до CFS и EEVDF

Основы Rust: синтаксис и структуры данных

Квиз: разбираетесь ли вы в многопоточности и конкурентном программировании

Программы для тестирования процессора и производительности ПК

Что такое многопоточность

Задача о Тирексе, который строил сеть наугад