Многоуровневая очередь обратной связи
В информатике многоуровневая очередь обратной связи — это алгоритм планирования . Алгоритмы планирования предназначены для постоянного выполнения какого-либо процесса, чтобы центральный процессор (ЦП) был занят. [1] Многоуровневая очередь обратной связи расширяет стандартные алгоритмы следующими требованиями к проектированию:
- Разделите процессы на несколько готовых очередей в зависимости от их потребности в процессоре.
- Отдавайте предпочтение процессам с короткими нагрузками процессора.
- Отдавайте предпочтение процессам с большим количеством всплесков ввода-вывода . (Процессы, связанные с вводом-выводом, будут находиться в очереди ожидания, чтобы дать другим процессам время ЦП.)
Многоуровневая очередь обратной связи была впервые разработана Фернандо Х. Корбато (1962). [2] За это достижение Ассоциация вычислительной техники наградила Корбато Премией Тьюринга . [3]
Планирование процессов
[ редактировать ]В то время как алгоритм многоуровневой очереди сохраняет процессы, постоянно назначенные их первоначальным назначениям в очереди, многоуровневая очередь с обратной связью перемещает процессы между очередями. [4] Сдвиг зависит от загрузки ЦП предыдущих временных интервалов . [5]
- Если процесс использует слишком много процессорного времени, он будет перемещен в очередь с более низким приоритетом.
- Если процесс связан с вводом-выводом или является интерактивным процессом, он будет перемещен в очередь с более высоким приоритетом.
- Если процесс слишком долго ожидает в очереди с низким приоритетом и голодает , он будет переведен в очередь с более высоким приоритетом.
Алгоритм
[ редактировать ]несколько очередей FIFO Используется , и операция выглядит следующим образом:
- верхнего уровня Новый процесс вставляется в конец (хвост) очереди FIFO .
- На каком-то этапе процесс достигает начала очереди и ему назначается процессор .
- Если процесс завершен в течение интервала времени данной очереди, он покидает систему.
- Если процесс добровольно отказывается от управления процессором, он покидает сеть очередей, а когда процесс снова становится готовым, он помещается в конец той же очереди, от которой он отказался ранее.
- Если процесс использует весь квант времени, он вытесняется и вставляется в конец следующей очереди более низкого уровня. Эта следующая очередь более низкого уровня будет иметь квант времени, больший, чем у предыдущей очереди более высокого уровня.
- Эта схема будет действовать до тех пор, пока процесс не завершится или не достигнет очереди базового уровня.
- В очереди базового уровня процессы циркулируют по круговому принципу, пока не завершатся и не покинут систему. Процессы в очереди базового уровня также можно планировать в порядке очереди . [6]
- При необходимости, если процесс блокируется для ввода-вывода, он повышается на один уровень и помещается в конец очереди следующего более высокого уровня. Это позволяет планировщику отдавать предпочтение процессам, связанным с вводом-выводом, и позволяет процессам выйти из очереди базового уровня.
Для планирования планировщик всегда начинает подбирать процессы из головы очереди самого высокого уровня. Только если очередь самого высокого уровня стала пустой, планировщик примет процесс из следующей очереди более низкого уровня. Та же политика применяется и для получения в последующих очередях более низкого уровня. Между тем, если процесс попадает в любую из очередей более высокого уровня, он вытесняет процесс в очереди более низкого уровня.
Кроме того, новый процесс всегда вставляется в конец очереди верхнего уровня, предполагая, что он завершится в течение короткого промежутка времени. Длинные процессы автоматически переходят в очереди более низкого уровня в зависимости от их затрат времени и уровня интерактивности. В многоуровневой очереди обратной связи процессу дается только один шанс завершиться на данном уровне очереди, прежде чем он будет переведен в очередь более низкого уровня.
Параметры планирования
[ редактировать ]В общем, многоуровневый планировщик очереди обратной связи определяется следующими параметрами: [6]
- Количество очередей.
- Алгоритм планирования для каждой очереди может отличаться от FIFO.
- Метод, используемый для определения момента перевода процесса в очередь с более высоким приоритетом.
- Метод, используемый для определения момента перевода процесса в очередь с более низким приоритетом.
- Метод, используемый для определения того, в какую очередь войдет процесс, когда этому процессу потребуется обслуживание.
Внешние ссылки
[ редактировать ]- Планировщики многоуровневых очередей обратной связи — разделение времени в Solaris 2.6
- Модели массового обслуживания совместного использования процессоров смешанных дисциплин планирования для системы с разделением времени
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Зильбершац, Авраам (1994). Концепции операционной системы, четвертое издание . Аддисон-Уэсли. п. 131. ИСБН 978-0-201-50480-4 .
- ^ Корбато, Фернандо Х.; Мервин-Даггетт, Марджори; Дейли, Роберт С. (1962). «Экспериментальная система разделения времени». Материалы весенней совместной компьютерной конференции AIEE-IRE '62 (весна), состоявшейся 1–3 мая 1962 г. п. 335. дои : 10.1145/1460833.1460871 . S2CID 14363753 .
- ^ Арпачи-Дюссо, Ремзи Х.; Арпачи-Дюссо, Андреа К. (2014). «Многоуровневая очередь обратной связи». Операционные системы: три простых части (PDF) . Книги Арпачи-Дюссо.
- ^ Зильбершац, Авраам (1994). Концепции операционной системы, четвертое издание . Аддисон-Уэсли. п. 147. ИСБН 978-0-201-50480-4 .
- ^ Зильбершац, Авраам (1994). Концепции операционной системы, четвертое издание . Аддисон-Уэсли. п. 148. ИСБН 978-0-201-50480-4 .
- ^ Jump up to: а б Зильбершац, Авраам; Гэлвин, Питер Баер; Ганье, Грег (2008). Концепции операционной системы (8-е изд.). Хобокен, Нью-Джерси: Уайли. п. 198. ИСБН 978-0470128725 .