Планировщик задач Linux

Последняя версия важнейшего компонента ядра повышает масштабируемость

Ядро Linux® продолжает развиваться - появляется поддержка новейших технологий, растут надежность, масштабируемость и производительность. Одним из важнейших компонентов ядра версии 2.6 является планировщик задач, разработанный Инго Молнаром (Ingo Molnar). Данный планировщик является динамическим, поддерживает распределение нагрузки, а его алгоритм имеет сложность O(1). Данная статья расскажет об этих и некоторых других свойствах планировщика.

М. Тим Джонс, инженер-консультант, Emulex

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



04.09.2008

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

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

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

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


Проблемы предыдущих версий планировщиков задач Linux

О важности O-нотации

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

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

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

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

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


Знакомство с планировщиком задач Linux 2.6

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

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

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

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

Рисунок 1. Структура очереди задач планировщика версии 2.6
Структура очереди задач планировщика версии 2.6

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

Работа планировщика задач не отличается сложностью: он просто выбирает задачу для выполнения из списка с наивысшим приоритетом. Чтобы повысить эффективность этого процесса, для определения наличия задач в списке используется битовый массив. Следовательно, для поиска бита, соответствующего списку с наивысшим приоритетом, можно использовать инструкцию 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.

Таблица 1. Функции, составляющие код планировщика версии 2.6
Имя функцииОписание функции
scheduleГлавная функция планировщика. Планирует выполнение задачи с наивысшим приоритетом.
load_balanceПроверяет, не требуется ли перераспределение нагрузки и, в случае необходимости, предпринимает попытку переноса задач.
effective_prioВозвращает эффективный приоритет задачи (рассчитанный на основе статического приоритета задачи и всех "наград" и "штрафов").
recalc_task_prioВычисляет "награду" или "штраф" для указанной задачи на основе времени простоя.
source_loadВычисляет консервативную оценку загрузки ЦП-источника (с которого может быть перенесена задача).
target_loadВычисляет либеральную оценку загрузки целевого ЦП (на который может быть потенциально перенесена задача).
migration_threadВысокоприоритетный системный поток, осуществляющий миграцию задач между ЦП.

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


Забегая вперед

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

Ресурсы

Научиться

  • Оригинал статьи Inside the Linux scheduler (EN).
  • В статье "Improving Linux kernel performance and scalability" (EN) (developerWorks, январь 2003 г.) рассказывается о том, как замерить производительность ядра Linux для последующей настройки системы (включая настройку планировщика).
  • Обзор Linux Process Scheduler Improvements in Version 2.6.0 (EN), подготовленный Open Source Development Labs, содержит достоверные данные по улучшениям в планировщике версии 2.6 по сравнению с версией 2.4 на примере различных многопроцессорных конфигураций.
  • Статья "Linux Kernel 2.6: the Future of Embedded Computing" (EN) (Linux Journal, март 2004 г.) рассказывает о части важнейших возможностей ядра версии 2.6, включая планирование задач и его влияние на встроенные системы.
  • Статья "Kernel comparison: Improvements in kernel development from 2.4 to 2.6" (EN) (developerWorks, февраль 2004 г.) позволит взглянуть на инструменты, тесты и методы за кулисами процесса создания ядра 2,6.
  • IBM Redbook An Application Centric Performance Evaluation of the Linux 2.6 Operating System (EN) (июль 2004 г.) содержит подробные сведения о масштабируемости и различных аспектах производительности реальных приложений в среде Linux 2.6.
  • Статья "Migrating from Linux 2.4 to 2.6 on iSeries and pSeries" (EN) (developerWorks, июль 2004 г.) содержит обзор различий между версиями 2.4 и 2.6 ядра Linux на платформе POWER.
  • В статье "Linux 2.6 for Embedded Systems -- Closing in on Real Time" (EN) (RTC Magazine, ноябрь 2003 г.) обсуждается мнение, согласно которому для встроенных систем реального времени лучшей реализацией планировщика является 2.6.
  • Доктор Ульрих Вейганд (Dr. Ulrich Weigand) рассказывает в своей презентации What's New in Linux 2.6 (EN) о том, как Linux 2.6 помогает в развитии платформы IBM zSeries.
  • В разделе Linux сайта developerWorks можно найти другие материалы для Linux-разработчиков.
  • Получайте самую свежую информацию из обзоров событий мира технологий и Web-трансляций developerWorks.(EN)

Получить продукты и технологии

Обсудить

Комментарии

developerWorks: Войти

Обязательные поля отмечены звездочкой (*).


Нужен IBM ID?
Забыли Ваш IBM ID?


Забыли Ваш пароль?
Изменить пароль

Нажимая Отправить, Вы принимаете Условия использования developerWorks.

 


Профиль создается, когда вы первый раз заходите в developerWorks. Информация в вашем профиле (имя, страна / регион, название компании) отображается для всех пользователей и будет сопровождать любой опубликованный вами контент пока вы специально не укажите скрыть название вашей компании. Вы можете обновить ваш IBM аккаунт в любое время.

Вся введенная информация защищена.

Выберите имя, которое будет отображаться на экране



При первом входе в developerWorks для Вас будет создан профиль и Вам нужно будет выбрать Отображаемое имя. Оно будет выводиться рядом с контентом, опубликованным Вами в developerWorks.

Отображаемое имя должно иметь длину от 3 символов до 31 символа. Ваше Имя в системе должно быть уникальным. В качестве имени по соображениям приватности нельзя использовать контактный e-mail.

Обязательные поля отмечены звездочкой (*).

(Отображаемое имя должно иметь длину от 3 символов до 31 символа.)

Нажимая Отправить, Вы принимаете Условия использования developerWorks.

 


Вся введенная информация защищена.


static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=40
Zone=Linux
ArticleID=335757
ArticleTitle=Планировщик задач Linux
publish-date=09042008