В. Столлингс - Операционные системы (1114679), страница 90
Текст из файла (страница 90)
Пака что все, как обычно. Новым ок азывается наличие вспомогательной очереди, в котоРую переносятся п о есс р ц ссы после их разблокирования по завершении операций ввода-нывода. П и вы д . Ри выборе процесса для выполнения преимущество отдается процессам из всп з вспомогательной очереди. Изучение производительности такай схемы показынает что ход лучше т, что с точки зрения беспристрастности данный подше простого кругового планирования. сзьтб ьтбор самого короткого процесса и, у снижению перекоса в пользу длинных процессов — исЕще олин путь к сни ен ол" зонание стратегии выбо одьз р т выбора самого короткого процесса (в!тогсевс Ргосеав ехт — есняющая стратегия, при которой для выполнения выехт — ЯР!ч).
Эта невытесняю Рвется процесс с наиме наименьшим ожидаемым временем исполнения. На рис. 9.5 и в табл. абл. 9.5 приведены результаты применения данной ется го атегии к нашем п им у римеру. Обратите внимание, что процесс Е обслуживание, с" гораздо раньше чем в м в случае применения РСРЯ-стратегии.
В отношении мени отклика об ~ая и и, я производительность системы также возрастает, на Часть 4. Плани .елава 9. гт --"анирование в системах с одним процес Где Очередь готовьа процессов Процессор л — 1 5.1'= — ?. + 5 л я 5„„= аТ„+ (1 — а) 5„, (9.3) Ожидание ввода-вывода 2 Ожидание ввода-вывода и ю 5,,= — „~,Т,, и ып Часть 4. Плани и этом увеличивается разброс его величины, в особенности для длинн"'-' оцессов (и, соответственно, снижается предсказуемость). Тайи апач Завершение ввода-вывода и Очередь ввода-вывода и Рис.
0.7. Диагро.мма работы виртуального кругового лланироваиия Основная трудность в применении стратегии ЯРЫ состоит в том, что, . е осуществления необходима по меньшей мере оценка времени выполйе ребующегося каждому процессу. При выполнении пакетных заданий 'ВП) юнадобиться оценка этого значения программистом и предоставлен вление,". перационной системе. Если оценка программиста существенно ниже $М„ юго времени выполнения, система может прекратить выполнение зада з ани |ромышленных системах часто выполняются одни и те же задания, а ия так-,, аожно собрать достаточно точную статистику.
В случае выполнения.: вактивных процессов операционная система может поддерживать в ивать во в выполнения средний "разрыв"' для каждого процесса. Простейшее в шее вы аие выглядит следующим образом: , — время работы процессора для 1-го экзе пляр ого процесса (общ ~ремя Работы для пакетного задания, . я ра оте); б ); ва при интерактивнои 5 — предсказанное значение для 1-го экземпляра 5, — предсказанное значение для первого экземпляра (не вычисляется). Для того чтобы избежать повторного вычисления всей сум су мы* уравнение (9.1) можно записать следующим образом: одинаковый вес, хотя обычно следует дать больший ольши вес экземплярам, выполнявшимся последними, так как они в большей ше степени отражают будущее поведение процесса.
Обычная технология предск редсказания удущего значеб ния на основе значений прошедших серий представляет собой взвешенное усреднение где а — постоянный весовой множитель (0<а <1), определяющий относительный вес последнего и предыдущих наблюдений (сравните с (9.2)). При использовании по- стоянного значения а, не зависящего от количества б й, . личества на людений, мы получаем си- туапшо, когда рассматриваются все прошлые значени прич . я, причем чем значение более давнее, тем меньше его вес. Чтобы было понятнее, распишем (9.3) как 5„„=аТ. +(1 — а)аТ„, +„.+(1 — а) аТ, +...+(1-а) 5,. (9.4) Поскольк и и 1- у а, -а меньше единицы, каждый последующий множитель в (9.4) меньше предыдущ .
Например, при а = О.З уравнение (9.4) залисывается как его. 5„„= О.ЗТ„+ 0.16Т„, + 0.032Т„, + 0.0064Т, +..., т.е чем старее наблю ени д ние, тем меньший вклад оно вносит в вычисляемое сред- нее значение. Значение коэффи и ФФ ц ента как Функции от положения члена в сумме по- казано на рис. 9.8. Чем б больше значение а, тем больший вес имеют послед- ние наблюдения. П и а = р =О.З в вычислении среднего значения, по сути, участвуют только т и-ч р - етыре последних наблюдения„в то время как при а =0.2 близ заметный вклад вносят в д ят восьмое и более поздние наблюдения. Значения а, пенна лизино к 1, позв л т нашему методу быстро реагировать.на любые изме- с е ння, но при этом вел Р у личивается и реакция на случайные отклонения от Реднего значения п и на ениям вычисляемого значения. : лава 9 тт ° ='анирование в системах с одним процессором 0.7 $6 Ю О.б 0,4 О.З 0.2 0,0 4 5 Е Возраст наблюдения Время а) Возрастающая функция Часть 4.
Плани Рис. 9.8. Весовые ноэффиииентны при разных знаненинх а На рис. 9.9 приведено сравнение простого и взвешенного усреднения 1вух разных значений а. На рис. 9.9,а значения а начинаются с 1 и постеи вырастают до 10, после чего продолжают удерживаться на этом уровне .. >ис. 9.9,6 наблюдаемые значения уменьшаются от 20 до 10.
В обоих случаях'. тачинаем с оценки 5, = О. Обратите внимание на то, насколько быстрее ре ' ;т на изменение наблюдаемых значений взвешенное среднее по сравне збычным средним, и чем больше значение а, тем выше скорость реакции. Основной риск при использовании стратегии ЯРЫ заключается в возмо голодании длинных процессов при стабильной работе коротких процессов. гого, хотя ЗРХ снижает перекос в пользу длинных процессов, его примен, нежелательно в системах с разделением времени или системах Р истемах об аботки . закций из-за отсутствия вытеснения. Возвращаясь к анализу наихудшего для метода ГСГЯ, мы увидим, что процессы ЪЧ, Х, У и Е будут выполня том же порядке, причем обслуживание процесса У имеет знач ачительно ху параметры,чем у других процессов.
0 1 2 3 4 5 б 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Время б) Убивающая функция рис. р,д тг снользование взвешенного усреднения ,..22ава 9. р.—, 9. хт танирование в системах с одним процессором Наименьшее остающееся время Стратегия наименьшего остающегося времени (зЬоггеа1 гегаа(п1пд $1п1~. БВТ) представляет собой вытесняющую версию стратегии БРИ. В этом планировщик выбирает процесс с наименьшим ожидаемым временем до око ння процесса.
При присоединении нового процесса к очереди готовых к исп"':.'", нению процессов может оказаться, что его оставшееся время в действительваа меньше, чем оставшееся время выполняемого в настоящий момент процес~~~'... Планировщик, соответственно, может применить вытеснение при готовности н(~;". вого процесса. Как и при использовании стратегии БРХ, планировщик для ко~'' Ректной работы Функции выбора должен оценивать время выполнения проц в этом случае также имеется риск голодания длинных процессов. ::., з В случае использования стратегии ЯВТ нет таких больших перекосов.
пользу длинных процессов, как при использовании стратегии ГСЕЯ; в отли ще'' стратегии ВК, здесь не генерируются дополнительные прерывания, что сниж" накладные расходы, Тем не менее в этом случае происходит увеличение н ' ных расходов из-за необходимости фиксировать и записывать время выпол процессов. В связи с тем что короткие задания немедленно получают преи ство перед выполняющимися длинными заданиями, стратегия БИТ сущес выигрывает у стратегии ЯРК во времени оборота. Обратите внимание, что в нашем примере в табл. 9.5 три наиболее кра процесса обслуживаются немедленно, что приводит к нормализованному врем' оборота для каждого из них, равному 1.0, Наивысшее отношение отклика В табл.
9.5 мы использовали как показатель нормализованное время об та, представляющее собой отношение времени оборота к действительному вре. ни обслуживания. Для каждого отдельного процесса этот показатель жела минимизировать, так же, как и среднее значение по всем процессам. Вообще.;.. воря, мы не можем знать время обслуживания заранее, но можем оценить'' либо на основе предыдущих выполнений, либо на основе информации, вво пользователем или задаваемой при настройке. Рассмотрим соотношение Й вЂ” отношение отклика; ю — время, затраченное процессом на ожидание; а — ожидаемое время обслуживания.
Если процесс будет немедленно диспетчеризован, его значение В будет но нормализованному времени оборота. Заметим, что минимальное значе (равное 1.0) осуществляется при входе процесса в систему. Таким образом, правило стратегии планирования наивысшего отнош отклика (111дйез1 геаропае гаМо пех( — ЯВКА) можно сформулировать так:. завершении или блокировании текущего процесса для выполнения из оче готовых процессов выбирается тот, который имеет наибольшее значение В.; кой подход довольно привлекателен, поскольку учитывает возраст процесса роткие процессы получают преимущество по отношению к продолжительны силу меньшего знаменателя, увеличиваю е щего отношение), однако и вели возраста процесса приводит к тому же у же результату, так что в конечном длинные процессы смогут конкурирова и овать с короткими.
ечном счете Как и в случае использования стратегий БВТ ЯРМ тегии требуется оценка времени обслуж и, в описанной ст служивания для оп еделения м стра- ного значения В. служ д ия максималь- Снижение приоритета Если у нас нет праце сов, то мы не можем использовать с. никаких указании об относительной продолжительнос ти ть ни однУ из стРатегий — ЯРХ, ЯНТ и НВЯХ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
