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

Главный недостаток приоритетного планирования заключается в возможности блокирования на неопределенно долгое время низкоприоритетных процессов.

Известен случай, когда в 1973 г. в Массачусетском технологическом институте при остановке компьютера IBM 7094 в очереди готовых процессов были обнаружены процессы, активизированные в 1967 г. но так и не выполненные.

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

  «Карусельная» стратегия планированияRR-Round Robin — применяется в системах разделения времени. Определяется небольшой отрезок времени t_k, названный квантом времени (10...100 мс). Очередь готовых процессов рассматривается как кольцевая. Процессы циклически перемещаются по очереди, получая CPU на время, равное одному кванту. Новый процесс добавляется в хвост очереди. Если процесс не завершился в пределах выделенного ему кванта времени, его работа принудительно прерывается, и он перемещается в хвост очереди.

 

Рис 18. Процессы на карусели. 

 

Свойства стратегии Round Robin сильно зависят от величины временного кванта t_k. Чем больше временной квант, тем ближе стратегия Round Robin приближается к FCFS-стратегии. При очень малых значениях временного кванта Round Robin стратегию называют разделением процессора — processor sharing. Теоретически это означает, что каждый из N процессов работает со своим собственным процессором, производительность процессора равна 1/ N от производительности физического процессора.

  Планирование с использованием многоуровневой очереди (Multilevel queue scheduling)

Эта стратегия разработана для ситуации, когда процессы могут быть легко классифицированы на несколько групп, например, часто процессы разделяют на две группы:

ü интерактивные (процессы переднего плана) ü пакетные (фоновые).

Интерактивные и пакетные процессы имеют различные требования к краткосрочному планировщику, например по отношению ко времени отклика.

Стратегия многоуровневой очереди разделяет очередь готовых процессов на несколько очередей, в каждой из которых находятся процессы с одинаковыми свойствами, и каждый из которых может планироваться индивидуальной стратегией, например, Round Robin стратегия для интерактивных процессов и FCFS для пакетных процессов.

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

Работа процесса из очереди с более низким приоритетом может быть приостановлена, если в одной из очередей с более высоким приоритетом появился процесс.

 

Использование многоуровневой очереди с обратными связями (multilevel feedback queue sheduling) (рис. 19)

 

 

Рис. 19. Многоуровневая очередь с обратными связями

 

Обычная многоуровневая очередь не допускает перемещения процессов между очередями. Многоуровневая очередь с обратными связями предполагает, что процессы при определенных условиях могут перемещаться между очередями. Здесь организуется N очередей. Все новые запросы поступают в конец первой очереди. Первый запрос из i-й очереди поступает на обслуживание лишь тогда, когда все очереди от 1-й до (i – 1)-й пустые. На обслуживание выделяется квант времени t_k. Если за это время обслуживание запроса завершается полностью, то он покидает систему. В противном случае недообслуженный запрос поступает в конец (i + 1)-й очереди.

После обслуживания запроса из i-й очереди система выбирает для обслуживания запрос из непустой очереди с самым младшим номером. Таким запросом может быть следующий запрос из очереди i или из очереди i + 1 (при условии, что после обслуживания запроса из очереди i последняя оказалась пустой). Новый запрос поступает в 1-ю очередь (i = 1). В такой ситуации после окончания времени t_k, выделенного для обслуживания запроса из очереди i, будет начато обслуживание запроса первой очереди. Если система выходит на обслуживание заявок из N-й очереди, то они обслуживаются либо по дисциплине FIFO (каждая заявка обслуживается до конца), либо по циклическому алгоритму. Данная система наиболее быстро обслуживает все короткие по времени обслуживания запросы. Недостаток системы заключается в затратах времени на перемещение запросов из одной очереди в другую.

Данная стратегия является универсальной и сочетает в себе свойства всех рассмотренных раньше стратегий — FCFS, SJF, приоритетная, Round Robin, многоуровневая очередь.

 

 

Рис. 20 Приоритетная, многоочередная дисциплина обслуживания

 

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

(из очереди с меньшим номером запрос из очереди i - 1 будет прерывать обработку запроса из очереди i).

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

 

ДОМАШНЯЯ РАБОТА

1. Выучить материал.

2. Ответить на вопросы.

 

Контрольные вопросы:

1. Дать определение понятию «процесс». Привести классификацию процессов по временным характеристикам

2. Перечислить состояния процесса. Нарисовать диаграмму переходов для состояний процессов 

3. Привести классификацию процессов по связности

4. Перечислить состояния процесса. Нарисовать диаграмму переходов между процессами

5. Дать определение понятию «очередь». Перечислить виды очередей процессов.

6. Перечислить функции ОС при работе с процессами

7. Перечислить и охарактеризовать критерии, позволяющие сравнивать алгоритмы краткосрочных планировщиков

8. Перечислить и охарактеризовать стратегии планирования процессора

9. Работу выслать на почту преподавателя

[e-mail]