Снижение приоритета
Если у нас нет никаких указаний об относительной продолжительности процессов, то мы не можем использовать ни одну из стратегий — SPN, SRT или HRRN. Еще один путь предоставления преимущества коротким процессам состоит в применении штрафных санкций к долго выполняющимся процессам. Другими словами, раз уж мы не можем работать с оставшимся временем выполнения, мы будем работать с затраченным временем.
Вот как этого можно достичь. Выполняется вытесняющее (по квантам времени) планирование с использованием динамического механизма. При входе процесса в систему он помещается в очередь RQO (см. рис. 9.4). После первого выполнения и возвращения в состояние готовности процесс помещается в очередь RQ1. В дальнейшем при каждом вытеснении этого процесса он вносится в очередь со все меньшим приоритетом. Соответственно, быстро выполняющиеся короткие процессы не могут далеко зайти в иерархии приоритетов, в то время как длинные процессы постепенно теряют свой приоритет. Таким образом, новые короткие процессы получают преимущество в выполнении над старыми длинными процессами. В рамках каждой очереди для выбора процесса используется стратегия FCFS. По достижении очереди с наиболее низким приоритетом процесс уже не покидает ее, всякий раз после вытеснения попадая в нее вновь (таким образом, эта очередь, по сути, обрабатывается с использованием циклической стратегии).
На рис. 9.10 проиллюстрирован этот механизм планирования; пунктирной линией показан путь длинного процесса по различным очередям. Такой подход известен как многоуровневый возврат (multilevel feedback2), поскольку при блокировании или вытеснении процесса осуществляется его возврат, на очередной уровень приоритетности.
Имеется несколько разновидностей данной схемы. В простейшем случае вытеснение выполняется так же, как и в случае применения стратегии RR, — через периодические интервалы времени. В нашем примере (рис. 9.5 и табл. 9.5) использован именно этот метод, с квантом времени, равным 1.
При такой простой схеме имеется один недостаток, заключающийся в том, что время оборота длинных процессов резко растягивается. В системе с частым запуском новых процессов в связи с этим вполне вероятно появление голодания. Для уменьшения отрицательного эффекта мы можем использовать разное время вытеснения для процессов из разных очередей: процесс из очереди RQO выполняется в течение одной единицы времени и вытесняется; процесс из очереди RQ1 выполняется в течение двух единиц времени и т.д. — процесс из очереди RQi
выполняется до вытеснения в течение 2i единиц времени. Использование этой схемы также проиллюстрировано на рис. 9.5 и в табл. 9.5.
Даже при выделении процессу с более низким приоритетом большего количества времени для выполнения не удается полностью избежать голодания. Еще одним средством против голодания может служить перемещение процесса в очередь с более высоким приоритетом, если процесс не был обслужен в течение некоторого порогового времени в данной очереди.
Дата добавления: 2016-06-05; просмотров: 1534;