Снижение приоритета

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

Вот как этого можно достичь. Выполняется вытесняющее (по квантам времени) планирование с использованием динамического механизма. При входе процесса в систему он помещается в очередь RQO (см. рис. 9.4). После первого выполнения и возвращения в состояние готовности процесс помещается в очередь RQ1. В дальнейшем при каждом вытеснении этого процесса он вносится в очередь со все меньшим приоритетом. Соответственно, быстро выполняющиеся короткие процессы не могут далеко зайти в иерархии приоритетов, в то время как длинные процессы постепенно теряют свой приоритет. Таким образом, новые короткие процессы получают пре­имущество в выполнении над старыми длинными процессами. В рамках каждой очереди для выбора процесса используется стратегия FCFS. По достижении очереди с наиболее низким приоритетом процесс уже не покидает ее, всякий раз после вытес­нения попадая в нее вновь (таким образом, эта очередь, по сути, обрабатывается с использованием циклической стратегии).

На рис. 9.10 проиллюстрирован этот механизм планирования; пунктирной линией показан путь длинного процесса по различным очередям. Такой подход известен как многоуровневый возврат (multilevel feedback²), поскольку при бло­кировании или вытеснении процесса осуществляется его возврат, на очередной уровень приоритетности.

Имеется несколько разновидностей данной схемы. В простейшем случае вытеснение выполняется так же, как и в случае применения стратегии RR, — через периодические интервалы времени. В нашем примере (рис. 9.5 и табл. 9.5) использован именно этот метод, с квантом времени, равным 1.

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

выполняется до вытеснения в течение 2ⁱ единиц времени. Использование этой схемы также проиллюстрировано на рис. 9.5 и в табл. 9.5.

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