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

В статье рассматривается архитектура планирощика задач ("scheduler") ядра Linux

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

Автор: Vinayak Hegde
Перевод: Андрей Киселев

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  7. Прочие :

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

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

Ссылки

Vinayak

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


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

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


Примечания читателей

Ivan Pesin, Russian Linux Team (ipesin at post.lviv.ua):

    
Есть небольшое замечание по сабжу относительно приоритетов. Важно 
понимать, что приоритет и значение, выставляемое командой (re)nice 
-- разные вещи. От приоритета процесса зависит сколько он получит 
процессорного времени. Когда планировщик выбирает процесс для выполнения
на процессоре, он, в общем случае, выбирает процесс с наибольшим (!) 
внутренним приоритетом.
       
Непосредственно выставить приоритет процесса невозможно, можно опредилить
значение nice, влияющее на приоритет. Кроме того, приоритет процесса
величина динамически изменяемая. Она зависит например от того сколько
времени уже было использовано процессом, сколько времени процесс находится
в очереди на выполнение. 
	    
Значение nice вносит коррективы в определение приоритета процесса. Кстати,
столь дивное название nice value объясняется тем, что он указывает
насколько "любезным" будет процесс по отношению к другим процессам.
Потому, чем _выше_ нужен приоритет, тем _меньше_ должно быть значение 
nice (процесс будет "менее любезен" по отношению к другим). И действительно, 
если значение nice устанавливается в пределах от -20 до 19 (в старых 
ATT системах этот диапазон был другим: от 0 до 39), то приоритет процесса
изменяется в пределах от 0 до 99.
		   
Наконец, увидеть эти значения можно при помощи программы ps:
		     
[ivan@eagle ivan]$ ps -o uid,pid,pri,ni,cmd
 UID PID PRI NI CMD
 701 3310 24 0 /bin/bash
 701 3343 23 0 ps -o uid,pid,pri,ni,cmd
[ivan@eagle ivan]$ nice -n 10 bash
[ivan@eagle ivan]$ ps -o uid,pid,pri,ni,cmd
 UID PID PRI NI CMD
 701 3310 24 0 /bin/bash
 701 3345 14 10 bash
 701 3375 13 10 ps -o uid,pid,pri,ni,cmd
[ivan@eagle ivan]$ exit
		 
Как видно, увеличив значение nice, приоритет процесса уменьшился. Следует
заметить, что поле PRI в выводе команды ps без указания ключа -o pri отображает 
не приоритет, а адаптированное значение, которое определяет стандарт Unix98 : 
чем _ниже_ адаптированное значение, тем выше приоритет процесса.

Copyright (C) 2003, Vinayak Hegde. Copying license http://www.linuxgazette.com/copying.html
Published in Issue 89 of Linux Gazette, April 2003


[ опубликовано 18/03/2004 ]

Vinayak Hegde. Перевод Андрей Киселев - Планировщик задач в Linux