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

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

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

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

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

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

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

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

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

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

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

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

Основная структура данных планировщика — это очередь выполнения ( runqueue ). Очередь выполнения определена в файле kernel/sched.c [21] Может возникнуть вопрос: почему используется файл kernel/sched.c , а не заголовочный файл include/linux/sched.h ? Потому что желательно абстрагироваться от реализации кода планировщика и обеспечить доступность для остального кода ядра только лишь некоторых интерфейсов. в виде структуры struct runqueue. Она представляет собой список готовых к выполнению процессов для данного процессора.