Разработка ядра Linux

• Должна быть обеспечена хорошая производительность для интерактивных приложений. Даже при значительной загрузке система должна иметь хорошую реакцию и немедленно планировать выполнение интерактивных задач.

• Должна быть обеспечена равнодоступность ресурсов (fairness). Ни один процесс не должен ощущать нехватку квантов времени за допустимый период. Кроме того, ни один процесс не должен получить недопустимо большое значение кванта времени.

• Должна быть обеспечена оптимизация для наиболее распространенного случая, когда число готовых к выполнению процессов равно 1–2, но в то же время должно обеспечиваться хорошее масштабирование и на случай большого числа процессоров, на которых выполняется большое число процессов.

Новый планировщик позволяет удовлетворить всем этим требованиям.

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

Основная структура данных планировщика — это очередь выполнения (runqueue). Очередь выполнения определена в файле kernel/sched.c[21] в виде структуры struct runqueue. Она представляет собой список готовых к выполнению процессов для данного процессора.

Для каждого процессора определяется своя очередь выполнения. Каждый готовый к выполнению процесс может находиться в одной и только в одной очереди выполнения. Кроме этого, очередь выполнения содержит информацию, необходимую для планирования выполнения на данном процессоре. Следовательно, очередь выполнения — это действительно основная структура данных планировщика для каждого процессора. Рассмотрим нашу структуру, описание которой приведено ниже. Комментарии объясняют назначения каждого поля.

struct runqueue {

 spinlock_t lock; /* спин-блокировка для зашиты этой очереди выполнения */

 unsigned long nr_running; /* количество задач, готовых к выполнению */

 unsigned long nr_switches; /* количество переключений контекста */

 unsigned long expired timestamp; /* время последнего обмена массивами */

 unsigned long nr_uninterruptible; /* количество заданий в состоянии

                                      непрерываемого ожидания */

 unsigned long long timestamp last tick; /* последняя метка времени

                                            планировщика */

 struct task_struct *curr; /* текущее задание, выполняемое на данном

                              процессоре */

 struct task_struct *idle; /* холостая задача данного процессора */

 struct mm_struct *prev_mm; /* поле mm_struct последнего выполняемого

                               задания */

 struct prio_array *active; /* указатель на активный массив приоритетов */

 struct prio_array *expired; /* указатель на истекший

                                массив приоритетов */

 struct prio_array arrays[2]; /* массивы приоритетов */

 struct task_struct *migration_thread; /* миграционный поток для

                                          данного процессора */

 struct list_head migration_queue; /* миграционная очередь для

                                      данного процессора */

 atomic_t nr_iowait; /* количество заданий, ожидающих на ввод-вывод */

};

Поскольку очередь выполнения — это основная структура данных планировщика, существует группа макросов, которые используются для доступа к определенным очередям выполнения. Макрос cpu_rq(processor) возвращает указатель на очередь выполнения, связанную с процессором, имеющим заданный номер. Аналогично макрос this_rq возвращает указатель на очередь, связанную с текущим процессором. И наконец, макрос task_rq(task) возвращает указатель на очередь, в которой находится соответствующее задание.