Geum.ru

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

Вид материалаЗадача
M LA = SUMMA LAi
SUMMA Pi = 1
Подобный материал:
1   2   3   4   5

ожидания tож в СМО поступает в среднем LA * tож заявок.

_

Среднее число занятых каналов обслуживания К равно

математическому ожиданию числа занятых обслуживанием каналов

обслуживания, являющегося случайной величиной, и характеризует

_

степень загрузки обслуживающей системы. Для определения К в

___

общем случае необходимо знание совокупности Рзанi, i = 0,m -

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

обслуживанием i каналов обслуживания. Важную роль в дальнейшем

играет загрузка PSI - вероятность того, что в произвольный момент

времени обслуживанием будут заняты все m каналов обслуживания:

_

PSI = К / m.

_

Среднее число заявок в системе Z представляет собой

математическое ожидание числа заявок, одновременно находящихся в

очереди или в канале обслуживания. Оно представляет собой

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

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

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

- - -

Z = l + K (УП-2)


Для СМО без потерь среднее число заявок в системе связано со

средним временем пребывания заявки в системе простым соотношением:

_ _ _ _ _

Z = l + K = LA * tож + LA * tоб =

_ _ _

LA(tож + tоб) = LA * tс (УП-3)


2.2. Разомкнутые СМО с пуассоновскими потоками событий.


2.2.1. Разомкнутые СМО с ожиданием (общий случай).


Рассмотрим СМО разомкнутого типа, содержащую m однотипных

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

___

распределением времени обслуживания со средним значением TAUоб

или, что эквивалентно, простейшим потоком обслуживаний с

___

интенсивностью MU = 1 / TAUоб независимо от типа обслуживаемой

заявки. При полностью загруженных каналах обслуживания заявки

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

равно n. Дисциплина ожидания - FIFO, заявки становятся

в очередь в порядке поступления, при переполнении очереди

вновь поступившая заявка получает отказ. Дисциплина обслужи-

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

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

на входе СМО относятся к одному из М типов, причем заявки i-го

типа образуют простейший поток с интенсивностью LAi

____

(i = 1, M). Поскольку рассматривается бесприоритетная СМО

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

поток, который будет также простейшим с интенсивностью

M

LA = SUMMA LAi

i = 1

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

пробыть в СМО не более TAUдоп единиц времени. Если время

пребывания заявки в системе tс превышает ТAUдоп, заявка покидает

систему и считается потерянной для системы. Нетерпеливость

заявок хорошо отражает свойство старения информации в

вычислительных системах реального времени. Будем считать ТAUдоп

случайной величиной, распределенной экспоненциально с

___

математическим ожиданием М(ТAUдоп) = ТAUдоп.

Удобной для дальнейшего рассмотрения абстракцией является

представление о простейшем потоке уходов из СМО с

___

интенсивностью NU = 1/ТAUдоп). Уходы заявки возможны либо из

очереди, если tож > ТAUдоп, либо из канала обслуживания, если

tож <= TAUдоп <= tс. Методически удобно рассматривать два потока

уходов с интенсивностями, соответственно, NUож и NUоб.

___

NUож = NUоб = NU = 1/TAUдоп


Определим основные показатели эффективности рассмотренной

СМО, пользуясь теорией непрерывных марковских цепей.

Возможные состояния СМО будем связывать с числом заявок,

находящихся в СМО:

S0 - в СМО нет ни одной заявки, каналы обслуживания

простаивают, очередь отсутствует;

S1 - в СМО одна заявка, ее обслуживанием занят один из

каналов обслуживания, другие (m - 1) канал обслуживания

простаивают, очередь отсутствует;

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

Si - в СМО i заявок, их обслуживанием заняты i каналов

обслуживания, другие (m - i) канал обслуживания

простаивают, очередь отсутствует;

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

Sm - в СМО m заявок, все каналы обслуживания загружены,

очередь отсутствует;

Sm+1 - в СМО (m + 1) заявок, все каналы обслуживания загружены,

последняя из пришедших в СМО заявок находится в очереди;

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

Sm+l - в СМО (m + l) заявок, все каналы обслуживания загружены,

l заявок находится в очереди (l - длина очереди);

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

Sm+n - в СМО m+n заявок, все каналы обслуживания загружены,

все n мест в очереди заняты ожидающими обслуживания

заявками, СМО в этом состоянии не способна принять

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

будут получать отказ (состояние "насыщения" системы).

Переходы между состояниями такой СМО будут происходить под

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

заявок из очереди или канала обслуживания, потоков обслуживаний.

Граф переходов, соответствующий описанной СМО, приведен на рис.


+----+ LA +----+ LA LA +----+ LA

| S0 +----->| S1 +-----> ... ----->| Si +-----> ...

| |<-----| |<----- ... <-----| |<-----

+----+ +----+ +----+ (i+1)*(MU+NUоб)

MU+NUоб 2*(MU+NUоб) i*(MU+NUоб)


LA +----+ LA +----+ LA

----->| Sm +----->|Sm+1+-----> ...

<-----| |<-----| |<-----

+----+ +----+m*(MU+NUоб)+2*NUож

m*(MU+NUоб) m*(MU+NUоб)+NUож


LA +----+ LA LA +----+

----->|Sm+l+-----> ... ----->|Sm+n|

<-----| |<----- <-----| |

m*(MU+NUоб)+l*NUож +----+ +----+

m*(MU+NUоб)+ m*(MU+NUоб)+

(l+1)*NUож n*NUож

Граф представляет типовую структуру НМЦ, известную в литературе

как "процесс гибели и размножения". Для такой НМЦ легко выводятся

выражения для предельных вероятностей состояний в установившемся режиме

(формулы Эрланга).

ЛАУ для предельных вероятностей состояний P0, P1,.., Pi,..,Pm, не

cвязанных с очередью, имеют вид:

-LA*P0 + (MU+NUоб)*P1 = 0;

-(LA+(MU+NUоб))*P1 + LA*P0 + 2*(MU+NUоб)*P2 = 0

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

-(LA+i*(MU+NUоб))*Pi + LA*P(i-1) + (i+1)*(MU+NUоб)*P(i+1) = 0

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

-(LA+m*(MU+NUоб))*Pm + LA*P(m-1) + [m*(MU+NUоб)+NUож]*P(i+1) = 0

Для состояний P(m+1),..., P(m+l),..., P(m+n), связанных с наличием

очереди, уравнения имеют вид:

-(LA+[m*(MU+NUоб)+NUож])*P(m+1) + LA*Pm + [m*(MU+NUоб)+2*NUож]*P(m+2) = 0

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

-(LA+[m*(MU+NUоб)+l*NUож])*P(m+l) + LA*P(m+l-1) +

+ [m*(MU+NUоб)+(l+1)*NUож]*P(l+2) = 0

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

-([m*(MU+NUоб)+n*NUож])*P(m+n) + LA*P(m+n-1) = 0

Выразим вероятности P1, P2,...., P(m+n) через вероятность P0. Из

первого уравнения получаем:

LA

P1 = --------- * P0,

(MU+NUоб)

из второго с учетом предыдущего выражения

2

LA LA LA

P2 = --------- * ----------- * P0 = -------------- * P0

2

(MU+NUоб) 2*(MU+NUоб) 1*2*(MU+NUоб)

и далее в общем случае:

i

LA ____

Pi = ------------------ * P0, i = 1, m;

i!*(MU+NUоб)**i

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

коэффициента, на который умножается вероятность P0, равен произведению

интенсивностей потоков событий, переводящих систему из состояния S0 в

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

переводящих систему их состояния Si в состояние S0.

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

состояний, связанных с наличием очереди:

m l

LA +-+ LA

Pm+l = --------------- * | | -------------------- * P0;

m!*(MU+NUoб)**m j=1 [m*(MU+NUоб)+j*NUож]

___

l = 1,n

Приведем интенсивности всех потоков к интенсивности потока

обслуживаний:

RO = LA/MU - приведенная интенсивность входящего потока,

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

СМО за среднее время обслуживания одной заявки;

ALFAож = NUож/MU - приведенная интенсивность потока уходов

из очереди;

ALFAоб = NUоб/MU - приведенная интенсивность потока уходов

из канала обслуживания.

Тогда получим

i

RO ----

Pi = -------------------- * Po, i = 1, m;

i!*(1 + ALFAоб)**i


m l

RO +-+ RO

Pm+l = ------------------- | | ----------------------------- P0;

m!*(1 + ALFAoб)**m j=1 [m*(1 + ALFAoб) + j*ALFAож]

___

l = 1,n.


Вероятность Р0 определяется из нормирующего условия

m+n

SUMMA Pi = 1

i = 0

и равна

+ i m

| m RO RO

Po =|1+SUMMA -------------------- + -------------------- *

| i = 1 i!*(1 + ALFAоб)**i m!*(1 + ALFAоб)**m

+

l +-1

n +-+ RO |

SUMMA | | -----------------------------|

l = 1 j=1 [m*(1 + ALFAоб) + j*ALFAож] |

+

Одним из важных показателей эффективности является среднее

_

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

зная распределение вероятностей состояний и связь номера

состояния с числом занятых каналов:

_ m m m m

К = 0 * Рo + SUMMA(i*Pi)+m*SUMMA(Pm+l) = SUMMA(i*Pi)+m*(1-SUMMA(Pi))

i = 1 l = 1 i = 0 i = 0

_

Аналогично средняя длина очереди l может быть определена на

______

основании распределения вероятностей состояния Pi, i = 0,(m+n)

и связи номера состояния с длиной очереди:

- m n n

l = 0 * SUMMA Pi + SUMMA l*P(m+l) = SUMMA l*P(m+l)

i = 0 l = 1 l = 1

Среднее число заявок в СМО:

_ _ _

Z = K + l.

В рассматриваемой СМО потери заявок возможны либо в форме

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

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

Вероятность отказа Ротк может быть определена как

вероятность нахождения системы в состоянии Рm+n, то есть

m+n

RO

Ротк = Рm+n = ----------------------------------------------- * P0

n

m+-+

m!*(1 + ALFAоб) | |[m*(1 +ALFAоб) + j*ALFAож]

j=1

Уход нетерпеливой заявки из СМО возможен либо во время

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

события как уход заявки из очереди и уход заявки из канала

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

представлена суммой

ож об

Ру = Ру + Ру (VII-9)

ож

где Ру - вероятность ухода заявки во время ожидания;

об

Ру - вероятность ухода заявки во время обслуживания.

Вероятность ухода заявки во время обслуживания можно

определить как отношение суммарной интенсивности ухода во время

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

-

К на интенсивность уходов из одного канала обслуживания NUоб, к

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

_

об К * NUоб

Ру = ----------

LA

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

_

ожидания через среднюю длину очереди l, интенсивность ухода

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

LA: _

ож l * NUож

Ру = ----------

LA

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

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

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

записать

ож об

Рп = Ротк + Ру + Ру


Вероятность обслуживания Роб, то есть вероятность появления

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

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

до единмицы:

Роб = 1 - Рп

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

о

потока СМО, как интенсивность потока обслуженных заявок LA :

о

LA = LA * Роб = LA*(1 - Рп)


2.2.2 Разомкнутые СМО с ожиданием и терпеливыми заявками


Рассмотрим теперь СМО с терпеливыми заявками и ограниченным

числом мест в очереди. В такой СМО возможны потери заявок лишь

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

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

на обслуживание.

Граф функционирования такой системы имеет вид:


+----+ LA +----+ LA LA +----+ LA

| S0 +----->| S1 +-----> ... ----->| Si +-----> ...

| |<-----| |<----- ... <-----| |<-----

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

MU 2*MU i*MU (i+1)*MU


LA +----+ LA +----+ LA

----->| Sm +----->|Sm+1+-----> ...

<-----| |<-----| |<-----

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

m*MU m*MU m*MU


LA +----+ LA LA +----+

----->|Sm+l+-----> ... ----->|Sm+n|

<-----| |<----- <-----| |

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

m*MU m*MU m*MU


Вероятности состояний имеют вид:


i

RO ----

Pi = ----- * Po, i = 1, m

i!


m l

RO RO ----

Pm+l = ----- * ------ * P0, l = 1, n

m! m**l

+ i m l +-1

| m RO RO n RO |

P0 = < 1 + SUMMA ----- + ---- * SUMMA ------ >

| i = 1 i! m! l = 1 m**l |

+ + .

Вторая сумма в этом выражении является суммой n членов

геометрической прогрессии с первым элементом и знаменателем,

равными RO/m, откуда следует:

+ i m n+1 +-1

| m RO RO RO/m - (RO/m) |

P0 = |1 + SUMMA ----- + ----- * ------------------ |

| i = 1 i! m! 1 - RO/m |

+ +


Распределение предельных вероятностей состояний позволяет

найти основные показатели эффективности СМО.

Вероятность потери заявки Pn совпадает с вероятностью

отказа Ротк и равна вероятности нахождения СМО в состоянии Sm+n:

m+n

RO

Pп = Pотк = Pm+n = -------- * P0

m! * m**n

Вероятность обслуживания Роб и интенсивность потока

о

обслуженных заявок LA определяются, соответственно,

выражениями

m+n

RO

Pоб = 1 - Pп = 1 - --------- * P0;

m! * m**n


+ m+n +

o | RO |

LA = LA * Роб = LA * | 1 - -------- * P0 |

| m! * m**n |

+ +


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

рассмотренной ранее структуры СМО согласно выражению:


- m n

К = SUMMA i*Pi + m*SUMMA P(m+l)

i = 0 l = 1


Более удобно определение среднего числа занятых каналов как

o

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

интенсивности обслуживания MU, характеризующей

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


o + m+n +

- LA LA*Роб | RO |

К = ---- = ------ = RO * Роб = RO * | 1 - --------- * P0|

MU MU | m! * m**n |

+ +

-

Найдем теперь среднюю длину очереди l:

m l

- n RO n RO

l = SUMMA l*P(m+l) = --- * P0 * SUMMA l* ----- (1)

l = 1 m! l = 1 m**l


Далее определяется срелнее число заявок в СМО

- - -

Z = K + l

Перейдем к определению временных характеристик.


Важным показателем эффективности СМО с ожиданием является

-

среднее время ожидания заявки в очереди tож, характеризующее

запаздывание заявки за счет наличия в СМО других заявок. Для

-

определения tож сформулируем возможные гипотезы о том, в каком

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

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

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

Если заявка застанет СМО в одном из состояний S0, S1, ...,

Sm-1, ей вообще не придется ждать (tож = 0), так как для этих

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

канала, следовательно, задержка отсутствует и обслуживание

заявки будет начато немедленно. Застав СМО в состоянии Sm, когда

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

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

одном из каналов обслуживания. Суммарный поток обслуживания при

полностью загруженных каналах складывается из m простейших

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

---

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

будет характеризоваться средней длительностью обслуживания

---

TAUоб/m и интенсивностью обслуживания m*MU. Вследствие от-

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

время ожидания заявки в рассматриваемой ситуации равно в среднем

1/(m*MU), причем вероятность этой ситуации равна Pm. Застав СМО

с вероятностью P(m+1) в состоянии S(m+1) (все каналы обслуживания

заняты, в очереди одна заявка), вновь прибывшая заявка займет

второе место в очереди и должна будет ждать в среднем 2/(m*MU)

единиц времени, и т.д. Последнее состояние, находясь в котором

СМО еще способна принять заявку в очередь, S(m+n-1) имеет веро-

ятность P(m+n-1), время ожидания заявки, заставшей СМО в состоянии

S(m+n-1), равно в среднем n/(m*MU). Время ожидания заявки, застав-

шей СМО в состоянии S(m+n), равно нулю, так как заявка получает

отказ и является потерянной для СМО.

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

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

времен ожидания, связанных с различными гипотезами:


- m - 1 1 n - 1 (l + 1)

tож = SUMMA 0*Pi + ---- * Pm + SUMMA ------- *P(m+l) + 0*P(m+n) =

i = 0 m*MU l = 1 m*MU


m l

n - 1 (l + 1) RO n - 1 RO

= SUMMA ------- Pm+l = --------- * Р0 * SUMMA (l+1) * ----- (2)

l = 0 m*MU m! * m*MU l = 0 m**l


Сравним выражения (2) и (1). Существует связь между этими

двумя характеристиками:

- -

l = LA * tож


Определим среднее время прибывания заявки в канале

обслуживания.

Время пребывания в канале обслуживания tоб - случайная

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

различные возможные ситуации. Если заявка застает СМО в

состоянии Sm+n, вероятность которой равна Pm+n = Pотк, время

пребывания ее в канале обслуживания равно нулю, поскольку заявка

получает отказ и тотчас же попадает в выходящий поток СМО.

Застав СМО в любом другом состоянии, что происходит с

вероятностью 1 - Pm+n = 1 - Pотк = Роб, заявка попадает в

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

в рассматриваемой СМО отсутствуют, непременно проходит

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

данной ситуации равно случайной величине, распределенной экспо-

---

ненциально со средней длительностью обслуживания TAUоб.

Теперь нетрудно найти среднее время обслуживания