На рисунке приведена диаграмма Ганга, располагающая процессы в очереди в соответствии со стратегией приоритетного планирования |П2 |П5 |П1 |П3 |П4 | | |WT2=0 мс |WT5=1 мс |WT1=6 мс |WT3=16 мс |WT4=18 мс | |
Приоритеты определяются исходя из совокупности внутренних и внешних по отношению к операционной системе факторов. Внутренние факторы: 1. требования к памяти 1. количество открытых файлов 1. отношение среднего времени ввода - вывода к среднему времени CPU и так далее Внешние факторы: 1. важность процесса 1. тип и величина файлов, используемых для оплаты 1. отделение, выполняющее работы и так далее
Внутренние факторы могут использоваться для автоматического назначения приоритетов самой операционной системой, а внешние для принудительного, с помощью оператора.
Главный недостаток приоритетного планирования заключается в возможности блокирования на неопределенно долгое время низкоприоритетных процессов.
Известен случай, когда в 1973 году в Массачусетском технологическом институте MIT при остановке компьютера IBM 7094 в очереди готовых процессов были обнаружены процессы, представленные в 1967 и все еще не выполненные.
Для устранения отмеченного недостатка используются следующие методы: процессы, время ожидания которых превышает фиксированную величину, например 15 минут, автоматически получают единичное приращение приоритета.
2.2.4. “Карусельная” стратегия планирования. RR-Round
Robin.
ROUND ROBIN СТРАТЕГИя ПРИМЕНяЕТСя В СИСТЕМАХ РАЗДЕЛЕНИя ВРЕМЕНИ. ОПРЕДЕЛяЕТСя НЕБОЛЬШОЙ ОТРЕЗОК ВРЕМЕНИ, НАЗВАННЫЙ КВАНТОМ ВРЕМЕНИ (10..100 МС). ОчЕРЕДЬ ГОТОВЫХ ПРОЦЕССОВ РАССМАТРИВАЕТСя КАК КОЛЬЦЕВАя. ПРОЦЕССЫ ЦИКЛИчЕСКИ ПЕРЕМЕЩАЮТСя ПО ОчЕРЕДИ, ПОЛУчАя CPU НА ВРЕМя, РАВНОЕ ОДНОМУ КВАНТУ. НОВЫЙ ПРОЦЕСС ДОБАВЛяЕТСя В ХВОСТ ОчЕРЕДИ. ЕСЛИ ПРОЦЕСС НЕ ЗАВЕРШИЛСя В ПРЕДЕЛАХ ВЫДЕЛЕННОГО ЕМУ КВАНТА ВРЕМЕНИ, ЕГО РАБОТА ПРИНУДИТЕЛЬНО ПРЕРЫВАЕТСя, И ОН ПЕРЕМЕЩАЕТСя В ХВОСТ ОчЕРЕДИ. Пример 4 П1(24 мс) П2(3 мс) П3(3 мс) q=4 мс. Диаграмма Ганга соответственно Round Robin стратегии для этого случая имеет вид: |П1 |П2 |П3 |П1 |П1 |П1 |П1 |П1 | |WT1=0 мс |7 |10 |14 |18 |22 |26 |30 |
Свойства Round Robin стратегии сильно зависят от величины временного кванта q. Чем больше временной квант, тем дольше Round Robin стратегия приближается к FCFS стратегии (для рассмотренного примера, если q>24 мс, то -> FCFS). При очень малых значениях временного кванта Round Robin стратегия называют разделением процессора — processor sharing. Теоретически это означает, что каждый из N процессов работает со своим собственным процессором, производительность процессора равна 1/N от производительности физического процессора.
2.2.5. ПЛАНИРОВАНИЕ с использованием многоуровневой очереди.(Multilevel queue scheduling).
ЭТА СТРАТЕГИя РАЗРАБОТАНА ДЛя СИТУАЦИИ, КОГДА ПРОЦЕССЫ МОГУТ БЫТЬ ЛЕГКО КЛАССИФИЦИРОВАНЫ НА НЕСКОЛЬКО ГРУПП, НАПРИМЕР, чАСТО ПРОЦЕССЫ РАЗДЕЛяЮТ НА ДВЕ ГРУППЫ: ИНТЕРАКТИВНЫЕ (ПРОЦЕССЫ ПЕРЕДНЕГО ПЛАНА) И ПАКЕТНЫЕ (ФОНОВЫЕ).
Интерактивные и пакетные процессы имеют различные требования к краткосрочному планировщику, например по отношению ко времени отклика.
Стратегия многоуровневой очереди разделяет очередь готовых процессов на несколько очередей, в каждой из которых находятся процессы с одинаковыми свойствами, и каждый из которых может планироваться индивидуальной стратегией, например Round Robin стратегия для интерактивных процессов и FCFS для пакетных процессов.
Взаимодействие очередей осуществляется по следующим правилам: ни один процесс с более низким приоритетом не может быть запущен, пока не выполнятся процессы во всех очередях с более высоким приоритетом.
Работа процесса из очереди с более низким приоритетом может быть приостановлена, если в одной из очередей с более высоким приоритетом появился процесс.
2.2.6. Программирование с использованием многоуровневой очереди с обратными связями (multilevel feedback queue sheduling).
ОБЫчНАя МНОГОУРОВНЕВАя ОчЕРЕДЬ НЕ ДОПУСКАЕТ ПЕРЕМЕЩЕНИя ПРОЦЕССОВ МЕЖДУ ОчЕРЕДяМИ. МНОГОУРОВНЕВАя ОчЕРЕДЬ С ОБРАТНЫМИ СВяЗяМИ ПРЕДПОЛАГАЕТ, чТО ПРОЦЕССЫ ПРИ ОПРЕДЕЛЕННЫХ УСЛОВИяХ МОГУТ ПЕРЕМЕЩАТЬСя МЕЖДУ ОчЕРЕДяМИ.
Процессы первоначально попадают в очередь 0, где каждому из них предоставляется квант времени, равный 8 мс. Те процессы, которые не успели выполниться в течение этого времени, перемещаются в очередь 1. Процессы из очереди 1 начинают обрабатываться только тогда, когда очередь 0 становиться пустой. Те процессы, которые не выполнились в очереди 1 (q=16 мс) перемещаются в очередь 2. Процессы из очереди 2 будут обрабатываться только в том случае, если становятся пустыми очереди 0 и 1.
Рассмотренная стратегия является наиболее универсальной и сочетает в себе свойства всех рассмотренных раньше стратегий.
1. FCFS 1. SJF 1. приоритетная 1. Round Robin 1. многоуровневая очередь
3. Управление невиртуальной памятью.
3.1. СВОППИНГ. (SWAPPING).
СВОППИНГОМ НАЗЫВАЕТСя МЕТОД УПРАВЛЕНИя ПАМяТЬЮ, ОСНОВАННЫЙ НА ТОМ, чТО ВСЕ ПРОЦЕССЫ, УчАСТВУЮЩИЕ В МУЛЬТИПРОГРАММНОЙ ОБРАБОТКЕ, ХРАНяТСя ВО ВНЕШНЕЙ ПАМяТИ.
Процесс, которому выделен CPU, временно перемещается в основную память (swap in/roll in).
В случае прерывания работы процесса он перемещается обратно во внешнюю память (swap out/roll out). Замечание: при своппинге из основной памяти во внешнюю (и обратно) перемещается вся программа, а не её отдельная часть.
Своппинг иногда используют при приоритетном планировании CPU. В этом случае с целью освобождения памяти для высокоприоритетных процессов, низкоприоритетные процессы перемещаются во внешнюю память.
Основное применение своппинг находит в системах разделения времени, где он используется одновременно с Round Robin стратегией планирования CPU.
В начале каждого временного кванта блок управления памятью выгружает из основной памяти процесс, работа которого была только что прервана, и загружает очередной выполненный процесс.
Метод своппинга влияет на величину временного кванта Round Robin стратегии. Пример. 1. пусть очередной загружаемый в память процесс имеет размер 100Кб. 1. диск позволяет читать данные со скоростью 1 Мб в секунду 1. следовательно, 100 Кб могут быть загружены за 100 мс. 1. будем считать, что для первоначального подвода головки чтения - записи потребуется 8 мс 1. таким образом, операция своппинг займет 108 мс, а общее время своппинга - 216 мс.
Для эффективной загруженности процессора время своппинга должно быть существенно меньше времени счета. Следовательно, для рассмотренного примера квант времени должен быть существенно больше, чем 216 мс. Ясно, что это число значительно увеличится, если перемещаемый процесс имеет размер, например, 1 Мб.
Недостаток “чистого” своппинга в больших потерях времени на загрузку или выгрузку процессов. Поэтому в современных операционных системах используется модифицированные варианты своппинга.
Так, например, во многих версиях операционной системы UNIX своппинг включается только в том случае, когда количество процессов в памяти становится слишком большим.
3.2. Смежное размещение процессов.
МЕТОДЫ РАЗМЕЩЕНИя ПРОЦЕССОВ В ОСНОВНОЙ ПАМяТИ ПО ОТНОШЕНИЮ К РАСПОЛОЖЕНИЮ УчАСТКОВ ПАМяТИ, ВЫДЕЛЕННЫХ ДЛя ОДНОЙ И ТОЙ ЖЕ ПРОГРАММЫ ДЕЛяТ НА ДВА КЛАССА. ПЕРВЫЙ — МЕТОД СМЕЖНОГО РАЗМЕЩЕНИя, А ВТОРОЙ — МЕТОД НЕСМЕЖНОГО РАЗМЕЩЕНИя.
Смежное размещение является простейшим и предполагает, что в памяти, начиная с некоторого начального адреса выделяется один непрерывный участок адресного пространства. при несмежном размещении программа разбивается на множество частей, которые располагаются в различных, необязательно смежных участках адресного пространства.
3.2.1. Однопрограммный режим.
РИСУНОК ИЛЛЮСТРИРУЕТ СМЕЖНОЕ РАЗМЕЩЕНИЕ (CONTIGUOUS ALLOCATION) ОДНОЙ ПРОГРАММЫ В ОСНОВНОЙ ПАМяТИ.
При смежном размещении размер загружаемой программы ограничивается размером накопителя. Для того чтобы при смежном размещении загружать программы, размеры которых превышают размеры накопителя, используют метод оверлейных сегментов (overlay segments).
В программе, имеющей древовидную структуру, модули второго уровня работают сугубо последовательно, поэтому в памяти может находиться только один из них.
Оверлейную структуру программы и последовательность загрузки оверлейных сегментов планирует сам программист.
В процессе выполнения программы все её адреса не должны быть меньше числа а. В противном случае возможна запись какого-либо результата работы программы (поверх операционной системы) и уничтожение некоторых её частей. Защиту операционной системы в случае смежного размещения при однопрограммном режиме можно осуществить с помощью регистра границы.
Во время работы прикладной программы все адреса, генерируемые CPU, сравниваются с содержимым регистра границы. Если генерируется адрес меньше числа а, работа программы прерывается.
3.2.2 Мультипрограммный режим с ФИКСИРОВАННЫМИ границами.
МУЛЬТИПРОГРАММИРОВАНИЕ С ФИКСИРОВАННЫМИ РАЗДЕЛАМИ (MULTIPROGRAMMING WITH A FIXED NUMBER OF TASKS) ПРЕДПОЛАГАЕТ РАЗДЕЛЕНИЕ АДРЕСНОГО ПРОСТРАНСТВА НА РяД РАЗДЕЛОВ ФИКСИРОВАННОГО РАЗДЕЛА. В КАЖДОМ РАЗДЕЛЕ РАЗМЕЩАЕТСя ОДИН ПРОЦЕСС.
Наиболее простой и наименее эффективный режим MFT соответствует случаю, когда трансляция программ осуществляется в абсолютных адресах для соответствующего раздела.
В этом случае, если соответствующий раздел занят, то процесс остается в очереди во внешней памяти даже в том случае, когда другие разделы свободны.
Уменьшить фрагментацию при мультипрограммировании с фиксированными разделами можно, если загрузочные модули получать в перемещаемых адресах. Такой модуль может быть загружен в любой свободный раздел после соответствующей настройки.
При мультипрограммировании с трансляцией в перемещаемых адресах имеются две причины фрагментации. Первая — размер загруженного процесса меньше размера, занимаемого разделом (внутренняя фрагментация), вторая — размер процесса в очереди больше размера свободного раздела, и этот раздел остается свободным (внешняя фрагментация).
Для защиты памяти при мультипрограммировании с фиксированным разделами необходимы два регистра. Первый — регистр верхней границы (наименьший адрес), второй — регистр нижней границы (наибольший адрес).
Страницы: 1, 2, 3, 4
