В. Столлингс - Операционные системы (1114679), страница 93
Текст из файла (страница 93)
Имеются следующие группы приоритетов 1приведены в порядке снижения приоритетов): управление блочными устройствами ввода-вывода; е управление файлами; управление символьными устройствами ввода-вывода; е пользовательские процессы. Глава 9. Планирование в системах с одним процессором гга ггггалгеаеггг выпоянягощггася ггроцесс Часть 4. Плаииро Такая иерархия должна обеспечить наиболее зФФективное использованиег"." * раиств вво ода-вывода. В группе пользовательских процессов использование ие ии исполнения приводит к применению штраФных санкций к процессам, ентираван анным на вычисления что также должно способствовать повышению > зективност ности системы.
В сочетании с круговой схемой с вытеснением данная атегия неплоха удовлетворяет требованиям к системе общего назначения с делением времени. Пример работы планировщика приведен в табл. 9.3. Процессы А, В и С соз зтся одновременно с одним и тем же базовым приорптетам 60 (мы игнориру наличие значения параметра п1се).
Таймер прерывает выполнение процесса раз в секунду и увеличивает значение счетчика текущего процесса. В примере .дполагается, что ни один процесс не блокируется сам по себе и нет никаких л л тих процессов, готовых к выполнению. Сравните эту таблицу с таал. 9.
г. 4. РЕЗН)МЕ, КЛНУЧЕВЫЕ ТЕРМИНЫ:-- И КОНТРОЛЬНЫЕ ВОПРОСЫ Операционная система должна принимать во время выполнения процессов ',.;:»-. г типа решений, связанных с планированием. Долгосрочное планирование онгеляет, когда новый процесс должен поступить в систему. Среднесрочное пларование является частью свопинга и определяет, когда программа должна ть полностью или частично загружена в основную память, с тем чтобы она:,"' гла выполняться. Краткосрочное планирование определяет, какой из готовых ыпалнению процессов будет выполняться процессором следующим. При разработке краткосрочного планировщика может использоваться ряд,"-' ~личных критериев.
В соответствии с некоторыми из них поведение системы :сматривается с точки зрения пользователя, другие же ориентированы на обю эффективность системы, что отвечает нуждам всех пользователей. Некото-: е из критериев можно легко выразить количественно, другие же по св по своей -:: ироде в большей степени качественные. С точки зрения пользователя на наиболее иным критерием является время отклика, в то время как с позиции си и ии системЫ' зее важна степень использования процессора. Имеется ряд алгоритмов краткосрочного планирования, осуществляющих.': бар среди готовых к выполнению процессов.
Первым поступил — первым обслужен. Выбирается процесс, ожид ш аюший обслуживания дольше других. Круговое планирование. Использует кванты времени для аграничени ре".;: ения вре мени непрерывного выполнения процесса, циклически обслуживая ая имею-' '-" щиеся процессы. Выбор самого короткого процесса.
Выбирается процесс с наименыпи н шим ожи.:". даемым временем работы; вытеснение процессов не применяется. Наименьшее остающееся время, Выбирается процесс с наименьш меньшим ожи-. = даемым временем оставшейся работы. Процесс может быть вытеснен друг~~~~""" готовым к выполнению процессом. Таблица 9 8 Пример традиционного планирования процессов в ЮХ1Х е Наивысшее отношение отклика. Принимаемое решение опирается на оценку нормализованного времени оборота. ° Снижение приоритета. Определяет множество очередей и распределяет в них процессы, основываясь на истории выполнения и других критериях. Выбор алгоритма планирования зависит от ожидаемой производительности и сложности реализации.
Глава 9. Планирование в системах с одним процессором р=Аг р'=р 1- — О<ф<а Р Ожидающие задания Обсяужиааеиие аадани4 гие возможные поступления заданий. Указание: сначала примите решение.б)р, том, какое задание будет выполняться последним. 11 Рис. 9.16. Отноигение отклика как функция времени. Докажите, что минимаксный алгоритм из предыдущей задачи минимизируеГ:"- максимальное время отношения для данного пакета заданий. Указание: рас-,,' смотрите задание с максимальным отношением отклика, до которого выпогь':,:, няются все остальные задания. Рассмотрите то же подмножество заданий.'.:, спланированных в другом порядке, и определите отношение отклика задания," выполняющегося последним. Обратите внимание — теперь наряду с заданиями~; из пакета в системе могут выполняться и другие задания.
Определим время пребывания Т„как среднее общее время, затрачиваемое про.,',. цессом на ожидание и обслуживание. Покажите, что в случае обслуживания'.' "первым вошел — первым вышел"' со средним временем обслуживания Т, Мастепенью загруженности процессора р справедливо соотношение Т, = Т,~~1 - р))','-, Процессор переключается между готовыми к выполнению процессами с бесконМ,'), ' ~'Уф ' ' ной скоростью без накладных расходов (зто идеализированная модель круговог~:,, планирования с использованием квантов времени, которые гораздо меныпе вреМз.;.'." ни обслуживания).
Покажите, что при распределенных в соответствии с законоМ-, Пуассона процессах с экспоненциальным временем обслуживания, входящих иВ-.:: бесконечного источника„среднее время отклика Л процесса со временем обслужа~-;- вания х задается соотношением К = хл! — р) . указание: обратитесь к основ уравнениям теории очередей, которые можно найти по адресЪ",. йс р: у~к1." 11атяса11)ги)5. сов~я~ипеп~яиррог~. ьст~)..
Затем примите количе).. ство ожидающих процессов в системе перед поступлением данного равным и. О. Большинство круговых планировщиков используют кванты времени фиксир~"'$" ванного размера. Приведите аргументы в пользу квантов малого размера. а:„':" затем — в пользу большого Размера квантов времени. Сравните типы систем,. заданий, для которых применимы те или иные аргументы. Ксть ли среди на9~-:"' такие, для которых применимы и те, и другие аргументы? 9.11. В системе с очередями новое задание должно ожидать своей очереди на об а о служивание. В то время, когда задание находится в состоянии ожидания ия, его приоритет линейно возрастает со временем со скоростью а от нулевого значе ния.
Задание находится в состоянии ожидания до тех пор, пока его приоритег не сравняется с приоритетом обслуживаемых заданий, после чего оно будет обслуживаться наравне с другими процессами с использованием кругового планирования (при атом его приоритет возрастает со скоростью р, меньшей, чем а). Этот алгоритм известен как круговой эгоистичный, поскольку задания пытаются (понапрасну) монополизировать процессор путем постоянного повышения приоритета, Воспользуйтесь рис.
9.17, чтобы показать, что среднее вре мя отклика Н„задания со временем обслуживания х задается формулой х-г )(', = — + 1-р 1-р" в предположении, что время поступления и обслуживания распределено экс- поненциально, со средними значениями 1/Л и з соответственно. Указание: рассмотрите систему в целом и две подсистемы в отдельности, Рис. 9.17. Эгоистичное круговое иланировакие Интерактивная система с использованием кругового планирования и свопинга пытается обеспечить гарантированный отклик на тривиальные запросы следующим образом. После завершения кругового цикла по всем процессам в состоянии готовности система определяет квант времени для каждого готового процесса на следующий цикл посредством деления максимального време- Глава 9.
Планированне в системах с одним процессором ни отклика на количество процессов, требующих обслуживания. Насколько.,1 обоснованна такая стратегия? Какой тип процессов в целом получает преимущества при многоуровневом- . возврате ор — иентированные на вычисления или ориентированные на опера. пнн ввода-вывода? Вкратце поясните свой ответ. Прп использовании стратегии планирования на основе приоритетов процессов ",.-:"- глэнпровщик передает управление определенному процессу, если только а состоянии ожидания не находится процесс с более высоким приоритетом.
Предположим„ „что при принятии решения о планировании не используетсй ов никакая иная информация. Примем также, что приоритеты процессов опре делаются при их создании и в дальнейшем не изменяются. Почему в такойк системе опасно использование алгоритма Деккера для обеспечения взаимонс.,: ключении (см. раздел ел 5.2)? Поясните это, описав, какая нежелательная си- 'Ф туапия может сложиться, и как это может произойти.
Пять пакетных заданий, от А до Е, поступают в вычислительный центр одновре. р'- И мое время работы — 15, 9, 3, 6 и 12 минут соответственно. Ий ."- нноб 3 7 9';а' приоритеты, определенные при передаче заданий, равны соответственно и 4, причем меньшее значение означает более высокий приоритет. Для каждогО 4 пе численных ниже алгоритмов определите время оборота каждого процесса;. и среднее время оборота всех процессов. Накладные расходы, связанны ерв-,- есп ключением процессов, не учитываются. Поясните, как вы р д мэ вы и ишли к данному ', ответу.
В трех последних случаях предполагается, что в определенный момент,',. времени работает только один процесс, вытеснения не происходит и все заданий. ориентированы на вычисления. а. Круговое планирование с размером кванта, равным 1 мин. б. Планирование с учетом приоритетов. в. ГСГБ при запуске процессов в следующем порядке: 15, 9, 3, 5 9,3 би12. г. Первым выполняется самое короткое задание. ,.я( РИЛОЖБНИЕ А.'::: ВРЕМЯ:-:ОХ~~ Время отклика — это время, затрачиваемое системой н ре ц а ак ию на дан4.' 1 ввод.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
