Сети массового обслуживания с простейшими потоками событий

Рассмотренные ранее системы массового обслуживания (СМО) позволя-

ют с той или иной степенью точности описывать процессы, протекающие в от-

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

Ограничимся рассмотрением линейных стохастических сетей, которые могут быть построены из конечного числа nСМО без потерь Si, i= 1,…nи ис- точника заявок S0следующим образом. Заявки из источника заявок S0посту- пают в сеть, причем с постоянной вероятностью p0i, i= 1,…n, заявка, появляю- щаяся на выходе источника, поступит в систему Si, i= 1,…n. Заявки, обслу- женные системой Si, i= 1,…n., с постоянной вероятностью pij, i= 1,…n, j=

1,…nпоступают в систему Sj, j= 1,…nили покидают сеть (j = 0), причем заяв-

ки, покидающие сеть, возвращаются в источник заявок. Очевидно, должно вы-

полняться равенство

причем p00= 0.

n

е p ij = 1, i= 0,…n,

j=0

Структура сети может быть представлена графом, вершины которого со-

ответствуют системам массового обслуживания Si, i= 1,…nи источнику зая- вок S0, а дуги, взвешенные вероятностями pij, i= 1,…n, j= 1,…n- передачами между элементами сети. Не следует путать этот граф, называемый графом пе- редачи сети, с графом переходов между состояниями системы, встречавшимся ранее при рассмотрении СМО с простейшими потоками событий.

Различают разомкнутые и замкнутые стохастические сети.

Разомкнутая сеть характеризуется постоянной и независящей от состоя- ния сети интенсивностью потока заявок lOна выходе источника заявок S0, при- чем интенсивность lOзаранее известна и является параметром сети.

Рис. 3.13. Граф передачи для разомкнутой СеМО

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

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

Рис. 3.14. Граф передачи для замкнутой СеМО

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

Полный перечень сведений (параметров) о стохастической сети содер-

жит:

1) число nСМО, образующих сеть;

2) число каналов обслуживания mi, входящих в состав СМО Si, i= 1,…n;

3) интенсивности потоков обслуживания miв СМО Si, i= 1,…n;

4) матрицу вероятностей передач p = [pij] i,j= 0,…n;

5) интенсивность lOпотока заявок на выходе источника заявок S0для ра-

зомкнутой сети или число Мзаявок, циркулирующих в замкнутой сети.

Матрица вероятностей передач [p], содержащая как в случае разомкну- той так и замкнутой сети n + 1 строку n + 1 столбец является важным парамет- ром сети, однако не может быть непосредственно использована для получения характеристики сети и составляющих ее СМО, поскольку для этого необходи- мо знание интенсивностей потоков заявок на входах СМО Si, i= 1,…n.

[p ij ] =

S 0

S1

S i

...

Sn

S 0

0 p10

...

P i 0

...

Pn 0

S1 p 01 p11

P i1

...

Pn1

...

...

...

...

...

...

...

S j

P 0 j

P1 j

P ij

...

P nj

....

...

...

...

...

...

...

S n

p 0n

P1n

P in

...

P nn

(3.48)

Возникает вопрос о трансформации входящего потока заявок с интен- сивностью lOко входам составляющих сеть СМО. Будем рассматривать только установившийся режим.

Обозначим через ai, i= 1,…nкоэффициент передачи (трансформации) входящего потока заявок ко входу системы Si, i= 1,…n, количественно равный среднему числу появлений произвольной заявки из входящего потока сети во входящем потоке СМО Si, иначе говоря равный среднему числу обслуживаний, получаемых произвольной заявкой в СМО Siза все время пребывания ее в се- ти. Тогда интенсивность входящего потока СМО Si, , может быть выражена че- рез интенсивность входящего потока сети lO:

li = ai lO , i= 1,…n.(3.49)

Поскольку рассматриваемая сеть без потерь, интенсивности выходящих

потоков СМО Siсовпадают с интенсивностями их входящих потоков. Интен- сивность входящего потока СМО Sjравна сумме долей потока, поступающих от источника заявок S0и от других СМО сети:

n

+ е (pij Чli ) j = 1,…n(3.50)

i =1

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

(p11 - 1) Ч a1 + p 21a 2 + ... + pn1 an

= -p 01 ь

п

П

э

(3.51)

- - - - - - - - - - - - - - - - - - - - п

p1n a1 + p 2n a2 + ... + (pnn - 1) Ч an

= -p 0n

Поскольку интенсивность источника заявок lOизвестна, анализ сети сво- дится к анализу совокупности независимых систем массового обслуживания Si, интенсивности входящих потоков которых liвыражены через интенсивность входящего потока сети lOи коэффициенты передачи ai, .

l1 = a1* lO ®

S1, m1, m1 ®

- - - - - - - - - - -

ln = an* lO ®

Sn, mn, mn ®

Рис. 3.15. Процедура анализа СеМО

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

li <1. (3.52)

M i mi

Поскольку li = ai, lOто данное выражение приводится к виду:

lO < m i mi

Ai

. (3.53)

Данное неравенство позволяет сформулировать ограничение сверху на интенсивность входящего потока сети lOиз условия существования устано- вившегося режима в стохастической сети

Йm m щ

lO < min к i i ъ, i = 1,…n(3.54)

Л ai ы

Если установившийся режим в сети существует, то для каждой из состав- ляющих сеть СМО Siнетрудно найти показатели эффективности tожi, tсi, li, Ki,пользуясь выражениями, приведенными ранее.

На основании показателей эффективности отдельных СМО находятся показатели эффективности сети в целом:

n n n

n

T ОЖ

= е(ai Чt ОЖi );

t C = е(ai Чt Ci ) l = е(l i );

K = е(K i );

i =1

i =1

K

n

ЕK i

i =1

i =1

n

Е m i

i =1

= i =1 . (3.55)

i =1

ВЕРОЯТНОСТНЫЕ АВТОМАТЫ

Вероятностный автомат является типичным представителем стохастиче-

ской динамической системы с дискретным временем.

Как было отмечено выше, для детерминированного конечного автомата функция переходов вида (2.11)

z(tj) = j[ z(tj-1), x(tj)]