Многоуровневые очереди с обратной связью (Операционные Системы)

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 16:49, 4 июня 2019.

Многоуровневые очереди с обратной связью в операционных системах - Это усовершенствование многоуровневого планирования очередей, когда процесс может перемещаться между очередями[Источник 1].

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

В многоуровневом алгоритме планирования очередей процессы постоянно назначаются очередями при входе в систему. Процессы не перемещаются между очередями. Преимущество этой настройки заключается в низких затратах на планирование, но недостаток в том, что они негибкие. Однако многоуровневое планирование очереди обратной связи позволяет процессу перемещаться между очередями. Идея состоит в том, чтобы разделить процессы с разными характеристиками процессора. Если процесс использует слишком много процессорного времени, он будет перемещен в очередь с более низким приоритетом. Точно так же процесс, который ждет слишком долго в очереди с более низким приоритетом, может быть перемещен в очередь с более высоким приоритетом. Эта форма старения предотвращает голодание[Источник 2].

Параметры многоуровневого планировщика очереди обратной связи

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

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

Корректировка приоритетов

Приоритеты корректируются следующим образом:

  • Работа начинается в очереди с наивысшим приоритетом.
  • Если время работы истекает, следует переместить его приоритет на один уровень ниже.
  • Если временные интервалы задания не истекают (вместо этого переключение контекста происходит из запроса ввода-вывода), следует увеличить его приоритет на один уровень до верхнего уровня приоритета.
  • Связанные с CPU задания сбрасываются, а задания ввода/вывода остаются приоритетными[Источник 4].

Алгоритмы

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

FCFS

Планирование обслуживания в порядке поступления (FCFS): это алгоритм планирования без перегрузки. ЦП назначен процессам в порядке их поступления. Какой бы процесс ни пришел первым в очередь готовности, этот процесс будет запланирован первым.

SJF

Сначала самое короткое задание (SJF): это алгоритм с невыполняющим расписанием. ЦП назначается процессу с наименьшим временем посылки. Если два процесса имеют одинаковое время пакета, для решения проблемы используется FCFS.

SRTF

Алгоритм первого планирования в кратчайшее оставшееся время (SRTF): это алгоритм упреждающего планирования. Процессор назначается процессу, который имеет наименьшее время посылки. Но если процесс прибывает позже с требованием времени пакета меньше, чем оставшееся время текущего запущенного процесса, то текущий процесс прерывается и ЦП будет назначен процессу с минимальным требованием времени пакета.

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

Алгоритм планирования приоритетов: ЦП назначается процессам в соответствии с приоритетом, заданным пользователем.

Round-robin

Алгоритм циклического планирования: это алгоритм упреждающего планирования. Он разработан специально для систем с разделением времени. Здесь равный приоритет будет отдан всем процессам. Определена небольшая единица времени, называемая квантом времени или интервалом времени. Процессор будет назначен каждому процессу в виде круговой очереди один раз для каждого процесса. После завершения одного временного кванта для процесса, ЦП будет передан другому процессу. Если у процесса больше времени пакета, чем у заданного кванта времени, он будет добавлен в конец очереди готовности. Таким образом, все процессы будут обрабатываться одинаково в этом алгоритме планирования Round-robin[Источник 5].

Пример многоуровневого алгоритма планирования очередей с пятью очередями

Пример многоуровневого алгоритма планирования очередей с пятью очередями:

  1. Системные процессы.
  2. Интерактивные процессы.
  3. Интерактивные процессы редактирования.
  4. Пакетные процессы.
  5. Студенческие процессы.

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

Рисунок 1 – Пример многоуровневого алгоритма планирования очередей с пятью очередями

Пример задачи

Рассмотрим таблицу, представленную на рисунке 1, из четырех процессов в разделе планирование многоуровневой очереди. Номер очереди обозначает очередь процесса. Приоритет очереди 1 больше, чем очереди 2. В очереди 1 используется Round Robin (Квант времени = 2), а в очереди 2 используется FCFS. Далее используется диаграмма Ганта, представленная на рисунке 2. При запуске обе очереди имеют процесс, поэтому процесс в очереди 1 (P1, P2) запускается первым (из-за более высокого приоритета) в режиме циклического перебора и завершается после 7 блоков, после чего начинается процесс в очереди 2 (P3) (поскольку процесса нет) в очереди 1), но пока он работает, P4 входит в очередь 1 и прерывает P3 и начинает работать в течение 5 секунд, а после его завершения P3 берет ЦП и завершает его выполнение[Источник 6].

Рисунок 2 – Таблица из четырех процессов в разделе планирование многоуровневой очереди
Рисунок 3 – Диаграмма Ганта

Источники

  1. Multilevel feedback queues // ScienceHQ.com [2013 — ]. URL: http://www.sciencehq.com/computing-technology/1353.html (дата обращения 06.04.2019).
  2. Multilevel Feedback Queue Scheduling // Studytonight [2019 — ]. URL: https://www.studytonight.com/operating-system/multilevel-feedback-queue-scheduling (дата обращения 06.04.2019).
  3. Multilevel Feedback Queue scheduling Tutorial With Example // Tutorialwing [2017 — ]. URL: https://tutorialwing.com/multilevel-feedback-queue-scheduling-tutorial-example/ (дата обращения 06.04.2019).
  4. Multilevel Feedback Queues (MLFQ) // lass.cs.umass.edu [2019 — ]. URL: http://lass.cs.umass.edu/~shenoy/courses/fall14/lectures/Lec05-part2.pdf (дата обращения 06.04.2019).
  5. MULTI LEVEL QUEUE ROUND ROBIN CPU SCHEDULING ALGORITHM (MQRR) // www.iraj.in [2017 — ]. URL: http://www.iraj.in/journal/journal_file/journal_pdf/3-386-1505390942108-113.pdf (дата обращения 06.04.2019).
  6. Operating System | Multilevel Queue Scheduling // GeeksforGeeks [2019 — ]. URL: https://www.geeksforgeeks.org/operating-system-multilevel-queue-scheduling/ (дата обращения 24.05.2019).