Алгоритм многоуровневого циклического выбора

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

Рисунок 2.8- Модель многоуровневого циклического вызова

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

Алгоритм многоуровневого планирования с учётом предварительных приоритетов работ.

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

Рисунок 2.9 - Модель многоуровневого циклического выбора с предварительным планировщиком

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

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