Закон сохранения времени ожидания

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

(2)

где - загрузка прибора, w_i - среднее время ожидания в очереди заявок типа

i = 1, …, M.

Закон (2) справедлив, если система отвечает следующим требованиям:

1. отсутствуют отказы в обслуживании,

2. система обслуживания простаивает лишь в том случае, если на ее входе нет заявок на обслуживание,

3. при наличии прерываний длительность обслуживания описывается экспоненциальным распределением,

4. все входные потоки описываются независимыми пуассоновскими распределениями, и длительность обслуживания не зависит от входных потоков.

Закон сохранения времени ожидания можно использовать для оценки достоверности приближенных результатов, полученных при анализе сложных дисциплин обслуживания.

Лекция. Характеристики дисциплин обслуживания

Характеристики бесприоритетных дисциплин обслуживания

При бесприоритетной дисциплине заявки разных типов не имеют заранее определенных привилегий на первоочередное обслуживание. Это правило выполняется, если заявки на обслуживание выбираются:

1) в порядке поступления; 2) в порядке, обратном порядку поступления; 3) наугад, т.е. путем случайного выбора из очереди.

Дисциплина обслуживания в порядке поступления называется FIFO, а дисциплина обслуживания в обратном порядке – LIFO. Указанные три бесприоритетные дисциплины характеризуются одинаковым средним временем ожидания заявок, но дисциплина FIFO минимизирует дисперсию времени ожидания, т.е. уменьшает разброс времени ожидания относительно среднего значения.

Бесприоритетное обслуживание на основе дисциплины FIFO организуется в соответствии со схемой:

z₁

О

z₂ Пр

.

.

.

z_m

где Пр - это процессор , О - очередь заявок типа z₁,…, z_M.

Вновь поступившая заявка заносится в конец очереди. Заявки выбираются на обслуживание из начала очереди. Пусть в систему поступают заявки М типов с интенсивностями λ₁,…,λ_M.Предположим, что каждый из входных потоков заявок – пуассоновский. Тогда суммарный поток заявок также пуассоновский и его интенсивность

(3)

Пусть известны также математические ожидания ₁, …, _M и вторые начальные моменты ₁⁽²⁾, …, _M⁽²⁾ времени обслуживания заявок типа 1, …, М. Эти значения характеризуют распределение времени выполнения соответствующих программ. Второй начальный момент – среднее значение квадрата случайной величины. Тогда при использовании бесприоритетной дисциплины обслуживания среднее время ожидания заявок всех типов одинаково и равно:

(4)

Выразим второй начальный момент через коэффициент вариации - отношение среднеквадратичного отклонения длительности обслуживания к его математическому ожиданию.

k=1,…,.M (6)

где R_k-1 = +…..+ ; R_k = +….+ - суммарные загрузки процессора потоками заявок z₁, …,z_k-1 и z₁, …, z_kсоответственно.

Используя коэффициенты вариации длительности обслуживания, выражение (6) можно представить в виде:

(6^/)

Проанализируем соотношение между временами ожидания заявок с разными приоритетами. При увеличении значения приоритета к=1…М-1 на единицу среднее время ожидания (6) изменяется на

,

где -положительный коэффициент, не зависящий от k.

После преобразований получаем

.

Т.к. R_i<1, то ,откуда следует, что ₁< ₂<…. _M . Таким образом, времена ожидания заявок монотонно увеличиваются с уменьшением приоритета.

Теперь сопоставим время ожидания заявок, имеющих относительные приоритеты 1, …, М, с временем ожидания при бесприоритетном обслуживании. Из формул (6) и (4) видно, что времена ожидания различаются постольку, поскольку различаются величины и (1-R)в знаменателях соответствующих выражений.

Т.к. , то ₁< < _M,

где - среднее время ожидания заявок при бесприоритетном обслуживании, причем ₁< ₂<…. _M. Сл-но, введение относительных приоритетов приводит к уменьшению времени ожидания заявок с высокими приоритетами и увеличению времени ожидания заявок с низкими приоритетами по сравнению с бесприоритетным обслуживанием.

_k

FIFO

ОП

₁

к

1 M

Характеристики дисциплины обслуживания с абсолютными приоритетами

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

О₁

z₁

О₂ z_i

z₂ Пр

.

.

. О_М

.

Z_М

2

1- заявка, ожидающая обслуживания

2- прерванная заявка

Для каждого потока заявок организуется очередь , в которой заявки размещаются в порядке поступления. Заявкам соответствуют абсолютные приоритеты 1, …, М. Если процессор занят обслуживанием заявки и на вход поступает заявка , то при заявка заносится в конец очереди , а при обслуживание заявки прерывается, заявка заносится в начало очереди и Диспетчер переключает процессор на обслуживание заявки .

Обслуживание прерванных заявок может проводиться: 1) от начала; 2) от момента прерывания (дообслуживание). По возможности стремятся использовать 2-й способ.

Если длительность обслуживания распределена по экспоненциальному закону, среднее время дообслуживания совпадает со средним временем обслуживания заявки.

Если потоки заявок - простейшие с интенсивностями и мат. ожидания и 2-е начальные моменты длительности обслуживания равны соответственно и и прерванная заявка дообслуживается от точки прерывания, то среднее время ожидания заявки с абсолютным приоритетом k(k = 1, …, М), определяется следующим образом:

(7)

– загрузка системы от первых j потоков заявок.

Сопоставление формул (7) и (6) показывает, что при обслуживании с абсолютными приоритетами длительность ожидания заявок k-го приоритета изменяется на величину

,

где первое слагаемое определяет влияние заявок более высокого приоритета, прерывающих обслуживание заявок данного приоритета, а второе слагаемое учитывает уменьшение времени ожидания заявок k-го приоритета за счет прерываний обслуживания заявок с меньшими приоритетами. Из этого выражения можно определить условие, при котором длительность ожидания в очереди заявок k-го приоритета при наличии прерываний будет меньше, чем длительность ожидания при обслуживании с относительными приоритетами, т.е. условие, при котором имеет вид:

Эффект от использования абсолютных приоритетов иллюстрирует рисунок:

где ОП – кривая относительного приоритета , АП – кривая абсолютного приоритета.

Присваивание заявкам абсолютных приоритетов приводит к уменьшению времени ожидания заявок с высокими приоритетами, но одновременно с этим увеличивается время ожидания низкоприоритетных заявок.