Планировщик ядра 2.6.23 открывает дорогу другим модулям планировщика, позволяя им работать параллельно с ядром. ("Модульность" в этом случае обозначает не то, что планировщик делится на загружаемые модули, а то, что код сам по себе стал модульным.) Более подробное описание работы планировщика можно найти в статье developerWorks "Внутреннее устройство планировщика Linux" (ссылку можно найти ниже в разделе Ресурсы).

Основные возможности и политики

Среди важнейших возможностей, реализованных в последнем планировщике, следующие:

• Модульный планировщик
• Полностью равномерный планировщик (CFS)
• Групповой планировщик CFS

Модульный планировщик

Введение классов планировщика обеспечивает его высокую расширяемость. Эти классы (модули планировщика) инкапсулируют политики планирования. Данный планировщик делит политики планирования на модули, но не разбивает на модули сам планировщик, как это делается в среде подключаемых планировщиков (Pluggable CPU scheduler framework) (в которой во время сборки ядра можно указать планировщик, используемый по умолчанию, а остальные планировщики можно использовать путём передачи ядру аргументов во время загрузки).

CFS

Полностью равномерный планировщик пытается запустить каждую задачу с "максимальной потребностью" в процессорном времени; это помогает обеспечить получение каждым процессом справедливой доли процессорного времени. CFS не рассматривает задачу как спящую, если она спит "очень" короткое время — спящая короткое время задача может получить небольшое бонусное время, но не больше, чем если бы она не спала.

Планировщик групп CFS

Рассмотрим пример двух пользователей, A и B, запускающих задания на машине. Пользователь A запустил всего две задачи, а пользователь B - 48 задач. Групповое планирование позволяет CFS равномерно распределять время по отношению к пользователям A и B, а не ко всем 50 задачам, работающим в системе. Оба пользователя получают равные доли. Пользователь B будет использовать свои 50% для запуска своих 48 задач и не сможет вторгнуться в 50% пользователя A.

Модуль планировщика CFS (реализован в kernel/sched_fair.c) используется для обеспечения следующих политик планирования: SCHED_NORMAL, SCHED_BATCH и SCHED_IDLE. Для политик SCHED_RR и SCHED_FIFO используется модуль планирования в реальном времени (этот модуль реализован в kernel/sched_rt.c).

Часть этих изменений была сделана, чтобы:

• Обеспечить лучшее планирование для серверов и рабочих станций.
• Реализовать новые востребованные функции.
• Улучшить эвристику. Анализатор, использовавшийся в планировщике vanilla, позволял легко реализовать некоторые атаки. Кроме того, неверная оценка эвристического сценария могла приводить к нежелательным последствиям.

Планировщик Rotating Staircase Deadline Scheduler RSDL - это планировщик процессов, который исключал код оценки интерактивности - алгоритм, позаимствованный из предыдущего планировщика процессов Linux, который на основании статистики пытался предсказать будущее с помощью эвристического анализа (и делал это неудачно). RSDL основывается на понятии "равномерности". Процессы считаются равными и получают одинаковое количество квантов машинного времени. Планировщик не следит и даже не пытается проверить, связаны ли эти процессы с процессором или устройствами ввода-вывода. RSDL улучшал воспринимаемую пользователем "интерактивность" и был готов ко включению в ядро 2.6, когда Инго Молнар (Ingo Molnar), создатель исходного планировщика процессов O(1), написал CFS, позаимствовав основные элементы архитектуры равномерного планирования RSDL. Он был хорошо воспринят многими хакерами, хотя RSDL (созданный Коном Коливасом) также был высоко оценен.

Все заслуги того, что "равномерное планирование" может быть достигнуто без конфликта с целевыми задержками интерактивности, остаются за Коном Коливасом. Созданием планировщиков RSDL/SD он доказал, что равномерности можно достигнуть без применения сложной эвристики для оценки интерактивности процессов.

CFS не использует массива приоритетов и не имеет артефакта переключения по массиву, как планировщик vanilla. Между RSDL и CFS есть ряд важных отличий:

• RSDL основан на принципе "жесткой равномерности"; CFS, напротив, учитывает длительность времени сна интерактивного процесса, поэтому процессы, спящие короткое время, получают немного больше процессорного времени.
• RSDL, в отличие от CFS, использует очереди приоритетов, как vanilla.
• В RSDL, как и в vanilla, имеется артефакт переключения по массиву, которого нет в CFS.

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

Важные структуры данных CFS

CFS использует для каждого процессора отсортированное по времени красно-чёрное дерево.

Определение красно-чёрного дерева из Википедии По определению, данному в Википедии, красно-черное дерево - это тип самосбалансированного бинарного дерева, структура данных, используемая для реализации ассоциативных массивов. В красно-чёрном дереве создаётся узел для каждого работающего процесса. Процесс, находящийся в самой левой позиции чёрно-красного дерева, является следующим запланированным процессом. Красно-чёрное дерево сложно устроено, но у него хорошее время исполнения в самом худшем варианте и оно эффективно на практике: оно позволяет выполнять поиск, добавление и удаление за время O(log n), где n - количество элементов дерева. Концевые вершины не являются информативными и не содержат данных. Для экономии памяти иногда роль всех концевых вершин играет один сигнальный узел. Все ссылки с внешних узлов на концевые вершины указывают на этот сигнальный узел.

Такой подход отлично работает по трём причинам:

• Красно-чёрное дерево всегда сбалансировано.
• Поскольку красно-чёрное дерево является бинарным, временная сложность операций поиска имеет логарифмический характер. Однако поиск не самого левого узла выполняется очень сложно, а указатель самого левого узла всегда кэширован.
• Для большинства операций в красно-чёрном дереве время выполнения составляет O(log n), тогда как в предыдущей версии планировщика с помощью массива приоритетов с фиксированным количеством приоритетов сложность составляла O(1). O(log n) – более медленное поведение, но это заметно лишь для очень большого числа задач. Это был один из первых моментов, которые проверил Молнар при разработке своего подхода на основе дерева.
• Красно-чёрное дерево может быть реализовано с помощью внутреннего хранилища—для хранения этой структуры данных не требуется внешних ресурсов хранения данных.

Давайте посмотрим на некоторые ключевые структуры данных, используемые новым планировщиком.

Изменения в struct task_struct

CFS исключает struct prio_array и вводит сущность планирования и классы планирования, определяемые struct sched_entity и struct sched_class, соответственно. Соответственно task_struct содержит информацию о двух других структурах, sched_entity и sched_class:

struct task_struct { /* Defined in 2.6.23:/usr/include/linux/sched.h */
....
- struct prio_array *array;
+ struct sched_entity se;
+ struct sched_class *sched_class;
 ....
 ....
};

Структура sched_entity

В этой структуре содержится достаточная информация для выполнения планирования задачи или группы задач. Она используется для реализации планировщика групп. Планируемая сущность может быть не связана с процессом.

struct sched_entity { /* Defined in 2.6.23:/usr/include/linux/sched.h */
 long wait_runtime; /* Amount of time the entity must run to become completely */
 /* fair and balanced.*/
 s64 fair_key;
 struct load_weight load; /* for load-balancing */
 struct rb_node run_node; /* To be part of Red-black tree data structure */
 unsigned int on_rq; 
 ....
};

Структура sched_class

Классы планирования подобны цепочке модулей, помогающих основному планировщику. Каждый модуль должен реализовать набор функций, как рекомендуется в struct sched_class.

struct sched_class { /* Defined in 2.6.23:/usr/include/linux/sched.h */
 struct sched_class *next;
 void (*enqueue_task) (struct rq *rq, struct task_struct *p, int wakeup);
 void (*dequeue_task) (struct rq *rq, struct task_struct *p, int sleep);
 void (*yield_task) (struct rq *rq, struct task_struct *p);

 void (*check_preempt_curr) (struct rq *rq, struct task_struct *p);

 struct task_struct * (*pick_next_task) (struct rq *rq);
 void (*put_prev_task) (struct rq *rq, struct task_struct *p);

 unsigned long (*load_balance) (struct rq *this_rq, int this_cpu,
 struct rq *busiest,
 unsigned long max_nr_move, unsigned long max_load_move,
 struct sched_domain *sd, enum cpu_idle_type idle,
 int *all_pinned, int *this_best_prio);

 void (*set_curr_task) (struct rq *rq);
 void (*task_tick) (struct rq *rq, struct task_struct *p);
 void (*task_new) (struct rq *rq, struct task_struct *p);
};

Давайте посмотрим на некоторые функции, приведенные в листинге 3:

• enqueue_task: эта функция вызывается, когда задача переходит в запущенное состояние. Она помещает планируемую сущность (процесс) в красно-чёрное дерево и инкрементирует переменную nr_running .
• dequeue_task: когда задача завершает работу, эта функция вызывается для исключения соответствующей сущности из красно-чёрного дерева. Она выполняет декремент переменной nr_running .
• yield_task: фактически, функция просто удаляется из очереди после постановки в очередь, если не включен compat_yield sysctl; в этом случае он размещает планируемую сущность в самом правом узле красно-чёрного дерева.
• check_preempt_curr: эта функция проверяет, может ли быть выгружена работающая на данный момент задача. Перед фактической выгрузкой работающей задачи модуль планировщика CFS выполняет проверку равномерности. Это обеспечивает вытесняющую многозадачность для просыпающегося процесса.
• pick_next_task: эта функция выбирает наиболее подходящий для запуска в следующую очередь процесс.
• load_balance: в каждом модуле планировщика реализуется пара функций load_balance_start() и load_balance_next(), реализующая итератор, который вызывается в процедуре load_balance модуля. Основной планировщик с помощью этого метода балансирует нагрузку процессов, управляемых модулем планировщика.
• set_curr_task: эта функция вызывается, когда изменяется класс планирования или группа задач для задачи.
• task_tick: эта функция чаще всего вызывается из таймерных функций; она может вызвать переключение процесса. Это обеспечивает вытесняющую многозадачность для работающих процессов.
• task_new: основной планировщик передаёт модулю планировщика возможность управления запуском новой задачи. Модуль планировщика CFS использует его для планирования групп, тогда как модуль планировщика для задач в реальном времени не использует его.

Поля CFS в очереди выполнения

Для каждой очереди выполнения существует структура, в которой хранится информация о соответствующем красно-чёрном дереве.

struct cfs_rq {/* Defined in 2.6.23:kernel/sched.c */
 struct load_weight load;
 unsigned long nr_running;

 s64 fair_clock; /* runqueue wide global clock */
 u64 exec_clock;
 s64 wait_runtime;
 u64 sleeper_bonus;
 unsigned long wait_runtime_overruns, wait_runtime_underruns;

 struct rb_root tasks_timeline; /* Points to the root of the rb-tree*/
 struct rb_node *rb_leftmost; /* Points to most eligible task to give the CPU */
 struct rb_node *rb_load_balance_curr;
#ifdef CONFIG_FAIR_GROUP_SCHED
 struct sched_entity *curr; /* Currently running entity */
 struct rq *rq; /* cpu runqueue to which this cfs_rq is attached */
 ...
 ...
#endif
};

Планировщик CFS использует политику умиротворения, которая гарантирует равномерность. Как только задача попадает в очередь выполнения, записывается текущее время, и пока процесс ожидает освобождения процессора, его значение wait_runtime увеличивается в зависимости от количества процессов, стоящих в очереди выполнения. При выполнении этих расчётов также учитываются значения приоритета для различных задач. Когда эта задача направляется на исполнение на процессор, её значение wait_runtime начинает уменьшаться, и как только оно упадёт до такого уровня, когда другие задачи станут новыми самыми левыми задачами красно-чёрного дерева, выполнение текущей задачи прерывается. Таким образом CFS пытается достичь идеальной ситуации, когда wait_runtime будет равен нулю!

CFS поддерживает выполнение задачи по отношению к общим часам очереди fair_clock cfs_rq->fair_clock), которые идут пропорционально реальному времени, что позволяет им задавать идеальную скорость выполнения для отдельно взятой задачи.

Как соотносятся степень детализации и время задержки? Степень детализации и время задержки связаны простым уравнением gran = (lat/nr) - (lat/nr/nr) где gran = степень детализации, lat = задержка и nr = количество работающих задач.

Например, если у вас запущены четыре задачи, то fair_clock будет увеличиваться на одну четвертую часть скорости обычного времени. Каждая задача пытается не отставать от своего идеального времени. Такое поведение является результатом квантовой природы многозадачности с разделением по времени. Таким образом, в каждый момент времени может работать только одна задача, а другие процессы накапливают долг (wait_runtime). Поэтому, как только задача начинает выполняться, она будет догонять свой долг (и немного больше, поскольку fair_clock не перестанет работать в момент, когда задача нагонит долг).

Приоритеты реализуются путём присвоения задачам весовых коэффициентов. Предположим, у нас есть две задачи, и одной необходимо выделять в два раза больше процессорного времени, чем другой; получается отношение 2:1. Расчёты изменяются таким образом, чтобы для задачи с весом 0,5 время проходило в два раза быстрее.

Мы ставим задачу в очередь в дереве на основе fair_clock.

Что касается квантов времени, нужно помнить, что CFS не использует их, по крайней мере так, как предыдущие планировщики. Кванты времени в CFS имеют переменную длину и определяются динамически.

Для балансировщика нагрузки модули планирования создают итераторы, которые используются для обхода задач, управляемых модулем планировщика, выполняя балансировку нагрузки.

Настройки реального времени

Для настройки планировщика в реальном времени введен ряд параметров sysctls (имена, заканчивающиеся на ns, являются единицами измерения в наносекундах), в том числе:

• sched_latency_ns: целевая задержка вытеснения для задач, связанных с процессором.
• sched_batch_wakeup_granularity_ns: степень детальности активизации для SCHED_BATCH.
• sched_wakeup_granularity_ns: степень детальности активизации для SCHED_OTHER.
• sched_compat_yield: производительность приложений, сильно зависящих от поведения sched_yield(), может варьировать из-за того, что CFS меняет этот параметр, поэтому рекомендуется включить опцию sysctls.
• sched_child_runs_first: дочерний элемент назначается следующим после fork; это поведение по умолчанию. Если установлено значение 0, то эстафета передаётся родителю.
• sched_min_granularity_ns: минимальная степень детальности вытеснения для задач, связанных с процессором.
• sched_features: содержит информацию о различных отладочных параметрах.
• sched_stat_granularity_ns: степень детальности сбора статистики планировщика.

Ниже приведены некоторые типовые значения параметров реального времени системы:

[root@dodge ~]# sysctl -A|grep "sched" | grep -v "domain"
kernel.sched_min_granularity_ns = 4000000
kernel.sched_latency_ns = 40000000
kernel.sched_wakeup_granularity_ns = 2000000
kernel.sched_batch_wakeup_granularity_ns = 25000000
kernel.sched_stat_granularity_ns = 0
kernel.sched_runtime_limit_ns = 40000000
kernel.sched_child_runs_first = 1
kernel.sched_features = 29
kernel.sched_compat_yield = 0
[root@dodge ~]#

Новый интерфейс отладки планировщика

С новым планировщиком поставляется неплохой интерфейс отладки, который также предоставляет статистику в реальном времени. Эти функции реализованы в kernel/sched_debug.c и kernel/sched_stats.h соответственно. Для сбора статистики планировщика и отладочной информации в реальном времени в псевдофайловую систему proc было добавлено несколько файлов:

• /proc/sched_debug: отображает текущие значения настроек реального времени планировщика, статистику CFS и информацию очереди выполнения по всем доступным процессорам. Функция sched_debug_show() вызывается и определяется в sched_debug.c, когда производится чтение этого файла proc.
• /proc/schedstat: выводит статистику очереди выполнения, а также статистику доменов для систем с SMP для всех подключенных процессоров. Функция show_schedstat(), определенная в kernel/sched_stats.h, обрабатывает операцию чтения этой записи proc.
• /proc/[PID]/sched: выводит информацию о соответствующих сущностях планирования. При чтении этого файла вызывается функция proc_sched_show_task(), определенная в kernel/sched_debug.c.

Какие изменения ожидаются в версии 2.6.24? Итак, вместо того, чтобы гнаться за глобальными часами (fair_clock), задачи гонятся друг за другом. Будут введены часы задач (сущности планировщика), vruntime, (wall_time/task_weight), часы для новых задач будут инициализироваться по аппроксимированному среднему значению.

Другие важные изменения затрагивают ключевые структуры данных. Ниже приведены плановые изменения в struct sched_entity:

struct sched_entity { /* Defined in /usr/include/linux/sched.h */
- long wait_runtime;
- s64 fair_key;
+ u64 vruntime;
- u64 wait_start_fair;
- u64 sleep_start_fair;
 ...
 ...
}

Ниже приведены изменения в struct cfs_rq:

 struct cfs_rq { /* Defined in kernel/sched.c */
- s64 fair_clock;
- s64 wait_runtime;
- u64 sleeper_bonus;
- unsigned long wait_runtime_overruns, wait_runtime_underruns;
+ u64 min_vruntime;
 
+ struct sched_entity *curr;
 
+#ifdef CONFIG_FAIR_GROUP_SCHED
 ...
+ struct task_group *tg; /* group that "owns" this runqueue */
 ...
#endif
 };

Для группировки задач была введена новая структура:

struct task_group { /* Defined in kernel/sched.c */
 #ifdef CONFIG_FAIR_CGROUP_SCHED
 struct cgroup_subsys_state css;
 #endif
 /* schedulable entities of this group on each cpu */
 struct sched_entity **se;
 /* runqueue "owned" by this group on each cpu */
 struct cfs_rq **cfs_rq;
 unsigned long shares;
 /* spinlock to serialize modification to shares */
 spinlock_t lock;
 struct rcu_head rcu;
};

Каждая задача отслеживает время своего выполнения, и на основе этих значений задачи ставятся в очередь. Это означает, что задача, работавшая меньше всего, будет самой левой. Приоритеты также реализованы путём взвешивания времени. Каждая задача пытается быть назначенной ровно один раз в течение периода:

sched_period = (nr_running > sched_nr_latency) ? sysctl_sched_latency : ((nr_running * sysctl_sched_latency) / sched_nr_latency)

где sched_nr_latency = (sysctl_sched_latency / sysctl_sched_min_granularity). Таким образом, если существует несколько запускаемых задач latency_nr, период планирования линейно удлиняется. sched_slice() - функция, определенная в sched_fair.c, где выполняются эти расчёты.

Итак, если каждая запускаемая задача получает свою справедливое количество времени sched_slice() , это значит, что она потратила sched_period времени, и каждая задача будет работать эквивалентное время, пропорциональное её весу. Кроме того, в любой момент времени CFS обязуется запустить сначала sched_period, поскольку последняя запланированная задача будет запущена вновь в этом окне.

Поэтому, когда появляется новая запускаемая задача, существуют жёсткие требования к её размещению. Эта задача не может быть запущена, пока не будут запущены все другие задачи; в противном случае данные им обещания будут нарушены. Однако, поскольку эта задача ставится в очередь, появление дополнительного веса в очереди выполнения сократит кванты для всех других задач, освободив свободное время в конце sched_priod точно под размер, нужный новой задаче. Туда и помещается новая задача.

Усовершенствование планирования групп в ядре 2.6.24

В ядре 2.6.24 вы сможете настроить планировщик на равномерность не только по отношению к задачам, но и к пользователям и группам. Задачи можно группировать в сущности, и планировщик будет равномерным по отношению к этим сущностям, и только потом - к задачам, входящим в эти сущности. Чтобы включить эту возможность, во время сборки ядра необходимо выбрать CONFIG_FAIR_GROUP_SCHED. По состоянию на сегодняшний день группировать можно только задачи SCHED_NORMAL и SCHED_BATCH.

Есть два взаимоисключающих способа группировки задач, основанных на:

• идентификаторах пользователя.
• псевдофайловой системе cgroup: Этот параметр позволяет администраторам создавать группы, если это необходимо. Более подробную информацию можно найти в файле cgroups.txt в директории документации исходного кода ядра.

Выбрать нужный вариант можно с помощью конфигурационных параметров ядра CONFIG_FAIR_USER_SCHED и CONFIG_FAIR_CGROUP_SCHED.

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

Благодарности

Я благодарен Петеру Зейлстре за значительный вклад в разработку планировщика CFS и за то, что он выделил из своего плотного графика время и дал мне свои комментарии и предположения по улучшению этой статьи. Выражаю признательность Шриватсе Ваддагири за отличную работу над планированием групп CFS, и создателю RSDL Кону Коливасу. Также выражаю благодарность Инго Молнару, поддерживающему планировщик Linux Scheduler, за интерес, проявленный к этой статье.

Об авторе

		Авинеш Кумар (Avinesh Kumar) является разработчиком системного программного обеспечения в Andrew File System Team в IBM Software Labs в Пуне (Индия). Он занимается отладкой дампов и крахов ядра и пользовательских программ, а также анализом сообщений об ошибках в системах Linux, AIX и Solaris. Авинеш имеет MCA от факультета вычислительной техники Пунского университета. Он энтузиаст Linux и проводит свободное время, изучая ядро Linux на своем компьютере с Fedora Core 6.