Алгоритм многоуровневых очередей (Multilevel Queue)

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

Алгоритм многоуровневые очереди с обратной связью (Multilevel Feedback Queue)

Дальнейшим развитием алгоритма многоуровневых очередей является добавление к нему механизма обратной связи, благодаря которому процесс может мигрировать из одной очереди в другую в зависимости от своего поведения. Планирование процессов между очередями осуществляется на основе вытесняющего приоритетного механизма. Процессы в очереди 1 не могут исполняться, если в очереди 0 есть хотя бы один процесс. Процессы в очереди 2 не будут выбраны для выполнения, пока есть хоть один процесс в очередях 0 и 1 и т. д. Если при работе процесса появляется другой процесс в более приоритетной очереди, исполняющийся процесс вытесняется новым. Планирование процессов внутри очередей 0 — 2 осуществляется с использованием алгоритма RR, в очереди 3 — алгоритма FCFS.

Родившийся процесс поступает в очередь 0. При выборе на исполнение он получает в свое распоряжение квант времени, например, размером 8 единиц. Если продолжительность его CPU burst меньше этого кванта времени, процесс остается в очереди 0. В противном случае он переходит в очередь 1. Для процессов очереди 1 квант времени имеет величину 16. Если процесс не укладывается в это время, он переходит в очередь 2. В очереди 2 величина кванта времени составляет 32 единицы. Если для непрерывной работы процесса этого мало, процесс поступает в очередь 3, для которой квантование времени не применяется и, при отсутствии готовых процессов в других очередях, может исполняться до окончания своего CPU burst. Чем больше значение продолжительности CPU burst, тем в менее приоритетную очередь попадает процесс, но тем на большее процессорное время он может рассчитывать. Таким образом, процессы, требующие малого времени работы процессора, окажутся размещенными в высокоприоритетных очередях, а процессы, требующие большого времени работы процессора и с низкими запросами к времени отклика — в низкоприоритетных.

Миграция процессов в обратном направлении может осуществляться по различным принципам. Например, после завершения ожидания ввода с клавиатуры процессы из очередей 1, 2 и 3 могут помещаться в очередь 0. После завершения дисковых операций ввода-вывода процессы из очереди 3 могут помещаться в очередь 1, а после завершения ожидания всех событий — из очереди 3 в очередь 2. Перемещение процессов из низкоприоритетных очередей в высокоприоритетные позволяет более полно учитывать изменение поведения процессов с течением времени.

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

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

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