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

Что такое планировщик задач?

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

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

О важности O-нотации O-нотация позволяет оценить количество времени, затрачиваемого на выполнение алгоритма. Время, затрачиваемое алгоритмом O(n) линейно зависит от объема входных данных n, тогда как алгоритм O(n^2) затратит время, равное квадрату этого объема. Алгоритм О(1) не зависит от объема входных данных и выполняется за постоянное время.

До выхода ядра версии 2.6 планировщик имел существенное ограничение, проявлявшееся при большом количестве выполняющихся задач. Причиной тому был алгоритм планировщика, имевший сложность O(n). При его использовании время, затрачиваемое на планирование, находится в функциональной зависимости от числа задач, выполняющихся в системе. Другими словами, чем больше число задач (n), тем больше времени требуется на их планирование. При очень высокой нагрузке планирование может занять почти все процессорное время, оставив собственно задачам лишь малую его долю. Таким образом, алгоритму не хватало масштабируемости.

Планировщик, применявшийся до выхода версии 2.6, также использовал единую очередь задач для симметричных мультипроцессорных (SMP) систем. Это означало, что задача могла быть назначена любому из процессоров, что хорошо для распределения нагрузки, но плохо для кэширования. Представим, например, что задача выполняется на ЦП-1 и ее данные находятся в кэше этого процессора. Если задача будет перепланирована на ЦП-2, ее данные потребуется убрать из кэша ЦП-1 и разместить в кэше ЦП-2.

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

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

Планировщик версии 2.6 спроектирован и разработан Инго Молнаром. Инго участвует в разработке ядра Linux с 1995 г. Он задался целью создать новый планировщик исключительно на основе алгоритмов сложности O(1) для пробуждения процессов, переключения контекстов и обработки прерывания таймера. Одной из причин возникновения потребности в новом планировщике были виртуальные машины Java™ (JVM). Модель программирования этого языка активно использует потоки, что приводит к росту накладных расходов при использовании планировщика с алгоритмом О(n). Планировщик с алгоритмом O(1) не имеет данного недостатка, поскольку его производительность не ухудшается при высокой нагрузке. Это позволяет обеспечить эффективную работу виртуальных машин Java™.

Помимо устранения прочих недостатков, в планировщике версии 2.6 решены три основные проблемы, присущие его предшественнику (O(n) и проблемы масштабируемости на многопроцессорных системах). Сейчас мы рассмотрим общие принципы устройства планировщика версии 2.6.

Основные структуры данных

Начнем с обзора структур данных, используемых планировщиком. Каждый ЦП имеет очередь задач, состоящую из 140 списков, обслуживаемых в порядке FIFO и содержащих задачи, имеющие соответствующий приоритет. Задачи, запланированные к выполнению, добавляются в конец списка. Каждой задаче выделяется отрезок времени, определяющий продолжительность ее выполнения. Первые 100 списков очереди задач зарезервированы для задач реального времени, а последние 40 - для пользовательских задач (см. рисунок 1). Позже вы поймете важность этого разграничения.

Помимо очереди задач ЦП, называемой активной очередью задач, существует еще неактивная очередь. После того, как задача, находящаяся в активной очереди, исчерпывает отведенный ей отрезок времени, она переносится в неактивную очередь. При переносе происходит пересчет ее отрезка времени (также пересчитывается ее приоритет, но об этом позже). Если в активной очереди отсутствуют задачи с данным приоритетом, соответствующие указатели активной и неактивной очередей меняются местами; при этом неактивный список становится активным.

Работа планировщика задач не отличается сложностью: он просто выбирает задачу для выполнения из списка с наивысшим приоритетом. Чтобы повысить эффективность этого процесса, для определения наличия задач в списке используется битовый массив. Следовательно, для поиска бита, соответствующего списку с наивысшим приоритетом, можно использовать инструкцию find-first-bit-set, которую поддерживает большинство архитектур процессоров. Время, затрачиваемое на поиск задачи, зависит не от числа активных задач, а от числа приоритетов. Следовательно, планировщик версии 2.6 является процессом сложности O(1), поскольку время, затрачиваемое на планирование задачи постоянно и детерминистично вне зависимости от числа активных задач.

Улучшенная поддержка симметричной многопроцессорной обработки

Итак, что же такое симметричная многопроцессорная обработка? Это архитектура, обеспечивающая одновременное выполнение отдельных задач на нескольких ЦП, в отличие от традиционной асимметричной обработки, при которой все задачи выполняются единственным ЦП. Симметричная многопроцессорная обработка может быть полезной для многопоточных приложений.

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

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

Вытеснение задач

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

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

Динамическое назначение приоритетов задач

Для предотвращения полной загрузки процессора единственной задачей и вызванного этим отсутствия доступа остальных задач к ЦП, планировщик версии 2.6 может динамически изменять приоритет задач. Это достигается путем "штрафования" задач, ограниченных скоростью процессора и "награждению" задач, ограниченных скоростью ввода/вывода. Задачи, ограниченные скоростью ввода/вывода, обычно создают нагрузку на ЦП при подготовке операций ввода/вывода и, затем, ожидают их завершения. Данный тип поведения позволяет другим задачам получить доступ к ЦП.

Снижение времени отклика Задачи, взаимодействующие с пользователем, являются интерактивными и, следовательно, получают преимущество перед неинтерактивными задачами. Поскольку взаимодействие с пользователем ограничено скоростью ввода/вывода (при выводе данных в стандартный поток вывода или при ожидании данных, поступающих через стандартный поток ввода), такие задачи получают повышение приоритета, что позволяет снизить время отклика.

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

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

Важно заметить, что коррекция приоритета производится только для пользовательских задач - задачи реального времени это не затрагивает.

Распределение нагрузки в симметричных многопроцессорных системах

Задачи, запущенные в SMP-системе, попадают в очередь задач одного из ЦП. В общем случае невозможно предсказать, завершится ли задача почти сразу или будет выполняться в течение длительного времени. Следовательно, первоначальное распределение задач по ЦП скорее всего будет неоптимальным.

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

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

Теперь вспомним, что кэш ЦП представляет собой локальную (находящуюся непосредственно в ЦП) память, обеспечивающую более высокую, чем системная память скорость доступа. Локальный кэш ЦП считается "горячим" если содержит данные задачи, выполняющейся на этом процессоре. Если же таких данных в кэше нет, то для данной задачи он считается "холодным".

К сожалению, обеспечение полной загрузки ЦП путем переноса задач приводит к возникновению такой неприятной проблемы, как "холодный" кэш.

Исходный код планировщика версии 2.6 компактно размещается в файле /usr/src/linux/kernel/sched.c. Список наиболее интересных функций, находящихся в данном файле, приведен в таблице 1.

Кроме того, в файле /usr/src/linux/kernel/sched.c можно найти структуру очереди задач. Новый планировщик также имеет функцию сбора статистики, которую можно активировать с помощью параметра конфигурации ядра CONFIG_SCHEDSTATS. Собранная статистика может быть получена из файла /proc/schedstat, находящегося в файловой системе /proc, и содержит различные сведения по каждому ЦП системы, включая статистику распределения нагрузки и переноса задач.

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

Об авторе

		M. Тим Джонс (M. Tim Jones) является архитектором встраиваимого программного обеспечения и автором работ: Программирование Приложений под GNU/Linux, Программирование AI-приложений и Использование BSD-сокетов в различных языках программирования. Он имеет опыт разработки процессоров для геостационарных космических летательных аппаратов, а также разработки архитектуры встраиваемых систем и сетевых протоколов. Сейчас Тим работает инженером-консультантом в корпорации Эмулекс (Emulex Corp.) в г.Лонгмонт, Колорадо.