Geum.ru

Задача анализа, т е. определение количественных

Вид материалаЗадача
K = SUMMA(Ki)
Delta = | р12 (р22-1) р32 | = |0,4 -1 0| = 0,1
Delta2 = | р12 -р01 р32 | = |0,4 0 0| = -0,4
Alfa1 = delta1 / delta = 10
Подобный материал:
1   2   3   4   5

инженерами. ЭВМ требует обслуживания в среднем каждые два часа.

Инженер тратит на обслуживание в среднем 12 минут. ЭВМ имеет

пропускную способность 3 зад/час. Сравнить по пропускной

способности лаборатории два варианта организации обслуживания ЭВМ:

1) каждый инженер обслуживает ЭВМ самостоятельно;

2) инженеры обслуживают ЭВМ совместно, однако их

взаимопомощь увеличивает производительность в 1,9 раз.


Решение.


В этой задаче источником заявок на обслуживание являются

ЭВМ, роль каналов обслуживания играют инженеры.

Первый вариант организации обслуживания сводится к

замкнутой СМО с параметрами:


M = 5; m = 2; n = M - m = 3.


Интенсивность входящего потока LA = 0,5 1/час,

интенсивность потока обслуживания MU1 = 5 1/час, RO = 0,1.

Вероятности состояний:


+ 2 3 4 5 +-1

| 5RO 5*4RO 5*4*3RO 5*4*3*2RO 5RO |

Р0 = |1 + --- + ----- + ------- + --------- + ------ | = 0,618

| 1! 2! 2!2 2!2**2 2!2**3 |

+ +


Р1 = 5*RO*Ро = 0,309; 4

2 Р4 = 15*RO *Р0 = 0,001;

Р2 = 10*RO *Р0 = 0,062;

3 15 5

Р3 = 15*RO *Р0 = 0,01; Р5 = -- RO *Р0 = 0.

2


Среднее число занятых инженеров:

_

К = 1*Р1 + 2*Р2 + 2*(1 - Р0 - Р1 - Р2) = 0,45.

_

Загрузка инженеров PSI = K/m = 0,227.


Среднее число обслуживаемых ЭВМ:

_ _

Z = M - K/RO = 0,45

_

l = 0.


Среднее число ЭВМ, занятых производительной работой, равно

_

M - Z = 4,55. Пропускная способность равна 13,65 зад/час.


Вариант со взаимной помощью сводится к замкнутой СМО с

параметрами:


M = 5; m = 1; n = 4; LA = 0,5 1/час,

MU2 = 1,9*MU1 = 9,5 1/час, RO = 0,053.


Вероятности состояний:


2 3 4 5 -1

Р0 = (1 + 5RO + 5*4RO + 5*4*3RO + 5*4*3*2RO + 5!RO ) = 0,751


Р1 = 0,199;

Р2 = 0,042;

Р3 = 0,007;

Р4 = 0,001;

Р5 = 0.


_ _ _

K = 0,249; Z = 0,3; l = 0,051.


Пропускная способность составляет

_

(M - Z)3 = 14,1 зад/час


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

лаборатории.


2.4. Сети массового обслуживания

с простейшими потоками событий.


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

позволяют с той или иной степенью точности описывать процессы,

протекающие в отдельных устройствах или подсистемах современных

вычислительных систем. Для исследования процессов в

вычислительной системе в целом необходимо рассматривать

взаимодействие некоторой совокупности систем массового

обслуживания (стохастическую сеть).

Ограничимся рассмотрением линейных стохастических сетей,

которые могут быть построены из конечного числа 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), причем заявки, покидающие сеть, возвращаются в источник

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


n ____

SUMMA Pij = 1, i = 0, n,

j = 0

причем Р00 = 0.

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

которого соответствуют системам массового обслуживания Si,

____

i=1, n, и источнику заявок S0, а дуги, взвешенные вероятностями

_____ ____

Pij, i = 0, n, j = 0, n - передачами между элементами сети. Не

следует путать этот граф, называемый графом передачи сети, с

графом переходов между состояниями системы, встречавшимся ранее

при рассмотрении СМО с простейшими потоками событий.

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

Разомкнутая сеть характеризуется постоянной и независящей от

состояния сети интенсивностью потока заявок LAо на выходе

источника заявок S0, причем интенсивность LAо заранее

известна и является параметром сети.


-------------

| Сеть|

Р0i | +----+ | Pi0

+------|-->| Si +--|-------+

| | +--+-+ | |

| | | | V

LA0+++ |Pji | | Pij| +-+LA0

S0 +++ | | | | +-+ S0

|| | | | | |

|| | | V | ||

|| | ++---+ | ||

|+------|-->| Sj +--|-------+|

| P0j | +----+ | Pj0 |

| ------------- |

------------------------------


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

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

задач, например, вычислительных систем оперативной обработки с

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

нее не могут попадать заявки извне, число заявок М,

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

условиями.

-------------

| Сеть|

Р0i | +----+ | Pi0

+------|-->| Si +--|-------+

| | +--+-+ | |

| | | | |

| |Pji | | Pij| |

| | | | | |

| | | | | |

| | | V | |

| | ++---+ | |

| +-|-->| Sj +--|--+ |

| P0j| | +----+ | |Pj0 |

| | ------------- | |

| | | |

| | S0 | |

| +------+-+<------+ |

+-----------+-+<-----------+

LA0


Заявка, появляющаяся в выходящем потоке замкнутой сети, тут

же вызывает появление новой заявки во входящем потоке,

интенсивность LA0 фиктивного источника заявок характеризует

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

внешних причин, а определяемую конфигурацией сети и ее

параметрами. Замкнутые стохастические сети используются для

описания вычислительных систем, с которыми в каждый момент

времени связано фиксированное число заявок, например, систем

пакетной обработки.

Полный перечень сведений о экспоненциальной стохастической

сети (ее параметров) содержит: 1) число n СМО, образующих сеть;

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

____

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

____ ____

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

интенсивность LA0 потока заявок на выходе источника заявок

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

замкнутой сети.


2.4.1. Анализ разомкнутых сетей массового обслуживания


Матрица вероятностей передач Р, содержащая как в случае

разомкнутой так и замкнутой сети n + 1 строку n + 1 столбец


S0 S1 ... Sj ... Sn

+ +

S0| 0 P01... P0j... P0n|

S1| P10 P11... P1j... P1n|

||poij|| = ...|. . . . . . . . . . . .|

Si| Pi0 Pi1... Pij... Pin|

...|. . . . . . . . . . . .|

Sn| Pn0 Pn1... Pnj... Pnn|

+ +


является важным параметром сети, однако не может быть непосредственно

использована для получения характеристики cети и составляющих ее СМО,

поскольку для этого необходимо знание интенсивностей

-----

потоков заявок на входах СМО Si, i = 1, n. Возникает вопрос о

трансформации входящего потока заявок с интенсивностью LAо

ко входам составляющих сеть СМО. Будем рассматривать только

-----

установившийся режим. Обозначим через ALFAi, i = 1, n

коэффициент передачи (трансформации) входящего потока заявок ко

----

входу системы Si, i = 1, n, количественно равный среднему числу

появлений произвольной заявки из входящего потока сети во

-----

входящем потоке СМО Si, i = 1, n, иначе говоря равный среднему


числу обслуживаний, получаемых произвольной заявкой в СМО Si,

----

i = 1, n за все время пребывания ее в сети. Тогда интенсивность

----

входящего потока СМО Si, i = 1, n может быть выражена через

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


----

LAi = ALFAi * LAо, i = 1, n


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

-----

выходящих потоков СМО Si, i = 1, n совпадают с интенсивностями

их входящих потоков. Интенсивность входящего потока СМО Sj,

-----

j = 1, n равна сумме долей потока, поступающих от источника

заявок S0 и от других СМО сети:


n ----

LAj = P0j * LAо + SUMMA(Pij * LAi), j = 1, n

i = 1


Выражая интенсивность LAi входящих и выходящих потоков СМО

----

Si, i = 1, n через интенсивность источника заявок


n

ALFAj*LAо = P0j*LAо + SUMMA(Pij*ALFAi*LAо) =

i = 1


+ n + ----

= LAо*|P0j + SUMMA(Pij*ALFAi)|, j = 1, n,

+ i = 1 +


и сокращая LAо в обеих частях равенства (УП-63), получим

систему линейных неоднородных алгебраических уравнений

----

относительно искомых коэффициентов передач ALFAi, i = 1, n:

+

(P11-1)*ALFA1 + P21*ALFA2 + ... + Pn1*ALFAn = - P01 |

P12*ALFA1 + (P22-1)*ALFA2 + ... + Pn2*ALFAn = - P02 \

. . . . . . . . . . . . . . . . . . . . . . . . . . . . /

P1n*ALFA1 + P2n*ALFA2 + ... + (Pnn-1)*ALFAn = - P0n |

+

имеющую единственное решение независимо от того, является ли

рассматриваемая сеть разомкнутой или замкнутой.

Поскольку для разомкнутой сети интенсивность источника

заявок LAо известна, анализ стохастической сети сводится к

анализу совокупности независимых систем массового обслуживания

----

Si, i = 1, n, интенсивности входящих потоков которых LAi,

-----

i = 1, n выражены через интенсивность входящего потока сети

-----

LAо и коэффициенты передачи ALFAi, i = 1, n (рис. УП-14).


+-----------+

LA1 = ALFA1*LAо ----->|S1, m1, MU1|----->

+-----------+

...........................................

+-----------+

LAn = ALFAn*LAо ----->|Sn, mn, MUn|----->

+-----------+


Рис. VII-14


Каждая из составляющих сеть СМО представляет собой СМО без

потерь с числом каналов обслуживания mi, характеризующихся

интенсивностью потока обслуживаний MUi. Однако, разложение сети

на независимые СМО возможно лишь при условии существования

установившегося режима в каждой из СМО сети, имеющего вид


LAi

--------- < 1 (VII-65)

mi*MUi


Поскольку LAi = ALFAi*LAо, то (УП-65) приводится к виду


mi*MUi ----

LAо < --------, i = 1, n

ALFAi


Данное неравенство позволяет сформулировать ограничение сверху

на интенсивность входящего потока сети LAо из условия

существования установившегося режима в разомкнутой

стохастической сети

+ +

| mi*MUi | ----

LAо < min | -------- |, i = 1, n (VII-66)

i | ALFAi |

+ +


Если установившийся режим в сети существует, то для каждой

----

из составляющих сеть СМО Si, i = 1, n нетрудно найти показатели

- - - -

эффективности tожi, tсi, li, Ki, пользуясь, соответственно,

выражениями (УП-32) - (УП-35):


+ j (mi+1) +-1

| mi ROi ROi |

Роi = | 1 + SUMMA ------ + --------------- | (VII-67)

| j = 1 j! mi!(mi - ROi) |

+ +


(mi+1)

- ROi

tожi = --------------------------- * Роi; (VII-68)

(mi - 1)!*MUi*(mi - ROi)**2


- - --- -

tсi = tожi + TAUобi = tожi + 1/MUi

- -

li = tожi * LAi;

-

Ki = ROi; (VII-69)

----

i = 1, n


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

находятся показатели эффективности сети в целом:


- n -

tожi = SUMMA(ALFAi * tожi);

i = 1

- n -

tс = SUMMA(ALFAi * tсi);

i = 1

- n -

l = SUMMA(li);

i = 1

- n -

K = SUMMA(Ki);

i = 1

n -

- SUMMA(Ki)

K i = 1

PSI = ---------- = ----------

n n

SUMMA(mi) SUMMA(mi)

i = 1 i = 1


Пример.


Найти значение критерия эффективности вида


- n -

Е = еож*tож + SUMMA енi*(mi - Ki),

i = 1


где еожi - штраф за единицу времени ожидания заявки в

очередях,

енi - штраф за недоиспользование каналов обслуживания в

системе Si для разомкнутой вычислительной сети, изображенной на

рис. УП - 2, при следующих ее параметрах: 1) число СМО n = 3; 2)

число каналов обсдуживания, соответственно, m1 = 1, m2 = 1, m3 =

2; 3) интенсивность потоков обслуживания, соответственно, MU1 =

-1 -1 -1

2с , MU2 = 0,8с , MU3 = 0,1с ; 4) матрица вероятностей

передач

+ + + +

| 0 Р01 Р02 Р03| | 0 1 0 0 |

Р = |Р10 Р11 Р12 Р13| = |0,1 0 0,4 0,5|

|Р20 Р21 Р22 Р23| | 0 1 0 0 |

|Р30 Р31 Р32 Р33| | 0 1 0 0 |

+ + + +


5) интенсивность входящего потока сети LAо = 0,02с. Значения

штрафов принять равными, соответственно, еож =10 усл.ед./с,

ен1 = 20 усл.ед., ен2 = 10усл.ед., ен3 = 2усл.ед.

На основании матрицы вероятностей передач в соответствии с

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

алгебраических уравнений:


|(Р11-1) Р21 Р31 | | -1 1 1|

DELTA = | Р12 (Р22-1) Р32 | = |0,4 -1 0| = 0,1;

| Р13 Р23 (Р33-1)| |0,5 0 -1|


|-Р01 Р21 Р31 | |-1 1 1|

DELTA1 = |-Р01 (Р22-1) Р32 | = | 0 -1 0| = -1;

|-Р01 Р23 (Р33-1)| | 0 0 -1|


|(Р11-1) -Р01 Р31 | | -1 1 1|

DELTA2 = | Р12 -Р01 Р32 | = |0,4 0 0| = -0,4;

| Р13 -Р01 (Р33-1)| |0,5 0 -1|


|(Р11-1) Р21 -Р01 | | -1 1 1|

DELTA3 = | Р12 (Р22-1) -Р01 | = |0,4 -1 0| = -0,5;

| Р13 Р23 -Р01 | |0,5 0 0|


позволяющие найти коэффициенты передач сети

ALFA1 = DELTA1 / DELTA = 10,

ALFA2 = DELTA2 / DELTA = 4,

ALFA3 = DELTA3 / DELTA = 5.


Проверим условие существования установившегося режима в

рассматриваемой сети в соответствии с (УП-66)


+ +

| m1*MU1 m2*MU2 m3*MU3 |

LAо < min |--------, --------, -------- | =

| ALFA1 ALFA2 ALFA3 |

+ +


+ +

| 1 * 2 1 * 0,8 2 * 0,1 |

min|-------, ---------, ---------| = 0,04

| 10 4 5 |

+ +


Установившийся режим в сети существует, поэтому можно

перейти к определению необходимых показателей эффективности СМО,

составляющих сеть, принимая интенсивности входящих потоков

-1

заявок равными LA1 = ALFA1*LAо = 10 * 0,02 = 0,2с ,

-1

LA2 = ALFA2*LAо = 4 * 0,02 = 0,08с ,

-1

LA3 = ALFA3*LAо = 5 * 0,02 = 0,1с .

В соответствии в (УП-69) определим среднее число занятых

каналов обслуживания в каждой из СМО:

-

К1 = RO1 = LA1/MU1 = 0,2/2 = 0,1;

-

К2 = RO2 = LA2/MU2 = 0,08/0,8 = 0,1;

-

К3 = RO3 = LA3/MU3 = 0,1/0,1 = 1.


В соответствии с (VII-67, 68) определим средние времена

задержек заявок в соответствующих СМО при каждом обслуживании, ис-

пользуя вероятности простоя каждой из СМО:

Po1 = 0,9; Pо2 = 0,9; Pо3 = 0,333;

-

tож1 = 0,055с;

-

tож2 = 0,055с;

-

tож3 = 3,33с;


Учитывая коэффициенты передачи ALFA1, ALFA2, ALFA3,

имеющие смысл среднего числа обслуживаний, получаемых

----

произвольной заявкой из входящего потока в системе Si, = 1, 3 за

все время ее пребывания в сети, найдем среднее время ожидания

заявки в очередях


- 3 -

tож = SUMMA(ALFAi*tожi) = 10*0,055 + 4*0,055 + 5*3,33 = 17,42c

i = 1


Теперь нетрудно найти значение критерия эффективности

Е = 10 * 17,42 + 20(1 - 0,1) + 10(1 - 0,1) + 2(2 - 1) =

203,2 усл.ед.


2.4.2. Анализ замкнутых сетей массового обслуживания


Замкнутые сети характеризуются тем, что интенсивность

LAо является искомой характеристикой сети, причем число M

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

-----

сети. Коэффициенты передач ALFAi, i = 1, n могут быть

определены как решение системы уравнений (УП-64). При

определении характеристик замкнутой сети необходимо

рассматривать сеть как систему более высокого уровня сложности

по отношению к составляющим ее СМО и характеризовать ее

множеством состояний. Под состоянием сети понимается

совокупность чисел (z1, z2, ..., zi, ..., zn), характеризующая

распределение заявок, находящихся в сети, среди составляющих ее

----

СМО Si, i = 1, n: в системе S1 находится z1 заявок, в системе S2

- z2 заявок, ..., в системе Sn находится zn заявок. Заявки,

----

находящиеся в СМО Si, i = 1, n, в общем случае обслуживаются

каналами обслуживания или стоят в очереди на обслуживание. С

каждым возможным состоянием сети можно связать его вероятность

P(z1, z2, ..., zi, ..., zn).


В установившемся режиме вероятность состояния разомкнутой

стохастической сети равна произведению вероятностей состояний

составляющих сеть СМО, поскольку функционирование отдельных СМО

можно считать независимым:

n

P(z1, ..., zi, ..., zn) = П Pzi,

i=1


где Pzi - вероятность того, что в СМО Si находится zi заявок.

Для замкнутой сети не все возможные состояния совокупности

из n СМО без потерь, каждая из которых характеризуется

бесконечным числом возможных состояний (z1, z2, ..., zi, ...,

zn), удовлетворяющих условию


n

SUMMA(zi) = M = const (VII-70)

i = 1


Установившийся режим в замкнутой сети всегда существует,

----

поскольку длина очереди в произвольной СМО Si, i = 1, n не

превышает величины (zi - mi), то есть конечна.

Обозначим допустимое множество состояний замкнутой сети,

удовлетворяющее условию (УП-70), через A(M,n), а число таких

состояний через |A(M,n)|. Число допустимых состояний замкнутой

сети |A(M,n)| равно числу различных распределений M заявок по n

системам и равно числу сочетаний

M

|A(M,n)| = C

M+n-1


Например, если замкнуть сеть, рассмотренную в примере УП-7, и

положить M равным 3, то число допустимых состояний замкнутой

3

сети будет равно |A(3,3)| = С = 5!/3!/(5-3)! = 5!/3!/2! = 10,

5

а множество A(3,3) будет иметь вид (3, 0, 0), (2, 1, 0), (1, 2, 0),

(0, 3, 0), (0, 2, 1), (0, 1, 2), (0, 0, 3), (1, 0,2), (2, 0, 1),

(1, 1, 1).

Вероятность состояния замкнутой сети определяется выражением


+ n + + n +

P(z1, ..., zi, ..., zn) = | П Pzi| / | SUMMA П Pzi| (VII-71)

+i=1 + + A(M,n) i=1 +


где SUMMA - символ суммирования по всем допустимым состояниям

A(M,n)

замкнутой сети. Знаменатель в (УП-71) необходим для нормирования

вероятностей с учетом ограничения (УП-70).

Поскольку замкнутая сеть построена из СМО без потерь, для

определения вероятностей состояний отдельных СМО, входящих в

(УП-71), приведем выражения (УП-29), (УП-31) к виду