 |
RR- одноуровневое циклическое обслуживание.
|
|
|
|
0 
(1- )
Рисунок 13.2 –RR-одноуровневое циклическое обслуживание.
Поступающие заявки с интенсивностью заносятся в очередь «0». Каждой заявке для обслуживания выделяется квант процессорного времени длительности q. (При вероятности 1- заявка покидает систему), с вероятностью 
заявка возвращается на дообслуживание.
Если трудоемкость представляет n единиц времени, то на ее обслуживание требуются n квантов времени q.
(13.1)
Через время q недообслуженная заявка возвращает в хвост очереди «0». Это событие наступает с вероятностью , которая может быть оценена как:
. Пропускная способность системы определяется формулой, с учетом этого получаем:
(13.2)
Если n-чрезмерно велик, то возрастают потери на диспетчеризацию, связанные с прерываниями. При малом n – увеличивается монополизация ресурсов процессора трудоемкими задачами, что приводит к возрастанию очереди вновь поступающих запросов. Данный алгоритм в основном обеспечивает увеличение оперативности доступа к процессору вновь поступающих запросов, с малой трудоемкостью.
Основным преимуществом алгоритма RR является обеспечение привилегий менее трудоемких запросов, с проигрыванием для более трудоемких запросов.
Число заявок в системе складывается из трех компонентов 
.
Здесь 
- это число заявок поступивших в очередь за время обслуживания запроса в первом кванте.
- число заявок вернувшихся в очередь за получение допущенных квантов времени.
- среднее число заявок поступивших в очередь в течение времени ожидания.
Основные различия дисциплины RR и FIFO.
- Уменьшение при RR среднего времени пребывания менее трудоемких заявок по сравнению c FIFO.
- Появление дополнительных прерываний для обеспечения квантования.
|
|
|
С целью частичного сокращения потерь, возможна модификация RR, которая заключается в следующем:
1. Добавление кванта времени при каждом поступлении в очередь новой заявки.
2. Обслуживаемой заявке добавляется новый квант времени при пустой очереди.
Для данной модели справедливы характеристики
Среднее число заявок в буфере:
(13.3)
где коэффициент ρ определяется формулой (13.2)
Среднее время ожидания запроса
(13.4)
Среднее время пребывания запроса с n- квантами
(13.5)
Осн. лит.102[9-16],
Доп. лит.6[6-12].
Контрольные вопросы:
1. В чем заключается сущность приоритетных и бесприоритетных дисциплины диспетчеризации?
2. В чем состоит суть линейных и циклических дисциплины обслуживания?
3. На какую характеристику обслуживания влияет трудоемкость решения задачи?
4. Как влияет квантование времени обслуживания на характеристики решения задачи?
5. Из чего формируется очередь запросов при циклической диспетчеризации?
Лекция 14. Алгоритм многоуровневого циклического планирования
Без приоритетов FВ.
Очередь запросов разбивается на N уровней. Вновь поступившие запросы с интенсивностью λ записываются в очередь первого уровня Q1. Из этой очереди они получают первый квант времени. Если первого кванта оказалось недостаточно, то запрос на получение второго кванта записывается в очередь второго уровня Q2. Из этой очереди, получив второй квант времени и не обслужившись за него, запрос перемещается в очередь третьего уровня Q3 и т.д.
 |
l q 1-s
P2l2
P3l3 s
.
.
Pnln
Рисунок 14.1 – Модель многоуровневого циклического планирования
В очереди нижнего уровня N накапливаются запросы, для обслуживания которых потребуется N и более квантов времени.
Каждая из этих очередей обслуживается по алгоритму FIFO, а между уровнями устанавливает приоритет: высший приоритет – очередь первого уровня, низкий приоритет – очередь N-го уровня. s-вероятность возвращения на дообслуживание.
|
|
|
Для рассматриваемой структуры справедлива эквивалентная модель
L
q
Рисунок 14.2 – Эквивалентная модель
Здесь L=l*n, где 
.
Таким образом, при геометрическом распределении вероятность Рk числа квантов n на задачу того, что заявка обслуживается ровно за К квантов времени q.
- это вероятность того, что заявка не обслуживалась за предыдущей К-1 квант времени t.
- интенсивность эквивалентного входного потока, который складывается из потоков интенсивностей 
где 
,
- поток запросов
Основным недостатком алгоритма является то, что трудоемкие запросы при обслуживании требуют больного числа прерываний.
Осн. лит.102[9-16],
Доп. лит.6[6-12].
Контрольные вопросы:
1. В чем сущность алгоритмов многоуровневой диспетчеризации?
2. Из чего складывается эквивалентный входной поток запросов при многоуровневой бесприоритетной диспетчерезации?
3. Принципы назначения приоритетов при многоуровневой приоритетной и бесприоритетной диспетчеризации.
4. Что обеспечивает многоуровневая диспетчеризация по сравнению с одноуровневыми дисциплинами.
Лекция 15. Алгоритм многоуровневого циклического планирования с учетом приоритетов работ.
Входной поток запросов расщепляется на N потоков с интенсивностью λ1,…,λN. Отнесение потока к тому или иному уровню производится на основе оценки его трудоемкости высшего приоритета. Например, в соответствии с алгоритмом SIF(Shortest Job First). На основе этого запроса с большой трудоемкостью обслуживания выделяются низкие приоритеты и они поступают в очереди соответствующих уровней. Для обслуживания запроса более низких уровней получают кванты большей длительностью. При завышении приоритета по окончании выделенного кванта времени запрос перемещается в очередь более низкого приоритета.
l1 1-s
q2
l2
l3 s
|
 |
Рис.15.1 – Модель многоуровневого циклического планирования с учетом приоритетов
Запрос приоритетом r заноситься в очередь Q2. Очередям Q1,…,QN выделяются кванты времени Косвенным оценочным критерием может служить вероятность Pk. У квантов времени индекс Р(qp) определяет длительность квантов времени
|
|
|
qp=2 r-1*q
где q- квант времени для запросов высшего приоритета. Увеличение кванта времени на обслуживание трудоемких запросов сокращает число прерываний. При удачном назначении приоритетов входные очереди обеспечивают адаптируемое по трудоемкости время обслуживания без прерываний на межуровневые переходы.
|
|
|
