Многоуровневая очередь обратной связи

Алгоритм планирования обработки

В информатике многоуровневая очередь обратной связи — это алгоритм планирования . Алгоритмы планирования разработаны так, чтобы какой-то процесс выполнялся постоянно, чтобы центральный процессор (ЦП) был занят. ^[1] Многоуровневая очередь обратной связи расширяет стандартные алгоритмы следующими требованиями к конструкции:

1. Разделите процессы на несколько очередей готовности в зависимости от их потребности в процессоре.
2. Отдавайте предпочтение процессам с короткими всплесками загрузки ЦП.
3. Отдавайте предпочтение процессам с высокой интенсивностью ввода-вывода . (Процессы, связанные с вводом-выводом, будут находиться в очереди ожидания , чтобы предоставить другим процессам процессорное время.)

Многоуровневая обратная связь была впервые разработана Фернандо Х. Корбато (1962). ^[2] За это достижение Ассоциация вычислительной техники наградила Корбато премией Тьюринга . ^[3]

Планирование процесса

В то время как алгоритм многоуровневой очереди сохраняет процессы постоянно назначенными на их первоначальные назначения очереди, многоуровневая обратная очередь перемещает процессы между очередями. ^[4] Сдвиг зависит от всплесков ЦП предыдущих временных интервалов . ^[5]

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

Алгоритм

Используется несколько очередей FIFO , и работа происходит следующим образом:

1. Новый процесс вставляется в конец (хвост) очереди FIFO верхнего уровня .
2. На определенном этапе процесс достигает начала очереди и ему назначается ЦП .
3. Если процесс завершается в течение временного интервала данной очереди, он покидает систему.
4. Если процесс добровольно отказывается от управления ЦП, он покидает сеть очередей, а когда процесс снова становится готовым, он помещается в конец той же очереди, которую он ранее оставил.
5. Если процесс использует все квантовое время, он вытесняется и вставляется в конец следующей очереди более низкого уровня. Эта следующая очередь более низкого уровня будет иметь квант времени, который больше, чем у предыдущей очереди более высокого уровня.
6. Эта схема будет продолжаться до тех пор, пока процесс не завершится или не достигнет очереди базового уровня.

• В очереди базового уровня процессы циркулируют по кругу, пока не завершатся и не покинут систему. Процессы в очереди базового уровня также могут быть запланированы по принципу «первым пришел — первым обслужен» . ^[6]
• При желании, если процесс блокируется для ввода-вывода, он повышается на один уровень и помещается в конец очереди следующего более высокого уровня. Это позволяет планировщику отдавать предпочтение процессам, связанным с вводом-выводом, и позволяет процессам выходить из очереди базового уровня.

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

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

Параметры планирования

В общем случае многоуровневый планировщик очереди обратной связи определяется следующими параметрами: ^[6]

• Количество очередей.
• Алгоритм планирования для каждой очереди, который может отличаться от FIFO.
• Метод, используемый для определения того, когда следует перевести процесс в очередь с более высоким приоритетом.
• Метод, используемый для определения момента, когда следует переместить процесс в очередь с более низким приоритетом.
• Метод, используемый для определения, в какую очередь попадет процесс, когда ему потребуется обслуживание.

Внешние ссылки

• Планировщики многоуровневой очереди обратной связи — Solaris 2.6 с разделением времени
• Модели очередей совместного использования процессоров для смешанных дисциплин планирования для систем с разделением времени

Смотрите также

• Расписание лотереи
• Справедливое планирование
• Круговое планирование

Ссылки

1. Зильбершатц, Абрахам (1994). Концепции операционных систем, четвертое издание . Addison-Wesley. стр. 131. ISBN 978-0-201-50480-4.
2. Corbató, Fernando J.; Merwin-Daggett, Marjorie; Daley, Robert C. (1962). "Экспериментальная система разделения времени". Труды весенней совместной компьютерной конференции 1-3 мая 1962 г. по - AIEE-IRE '62 (весна) . стр. 335. doi :10.1145/1460833.1460871. S2CID  14363753.
3. Arpaci-Dusseau, Remzi H.; Arpaci-Dusseau, Andrea C. (2014). «Многоуровневая очередь обратной связи». Операционные системы: три простых части (PDF) . Книги Arpaci-Dusseau.
4. Зильбершатц, Абрахам (1994). Концепции операционных систем, четвертое издание . Addison-Wesley. стр. 147. ISBN 978-0-201-50480-4.
5. Зильбершатц, Абрахам (1994). Концепции операционных систем, четвертое издание . Addison-Wesley. стр. 148. ISBN 978-0-201-50480-4.
6. Silberschatz, Abraham; Galvin, Peter Baer; Gagne, Greg (2008). Концепции операционных систем (8-е изд.). Hoboken, NJ: Wiley. стр. 198. ISBN 978-0470128725.