Jump to content

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

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

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

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

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

[ редактировать ]

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

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

Алгоритм

[ редактировать ]

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

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

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

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

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

[ редактировать ]

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

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

См. также

[ редактировать ]
  1. ^ Зильбершац, Авраам (1994). Концепции операционной системы, четвертое издание . Аддисон-Уэсли. п. 131. ИСБН  978-0-201-50480-4 .
  2. ^ Корбато, Фернандо Х.; Мервин-Даггетт, Марджори; Дейли, Роберт С. (1962). «Экспериментальная система разделения времени». Материалы весенней совместной компьютерной конференции AIEE-IRE '62 (весна), состоявшейся 1–3 мая 1962 г. п. 335. дои : 10.1145/1460833.1460871 . S2CID   14363753 .
  3. ^ Арпачи-Дюссо, Ремзи Х.; Арпачи-Дюссо, Андреа К. (2014). «Многоуровневая очередь обратной связи». Операционные системы: три простых части (PDF) . Книги Арпачи-Дюссо.
  4. ^ Зильбершац, Авраам (1994). Концепции операционной системы, четвертое издание . Аддисон-Уэсли. п. 147. ИСБН  978-0-201-50480-4 .
  5. ^ Зильбершац, Авраам (1994). Концепции операционной системы, четвертое издание . Аддисон-Уэсли. п. 148. ИСБН  978-0-201-50480-4 .
  6. ^ Jump up to: а б Зильбершац, Авраам; Гэлвин, Питер Баер; Ганье, Грег (2008). Концепции операционной системы (8-е изд.). Хобокен, Нью-Джерси: Уайли. п. 198. ИСБН  978-0470128725 .
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: d1d16de4d8331e4fc2c7a1e8addd5f49__1701693360
URL1:https://arc.ask3.ru/arc/aa/d1/49/d1d16de4d8331e4fc2c7a1e8addd5f49.html
Заголовок, (Title) документа по адресу, URL1:
Multilevel feedback queue - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)