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

Википедии, красно-черное дерево
— это тип самосбалансированного бинарного дерева, структура данных,
используемая для реализации ассоциативных массивов. В красно-чёрном
дереве создаётся узел для каждого работающего процесса. Процесс,
находящийся в самой левой позиции чёрно-красного дерева, является
следующим запланированным процессом. Красно-чёрное дерево сложно
устроено, но у него хорошее время исполнения в самом худшем варианте и
оно эффективно на практике: оно позволяет выполнять поиск, добавление и
удаление за время 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:

Листинг 1. Структура task_struct

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

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

Листинг 2. Структура 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.

Листинг 3. Структура 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 в очереди выполнения

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

Листинг 4. Структура cfs_rq

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

Планировщик
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: степень детальности сбора статистики планировщика.

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

Листинг 5. Типичные значения параметров реального времени

[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

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

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

Листинг 6. Планируемые изменения в структуре sched_entity для ядра 2.6.24

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:

Листинг 7. Планируемые изменения в структуре cfs_rq для ядра 2.6.24

 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
};

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

Листинг 8. Новая структура task_group

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.

Карта сайта: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34 Текст перед ссылками: Дойки видео на сайте http://rudojki.com . Текст после ссылок: