Алгоритмы планирования. 
Операционные системы

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

Планирование, но срокам выполнения (deadline scheduling). При таком планировании процесс должен быть выполнен за строго определенное время, например, процесс обнаружения и распознавания самолета противника. В противном случае его выполнение не имеет смысла. Однако при этом другие процессы в системе, например системные, не должны приостанавливаться, иначе сама система перестанет быть работоспособной. Такое планирование чрезвычайно сложно, так как априори очень трудно заранее предсказать время, необходимое на выполнение некоторой задачи. Используется в ОС специального назначения.

Планирование типа «первый вошел — первый обслужен» (First-ComeFirst-Served, FCFS). Т акое планирование является наиболее простым. Процесс, поступивший первым, выполняется до его полного завершения, при этом используется механизм невытесняющей многозадачности. Затем загружается второй процесс и т. д. Несмотря на простоту, такое планирование имеет очень серьезный недостаток: если выполняется задача с большим временем выполнения, то остальные задачи очереди ждут, пока она не закончится, в том числе и системные процессы, что может привести к краху ОС. Такая схема планирования будет хорошо работать, например, в обслуживании систем баз данных, где короткие поступающие в систему запросы не требуют большого времени выполнения и длина очереди не будет большой.

Планирование по наивысшему приоритету (Highest-Priority-First, HPF). В этом методе^[1] процессор предоставляется тому процессу, который имеет наивысший приоритет. Если не допускается вытеснение процесса, то он выполняется до тех пор, пока не выполнится или не будет заблокирован. Если вытеснение разрешено, то поступивший процесс с более высоким приоритетом прервет выполняющийся процесс, и ему будет передано управление на выполнение. Вытесненный процесс перейдет в очередь готовых процессов. Когда процессор освобождается, то для выполнения из очереди Ready выбирается процесс с наивысшим приоритетом.

Если очередь Ready отсортирована по приоритетам, то первый процесс выбирается автоматически. В противном случае необходимо проводить повторную сортировку всей очереди с некоторым интервалом времени с учетом параметров процессов.

В стратегии IIPF необходимо назначать параметр, определяющий величину приоритета. Иногда таким параметром является первое самое короткое задание, как в методе SJF (shortest job first). Здесь, как правило, используется ожидаемое (оцениваемое) время выполнения процесса, ибо точное время известно очень редко.

Метод круговорота (карусель, Round Robin, RR). В этом алгоритме планирования¹, известном уже более 50 лет, процессы располагаются в очереди, организованной как FIFO, но каждому процессу предоставляется некоторый интервал времени, называемый квантом. По истечении этого кванта задача перемещается в конец очереди, а процессор начинает обрабатывать следующую задачу.

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

Существует много разновидностей этого метода, например, «эгоистический» (selfish round robin). В этой разновидности алгоритма выполняется процесс, имеющий наивысший приоритет. С одной стороны, чем дольше выполняется процесс, тем ниже становится его приоритет. С другой стороны, с увеличением времени ожидания растут приоритеты ждущих процессов, и как только у некоторого процесса приоритет превысит значение выполняемого процесса, система переключится на выполнение этого процесса, а текущий процесс перейдет в состояние ожидания.

Самая короткая задача — вперед (Shortest-Job-First, SJF). В этом алгоритме^[2][3] предполагается, что система выбирает из очереди те задачи, которые требуют самого короткого времени исполнения, поскольку они будут удаляться из системы за минимальное время. Следовательно, при использовании модели FIFO производительность системы будет повышаться из-за уменьшения среднего времени ожидания задач в очереди.

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

Еще большие проблемы здесь возникают при учете приоритетов задач. В этом случае каждый разработчик придумывает свой вариант разрешения вопросов об очередности выполнения задач.

Планирование по остаточному времени (Shortest-remaining-timescheduling, SRT). Алгоритм SRT является аналогом SJF и обычно используется в системах с разделением времени. Здесь выбирается процесс, требующий минимального времени до его завершения. Работающий процесс выполняется до конца либо до того момента, когда в систему поступает новый процесс, с более коротким временем выполнения. В последнем случае исполняемая задача выгружается и поступает в очередь на выполнение. Понятно, что SRT имеет более высокие накладные расходы, чем SJF, поскольку системе требуется проводить периодическое «взвешивание» времени выполнения процессов. Однако это время оценки невелико, поскольку необходимо «взвесить» только два процесса — выполняемый и вновь поступивший в систему, игнорируя все остальные процессы.

Планирование по остаточному отношению (Highest-Response-RatioNext, HRRN). Эта стратегия управления использует приоритеты, вычисляемые нс только на основании времени обслуживания, но и на времени ожидания. Динамический приоритет HRRN вычисляется по следующей формуле:

где time waiting — время ожидания процесса в очереди; service time — время выполнения процесса. С одной стороны, поскольку время выполнения находится в знаменателе, то короткие задачи будут иметь преимущества. С другой стороны, присутствие времени ожидания в числителе позволяет длинным программам не слишком долго стоять в очереди.

Вероятностное планирование (Lottery scheduling). В этом алгоритме¹ каждому процессу присваивается некоторый номер, а планировщик случайным образом выбирает номер некоторого процесса, который будет выполняться следующим. Для выбора некоторого номера используется равномерное распределение. Этот способ планирования близок к SPN и обычно применяется для разрешения проблемы нехватки ресурсов — старвации (starvation). Эта проблема иногда возникает, когда некоторому процессу систематически недостаточно ресурсов для его работы^[4][5]. Старвация появляется из-за ошибок планирования, взаимоисключающих процессов или даже утечек ресурсов (памяти).

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

Многоуровневые очереди с обратной связью (Multilevel Feedback Queves FB). Основной алгоритм FB (feedback) использует n очередей, каждая из которых обслуживается в порядке поступления. Новый процесс поступает в первую очередь, затем после получения кванта времени он переходит в очередь со следующим номером и так далее после очередного кванта времени. Согласно этому алгоритму процессор сначала обслуживает непустую очередь с наименьшим номером. Каждый, вновь поступающий на обслуживание процесс получает наивысший приоритет и выполняется подряд в течение такого количества квантов времени, пока не придет следующий процесс. Но если приход нового процесса задерживается, то текущий процесс не может проработать большее количество квантов, чем предыдущий процесс.

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

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

В основе метода многоуровневого планирования лежит следующий механизм: операции, которые встречаются часто, должны требовать меньше времени, чем те, которые встречаются редко. С этой целью все операции в зависимости от частоты выполнения разбиваются на уровни. Часто используется трехуровневая система планирования: диспетчер, краткосрочный планировщик и долгосрочный планировщик^[6].

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

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

Долгосрочный планировщик осуществляет более глубокий анализ состояния процесса с анализом размера задачи и оценки времени ее выполнения.

Если априори известна частота появления вызовов на каждом уровне, то, пользуясь многоуровневым планированием, можно ввести ограничения на допустимый объем вычислений на каждом уровне, что во многом определяет используемые алгоритмы планирования на каждом уровне^[7].

На рис 3.2 показано, как происходит выполнение процессов для различных алгоритмов планирования. Для сравнения показаны разные варианты алгоритмов RR и Feedback с выделением процессу одного (q =1), двух (<7 = 2) или четырех (q = 4) квантов времени.

Планирование в UNIX. Традиционное планирование в UNIX-подобных ОС построено на основе многоуровневых очередей с обратной связью (FB), использующее метод RR в каждой приоритетной очереди. В качестве времени переключения используется один квант. Приоритеты основаны на типе процессов и истории их выполнения. Для планирования используются следующие формулы:

где CPUj (i) — величина занятости процессора процессом j на интервале времени г; Pj (i) — приоритет процесса j в начале интервала г; наименьшая величина соответствует наибольшему приоритету; Basej — базовый приоритет процесса j; nice — регулировочный фактор, управляемый пользователем.

Для изменения приоритета применяется команда Venice, использующая следующий синтаксис:

renice PRIORITY PID

где PRIORITY — значение приоритета от -20 до 19, a PID идентификатор (номер) процесса. По умолчанию у всех процессов приоритет равен 0. Чем ниже значение — тем выше приоритет, т. е. -20 — это самый высокий приоритет, а 19 — самый низкий.

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

Базовый приоритет назначается для подразделения процессов в некоторые группы уровней приоритетов. Параметры CPU и nice ограничивают возможности перехода процессов между этими группами. Разделение на группы процессов используются для оптимизации доступа к блокориентированным устройствам (например, дискам) и для повышения скорости отклика ОС на системные запросы. Диапазоны таких групп распределяются по приоритетам (в убывающем порядке).

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

Применение истории выполнения позволяет штрафовать для повышения эффективности их операций I/O. Использование стратегии планирования RR с вытеснением наилучшим образом способствует требованиям ОС разделения времени (общего назначения).

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

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

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

• [1] Conway R. W., Maxwell W. L., Miller L. W. Theory of Scheduling. Addison-Wesley, Reading, 1967.
• [2] Kleinrock L. Analysis of a Time-Shared Processor // Naval Research Logistics Quarterly.11:1. March. 1964. P.59−73.
• [3] Cobham A. Priority Assignment in Waiting Line Problems //Journal of Operations Research.2:70. 1954. P. 70−76.
• [4] Lottery Scheduling: Flexible Proportional-Share Resource Management / C. A. Waldspurger, W. E. Weihl. The 1994 Operating Systems Design and Implementation conference (OSDI '94).November. 1994. Monterey, California.
• [5] Tanenbaum A. Modern Operating Systems. Prentice Hall, 2001. P. 184—185.
• [6] Stallings W. Operating Systems: Internals and Design Principles.
• [7] Finkel R. An Operating Systems Vade Mecum. Englewood Cliffs, N. J.: Prentice Hall, 1988.