Планирование . (задания).

Планирование . (задания).
Введение
1. Уровни планирования
2. Цели планирования
3. Критерии планирования
4. Планирование с переключением и без переключения
5. Интервальный таймер или прерывающие часы-будильник
6. Приоритеты
6.1. Статические и динамические приоритеты
6.2. Покупаемые приоритеты
7. Планирование по сроку завершения
8. Планирование по принципу FIFO («первый пришедший обслуживается первым»)
9. Циклическое планирование (RR)
10. Размер кванта времени
11. Планирование по принципу SJF («кратчайшее задание — первым»)
12. Планирование по принципу SRT («по наименьшему остающемуся времени»)
13. Планирование по принципу HRN («по наибольшему относительному времени реакции»)
14. Многоуровневые очереди с обратными связями
Заключение
СПИСОК ЛИТЕРАТУРЫ

Обычно в системе предусматривается некоторая очередь самого нижнего уровня, которая реализует принцип циклического обслуживания и в которой данный процесс циркулирует до тех пор, пока не завершится.
Во многих структурах многоуровневых очередей с обратными связями квант времени, предоставляемый данному процессу при Переходе в каждую очередь более низкого уровня, увеличивается.
 
Рис.4. Многоуровневые очереди с обратными связями
Таким образом, чем дольше находится процесс в сети очередей, тем больший квант времени выделяется ему с каждым разом, когда он получает в свое распоряжение ЦП. Однако ему не удается получать ЦП слишком часто, поскольку процессы, находящиеся в очередях более высоких уровней, имеют и более высокий приоритет. Процесс, находящийся в данной очереди, может начать выполнение только в случае, если нет ожидающих во всех очередях более высоких уровней. Выполняющийся процесс прерывается, если поступает новый процесс в очередь более высокого уровня.
Теперь, после того как мы описали работу сети очередей, рассмотрим, каким образом подобный механизм реагирует на различные типы процессов. Этот механизм должен оказывать предпочтение процессам, лимитируемым вводом-выводом, чтобы обеспечить хорошую загрузку устройств ввода-вывода и малое время реакции на запросы интерактивных пользователей. И действительно, так и будет, поскольку процесс, связанный с вводом-выводом, будет поступать в очередь с очень высоким приоритетом и ему будет быстро предоставляться ЦП. Квант времени для первой очереди выбирается достаточно большим, с тем, чтобы подавляющее большинство заданий, связанных с вводом-выводом, успевало выдать запрос ввода-вывода еще до истечения первого кванта. Когда подобный процесс выдает запрос ввода-вывода, он выходит из сети очередей, причем, получив истинно приоритетное обслуживание, что и требовалось.
Рассмотрим теперь задание, лимитируемое ЦП и требующее много времени ЦП. Это задание поступает в верхнюю очередь сети, очередь с очень высоким приоритетом. Первый раз задание получает в свое распоряжение ЦП весьма быстро, однако после истечения выделенного ему кванта времени процесс переходит в конец очереди следующего нижележащего уровня. Теперь этот процесс будет иметь более низкий приоритет, так что вновь поступающие процессы, особенно связанные по преимуществу с вводом-выводом, будут первыми получать в свое распоряжение ЦП. Со временем данный вычислительный процесс все же получит ЦП, ему будет выделен квант времени большей величины, чем в очереди наивысшего приоритета, но он снова не успеет завершиться по истечении этого полного кванта. Затем он будет помещен в конец очереди следующего нижележащего уровня. Таким образом данный процесс будет продолжать переходить в очереди с более низкими приоритетами, будет дольше ждать в промежутках между выделяемыми ему квантами времени и каждый раз полностью использовать свой квант, когда будет получать в свое распоряжение ЦП (если при этом не будет прерываться из-за поступления процесса с более высоким приоритетом). В конце концов, этот вычислительный процесс окажется в очереди самого низкого уровня с циклическим обслуживанием, где и будет циркулировать, пока не завершится.
Многоуровневые очереди с обратными связями — это идеальный механизм, позволяющий разделять процессы на категории в соответствии с их потребностями во времени ЦП. В системе с разделением времени каждый раз, когда процесс выходит из сети очередей, он может быть помечен признаком очереди самого низкого уровня, в которой он побывал. Когда этот процесс впоследствии вновь войдет в сеть очередей, он будет направлен прямо в ту очередь, в которой он последний раз завершал свою работу. Здесь планировщик действует на основе следующего эвристического правила: поведение процесса в недавнем прошлом может служить хорошим ориентиром для определения его поведения в ближайшем будущем. Поэтому процесс, лимитируемый ЦП, при своем возвращении в сеть очередей не будет помещаться в очереди более высоких уровней, где он только мешал бы обслуживать короткие процессы высокого приоритета или процессы, лимитируемые вводом-выводом.
Если процессы всегда помещать в сеть очередей на самый низкий уровень, который они занимали прошлый раз, то система не сможет реагировать на изменения характера процесса, например на то, что процесс, бывший по преимуществу вычислительным, становится преимущественно «обменным». Эту проблему можно решить, если в метке, которой сопровождается процесс, указывать длительность его выполнения при последнем пребывании в сети очередей. Когда такой процесс вновь поступит в сеть очередей, его можно будет поместить в нужную очередь. Если процесс войдет в новую фазу, в которой он вместо лимитируемого ЦП станет обменным, первоначально он будет несколько страдать от «неповоротливости» системы, пока система не определит, что характер процесса изменился. Однако описываемый механизм планирования довольно быстро реагирует на подобные изменения. Еще один путь обеспечения быстрой реакции системы на изменения в поведении процесса — это позволить процессу перемещаться на один уровень вверх в сети очередей каждый раз, когда он добровольно освободит ЦП еще до истечения выделяемого ему кванта времени.
Многоуровневые очереди с обратными связями — показательный пример адаптивного механизма, механизма, который может реагировать на изменение поведения контролируемой им системы. Адаптивные механизмы, как правило, требуют больших накладных расходов, чем неадаптивные, однако присущая им чувствительность к изменениям режима работы делает систему более реактивной и компенсирует накладные расходы.
Одним из распространенных вариантов механизма многоуровневых очередей с обратными связями является вариант, в котором процесс несколько раз циркулирует в каждой очереди, прежде чем перейти в очередь следующего нижележащего уровня. Как правило, количество подобных циклов в каждой очереди увеличивается по мере перехода процесса на нижележащие уровни.
Заключение
Планировщики процессоров определяют, когда следует предоставлять процессоры и каким процессам. Планирование на верхнем уровне, или планирование заданий, определяет, какие задания будут допускаться в систему. После допуска в систему эти задания становятся процессами или группами процессов. Планирование на нижнем уровне, или диспетчирование, определяет, какому из готовых к выполнению процессов будет предоставлен в распоряжение центральный процессор в следующий раз. Планирование на промежуточном уровне определяет, каким процессам будет разрешено состязаться за захват ЦП и какие процессы будут кратковременно приостанавливаться в связи с текущими изменениями в нагрузке на систему.
Дисциплина планирования должна быть справедливой, обеспечивать максимальную пропускную способность системы, приемлемые времена ответа для максимального количества пользователей, работающих в интерактивном режиме, предсказуемость, минимальные накладные расходы, сбалансированное использование ресурсов, сбалансированность времени ответа и коэффициента использования ресурсов, должна исключать бесконечное откладывание процессов, учитывать приоритеты, оказывать предпочтение тем процессам, которые занимают ключевые ресурсы, предусматривать улучшенное обслуживание для процессов, отличающихся «примерным поведением», и «плавно деградировать» при увеличении нагрузок. Многие из этих целей противоречат друг другу, что делает планирование весьма сложной проблемой.
Для достижения указанных целей механизм планирования должен учитывать, лимитируется ли процесс вводом-выводом или вычислениями, является ли процесс пакетным или диалоговым, обязательно ли малое время ответа, приоритет каждого процесса, частоту генерации каждым процессом прерываний по отсутствию нужных страниц, частоту переключений с низкоприоритетных процессов на поступающие процессы более высокого приоритета, приоритеты процессов, ожидающих освобождения уже занятых ресурсов, длительность периода времени, в течение которого ожидает каждый процесс, суммарное время работы каждого процесса и оценочное время, необходимое каждому процессу для завершения.
Планирование считается планированием без переключения, если центральный процессор нельзя отнять у занимающего его процесса; в противном случае планирование считается планированием с переключением. Планирование с переключением играет важную роль в мультипрограммных системах, в которых некоторые процессы должны обслуживаться очень быстро, причем особенно важное значение они имеют в системах реального времени и системах с разделением времени.
Полезной компонентой системы планирования с переключением является интервальный таймер, или прерывающие часы. По истечении заданного временного интервала таймер генерирует сигнал прерывания, по которому управление центральным процессором переходит от текущего процесса к операционной системе. Операционная система может после этого запустить в работу следующий процесс.
Статические приоритеты остаются одинаковыми на всем протяжении выполнения процесса; динамические приоритеты меняются в ответ на изменения ситуации в системе. Некоторые системы предоставляют пользователю возможность покупать для своих программ более высокие приоритеты.
Планирование по сроку завершения организуется таким образом, чтобы определенные процессы завершались в определенные сроки. Планирование по сроку завершения — это сложная проблема, особенно в условиях, когда в промежутке между моментом начала выполнения процесса и запланированным сроком его завершения в систему могут поступать дополнительные задания.
Принцип FIFO («первый пришедший обслуживается первым») — это дисциплина планирования без переключения, при которой процессам предоставляется ЦП в соответствии со временем их поступления в список готовых к выполнению. Это распространенная дисциплина планирования заданий в системах пакетной обработки, однако, она не позволяет гарантировать приемлемые времена ответа для интерактивных пользователей.
Циклическое планирование (RR) — это по сути вариант FIFO с переключением ЦП. Диспетчирование процессов осуществляется здесь по принципу FIFO, однако ЦП предоставляется им только на ограниченное время, называемое квантом времени. Если квант времени некоторого процесса истечет до того, как этот процесс добровольно освободит ЦП, у него будет отобран ЦП, а затем выделен другому готовому для выполнения процессу. Циклическое планирование применяется обычно для того, чтобы гарантировать приемлемые времена ответа для интерактивных пользователей.
Определение оптимального размера кванта времени представляет собой сложную проблему. Размер кванта имеет первостепенное значение с точки зрения обеспечения рационального использования ресурсов системы и получения приемлемых времен ответа. Очень большой размер кванта приводит к тому, что любая дисциплина планирования с переключением начинает приближаться по своим характеристикам к аналогу без переключения. При очень малом размере кванта время ЦП непроизводительно расходуется на многочисленные контекстные переключения при переходе с процесса на процесс. Как правило, размер кванта стараются выбирать настолько большим, чтобы подавляющее большинство тривиальных запросов можно было полностью обслужить в рамках одного кванта. Например, в системе, лимитируемой вводом-выводом, размер кванта выбирается таким, чтобы большинство процессов успевало сформировать и выдать свой следующий запрос ввода-вывода в пределах одного кванта времени.
Планирование по принципу SJF («кратчайшее задание — первым») — это планирование без переключений, применяемое преимущественно для планирования пакетных заданий. Оно обеспечивает минимальное среднее время ожидания для заданий, однако для длинных заданий время ожидания может оказаться большим.
Дисциплина SRT («по наименьшему остающемуся времени») — это аналог принципа SJF с переключением. При планировании по принципу SRT выполнение текущего процесса может быть прервано при поступлении нового процесса с более коротким оценочным временем выполнения. Механизму SRT свойственны более высокие накладные расходы, чем SJF, однако он обеспечивает лучшее обслуживание поступающих коротких заданий. Он позволяет еще больше снизить средние времена ожиданий для всех заданий, однако длинные задания могут испытывать даже большие задержки, чем в случае SJF.
Предложенный Бринком Хансеном принцип HRN («по наибольшему относительному времени ответа») — это планирование без переключения, при котором в определенной степени корректируются некоторые недостатки SJF, в частности исключается чрезмерное игнорирование длинных заданий и чрезмерная благосклонность к коротким новым заданиям.
Одним из наиболее совершенных механизмов планирования, применяемых в настоящее время, является сеть многоуровневых очередей с обратными связями. Это схема планирования с переключением процессов, которая особенно эффективна для систем, где выполняются смеси разнородных заданий. Новые процессы поступают в сеть очередей с очень высоким начальным приоритетом и быстро обслуживаются, если они являются либо интерактивными, либо лимитируемыми вводом-выводом. Процессы, лимитируемые ЦП, полностью используют выделенный им квант времени, а затем переходят в конец очереди следующего, более низкого приоритетного уровня. Чем дольше данный процесс занимает ЦП, тем ниже становится его приоритет, пока процесс не опускается в очередь самого низкого приоритета, которая реализует принцип циклического обслуживания и в которой он циркулирует до тех пор, пока не завершится. Как правило, размер кванта времени, предоставляемого процессу, увеличивается по мере перехода процесса в каждую следующую очередь.
Сеть многоуровневых очередей с обратными связями — это пример адаптивного механизма планирования, который реагирует на изменение поведения контролируемой им системы.
СПИСОК ЛИТЕРАТУРЫ
1. Brinch Hansen P., "Short-Term Scheduling in Multiprogramming Systems", Third ACM Symposium on Operating Systems Principles, Stanford University, October 1971, pp. 103—105.
2. Brinch Hansen P., Operating System Principles, Englewood Cliffs, N. J.: Prentice-Hall, 1973.
3. Wulf W A., Cohen E., Corwin W., Jones A. et al., "HYDRA: The Kernel of a Multiprocessor Operating System", CACM, Vol. 17, No. 6, 1974, pp. 337—345.
4. Abell U. A., Rosen S., Wagner R. E., "Scheduling in a General-Purpose Operating System", Proc. AFIPS, FJCC, Vol. 37, 1970, pp. 89—96.
5. Babad J. M., "A Generalized Multi-Entrance Time-Sharing Priority Queue", JACM, Vol. 22, No. 2, April 1976, pp. 231—247.

1
2