Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10 | Следующая страница реферата

На рисунке приведены диаграммы Ганга очереди готовых процессов вариант 1:
|П1 |П2 |П3 |WT=17 мс |
|WT1=0 мс |WT2=24 мс |WT3=27 мс | |

вариант 2:
|П2 |П3 |П1 |WT=3 мс |
|WT2=0 мс |WT3=3 мс |WT1=6 мс | |

Стратегии FCFS присущ так называемый “эффект конвоя”. В том случае, когда в компьютере имеется один большой процесс и несколько малых, то все процессы собираются в начале очереди готовых процессов, а затем в очереди к оборудованию. Таким образом, “эффект конвоя” приводит к снижению загруженности как процессора, так и периферийного оборудования.

2.2.2. Стратегия - наиболее короткая работа! SJF.

SJF — SHORTEST JOB FIRST. ОДНИМ ИЗ МЕТОДОВ БОРЬБЫ С “ЭФФЕКТОМ КОНВОя” яВЛяЕТСя СТРАТЕГИя, ПОЗВОЛяЮЩАя ПРОЦЕССУ ИЗ ОчЕРЕДИ ВЫПОЛНяТЬСя ПЕРВЫМ.
Пример № 2

Пусть четыре процесса одновременно попадают в очередь готовых процессов и имеют следующие значения времени последующего обслуживания
П1(6 мс)
П2(8 мс)
П3(7 мс)
П4(3 мс)
|П4 |П1 |П3 |П2 |WT=7 мс |
|WT4=0 мс |WT1=3 мс |WT3=9 мс |WT2=16 мс | |

На рисунке приведена диаграмма Ганга, построенная в соответствии со стратегией SJF.

Легко посчитать, что при использовании FCFS - стратегии среднее время ожидания для тех же процессов равно 10.25 мс, таким образом стратегия SJF снижает время ожидания очереди. Наибольшая трудность в практической реализации SJF заключается в невозможности заранее определить величину времени последующего обслуживания.

Поэтому стратегия SJF часто применяется в долгосрочных планировщиках, обслуживающих пакетный режим. В этом случае вместо величины времени последующего обслуживания используется допустимое максимальное время выполнения задания, которое программист должен специфицировать перед отправкой задания в пакет.

2.2.3. Приоритетное планирование.

ОПИСАННЫЕ РАНЕЕ СТРАТЕГИИ МОГУТ РАССМАТРИВАТЬСя КАК чАСТНЫЕ СЛУчАИ
СТРАТЕГИИ ПРИОРИТЕТНОГО ПЛАНИРОВАНИя. ЭТА СТРАТЕГИя ПРЕДПОЛАГАЕТ, чТО
КАЖДОМУ ПРОЦЕССУ ПРИПИСЫВАЕТСя ПРИОРИТЕТ, ОПРЕДЕЛяЮЩИЙ ОчЕРЕДНОСТЬ
ПРЕДОСТАВЛЕНИя ЕМУ CPU. НАПРИМЕР, СТРАТЕГИя FCFS ПРЕДПОЛАГАЕТ, чТО ВСЕ
ПРОЦЕССЫ ПРЕДПОЛАГАЕТ, чТО ВСЕ ПРОЦЕССЫ ИМЕЮТ ОДИНАКОВЫЕ ПРИОРИТЕТЫ, А
СТРАТЕГИя SJF ПРЕДПОЛАГАЕТ, чТО ПРИОРИТЕТ ЕСТЬ ВЕЛИчИНА, ОБРАТНАя ВРЕМЕНИ
ПОСЛЕДУЮЩЕГО ОБСЛУЖИВАНИя.

Приоритет — это целое положительное число, находящееся в некотором диапазоне, например от 0 до 7, от 0 до 4095. Будем считать, что чем меньше значение числа, тем выше приоритет процесса.
|Пример №3. |приоритет |
|П1(10 мс) |3 |
|П2(1 мс) |1 |
|П3(2 мс) |3 |
|П4(1 мс) |4 |
|П5(5 мс) |2 |

На рисунке приведена диаграмма Ганга, располагающая процессы в очереди в соответствии со стратегией приоритетного планирования
|П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).

ЭТА СТРАТЕГИя РАЗРАБОТАНА ДЛя СИТУАЦИИ, КОГДА ПРОЦЕССЫ МОГУТ БЫТЬ
ЛЕГКО КЛАССИФИЦИРОВАНЫ НА НЕСКОЛЬКО ГРУПП, НАПРИМЕР, чАСТО ПРОЦЕССЫ
РАЗДЕЛяЮТ НА ДВЕ ГРУППЫ: ИНТЕРАКТИВНЫЕ (ПРОЦЕССЫ ПЕРЕДНЕГО ПЛАНА) И
ПАКЕТНЫЕ (ФОНОВЫЕ).

Интерактивные и пакетные процессы имеют различные требования к краткосрочному планировщику, например по отношению ко времени отклика.

Рекомендуем скачать другие рефераты по теме: бизнес реферат, нормы реферата.



Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10 | Следующая страница реферата

Поделитесь этой записью или добавьте в закладки