В. Столлингс - Операционные системы (1114679), страница 92
Текст из файла (страница 92)
Это позволяет рассматривать влияние различных р ст атегий планированМ; ' процесс как Функцию от длины процесса. а на ие. 9 лб',, На рис. 9.14 показано нормализованное время оборота, а на рис. 9. еднее время ожидания. Взглянув на время оборота, мы можем увидеть, оизводительность ГСГЯ получается весьма непривлекател ьной — примерЕвР;,. ети процессов время оборота более чем в 10 раз превы е р евышает в емя обслуга„, ' я„к тому же это самые короткие процессы. С другой сторо, ре сто ны, время о :я при этом одинаково для всех процессов, что обуслов словлено независиМ ратегии от времени обслуживания.
При применении стратегии ВВ используется квант, р й т авный одной емени ~см. рис. 9.14 и 9.15). За исключением очень коротких процессов „, -: лжительность которых менее одного кванта при этой стр й с атегии нормализо емя оборота равняется примерно 5 квантам для всех проц х п цессов, тем самыми .,... чивается беспристрастность.
Производительность при и и использовании стра.... 'Х выше, если не принимать во внимание короткие роц ие и ессы. Стратегия,, ... ~едставляющая собой версию ЯРЫ с вытеснением, пре д восхо ит ЯРЫ по .Р' .в опо .тельности, за исключением 7% самых длинных процессов. Р' . идн там исследований, среди невытесняющих стратеги й плани ванин ГСГЯ от. ро ,з-" предпочтение длинным процессам, а ЯРЫ вЂ” коротким. Стра тывэлась как компромиссное решение, и именно такой, по результатам исследова.
ния, она и является. И, наконец, как и ожидалось, стратегия со снижением при орнтета с одинаковыми квантами времени для всех очередей неплохо работает с короткими процессами. 10 20 ЗО 40 50 60 70 ВО 90 Проиенуили по времени обслуживания Рис. 9.Е4. Результаты имитационного моделирования для нормализованного времени оборота Все рассмотренные алгоритмы планирования рассматривают множество готовых к выполнению процессов как единый пул, из которого выбирается очередной процесс для выполнения. Этот пул может быть разделен по степени приоритета процессов, но в противном случае он остается гомогенным. Однако в многопользовательских системах при организации приложений или заданий отдельных пользователей как множества процессов (илн потоков) у них имеется структура, не распознаваемая традиционными планировщиками.
С точки зрения пользователя, важно не то, как будет выполняться отдельный процесс. а то, как будет выполняться множество процессов, составляющих единое приложение. Таким образом, было бы неплохо, если бы планирование осуществлялось с учетом наличия таких множеств процессов. данный подход в целом известен как справедливое (ХаЕг-эЬаге) планирование. Эта же концепция может быть распространена на группы пользователей, даже если каждый из пользователей представлен единственным процессом. Например, в системе с разделением времени мы можем рассматривать всех пользователей данного отдела как членов Глава 9.
Планирование в системах с одним процессором Где а'и,. (') бп'и, (') Р,(1) Часть 4. Плани группы. Планировщик принимает решения с учетом необходимости -тавить каждой группе пользователей по возможности одинаковый сервис. фа„~ м образом, если в системе находится много пользователей из одного отдела, тв-, '. менение времени отклика должно в первую очередь коснуться именно польщ„ гелей этого отдела, не затрагивая прочих пользователей. 30 40 50 60 70 80 90 !00 Процентили но времени обслужиеенин Рис.
9.Ж Результаты имитаиионноео моделирование для времени ожидания Термин справедливое планирование указывает на философию, лежащую%::.., :нове такого планирования. Каждому пользователю назначен определен .с, который определяет долю использования системных ресурсов данным и евателем. В частности, каждый пользователь использует процессоР. Д ыма работает более или менее линейно, так что если вес пользователя А ®.4 аза превышает вес пользователя В, то в течение достаточно длительного П)~' ежутка времени пользователь А должен выполнить в два раза болыпую Ра~~.;е..' ем пользователь В. Цель справедливого планирования состоит в отслеживзн~~(~' спользования ресурсов и предоставлении меньшего количества ресурсов т949~'" ользователю, который уже получил лишнее, и большего количества — твазФ- ья доля оказалась меньше справедливой. Выл предложен ряд алгоритмов справедливого планирования (НЕЫ~~-' 'АУ88, ЧУООП863.
В этом разделе мы рассмотрим описанную в (НЕХК841 ланирования, реализованную в ряде систем ШЧ1Х. Эта схема известна-: праведливый планировщик (Ха(г-зЬаге естес(ц1ег — ГББ). г88 при принятИИ"' . зения рассматривает историю выполнения связанной группы процессов в ~ндивидуальными историями выполнения каждого процесса.
Система разА,,:,, ~ользовательское сообщество на множество групп со справедливым плани,, кием и распределяет процессорное время между ними. Так если у , если у нас имеется четыре группы, каждая из них получит по 25% процессорного в о времени. В результате каждая группа обеспечивается виртуальной системой раб , Ра отающей, со ответственно, медленнее, чем система в целом. Планирование осуществляется исходя из приоритетов с учетом м приоритета процесса, недавнего использования им процессора и недавнего использ ользования процессора группой, к которой он принадлежит. Чем болыле числово словое значение итета, тем ниже сам приоритет.
Для процесса ) из ру применимы ледующие формулы: ме руженности процессора процессом у на интервале 1е — мера загруженности процессора группой 1е на интервале 1; — приоритет процесса ) в начале интервала 1 (меньшее значение соответствует большему приоритету); — базовый приоритет процесса ); И' — вес, назначенный группе й (О< И' <1 и ~~) И', =-1).
Каждому процессу назначается базовый приоритет. Приоритет процесса снижается по мере использования им процессора, так же как и по мере использования процессора группой в целом. В случае использования процессора группой среднее значение нормализуется делением на вес группы. Чем больший вес назначен группе, тем меньше использование ею процессора влияет на приоритет.
В табл. 9.7 приведен пример, в котором процесс А находится в одной группе, а процессы В и С вЂ” в другой; вес каждой группы равен 0.5. Предположим. что все процессы ориентированы на вычисления и всегда готовы к выполнению. Вазовы ~ вый приоритет всех процессов — 60.
Степень использования процессора опРеделяется следующим образом: процессор прерывается 60 раз в секунду: при каждом прерывании увеличивается значение счетчика использования процессора тек ущего процесса„так же как и соответствующего счетчика группы. Один раз в секунду происходит перерасчет приоритетов. В приведенной схеме первым запускается процесс А.
Позже его вытесняет другой. П р.' й. Процессы В и С теперь имеют более высокий по сравнению с А приоритет, и на вып , и на выполнение передается процесс В. По окончании второй единицы времени наи наивысший приоритет снова имеет процесс А, который и передается на выполнение. лнение. После этого ситуация повторяется с тем отличием, что теперь наивысший и ий приоритет имеет процесс С.
Очередность выполнения процессов такова: А. В, А С ° ° А, С. А, В, А, С, .... В результате 50% времени процессор занят выполнением процесса А, и 50% — выполнением процессов В и С. г лана 9. Планирование н системах с одним процессором ° Ю о -» в ° ° »~ Ю Г- С и,.~)= а и,( -1) Р (~)=Вальс + ' +п~сс »»» ЯР $»Х) Г » «Г- ».~ О»»'4 Ф Ф Ю »»»»Р Г ° ° »О Г" 4 е программа свопинга; »» х Ръ Ф» й~ й О Ф» х х Ф, х х х Ж о Ф» х СФ х х о х й~ »» х» й х х» Ф й о х, йГ о х 9 3. ТРАДИЦИОННОЕ ПЛАВНРОВАНж'-Ц~~Щ В этом разделе мы рассмотрим традиционное планирование БЖ1Х, исполь зуемое как в ЗЪ'ЯЗ, так и в 4.3 ВЯО 11гПХ.
Эти системы в первую очередь пред назначены для работы в интерактивной среде с разделением времени. Алгоритм планирования разработан таким образом, чтобы обеспечить приемлемое время отклика для интерактивных пользователей, в то же время гарантируя отсутствие голодания низкоприоритетных заданий. Хотя описываемый алгоритм и был заменен в более современных версиях БХ1Х, его изучение как представителя практически используемых алгоритмов с разделением времени не лишено основания. Схема планирования БВЧ4 соответствует требованиям реального времени, но этот вопрос мы обсудим в главе 10, "Многопроцессорное планирование и пла нирование реального времени".
Традиционный планировщик БМ1Х использует многоуровневый возврат с применением кругового планирования в пределах очередей каждого приоритета, а также односекундное вытеснение. Таким образом, если текущий процесс не блокируется или не завершается в пределах одной секунды, он вытесняется. Приоритет основан на типе процесса и истории выполнения. Применяются следующие формулы: СР~/,(~) — мера использования процессора процессом у на протяжении интервала 1; Р, (~) — приоритет процесса у в начале интервала 1 (меньшее значение соответствует большему приоритету); Ваас,.
— базовый приоритет процесса и пке, — указываемый пользователем коэФФициент. Приоритет каждого процесса пересчитывается один раз в секунду, в момент принятия решения о том, какой процесс будет выполняться следующим. Назначение базового приоритета состоит в разделении процессов на фиксированные ~руппы уровней приоритетов. Значения компонентов СРУ и п1се ограничены требованием того, чтобы процесс не мог выйти из назначенной ему на основании базового приоритета группы. Эти группы используются для оптимизации досту" па к блочным устройствам 1например, к диску) и обеспечения быстрого отклика операционной системы на системные вызовы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
