Почему так важна архитектура планировщика

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

В этой статье я преднамеренно старался избегать комментариев исходного кода планировщика, поскольку вы легко сможете найти их (комментарии) в Сети (см. радел Ссылки). Здесь рассматриваются проблемы, с которыми столкнулись разработчики при создании нового планировщика, как эти проблемы были решены и в каком направлении предполагается развивать планировщик дальше. Могу сказать, что лучший путь к пониманию лежит через изучение исходного кода. Если у вас установлены исходные тексты ядра, то реализацию планировщика вы найдете в kernel/sched.c.

Цели планирования

Планировщик Linux преследует несколько целей :

1. Беспристрастность :

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

2. Производительность и загрузка процессора :

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

3. Минимальные накладные расходы :

   Сам планировщик должен занимать процессор настолько малое время, насколько это возможно. Время реакции планировщика должно быть минимальным. Но тут есть хитрый момент. Вообще считается, что процесс планирования не есть полезная работа (??). Однако, если планирование произведено безупречно, даже если оно потребовало дополнительных затрат некоторого количества времени, то это определенно стоит затраченных усилий. Но как решить -- где "золотая середина"? Большинство планировщиков решают эту проблему с помощью эвристических алгоритмов.

4. Планирование на основе приоритетов :

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

5. Время цикла обслуживания, время ожидания :

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

6. Время отклика и дисперсия :

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

7. Прочие :

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

Усовершенствования в планировщике

• Алгоритм планирования сложности O(1)

  Вы можете спросить: "Что такое O(1)?". Об O() (часто эту нотацию называют "большое О") я расскажу лишь вкратце. Более подробную информацию о "большом О" вы найдете в любой хорошей книге, посвященной алгоритмам (от себя могу порекомендовать http://algolist.manual.ru/misc/o_n.php прим. перев.). Методика O() используется для оценки производительности алгоритмов вне зависимости от машинной реализации. Она определяет верхний предел времени работы алгоритма для самого тяжелого случая. Это исключительная методика, применяемая для сравнения эффективности алгоритмов относительно времени исполнения.

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

  Планировщик Linux тратит постоянное время для того, чтобы наметить процессы в очереди готовых к запуску задач. Следовательно, можно сказать, что он имеет уровень сложности O(1). Независимо от количества активных процессов в системе, планировщик всегда затрачивает одинаковое время на их планирование. Алгоритм "пробуждения" процесса, выбор следующего, переключение контекста и накладные расходы на обработку прерываний от таймера в текущей версии ядра (здесь имеется ввиду ядро 2.5.49 -- см. раздел Ссылки) имеет сложность O(1).

• Улучшенная поддержка SMP и масштабируемость

  Как уже упоминалось в самом начале, ядро Linux имеет очень широкий диапазон применений, начиная от наручных часов и заканчивая супер-ЭВМ. В более ранних версиях планировщика имелись определенные проблемы с масштабируемостью. Частично эти проблемы снимались путем внесения изменения в ядро, предназначенного для целевой архитектуры. Однако, в целом масштабируемость планировщика оставляла желать лучшего. В новом планировщике значительно улучшена масштабируемость и поддержка SMP (от англ. Symmetric Multi Processing -- Симметричное Мультипроцессирование, т.е. поддержка многопроцессорных систем прим. перев.) Значительно улучшена производительность планировщика на многопроцессорных системах. Одна из целей, обозначенных Инго Молнаром (Ingo Molnar) -- автора O(1)-планировщика, состоит в том, чтобы полностью загрузить процессоры работой на SMP-системах, если таковая (работа) имеется. Кроме того, необходимо обратить внимание на то, что задачи иногда не планируются на различные процессоры. Это должно помочь избежать переполнения кеша с запрашиваемыми данными.

• Пакетное планирование задач

  Это не совсем новая особенность, но имеется ряд "заплат", которые могли бы быть приняты в ядро для поддержки пакетного планирования. В ранних версиях ядра также имелась некоторая поддержка пакетного планирования. На текущий момент выполняется приоритетное пакетное планирование. В ядре используется примерно 40 уровней приоритетов^[*1] (хотя все они отображаются примерно на 5 различных уровней). Пакетные задания получают процессор главным образом тогда, когда в системе не очень много интерактивных процессов или процессов, занятых вычислительной работой ("числодробилок"), которые имеют более высокий приоритет. Пакетным задачам выделяются большие кванты времени, по сравнению с обычными процессами, что в свою очередь минимизирует количество обращений к кешу с целью подкачки данных, повышая тем самым общую производительность пакетных заданий.

• Улучшена производительность интерактивных задач

  Одно из главных усовершенствований в планировщике -- это обнаружение и повышение производительности интерактивных задач. Достичь этого в старом планировщике было очень тяжело. В новом планировщике обнаружение интерактивных процессов отделено от других задач планирования, таких как управление квантами времени. Интерактивные процессы обнаруживаются на основе статистики времени использования. Это означает, что интерактивные процессы имеют короткое время отклика при тяжелых нагрузках, а "жадные" до процессора задачи не смогут его монополизировать. Новый планировщик определяет активность интерактивного процесса и отдает ему преимущество перед другими процессами. Даже тогда, когда задача планируется среди других интерактивных процессов с использованием циклического (Round-Robin) алгоритма. Это очень важно для настольных систем, так как теперь пользователь не будет замечать увеличения времени отклика, когда он запускает задачи, интенсивно использующие процессор, например перевод музыкальных файлов в формат ogg. В будущем планируется объединение алгоритма O(1) с кодом приоритетного прерывания (preemption), чтобы уменьшить время отклика для интерактивных задач.

• Улучшена масштабируемость и поддержка большего количества архитектур

  Благодаря изменениям, внесенным в новый планировщик, он легче переносится на другие архитектуры, типа NUMA (от англ. Non-Uniform Memory Access -- неоднородный доступ к памяти прим. перев.) и SMT (от англ. Simultaneous Multithreading -- Параллельная Многопоточность прим. перев.)
  
  От переводчика:
  Основная идея NUMA архитектуры заключается в образовании основной вычислительной системы посредством объединения однотипных модулей, коммутируемых высокоскоростной сетью. Каждый модуль может состоять из одного или нескольких процессоров со своей локальной памятью, которая образует единое адресное пространство системы и часто подсистемы ввода/вывода.
  Технология SMT позволяет одному процессору работать за нескольких сразу, повышая эффективность распределения и управления вычислительной нагрузкой. Когда обычный процессор выполняет несколько задач, он может перейти к следующей лишь после того, как завершит предыдущую. Многопоточный процессор способен обрабатывать сразу несколько потоков команд (или "нитей" -- threads) одновременно. Используя механизм многопоточности, SMT-процессор может выполнять от четырех до десяти команд за такт, тогда как обычный выполняет, как правило, лишь от одной до четырех. Кроме того, чтобы воспользоваться технологией SMT, переписывать приложения не потребуется.
  
  Архитектура NUMA используется на некоторых высокопроизводительных серверах и супер-ЭВМ. Кроме того, продолжается работа над SMT (Symmetric Multithreading -- Симметричная Многопоточность. Здесь я хочу внести некоторую ясность -- автор расшифровывает аббревиатуру SMT как Symmetric Multithreading -- Симметричная Многопоточность, однако в процессе работы над переводом я встречал расшифровку этой аббревиатуры как Simultaneous Multithreading -- Параллельная Многопоточность, что на мой взгляд, более точно отражает смысл этой технологии прим. перев.). SMT также известна под термином : HyperThreading (Гиперпоточность). Одна из причин этой работы состоит в том, что сейчас каждый процессор имеет свою очередь задач. И только код, управляющий распределением вычислительной нагрузки, имеет "глобальное" значение для системы. Таким образом, для отдельных архитектур, необходимо внести изменения в эту согласующую часть. Недавно были выпущены "заплаты" для NUMA. Они были введены в состав ядра 2.5.59. SMT-процессоры имеют два (или более) виртуальных процессора на одном физическом кристалле -- один "логический" процессор может выполнять какую нибудь работу, в то время как другой ожидает доступа к памяти. SMT может рассматриваться как своего рода NUMA, поскольку совместно используют кеш-память, а поэтому получают более быстрый доступ к памяти, к которой недавно обращался один из них. В направлении SMT также ведется работа, но новый O(1)-планировщик способен обслуживать SMT-процессоры достаточно хорошо и без внесения каких либо изменений. Недавно были выпущены "заплаты" к ядру для SMT. Хотя архитектура NUMA и имеет некоторое сходство с архитектурой SMT, тем не менее, планировщик Linux обрабатывает их по-разному.

• Прочие улучшения

  Планировщик дает дочерним (fork()ed) процессам более высокий приоритет, чем родительским процессам. Это может оказаться полезным для серверов, в которых ветвление часто используется для обслуживания запросов. Кроме того, это может оказаться полезным для приложений с графическим интерфейсом. Имеются также некоторые дополнения к планированию процессов реального времени (real-time), базирующемуся на приоритетах.

Ссылки

• Домашняя страница Ingo Molnar (O(1) patches)
• Linux Kernel Internals - Tigran Aivazian
• (на OpenNet имеется русский перевод)
• Обзор исходного кода ядра Linux на lxr.linux.no
  1. Дизайн планировщика
  2. Некоторые примечания к функциям планировщика

Vinayak

В настоящее время ведет курс APGDST в NCST. Область его интересов - сети, системы параллельных вычислений и языки программирования. Он верит, что Linux даст программной индустрии то же, что в свое время дало изобретение печати миру науки и литературы. В редкие периоды свободного времени он любит слушать музыку и читать книги. В настоящее время работает в проекте LIberatioN-UX, где он занимается настройкой удаленно-загружаемых рабочих станций под управлением Linux (тонкие клиенты) для учебных заведений/корпораций.

Примечания редактора

^[*1] См. info-страницы к программе nice -- уровни от -20 (самый высокий уровень) до 19 (самый низкий уровень).