Планировщик задач Linux. Тонкая настройка планировщика.

Применение генетического алгоритма для оптимизации процесса планирования.

Лапушкин Антон Сергеевич,

аспирант Московского Инженерно-Физического Института,

главный специалист Службы безопасности ООО «Мострансгаз».

Операционная система (далее ОС) Linux давно зарекомендовала себя как надежное и эффективное средство решения любых задач. По многим параметрам ей нет равных в сфере серверных приложений. Некоторые дистрибутивы Linux так адаптированы для работы  обыкновенного пользователя и решения его повседневных задач, что могут смело носить название настольной рабочей системы, немногим уступая ОС Microsoft Windows. Секрет такого успеха Linux кроется в его некоммерческом характере и открытых кодах. Любой разработчик, обладающий желанием и необходимыми знаниями, может внести изменение в код Linux, начиная с графических приложений и заканчивая ядром ОС. Над ОС Linux трудится не узкий круг программистов, а мировое сообщество разработчиков. Именно по этой причине Linux развивается быстрыми темпами, постоянно выходят обновления компонентов ОС. В случае выявления ошибки в коде, она исправляется за максимально короткие сроки. Фундаментом ОС Linux является ее ядро, которое также как и все остальные компоненты периодически обновляется. В подсистемы ядра вносятся изменения, оптимизирующие его работу, добавляющие поддержку нового оборудования. В данной статье речь пойдет об одной из подсистем ядра, называемой планировщиком задач, и об идее разработчика Джейка Мойланена (Jake Moilanen) по внедрению в подсистему планирования генетического алгоритма, позволяющего оптимизировать ее работу.

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

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

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

Алгоритм планирования Linux 2.6 был полностью переработан Инго Молнаром (Ingo Molnar). Для поиска очередной для запуска задачи взамен неэффективной операции последовательного сравнения приоритетов стала применяться битовая строка приоритетов и процессорная операция поиска первого установленного бита в ней, выполняющаяся за фиксированное количество тактов. Таким образом, время планирования перестает зависеть от количества задач в системе[1]. Далее речь пойдет исключительно о планировщике Linux 2.6.

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

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

child_penalty: Процент величины sleep_avg задачи родителя, наследуемая его потомками. sleep_avg – средняя величина времени, которое задача проводит в состоянии сна, используется планировщиком для определения степени ее интерактивности. Задачи с большим значением sleep_avg рассматриваются планировщиком как интерактивные, им назначается  более высокий динамический приоритет и более длительный квант времени. Обычно значение child_penalty близко к 100 процентам.

exit_weight: При завершении вычислительной задачи, величина sleep_avg ее родителя уменьшается пропорционально величинам exit_weight и sleep_avg завершающейся задачи.

interactive_delta: По истечении выделенного кванта времени задача, рассматриваемая планировщиком как интерактивная, вместо перемещения в неактивную очередь отработавших задач заново помещается в очередь активных задач. Значение interactive_delta используется планировщиком при расчете степени интерактивности задачи для принятия решения о ее сохранении в очереди активных задач.

max_sleep_avg: Максимальное значение величины среднего времени сна задачи (sleep_avg). С ее увеличением задаче необходимо больше проводить в состоянии сна, чтобы быть рассмотренной планировщиком в качестве интерактивной.

min_timeslice и max_timeslice: Минимальное и максимальное значения назначаемого задаче кванта времени. Задаче с большим динамическим приоритетом назначается больший квант времени.

parent_penalty: Процент величины sleep_avg задачи родителя, который остается ей после выполнения операции fork (). Как правило, величина parent_penalty равна 100 процентам, т.е. задача не теряет своей интерактивности после порождения новых задач. Уменьшение parent_penalty приводит к введению штрафа за порождение своих потомков для интерактивных задач.

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

starvation_limit: Как упоминалось ранее, по истечении выделенного кванта времени, интерактивные задачи могут быть заново помещены в активную очередь, в то время как обычные задачи перемещаются в неактивную очередь. Сохранение интерактивных задач в активной очереди позволяет им оставаться в состоянии готовности к выполнению, что играет важную роль для интерактивности всей системы в целом. Но это может привести к так называемому голоданию задач, находящихся в неактивной очереди, так как откладывается переключение между приоритетными очередями и соответственно их выполнение. Для предотвращения длительного голодания отработавших задач вводится величина starvation_limit, ограничивающая время их пребывания в неактивной очереди. Увеличение starvation_limit дает больше возможности для работы интерактивных задач в активной очереди за счет голодания отработавших задач. Уменьшение приводит к более справедливому поведению планировщика, но за счет уменьшения общей интерактивности системы[2].

Константы задаются в коде планировщика задач перед компиляцией ядра, т.е. не могут быть изменены в процессе работы системы. Для семейства ядер Linux 2.6 был разработан код-заплатка, подменяющий константы переменными и позволяющий изменять их  значения через интерфейс файловой системы /proc без перекомпиляции ядра. Таким образом, появляется возможность подстраивать работу планировщика к различным нагрузкам в реальном режиме времени без перекомпиляции ядра.

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

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

Принципиально новый подход был предложен разработчиком Джейком Мойланеном. Идея нового подхода заключается в применении генетического алгоритма базирующего на теории эволюции для подбора оптимальных настроек планировщика. Первоначально генерируется некоторое число различных вариантов тонких настроек планировщика, в терминологии теории эволюции называемое популяцией. Каждый представитель популяции апробируется в условиях текущей нагрузки. После чего производится оценка его влияния на производительность системы. В случае негативного влияния вариант настроек отбрасывается, при положительном влиянии он вовлекается в процесс эволюции – комбинируется с другими удачными вариантами, и процесс повторяется. После определенного количества итераций алгоритм определяет оптимальные настройки планировщика для текущей нагрузки на систему[3].

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

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

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

2)                 по результатам работы ядра для политики вычисляется величина fitness, показывающая, на сколько эффективно ядро работало с заданными значениями настроек;

3)                 процесс повторяется для всех политик из популяции;

4)                 все политики популяции сравниваются по значениям величины fitness. Политики со значением fitness ниже порогового отбрасываются;

5)                 путем комбинирования (скрещивания) оставшихся успешных политик создается новая популяция, обладающая лучшими качествами предыдущей;

6)                 чтобы новая популяция не выродилась, в нее вносится элемент случайности путем мутации (изменения) значений некоторых настроек заданного процента политик;

7)                 процесс повторяется, начиная с этапа 1.

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

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

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

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

Именно по такому принципу рассчитывается величина fitness для разных типов политик планирования. Учитывается комплекс параметров функционирования ядра – главным образом различные задержки. Например, для задач реального времени оценивается критичная для них задержка запуска, т.е. время с момента готовности к запуску до момента предоставления процессора. Для всех типов задач учитывается время с момента выполнения вызова fork родителем до момента выполнения потомка. Учитывается статистика работы планировщика – количество контекстных переключений задач в единицу времени. Разработчиком было сделано предположение, что чем меньше суммарные задержки, тем более эффективно работает система, и наоборот. Таким образом, значение fitness для политик с меньшими значениями задержек больше. Такие политики планирования принимаются как более эффективные среди остальных политик в популяции.

По данным разработчика Джейка Мойланена, тестирование с помощью Unixbench и SpecJBB ядра Linux с планировщиком, настраиваемым генетическим алгоритмом, показало улучшение некоторых показателей эффективности работы ядра на 1-3%. Но на некоторых смесях задач данное ядро показало ухудшение производительности системы. Причина этого кроется в методике расчета fitness, которая на данный момент требует доработки. Но, не смотря ни на что, попытка внедрения генетического алгоритма в ядро Linux является значительным событием, и она, безусловно, получит развитие в последующих версиях ядра.

Литература.

1. Роберт Лав. “Разработка ядра Linux, 2-е издание”. Пер. с англ. – М.: ООО “И.Д. Вильямс”, 2006. – 448 с.

2. Rick Fujiyama, Jeff Scherpelz, Matt Ferlo. “Analyzing the Linux schedulers’s tunables”, 2003 – 19 с.

3. Ashton Mills. “Inside the self-tuning "Genetic" Linux”. Интернет ресурс:
http://apcmag.com/3095/inside_the_self_tuning_genetic_linux/, 2006.

4. Jake Moilanen, “Jake Moilanen's Linux Kernel Homepage”. Интернет ресурс: http://kernel.jakem.net/, 2007.

Поступила в редакцию 20 июня 2007 г.