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

2

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

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

Долгое время в Linux присутствовал фактически один scheduler — O(1). Да были другие предложения вроде Staircase от Кона Коливаса (Con Kolivas, http://ck.kolivas.org/patches/pre-releases/2.6.21-rc7/2.6.21-rc7-ck1/patches/), с мая 2007 его разработка прекращена. Или Fairsched (http://sourceforge.net/projects/fairsched). Но все они были реализованы исключительно в виде дополнений, не попадая основную ветку. Сегодня наметилась явная активность разработчиков в этом направлении. Сообщения о новых реализациях появляются на KernelTrap чуть ли не ежемесячно.

Стандартному планировщику O(1) уже более 15 лет. В июле 1993 года Линус Торвальдс в своем сообщении (http://kerneltrap.org/mailarchive/linux-activists/36335) описал принцип работы планировщика задач Linux. Оригинальный файл этого планировщика sched.c содержал всего 254 строки кода. Это был простой и понятный алгоритм. В 1996 году нем было уже более 6 тысяч строк. Только через 10 лет в 2002 году первое глобальное изменение ultra-scalable O(1) scheduler от Инго Молнара (Ingo Molnar). В последних версиях sched.c содержит уже более 7000 строк.

Алгоритм работы O(1) очень прост. Каждая задача имела фиксированное число (tick), которое пересчитывается с каждым системным тиком (по умолчанию 100 Hz), при выходе из режима ядра или при появлении более приоритетной задачи. Алгоритм просто делит число на два и добавляет базовую величину (по умолчанию 15, с учетом величины nice). Когда тик становится равным 0, он пересчитывается. Кроме этого каждый процессор имеет две очереди. В одной находятся готовые к запуску задачи, во вторую помещаются отработавшие и спящие задачи, которые например, ожидают не доступного в настоящее время ресурса. Когда первая очередь пустеет, очереди меняются местами. Поэтому время работы алгоритма постоянно и не зависит от количества процессов. Современная реализация O(1) используют уже более сложные алгоритмы, анализируя среднее время сна процесса, чтобы обнаружить интерактивные задачи ожидающие ответа пользователя и стараясь задержать их подольше в активном дереве.

В ядро 2.6.23 после трех месяцев обкатки в экспериментальной -mm ветке ядра, был включен в качестве основного планировщик CFS (Completely Fair Scheduler, абсолютно справедливый планировщик). Алгоритм которого полностью пересмотрен и весьма сложен. В отличие от O(1) CFS равномернее распределяет процессорное время (фактически если задачи две, то каждая получит ровно 50% CPU), распределяет задачи по нескольким ядрам и имеет меньшее время отклика. Для настройки CFS используется файл /proc/sys/kernel/sched_granularity_ns, в котором по умолчанию установлен режим desktop (меньшее время задержки), но при необходимости его можно переключить в server.

$ cat server > /proc/sys/kernel/sched_granularity_ns

Con Kolivas остановив разработку ветки ck, в марте анонсировал совершенно новый планировщик RSDL (Rotating Staircase DeadLine scheduler), в последствии он был переименован в SD (Staircase Deadline, ck.kolivas.org/patches/staircase-deadline). За его основу был взят Staircase. Задача нового планировщика исключить зависания присущие O(1), здесь все процессы равны, каждому дается своя квота, исчерпав которую он опускается на следующий уровень приоритета, где получает новую квоту. Причем каждый уровень также имеет свою квоту, если ее исчерпает хотя бы один процесс, все перейдут на следующий уровень, в не зависимости от того отработали ли они свою квоту или нет. Планировщик также пытается определить интерактивные процессы, автоматически повышая им приоритет. Версия SD показывала неплохие результаты на серверах, и поговаривали, что этот планировщик будет включен в основную ветку начиная с 2.6.22, но из-за проблем со здоровьем разработка шла относительно медленно и Инго Молнар обогнал соперника.

Как ответ на сложность CFS Роман Зиппель (Roman Zippel) представил рабочий прототип базового алгоритма нового планировщика RFS (Really Fair Scheduler, kerneltrap.org/RFS), который помещает задачу в виртуальную (нормализованную) time line, в которой имеет значение только относительное расстояние между двумя любыми задачами. После некоторых споров в ответ на этот прототип Инго Молнар представил свою версию, которую он назвал RSRFS (Really Simple Really Fair Scheduler) реализованный поверх CFS, и включающий алгоритм из RFS. Есть и патчи к CFS, например programming.kicks-ass.net/kernel-patches/sched-cfs.

За последние 2,5 года было предложено около 300 алгоритмов, так что вряд ли здесь будет спокойно в ближайшее время.

Проект DeskOpt

Интересный проект был представлен примерно полгода назад в списке рассылки разработчиков ядра Linux. Программа DeskOpt (www.stardust.webpages.pl/files/tools/deskopt) представляет собой демон, написанный на языке высокого уровня Python, который отслеживает запускаемые пользователем приложения и автоматически выбирает оптимальные параметры работы планировщика процессов CFS и планировщик ввода/вывода (CFQ, anticipatory, deadline). Все настройки осуществляются путем редактирования конфигурационного файла, в котором по умолчанию описано три класса оптимизации: игры, просмотр видео и прослушивание музыки. Текущая версия 0.6-rc1 от января 2008 года. DeskOpt легко устанавливается

Требования:
— Python 2.x (http://python.org/)
— elementtree (http://effbot.org/downloads/#elementtree)
$ tar xjvf deskopt-006-rc1.tar.bz2

$ cd deskopt-006-rc1

$ cp deskopt /usr/local/bin/
$ sudo mkdir /etc/deskopt/
$ sudo cp deskopt.conf /etc/deskopt/
$ sudo cp deskopt.rc /etc/init.d/

К онфигурационный файл имеет простой XML формат, в нем уже есть готовые настройки. В простейшем случае команда выглядит так:

$ sudo deskopt -c /etc/deskopt/deskopt.conf

2 комментария


  1. vadek
    // Ответить

    Все эти планировщики хороши и разработчикам респект. Но! Применительно к реальной жизни. На сегодня рассматривать можно а) серверы баз данных; б) серверы приложений; в) рабочие станции. Кто бы мог предложить обзор производительности наиболее популярных планировщиков в этих задачах? Уже очень очевидно, что универсального планировщика не создать и потому интересует именно сравнение их между собою с целью выбора оптимального для той или иной задачи. Спасибо.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *