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

Планирование и диспетчеризация процессов

Уровни планирования

Задача планирования загрузки процессоров - определение когда и каким процессам следует выделять ресурсы процессора.

Существуют три уровня такого планирования:

1. Планирование на верхнем уровне.

Планирование на промежуточном уровне.

Средства этого уровня определяют, каким процессам будет разрешено конкурировать за захват ЦП. Планировщик этого уровня определяет, какие процессы приостанавливаются, а какие возобнавляются.

Планирование на нижнем уровне.

Средства этого уровня выполняют диспетчерские функции, определяя, какому из готовых к выполнению процессов будут предоставлены ресурсы ЦП.

Планирование на нижнем уровне выполняется диспетчером, который всегда располагается в оперативной памяти.

Ввод заданий

Активизация Приостановка Планирование промежуточного уровня

Блокирование Предоставление ЦП Планирование нижнего уровня

Рис. Уровни планирования

Цели планирования

Дисциплина планирования должна обеспечивать: максимальную пропускную способность системы; приемлемые времена ответа для максимального количества пользователей; предсказуемость; минимальные накладные расходы; сбалансированное использование ресурсов; сбалансированность времени ответа и коэффициента использования ресурсов; должна исключать бесконечное откладывание процессов; учитывать приоритеты; оказывать предпочтение тем процессам, которые занимают ключевые ресурсы

Факторы, учитываемые при планировании

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

Планирование с переключением и без переключения

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

Планирование с переключением необходимо в системах, где процессы высокого приоритета требуют немедленного внимания.

Приоритеты

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

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

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

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

Планирование по принципу FIFO (first-in-first-out)

Принцип FIFO, “ первый пришедший обслуживается первым”, является наиболее простой дисциплиной планирования. ЦП предоставляется процессам в порядке их прихода в очередь готовности.

После того, как процесс получает ЦП в свое распоряжение, он выполняется до завершения, т.е. это дисциплина планирования без переключения.

Готовые процессы Завершение

Z Y XЦП

Рис. Планирование по принципу FIFO

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

Циклическое планирование RR (round robin)

Планирование по принципу RR предполагает диспетчирование процессов по принципу FIFO, но каждый процесс получает временной квант, в течение которого он может использовать ресурсы ЦП. Если завершения процесса не происходит по истечении кванта времени, то этот процесс переводится в конец списка готовых к выполнению процессов, а ресурсы ЦП предоставляются следующему процессу из списка.

Готовые процессы Завершение

X Z Y XЦП

Истечение кванта времени

Рис. Планирование по принципу RR

Очевидно, что для данного алгоритма планирования основной вопрос заключается в определнии размера кванта времени, и следует ли делать его фиксированным или переменным.

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

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

Готовые процессы Завершение

Z1 Y1 X1ЦП Уровень 1 FIFO

Истечение кванта времени

Готовые процессы Завершение

X1 Z2 Y2 X2ЦП Уровень 2 FIFO

Истечение кванта времени

. . .

Готовые процессы Завершение

Xn-1 Zn Yn XnЦП Уровень n RR

Истечение кванта времени

Рис. Многоуровневые очереди с обратными связями

Планироване в многопроцессорных системах

Цель: максимальная производительность и минимальное время реагирования.

Важен не только порядок выполнения процессов, но и то на каких процессорах эти процессы должны выполнятся.

Взаимодействующие процессы часто объединяются в задачи.

Планирование:

· С временным разделением (timesharing sheduling)

· Привязка задач к процессорам ( processor affinity)

ü Мягкая, пытающаяся на одном

ü Жесткая, всегда на одном.

· Задачно независимые (все однопроцессорные)

· Задачно ориентированные

ü SNPF smallest number of process first наибольшее количество процессов первым (приоритет обратно пропорционален количеству процессов)

ü RR

ü Динамическое разделение. Планировщик поровну распределяет процессоры системы между задачами

Планирование реального времени

Статические не позволяют менять приоритет процесса во время его выполнения (в жестких СРВ) RM rate-monotonic монотонно увеличивает приоритет

Динамические могут менять приоритеты во время выполнения. EDF earlest deadline first ближайший срок завершения первым

Дисциплина SJN Shortest Job Next – следующим будет выполнятся кратчайшее задание.

SRT Shortest remaining time – следующим будет выполнятся задание требующее меньше времени.

Планирование процессов в UNIX – карусель с многоуровневой обратной связью. Если приоритет одинаковый то выбирается тот процесс который дольше всего находится в состоянии «готов к выполнению»

ИЦП – использование ресурсов центрального процессора

ИЦП = ИЦП/2

Приоритет = (ИЦП/2)+Базовый уровень приоритета

У активного процесса ИЦП = ИЦП+1 по каждому прерыванию за время кванта интервальный таймер выдает несколько сигналов прерываний.

Win 3.11 – невытесняющая многозадачность (FIFO)

Win 9x – вытесняющая многозадачность, квант = 20 мсек, макс 32 приоритета, внешние события повышают приоритет, приоритет падает до исходного, приоритет растет если процесс захватил монопольный (неразделяемый) ресурс.

Win NT-2000

Приоритеты 4 класса 32 градации

Реального времени – 24

Высокий 13

Нормальный 9 интерактивный 7 фоновый

Отложенный 4

1. выбирается процесс с наивысшим приоритетом

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

3. по истечению кванта времени приоритет уменьшается

4. если процесс перешел в ожидание не исчерпав кванта времени, то приоритет повышается.

QNX – абсолютные приоритеты