Планирование работы ЦП

Планирование работы ЦП (CPU scheduling) — это функция операционной системы, которая определяет, какой готовый процесс или поток будет выполняться на процессоре следующим, балансируя такие цели, как отзывчивость, пропускная способность, справедливость и соблюдение сроков.

Definition

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

Scope

Эта тема охватывает политики планирования и их оценку: «первым пришел — первым обслужен», «кратчайшая работа первой», циклическое планирование, приоритетное планирование и многоуровневые очереди обратной связи; вытесняющее и невытесняющее планирование; критерии использования ЦП, пропускной способности, времени оборота, времени ожидания и времени отклика; а также планирование на многопроцессорных системах и для систем реального времени. Она исключает представление планируемых задач (управление процессами и потоками) и синхронизацию (параллелизм).

Core questions

• По каким критериям измеряется качество планирования?
• Чем отличаются общие алгоритмы планирования по справедливости и эффективности?
• Когда планировщик должен вытеснять выполняющуюся задачу?
• Как планирование адаптируется для многопроцессорных систем и сроков реального времени?

Key concepts

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

Key theories

Цели и компромиссы планирования

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

Mechanisms

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

Clinical relevance

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

History

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

Debates

Справедливость против пропускной способности и приоритета

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

Key figures

• Edsger W. Dijkstra
• Abraham Silberschatz
• Andrew S. Tanenbaum
• C. L. Liu
• James W. Layland

Seminal works

• silberschatz2018
• tanenbaum2014os

Frequently asked questions

В чем разница между вытесняющим и невытесняющим планированием?

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

Что такое голодание и как его предотвратить?

Голодание возникает, когда задача никогда не планируется к выполнению, потому что задачи с более высоким приоритетом постоянно получают преимущество. Обычно оно предотвращается с помощью старения (aging), которое постепенно повышает приоритет долго ожидающих задач, чтобы они в конечном итоге были выполнены.