3. Длительность обслуживания заявок

Длительность обслуживания заявки равна промежутку времени, необходимому прибору (устройству) для обслуживания заявки. В об­щем случае — это случайная величина с законом распределения В() и математическим ожиданием (средним значением) . Типы заявок различаются либо законами распределения, либо только средними значениями длительности обслуживания при одинаковых законах распределения. При этом принимается предположение о независи­мости длительностей обслуживания для различных заявок одного типа, которое вполне справедливо для большинства реальных систем. Длительность обслуживания заявки процессором определяется вре­менем выполнения соответствующей программы. В случае малой разветвленности программы, когда число выполняемых операций прак­тически постоянно, длительность обслуживания может считаться по­стоянной и равной . В общем случае прикладные программы реа­лизуют сложные алгоритмы с большим числом разветвлений. Коли­чество операций, выполняемых в процессе обслуживания заявок одного типа, зависит от того, по какой ветви идет реализация алго­ритма. В свою очередь путь реализации алгоритма определяется со­стоянием управляемого объекта, т. е. данными, поступающими в систему. При этом время выполнения программы рассматривается как случайная величина с математическим ожиданием  и диспер­сией D. Значения  и D определяются путем статистической обработки многих прогонов програм­мы на ЭВМ.

• Гамма-распределение длительности обслуживания.

Если известны математическое ожидание * и дисперсия D*, то время выполнения программы, т. е. длительность обслуживания, аппроксимируется в общем случае гамма-распределением. Основанием для такой аппрок­симации являются следующие свойства гамма-распределения:

1) гам­ма-распределение определяет случайную величину в области поло­жительных значений; время обслуживания определено именно в этой области;

2) многие аналитические результаты получаются достаточно легко в случае, когда время обслуживания заявок распределено по этому закону;

3) гамма-распределение может рассматриваться как некоторое общее распределение, из которого путем изменения пара­метра могут быть легко получены другие виды распределений.

Гамма-распределение — это унимодальное распределение с плот­ностью вероятности

, >0, (7)

где  — математическое ожидание длительности обслуживания; k — параметр распределения (k1); Г(k) — гамма-функция.

Математическое ожидание и дисперсия соответственно равны

.

Частный случай гамма-распределения при k=1 — это экспоненциальное рас­пределение

,

а его предел при k соответствует постоянной длительности обслужива­ния заявок, равной ft, по­скольку дисперсия гамма-распределения D[] стре­мится к нулю при неогра­ниченном увеличении па­раметра k.

Выражение (7) пред­ставляет собой плотность вероятности для любых положительных значений параметра k, поэтому любым заданным значениям математического ожидания * и дисперсии D* может быть поставлено в соответствие распределение вида (7). При этом k = (*)²/D*.

• Распределение длительности обслуживания по закону Эрланга.

При целочисленном k выражение (7) упрощается, поскольку

Г(k)=(k-1)!. в этом случае гамма-распределение вырождается в рас­пределение Эрланга k-го порядка с математическим ожиданием . Такое распределение представляет собой распределение суммы k не­зависимых случайных величин, каждая из которых распределена по экспоненциальному закону с математическим ожиданием /k.

Рис. 8. Нормированное распределение Эрланга

Форма распределения Эрланга приведена на рис. 8. В отличие от распределения Эрланга (6) математическое ожидание рассмат­риваемого распределения не зависит от k и всегда равно . Таким образом, при изменении параметра k изменяется форма распределе­ния при неизменном математическом ожидании. При достаточно боль­ших k(k>5) распределение (7) почти симметрично относительно . Кроме того, распределение Эрланга (6) при k стремится к нормальному, в то время как распределение Эрланга (7) приводит в пределе к детерминированному значению . Распределение (7) обычно называют нормированным распределением Эрланга.

• Экспоненциальное распределение длительности обслуживания.

Если известно только среднее время выполнения программы и, сле­довательно, отсутствуют сведения о законе распределения, то время выполнения программы целесообразно аппроксимировать экспонен­циальным распределением вида

. (8)

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

1) использование экспоненциального распределения упрощает аналитические выкладки;

2) получаемые оценки являются предельными (например, время ожи­дания при других законах обслуживания, у которых коэффициенты вариации меньше единицы, оказывается не большим, чем при экспо­ненциальном).

Рис. 9. К определению времени дообслуживания заявки

Экспоненциальное распределение длительности обслуживания имеет следующее замечательное свойство. Если прибор занят обслу­живанием заявки и длительность обслуживания распределена по экспоненциальному закону, то интервал времени от любого случай­ного момента времени до момента окончания обслуживания заявки имеет то же экспоненциальное распределение с тем же средним. Это свойство иллюстрируется рис. 9. Здесь t_l и t₂ — моменты начала и окончания обслуживания, длительность которого равна . Пусть t* — случайный момент времени, причем t₁<t*<t₂. Тогда длительность дообслуживания ₂= t₂ — t* распределена, так же как и , по закону (8) с тем же средним *. Из этого свойства следует, что при экспоненциальном законе обслуживания в случае прерывания время дообслуживания заявки является случайной величиной с тем же зако­ном распределения, что и длительность обслуживания. Иначе гово­ря, процессы обслуживания и дообслуживания протекают одинаково. Это на первый взгляд парадоксальное свойство экспоненциального распределения —следствие отсутствия последействия, присущего всем процессам с экспоненциальным распределением интервалов вре­мени.

Наряду со средней длительностью обслуживания используется понятие интенсивности обслуживания  — величины, обратной сред­ней длительности обслуживания

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

Некоторые аналитические зависимости могут быть получены в общем виде для произвольного закона распределения времени обслу­живания заявок. При этом для определения характеристик обслужи­вания заявок оказывается вполне достаточным знание нескольких первых моментов распределения времени обслуживания. В частности, при исследовании дисциплин обслуживания в ЦУС для определения среднего времени ожидания заявок необходимо задать кроме мате­матического ожидания  лишь второй начальный момент ⁽²⁾ вре­мени обслуживания заявок.

4. Основные характеристики качества функционирования цифровых управляющих систем и закон сохранения времени ожидания

Характеристики ЦУС при одномерном потоке заявок. Одной из важнейших характеристик качества функционирования ЦУС (цифро­вых управляющих систем) является загрузка:

, (9).

где , — интенсивность поступления заявок в систему;  — интенсив­ность обслуживания заявок.

Заменяя в (9)  величиной 1/, получаем =. Значение  определяет среднее число заявок, поступающих в систему за среднее время обслуживания одной заявки. Наряду с этим величина загруз­ки характеризует долю времени, в течение которого обслуживающий прибор занят обслуживанием заявок, и одновременно вероятность того, что в произвольный момент времени обслуживающий прибор работает (не простаивает). Покажем это следующими элементарными рассуждениями. Пусть рассматриваемая система функционирует в течение достаточно большого периода времени Т. Число заявок, по­ступивших в систему, равно в среднем Т, и они обслуживаются в среднем за время T, где — средняя длительность обслуживания. Тогда доля времени, в течение которого система была занята обслу­живанием заявок

.

Поскольку загрузка  определяет вероятность того, что система занята обслуживанием, т. е. работает, то вероятность простоя опре­деляется значением =1—, называемым коэффициентом простоя. При этом предполагается, что <1, что справедливо для всех ре­альных систем.

Все время работы системы можно условно разбить на два интервала: интервал переходного режима работы системы от момента начала ра­боты системы до момента входа в стационарный режим и интервал стационарного режима. Стационарным (установившимся) режимом называют такой режим работы, при котором вероятностные характе­ристики функциониррвания системы не зависят от времени. Условие существования стационарного режима определяется значением за­грузки <1. Если >1, т.е. интенсивность поступления заявок превышает интенсивность их обслуживания, то работа системы ха­рактеризуется неограниченным возрастанием длины очереди заявок перед обслуживающим прибором, т.е. не существует стационарного режима работы системы. Случай равенства интенсивностей поступле­ния заявок и их обслуживания (р=1) не тривиален и требует в каждом конкретном случае особого рассмотрения.

Качество функционирования ЦУС определяется временем пребы­вания заявок в системе, равным промежутку времени от момента поступления заявки в систему до момента окончания обслуживания ее в процессоре. Время пребывания u складывается из времени ожидания , когда заявка находится в очереди, и времени обслужива­ния  ее в процессоре, т. е.

.

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

.

Если обслуживание заявки не прерывается, то ^п=0 и  = ^н.

При исследовании дисциплин обслуживания заявок в ЦУС вре­мя обслуживания  не изменяется с изменением дисциплины. Сле­довательно, наряду со временем пребывания как характеристики ка­чества функционирования ЦУС может использоваться время ожида­ния заявок в системе. Поскольку большинство результатов получе­но для времени ожидания, в дальнейшем в качестве основной ха­рактеристики функционирования ЦУС будем рассматривать время ожидания заявок, помня, что u=+. Остальные характеристики обслуживания заявок, такие, как средняя длина очереди и среднее число заявок в системе, связаны простыми соотношениями с време­нем пребывания и временем ожидания заявок.

Для систем с неограниченным ожиданием, когда поступившая заявка ожидает в очереди обслуживания сколь угодно долго, не по­кидая систему, средняя длина очереди связана со средним временем ожидания заявок  зависимостью l=, где — интенсивность по­ступления заявок в систему. Это выражение становится очевидным, если учесть, что за время w в среднем поступает  заявок, кото­рые ожидают в очереди начала обслуживания.

Аналогичными рассуждениями можно получить выражение для среднего числа заявок в системе:

.

Среднее число заявок в системе больше средней длины очереди заявок на величину загрузки , которая в данном случае может рассматриваться как среднее число заявок, обслуживаемых в про­цессоре ЦУС. Действительно, в процессоре на каждый момент вре­мени с вероятностью  находится одна заявка на обслуживании и с вероятностью (1—) — нуль заявок (процессор простаивает). По­этому среднее число заявок, обслуживаемых в процессоре, равно 1+(1-)0=.

• Характеристики ЦУС при многомерном потоке заявок.

На вход обслуживающего прибора может поступать многомерный поток за­явок с интенсивностью ₁,. . ., _М, состоящий из заявок типа 1, . . ., М. Тогда загрузка прибора потоком заявок типа i будет составлять _i=_i_i, где _i — средняя длительность обслуживания за­явок типа _i.

Суммарная (общая) загрузка прибора со стороны всех потоков

В этом случае условие существования стационарного режима представляется в виде R<1 и коэффициент простоя прибора =1—R. Остальные характеристики обслуживания в слу­чае многомерного потока определяются для каждого потока анало­гичным образом и для заявок типа i равны u_i=_i+_i, l_i=_i_i, n_i=_iu_i, . Среднее время ожидания _ср и пребывания u_ср одной за­явки из суммарного потока в системе:

где _i/ — вероятность того, что поступившая заявка является заявкой типа i; — среднее число заявок всех типов, находящихся в очереди (или в очередях в случае нескольких очередей); — среднее число заявок всех типов в системе

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

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

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

(10)

т. е. инвариантна относительно дисциплины обслуживания. Здесь _i—загрузка прибора; _i — среднее время ожидания в очереди за­явок типа i = l, ..., М.

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

1) отсутствие отказов в обслуживании, т. е. все заявки на обслуживание удовлетворяются;

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

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

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

Значение константы в (10) можно определить следующим обра­зом. Простейшей является дисциплина обслуживания заявок в порядке их поступления, для которой среднее время ожидания заявок различных типов одинаково и равно

где _i⁽²⁾ — второй начальный момент длительности обслуживания за­явок типа i=l,...,М.

С учетом этого закон (10) можно записать в виде

(11)

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