Роберт Лав - Разработка ядра Linux

Рис. 4.1. Вычисление кванта времени процесса

Следует заметить, что процесс не обязательно должен использовать весь свой квант времени за один раз. Например, процесс, у которого квант времени равен 100 мс, не обязательно должен беспрерывно выполняться в течение 100 мс, рискуя потерять всю оставшуюся неистраченную часть кванта времени. Процесс может выполняться в течение пяти периодов длительностью по 20 мс каждый.

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

Когда истекает квант времени процесса, считается, что процесс потерял право выполняться. Процесс, у которого нет кванта времени, не имеет права выполняться до того момента, пока все другие процессы не используют свой квант времени. Когда это случится, то у всех процессов будет значение оставшегося кванта времени, равное нулю. В этот момент значения квантов времени для всех процессов пересчитываются. В планировщике ОС Linux используется интересный алгоритм для обработки ситуации, когда все процессы использовали свой квант времени. Этот алгоритм будет рассмотрен далее.

Вытеснение процесса

Как уже упоминалось, операционная система Linux использует вытесняющую многозадачность. Когда процесс переходит в состояние TASK_RUNNING, ядро проверяет значение приоритета этого процесса. Если это значение больше, чем приоритет процесса, который выполняется в данный момент, то активизируется планировщик, чтобы запустить новый процесс на выполнение (имеется в виду тот процесс, который только что стал готовым к выполнению). Дополнительно, когда квант времени процесса становится равным нулю, он вытесняется и планировщик готов к выбору нового процесса.

Стратегия планирования в действии

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

В такой системе планировщик установит для текстового редактора больший приоритет и выделит более продолжительный квант времени, чем для видеокодера, так как текстовый редактор — интерактивная программа. Для текстового редактора продолжительности кванта времени хватит с избытком. Более того, поскольку текстовый редактор имеет больший приоритет, он может вытеснить процесс видеокодера при необходимости. Это гарантирует, что программа текстового редактора будет немедленно реагировать на нажатия клавиш. Однако это не причинит никакого вреда и видеокодеру, так как программа текстового редактора работает с перерывами, и во время перерывов видеокодер может монопольно использовать систему. Все это позволяет оптимизировать производительность для обоих приложений.

Алгоритм планирования

В предыдущих разделах была рассмотрена в самых общих чертах теория работы планировщика процессов в операционной системе Linux. Теперь, когда мы разобрались с основами, можно более глубоко погрузиться в то, как именно работает планировщик ОС Linux.

Программный код планировщика операционной системы Linux содержится в файле kernel/sched.c. Алгоритм планирования и соответствующий программный код были существенно переработаны в те времена, когда началась разработка ядер серии 2.5. Следовательно, программный код планировщика является полностью новым и отличается от планировщиков предыдущих версий. Новый планировщик разрабатывался для того, чтобы удовлетворять указанным ниже требованиям.

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

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

• Должна быть реализована улучшенная SMP-привязка (SMP affinity). Задания, для выполнения на каждом процессоре многопроцессорной системы, должны быть распределены правильным образом, и, по возможности, выполнение этих задач должно продолжаться на одном и том же процессоре. Осуществлять миграцию заданий с одного процессора на другой необходимо только для уменьшения дисбаланса между размерами очередей выполнения всех процессоров.

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

• Должна быть обеспечена равнодоступность ресурсов (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) возвращает указатель на очередь, в которой находится соответствующее задание.