Ремонт принтеров, сканнеров, факсов и остальной офисной техники


назад Оглавление вперед




[46]

K j=1

Решение системы, составленной изуравнений (7.8) и нормирующего уравнения

а1 +... + aK = 1, определяет значения вероятностей а =aK}. Уравнения (7.7), (7.8) называются

уравнениями равновесия. Они легко составляются по графу марковской цепи с учетом того, что в каждом состоянии входящий поток должен равняться исходящему потоку. Так, для цепи на рис. 7.3 имеем

Состояние

С учетом равенства интенсивности входящего и исходящего потока

/иа2 = (Л/2 +Л)а < Ла1 + /иа3 = (и + Л) а2;

-а1 +Ла2 = /ла3; 2

Полученная система является системой уравнений равновесия для цепи, изображенной на рис. 7.3 и заданной матрицей (7.6).

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

свойством обладает только одно распределение - экспоненциальное, функция плотности вероятности которого имеет следующий вид: p(t) = 1/rexp(-t/г), где т - параметр распределения,

определяющий математическое ожидание случайной величины t. Таким образом, непременное свойство непрерывного марковского процесса - экспоненциальность распределения времени пребывания процесса в каждом из состояний.

Если снять указанное ограничение на время пребывания процесса в состояниях s1,...,sK, т.е.

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

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

Интенсивность входящего потока /иа2

Ла1 + /иа3

2 12

Интенсивность исходящего потока

л Л

2 ) 1

/ а3


обслуживается в системе путем предоставления ей некоторых ресурсов на какое-то время и, будучи обслуженной, покидает систему. Определение времени пребывания заявок в системе составляет сущность теории массового обслуживания. Наиболее характерный момент функционирования систем массового обслуживания - наличие очередей, в которых поступившие заявки ждут момента освобождения ресурсов, занятых обслуживанием других, например, ранее поступивших заявок. ЭВМ можно рассматривать как систему массового обслуживания, на вход которой поступают задания, обслуживаемые путем предоставления им процессорного времени и времени остальных устройств ЭВМ. Анализ ЭВМ как системы массового обслуживания позволяет определить число заданий, находящихся в ЭВМ на различных стадиях обслуживания, время ожидания заданий в очередях, время пребывания задании в ЭВМ и другие характеристики процесса обработки заданий, функционирования ЭВМ и ее устройств.

Система массового обслуживания (рис. 7.4) состоит из входящего потока заявок а, очереди Q, дисциплины обслуживания D, определяющей порядок выбора заявок из очереди, и обслуживающего прибора П или К одинаковых обслуживающих приборов (каналов) П1,...,ПК. Система, содержащая только один прибор (канал), называется одноканальной, а

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

Таким образом, система массового обслуживания характеризуется следующим набором параметров:

1)распределением длительности интервалов между заявками входящего потока р(а);

2)дисциплиной обслуживания заявок D;

3)числом обслуживающих приборов (каналов) К;

4)распределением длительности обслуживания заявок приборами (каналами) р(Ь). Указанный набор параметров полностью определяет порядок функционирования

системы. Процесс функционирования количественно оценивается следующим набором основных характеристик:

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

2)длиной очереди - числом заявок, ожидающих обслуживания;

3)числом заявок, находящихся в системе (в очереди и на обслуживании приборами);

4)временем ожидания заявки - от момента поступления заявки в систему до начала обслуживания;

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

а)

Q

D

П

б)

Q

D

п1

п2

a

a

Рис. 7.4. Одноканальная (а) и многоканальная (б) система массового обслуживания


Наряду с основными характеристиками для оценки функционирования системы используются дополнительные характеристики: длительность простоя, непрерывной занятости приборов и др.

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

В теории массового обслуживания изучаются и более сложные объекты - сети. Сеть массового обслуживания - совокупность взаимосвязанных систем массового обслуживания. Пример сети представлен на рис. 7.5. Здесь S0 - узел - источник заявок, S1,..., S4 - системы

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

из узла Si в узлы S,, SkSt соответственно, причем pij + pjk +... + pa = 1.

Рис. 7.5. Граф сети массового обслуживания

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

Сеть массового обслуживания задается следующим набором параметров:

1)параметрами источника заявок;

2)структурой, определяющей конфигурацию связей и вероятности передачи заявок между узлами сети;

3)параметрами систем массового обслуживания Si, i=1, ......, N- дисциплиной

обслуживания Di, числом каналов Ki и распределением длительности обслуживания заявок

p (bi).

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



[стр.Начало] [стр.1] [стр.2] [стр.3] [стр.4] [стр.5] [стр.6] [стр.7] [стр.8] [стр.9] [стр.10] [стр.11] [стр.12] [стр.13] [стр.14] [стр.15] [стр.16] [стр.17] [стр.18] [стр.19] [стр.20] [стр.21] [стр.22] [стр.23] [стр.24] [стр.25] [стр.26] [стр.27] [стр.28] [стр.29] [стр.30] [стр.31] [стр.32] [стр.33] [стр.34] [стр.35] [стр.36] [стр.37] [стр.38] [стр.39] [стр.40] [стр.41] [стр.42] [стр.43] [стр.44] [стр.45] [стр.46] [стр.47] [стр.48] [стр.49] [стр.50] [стр.51] [стр.52] [стр.53] [стр.54] [стр.55] [стр.56] [стр.57] [стр.58] [стр.59]