Многоуровневые очереди (Multilevel Queue)

Содержание.

3.1. Стратегии планирования.

3.1.1. Критерии планирования процессора.

3.1.2. Дисциплина диспетчеризации FCFS (First Come – First Served).

3.1.3. Дисциплина диспетчеризации RR (Round Robin - круговорот).

3.1.4. Дисциплина диспетчеризации SJF Shortest-Job-First.

3.2. Планирование по наивысшему приоритету.

Простой круговорот.

3.4. Очереди с обратной связью.

3.1. Стратегии и критерии планирования процессов.

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

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

 

 

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

ü по возможности завершить вычислительные процессы в том же самом порядке, в котором они были начаты;

ü отдавать предпочтение процессам с наивысшим приоритетом;

ü предоставлять всем процессам одинаковое время ожидания.

Для сравнения алгоритмов диспетчеризации используются следующие критерии:

1. Использование или утилизация CPU (CPU utilization). Использование CPU теоретически может находиться пределах от 0 до 100%. В реальных системах использование CPU колеблется в пределах 40% для легко загруженного CPU, 90% для тяжело загруженного CPU.

2. Пропускная способность (CPU throughput). Пропускная способность CPU может измеряться количеством процессов, которые выполняются в единицу времени.

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

4. Время ожидания (waiting time). Под временем ожидания понимается суммарное время нахождения процесса в очереди готовых процессов.

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

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

3.2. Дисциплина диспетчеризации FCFS (First Come, First Served - Первый пришел, первый обслуживается).

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

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

К достоинствам этой дисциплины можно отнести простоту реализации и малые расходы системных ресурсов на формирование очереди задач. В то же время он имеет и много недостатков. Рассмотрим следующий пример.

Пример 1. Пусть в состоянии готовность находятся три процесса P₀, P₁ и P₂, для которых известны значения времени последующего обслуживания процессором. Эти времена приведены в таблице 3.1. в некоторых условных единицах. Для простоты будем полагать, что вся деятельность процессов ограничивается использованием только одного промежутка процессорного времени, что процессы не совершают операций ввода-вывода, и что время переключения контекста пренебрежимо мало.

P2 P1 P0

Таблица 3.1.

Время	P0	P1	P2	Всего	Средняя
Процессорное
Ожидания
Оборота

 

Если процессы распложены в очереди процессов готовых к исполнению в порядке P₀, P₁, P₂, то картина их выполнения выглядит так, как показано на рисунке 3.2. Первым для выполнения выбирается процесс P₀, который получает процессор на все время своего CPU burst, т. е. на 13 единиц времени. После его окончания в состояние исполнение переводится процесс P₁, занимая процессор на 4 единицы времени. И, наконец, возможность работать получает процесс P₂. Время ожидания для процесса P₀ составляет 0 единиц времени, для процесса P₁ – 13 единиц, для процесса P₂ – 13 + 4 = 17 единиц. Таким образом, среднее время ожидания в этом случае – (0 + 13 + 17)/3 = 10 единиц времени. Полное время выполнения для процесса P₀ составляет 13 единиц времени, для процесса P₁ – 13 + 4 = 17 единиц, для процесса P₂ – 13 + 4 + 1 = 18 единиц. Среднее полное время выполнения оказывается равным (13 + 17 + 18)/3 = 16 единицам времени.

Пример 2. Пусть те же самые процессы, что в примере 1 расположены в порядке P₂, P₁, P₀. Картина их выполнения будет соответствовать рисунку 3.3.

P2 P1 P0

Рис 3.3. Выполнение процессов в порядке P₂, P₁, P₀

Таблица 3.2.

Время	P0	P1	P2	Всего	Средняя
Процессорное
Ожидания
Оборота

 

 

Время ожидания для процесса P₀ равняется 5 единицам времени, для процесса P₁ – 1 единице, для процесса P₂ — 0 единиц. Среднее время ожидания составит (5 + 1 + 0)/3 = 2 единицы времени. Это в 5 (!) раз меньше, чем в предыдущем случае. Полное время выполнения для процесса P₀ получается равным 18 единицам времени, для процесса P₁ – 5 единицам, для процесса P₂ – 1 единице. Среднее полное время выполнения составляет (18 + 5 + 1)/3 = 8 единиц времени, что в 2 раза меньше чем при первой расстановке процессов.

Как видим, среднее время ожидания и среднее полное время выполнения для этого алгоритма существенно зависят от порядка расположения процессов в очереди. Стратегии FCFS присущ так называемый “эффект конвоя”. Если в системе есть процесс с длительным процессорным временем, то короткие процессы, перешедшие в состояние готовность после длительного процесса, будут очень долго ждать начала своего выполнения: все процессы собираются в начале очереди готовых процессов, а затем в очереди к оборудованию. Поэтому “эффект конвоя” приводит к снижению загруженности как процессора, так и периферийного оборудования. Алгоритм FCFS практически неприменим для систем разделения времени. Слишком большим получается среднее время отклика в интерактивных процессах.

3.2.1. Дисциплина диспетчеризации RR (Round Robin круговорот).

Модификацией алгоритма FCFS является алгоритм, получивший название Round Robin (Round Robin – это вид детской карусели в США) или сокращенно RR. Данная дисциплина предполагает, что каждая задача получает процессорное время порциями – квантами времени q. После окончания кванта времени q задача снимается с процессора и он передается следующей задаче. Снятая задача ставится в конец очереди задач, готовых к выполнению. Дисциплина RR иллюстрируется рис. 3.4.

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

1. Время непрерывного использования процессора, требующееся процессу, (остаток текущего процессорного времени) меньше или равно продолжительности кванта времени. Тогда процесс по своей воле освобождает процессор до истечения кванта времени, на исполнение выбирается новый процесс из начала очереди и таймер начинает отсчет кванта заново.

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

Пример 3. Рассмотрим три процесса, что в примере 1 и пусть величина кванта времени равна 4. Выполнение этих процессов иллюстрируется таблицей 3.2. Обозначение “И” используется в ней для процесса, находящегося в состоянии исполнение, обозначение “Г” – для процессов в состоянии готовность, пустые ячейки соответствуют завершившимся процессам. Состояния процессов показаны на протяжении соответствующей единицы времени, т. е. колонка с номером 1 соответствует промежутку времени от 0 до 1.

Таблица 3.2.

Дисциплина диспетчеризации RR процессов P₀, P₁, P₂ для кванта времени q=4 сек.

время

P0

И

И

И

И

Г

Г

Г

Г

Г

И

И

И

И

И

И

И

И

И

P1

Г

Г

Г

Г

И

И

И

И

P2

Г

Г

Г

Г

Г

Г

Г

Г

И

Первым для исполнения выбирается процесс P₀. Продолжительность его процессорного времени больше, чем величина кванта времени, и поэтому процесс исполняется до истечения кванта, т. е. в течение 4 единиц времени. После этого он помещается в конец очереди готовых к исполнению процессов, которая принимает вид P₁, P₂, P₀. Следующим начинает выполняться процесс P₁. Время его исполнения совпадает с величиной выделенного кванта, поэтому процесс работает до своего завершения. Теперь очередь процессов в состоянии готовность состоит из двух процессов P₂, P₀. Процессор выделяется процессу P₂. Он завершается до истечения отпущенного ему процессорного времени, и очередные кванты отмеряются процессу P₀ – единственному, не закончившему к этому моменту свою работу. Время ожидания для процесса P₀ (количество символов “Г” в соответствующей строке) составляет 5 единиц времени, для процесса P₁ – 4 единицы времени, для процесса P₂ – 8 единиц времени. Таким образом, среднее время ожидания для этого алгоритма получается равным (5 + 4 + 8)/3 = 5,6(6) единицы времени. Полное время выполнения для процесса P₀ (количество непустых столбцов в соответствующей строке) составляет 18 единиц времени, для процесса P₁ – 8 единиц, для процесса P₂ – 9 единиц. Среднее полное время выполнения оказывается равным (18 + 8 + 9)/3 = 11,6 (6) единицам времени.

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

На производительность алгоритма RR сильно влияет величина кванта времени. Рассмотрим тот же самый пример c порядком процессов P₀, P₁, P₂ для величины кванта времени равной 1 (см. таблицу 3.3.). Время ожидания для процесса P₀ составит 5 единиц времени, для процесса P₁ – тоже 5 единиц, для процесса P₂ – 2 единицы. В этом случае среднее время ожидания получается равным (5 + 5 + 2)/3 = 4 единицам времени. Среднее полное время исполнения составит (18 + 9 + 3)/3 = 10 единиц времени.

Таблица 3.3.

Дисциплина диспетчеризации RR процессов P₀, P₁, P₂ для кванта времени q=1 сек.

время

P0

И

Г

Г

И

Г

И

Г

И

Г

И

И

И

И

И

И

И

И

И

P1

Г

И

Г

Г

И

Г

И

Г

И

P2

Г

Г

И

При очень больших величинах кванта времени, когда каждый процесс успевает завершить свое процессорное время до возникновения прерывания по времени, алгоритм RR вырождается в алгоритм FCFS. При очень малых величинах создается иллюзия того, что каждый из n процессов работает на своем собственном виртуальном процессоре с производительностью ~ 1/n от производительности реального процессора. Это справедливо лишь при теоретическом анализе при условии пренебрежения временами переключения контекста процессов. В реальных условиях при слишком малой величине кванта времени и, соответственно, слишком частом переключении контекста, накладные расходы на переключение резко снижают производительность системы.

3.2.2. Дисциплина диспетчеризации SJF (Shortest-Job-First – Кратчайшее задание первым) или SRT (ShortTest Remaining Time – Следующее задание с меньшим временем).

Для рассмотренных алгоритмов FCFS и RR существенным является порядок расположения процессов в очереди процессов готовых к исполнению. Если короткие задачи расположены в очереди ближе к ее началу, то общая производительность этих алгоритмов значительно возрастает. Если знать процессорное время следующих процессов, находящихся в состоянии готовность, то можно выбирать для исполнения не процесс из начала очереди, а процесс с минимальным процессорным временем. Если же таких процессов два или больше, то для выбора одного из них можно использовать известный алгоритм FCFS. Квантование времени при этом не применяется. Описанный алгоритм получил название “кратчайшая работа первой” или Shortest Job First (SJF).

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

Пример 4. Пусть в состоянии готовность находятся четыре процесса P₀, P₁, P₂ и P₃, для которых известны их процессорные времена. Эти времена приведены в таблице 3.4. Как и прежде, будем полагать, что вся деятельность процессов ограничивается использованием только одного промежутка CPU burst, что процессы не совершают операций ввода-вывода, и что время переключения контекста пренебрежимо мало.

Таблица 3.4.

Время выполнения процессов P₀, P₁, P₂, P₃.

Процесс	P0	P1	P2	P3
Продолжительность очередного CPU burst

При использовании невытесняющего алгоритма SJF первым для исполнения будет выбран процесс P₃, имеющий наименьшее значение процессорного времени. После его завершения для исполнения выбирается процесс P₁, затем P₀ и, наконец, P₂. Вся эта картина изображена в таблице 3.5.

Таблица 3.5.

Выполнение процессов P₀, P₁, P₂, P₃ при использовании невытесняющего

алгоритма SJF.

время

P0

Г

Г

Г

Г

И

И

И

И

И

P1

Г

И

И

И

P2

Г

Г

Г

Г

Г

Г

Г

Г

Г

И

И

И

И

И

И

И

P3

И

Как видим, среднее время ожидания для алгоритма SJF составляет (4 + 1 + 9 + 0)/4 = 3,5 единицы времени. Легко посчитать, что для алгоритма FCFS при порядке процессов P₀, P₁, P₂, P₃ эта величина будет равняться (0 + 5 + 8 + 15)/4 = 7 единицам времени, т. е. будет в 2 раза больше, чем для алгоритма SJF. Можно показать, что для заданного набора процессов (если в очереди не появляются новые процессы) алгоритм SJF является оптимальным с точки зрения минимизации среднего времени ожидания среди класса всех невытесняющих алгоритмов.

Действительно, пусть a, b, c, d – время выполнения для 4 процессов. Тогда время выполнения для первого будет – a, для второго – a + b, для третьего – a + b + c, для четвертого – a + b + c + d.

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

a +a + b + a + b + c + a + b + c + d = 4a + 3b + 2c + d.

Среднее полное время исполнения: (4a + 3b + 2c + d)/4

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

Для рассмотрения примера вытесняющего SJF планирования мы возьмем ряд процессов P₀, P₁, P₂ и P₃ c различными временами CPU burst и различными моментами их появления в очереди процессов готовых к исполнению (см. таблицу 3.6.).

Таблица 3.6.

Выполнение процессов P₀, P₁, P₂, P₃ при использовании вытесняющего алгоритма SJF.

Процесс	Время появления в очереди	Продолжительность очередного CPU burst
P0
P1
P2
P3

В начальный момент времени в состоянии готовность находятся только два процесса P₀ и P₃. Меньшее процессорное время у процесса P₃, поэтому он и выбирается для исполнения (см. таблицу 3.7.). По прошествии 2-х единиц времени в систему поступает процесс P₁. Его процессорное время меньше, чем остаток процессорного времени у процесса P₃, который вытесняется из состояния исполнение и переводится в состояние готовность. По прошествии еще 2-х единиц времени процесс P₁ завершается, и для исполнения вновь выбирается процесс P₃. В момент времени t = 6 в очереди процессов готовых к исполнению появляется процесс P₂, но поскольку ему для работы нужно 7 единиц времени, а процессу P₃ осталось трудиться всего 2 единицы времени, то процесс P₃ остается в состоянии исполнение. После его завершения в момент времени t = 7 в очереди находятся процессы P₀ и P₂, из которых выбирается процесс P₀. Наконец, последним получит возможность выполняться процесс P₂.

время
P0	Г	Г	Г	Г	Г	Г	Г	И	И	И
P1			И	И
P2							Г	Г	Г	Г
P3	И	И	Г	Г	И	И	И

 

время
P0	И	И	И
P1
P2
P3	Г	Г	Г	И	И	И	И	И	И	И

Основную сложность при реализации алгоритма SJF представляет невозможность точного знания процессорного времени очередного процесса для исполняющихся процессов. В пакетных системах количество процессорного времени, требующееся заданию для выполнения, указывает пользователь при формировании задания. Эту величину можно взять для осуществления долгосрочного SJF планирования. Если пользователь укажет больше времени, чем ему нужно, он будет ждать получения результата дольше, чем мог бы, так как задание будет загружено в систему позже. Если же он укажет меньшее количество времени, задача может не досчитаться до конца. Таким образом, в пакетных системах решение задачи оценки времени использования процессора перекладывается на плечи пользователя. При диспетчеризации можно делать прогноз длительности следующего процессорного времени, только исходя из предыстории работы процесса. Пусть t(n) – величина процессорного времени n -го процесса, T(n + 1) – предсказываемое значение процессорного времени для n + 1-го процесса, a – некоторая величина в диапазоне от 0 до 1.

Определим рекуррентное соотношение

T(0) положим произвольной константой. Первое слагаемое учитывает последнее поведение процесса, тогда как второе слагаемое учитывает его предысторию. При a = 0 мы перестаем следить за последним поведением процесса, фактически полагая

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

Положив a = 1, мы забываем о предыстории процесса. В этом случае мы полагаем, что процессорное время очередного процесса будет совпадать с процессорным временем последнего процесса:

Обычно выбирают для равноценного учета последнего поведения и предыстории. Надо отметить, что такой выбор a удобен и для быстрой организации вычисления оценки T(n + 1). Для подсчета новой оценки нужно взять старую оценку, сложить с измеренным процессорным временем и полученную сумму разделить на 2, например, с помощью ее сдвига на 1 бит вправо. Полученные оценки T(n + 1) применяются как продолжительности очередных промежутков времени непрерывного использования процессора для краткосрочного SJF планирования.

3.2.3. Гарантированное планирование.

При интерактивной работе N пользователей в вычислительной системе можно применить алгоритм планирования, который гарантирует, что каждый из пользователей будет иметь в своем распоряжении ~ 1/N часть процессорного времени. Пронумеруем всех пользователей от 1 до N. Для каждого пользователя с номером i введем две величины: T_i - время нахождения пользователя в системе, или, другими словами длительность сеанса его общения с машиной, и t_i - суммарное процессорное время уже выделенное всем его процессам в течение сеанса. Справедливым для пользователя было бы получение T_i/N процессорного времени. Если

то i - й пользователь несправедливо обделен процессорным временем. Если же

то система явно благоволит к пользователю с номером i. Вычислим для каждого пользовательского процесса значение коэффициента справедливости

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

3.2.4. Приоритетное планирование.

Алгоритмы SJF и гарантированного планирования представляют собой частные случаи приоритетного планирования. При приоритетном планировании каждому процессу присваивается определенное числовое значение — приоритет, в соответствии с которым ему выделяется процессор. Процессы с одинаковыми приоритетами планируются в порядке FCFS. Для алгоритма SJF в качестве такого приоритета выступает оценка продолжительности следующего CPU burst. Чем меньше значение этой оценки, тем более высокий приоритет имеет процесс. Для алгоритма гарантированного планирования приоритетом служит вычисленный коэффициент справедливости. Чем он меньше, тем больше приоритет у процесса.

Принципы назначения приоритетов могут опираться как на внутренние критерии вычислительной системы, так и на внешние по отношению к ней. Внутренние используют различные количественные и качественные характеристики процесса для вычисления его приоритета. Это могут быть, например, определенные ограничения по времени использования процессора, требования к размеру памяти, число открытых файлов и используемых устройств ввода-вывода, отношение средних продолжительностей I/O burst к CPU burst и т. д. Внешние критерии исходят из таких параметров, как важность процесса для достижения каких-либо целей, стоимость оплаченного процессорного времени и других политических факторов. Высокий внешний приоритет может быть присвоен задаче лектора или того, кто заплатил $100 за работу в течение одного часа.

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

Пусть в очередь процессов, находящихся в состоянии готовность, поступают те же процессы, что и в примере из раздела 3.5. для вытесняющего алгоритма SJF, только им дополнительно еще присвоены приоритеты (см. таблицу 3.8.). В вычислительных системах не существует определенного соглашения, какое значение приоритета - 1 или 4 считать более приоритетным. Во избежание путаницы, во всех наших примерах мы будем предполагать, что большее значение соответствует меньшему приоритету, т.е. наиболее приоритетным в нашем примере является процесс P₃, а наименее приоритетным – процесс P₀.

Процесс	Время появления в очереди	Продолжительность очередного CPU burst	Приоритет
P0
P1
P2
P3

Как будут вести себя процессы при использовании невытесняющего приоритетного планирования? Первым для выполнения в момент времени t = 0 выбирается процесс P₃, как обладающий наивысшим приоритетом. После его завершения в момент времени t = 5 в очереди процессов готовых к исполнению окажутся два процесса P₀ и P₁. Больший приоритет из них у процесса P₁ он и начнет выполняться (см. таблицу 3.9.). Затем в момент времени t = 7 для исполнения будет избран процесс P₂ и лишь потом процесс P₀.

время
P0	Г	Г	Г	Г	Г	Г	Г	Г	Г	Г
P1			Г	Г	Г	И	И
P2							Г	И	И	И
P3	И	И	И	И	И

 

время
P0	Г	Г	Г	Г	И	И	И	И	И	И
P1
P2	И	И	И	И
P3

Иным будет предоставление процессора процессам в случае вытесняющего приоритетного планирования (см. таблицу 3.10.). Первым, как и в предыдущем случае, исполняться начнет процесс P₃, а по его окончании процесс P₁. Однако в момент времени t = 6 он будет вытеснен процессом P₂ и продолжит свое выполнение только в момент времени t = 13. Последним, как и раньше будет исполнен процесс P₀.

 

В рассмотренном выше примере приоритеты процессов не изменялись с течением временем. Такие приоритеты принято называть статическими. Механизмы статической приоритетности легко реализовать, и они сопряжены с относительно небольшими издержками на выбор наиболее приоритетного процесса. Однако статические приоритеты не реагируют на изменения ситуации в вычислительной системе, которые могут сделать желательной корректировку порядка исполнения процессов. Более гибкими являются динамические приоритеты процессов, изменяющие свои значения по ходу исполнения процессов. Начальное значение динамического приоритета, присвоенное процессу, действует в течение лишь короткого периода времени, после чего ему назначается новое, более подходящее значение. Изменение динамического приоритета процесса является единственной операцией над процессами, которую мы до сих пор не рассмотрели. Как правило, изменение приоритета процессов проводится согласованно с совершением каких-либо других операций: при рождении нового процесса, при разблокировке или блокировании процесса, по истечении определенного кванта времени или по завершении процесса. Примерами алгоритмов с динамическими приоритетами являются алгоритм SJF и алгоритм гарантированного планирования. Схемы с динамической приоритетностью гораздо сложнее в реализации и связанны с большими издержками по сравнению со статическими схемами. Однако их использование предполагает, что эти издержки оправдываются улучшением поведения системы.

Главная проблема приоритетного планирования заключается в том, что при ненадлежащем выборе механизма назначения и изменения приоритетов низкоприоритетные процессы могут быть не запущены неопределенно долгое время. Обычно случается одно из двух. Или они все же дожидаются своей очереди на исполнение (в девять часов утра в воскресенье, когда все приличные программисты ложатся спать). Или вычислительную систему приходится выключать, и они теряются (при остановке IBM 7094 в Массачусетском технологическом институте в 1973 году были найдены процессы, запущенные в 1967 году и ни разу с тех пор не исполнявшиеся). Решение этой проблемы может быть достигнуто с помощью увеличения со временем значения приоритета процесса, находящегося в состоянии готовность. Пусть изначально процессам присваиваются приоритеты от 128 до 255. Каждый раз, по истечении определенного промежутка времени, значения приоритетов готовых процессов уменьшаются на 1. Процессу, побывавшему в состоянии исполнение, восстанавливается первоначальное значение приоритета. Даже такая грубая схема гарантирует, что любому процессу в разумные сроки будет предоставлено право на исполнение.

Многоуровневые очереди (Multilevel Queue)

Для систем, в которых п<

Поделиться:

Воспользуйтесь поиском по сайту: