Linux Kernel (Ядро линукса) (часть 1)

Планирование процессов

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

Как всегда, для упрощения описания мы ограничиваемся архитектурой 80x86. В частности, мы предполагаем, что система использует модель однородного доступа к памяти, и что системный тик равен 1 мс.

Политика планирования

Алгоритм планирования в традиционных Unix-подобных операционных системах должен отвечать нескольким конфликтующим требованиям: быстрое время отклика процесса, удовлетворительное обеспечение фоновых задач ресурсами, недопущение голодной смерти” процессов, сбалансированное удовлетворение нужд низко- и высокоприоритетных процессов и т. д. Набор правил, определяющих, когда и как выбирается новый процесс для выполнения, называется политикой планирования.

Планирование в Linux основано на технике разделения времени. Несколько процессов работают мультиплексно по времени”, поскольку время процессора разбито на отрезки, каждый из которых предоставляется одному работающему процессу1. Конечно, один процессор в данный момент времени может выполнять только один процесс. Если текущий процесс не завершается к моменту истечения отрезка, или кванта, времени, может произойти переключение на другой процесс. Разделение времени основано на прерываниях от таймера и, таким образом, прозрачно для процессов. Для обеспечения разделения времени процессора никакой дополнительный код в программах не требуется.

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

В Linux приоритет процесса является динамическим понятием. Планировщик отслеживает, чем занимаются процессы, и периодически корректирует их приоритеты. Таким образом, процессы, которым долгое время было отказано в доступе к процессору, "проталкиваются” за счет динамического увеличения их приоритета. Соответственно, процессы, работающие слишком долго, ”на- казываются” понижением приоритета.

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

Альтернативная классификация различает три вида процессов:

- Интерактивные процессы — эти процессы постоянно взаимодействуют с пользователями и, следовательно, много времени проводят в ожидании нажатия на клавишу или манипуляции с мышью. При поступлении входных данных процесс должен быть быстро разбужен”, иначе пользователь сочтет систему медлительной. Как правило, среднее время задержки должно лежать в интервале от 50 до 150 мс. Разброс между такими задержками тоже должен быть невелик, чтобы пользователь не подумал, что система ведет себя странно. Типичными интерактивными программами
являются командные оболочки, текстовые редакторы и графические приложения.

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

- Процессы реального времени — эти процессы предъявляют к планированию очень жесткие требования. Их ни в коем случае нельзя блокировать ради процессов с низким приоритетом, а также они должны иметь гарантированно малое время отклика с минимальным разбросом. Типичными программами реального времени являются аудио- и видеоплееры, программы управления роботами и программы, собирающие данные с физических датчиков.
Предложенные здесь две классификации в определенном смысле независимы. Например, пакетный процесс может быть привязан либо к вводу/выводу (сервер базы данных), либо к процессору (программа рендеринга, т. е. визуализации изображения). В то время как программы реального времени легко распознаются как таковые алгоритмом планирования в Linux, простой способ отличить интерактивную программу от пакетной отсутствует. Планировщик в Linux придерживается сложного эвристического алгоритма, основанного на предыдущем поведении процесса, когда решает, следует ли считать данный процесс интерактивным или пакетным. Естественно, планировщик благоволит” интерактивным процессам за счет пакетных.

Программисты могут повлиять на приоритеты планирования с помощью системных вызовов.