книги из ГПНТБ / Приоритетные системы обслуживания

Hh(t).

Чтобы формулы (1.4) — (1.6) были

верны

и для указанного случая,

будем

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

лишь

после окончания своего про­

cofe(s, t) = !Ae~swk{t).

(1.8)

Т е о р е м а

2.

При

прямом

порядке

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

вызовов

приоритета k

a) wh(t) задается

формулами

>k

(s, t) = e^~ak+ak"k^V

{1 - s je

- t * - « * + p 0

(*) dx

-

0

_

( 1 -

Я й

_ , (s)) j

e - l s - a b + a k * b ( s

) l x Pt

(x) dx} ;

(1.9)

0

oo

f

е-** Рг

(t)dt={l

— л*_, (s -f - ak-aknkk(s))}-'

{1 -

0

oo

-

(s f

ak -

aknkk

(s))$er«PQ(t)dt};

(1.10)

0

oo

j

er« P0

(t) dt ^ [s f ak

-

aknk

(s)]-';

(1.11)

б) существует

предел

®k(ùk(s)s =

lim (ùk(s,

t)

1 — akhkL

s + a f e - 1

— ok_xnk_x (s)

(1.12)

1 +

° Ѵ - і л

й - п

s —ak +

akhk(s)

Теорема 2 следует из теор. 1, § 2, гл. 2.

Т е о р е м а

3. При инверсионном

порядке

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

вызо­

вов приоритета k <ЙЙ(5,

t) вычисляется

по

формуле

(s, t) = Р0 (t) +

f P, (и) du

f é-*+°k-*k*kk№+"-'>

d n é _ , (V) -T-

11=0

V=:t—U

t

OO

j

P..{u)du

l

е-{$+аь-а^ш»+»-»аНк(ѵ),

(1.13)

где Pu(0

и

P\(t)

те же,

что и в

теореме

2, а Р г ( 0 определяется

из

соотношения

оо

со

s

\ e-siP0(t)dt

-г

(1 — л ц ф )

\erstPx{t)dt

+

о

о

( l - V ( s ) )

f e - ^ P , ( 0 ^ =

I -

(1-14)

ô

Теорема 3 получена из формул

(7.18)

и

(7.20)

гл. 2.

Стационарное распределение времени ожидания вызовом прио­

ритета k

при

инверсионном

порядке

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

немедленно

определяется

из теорем

1 и 2 § 9 гл. 2.

Т е о р е м а

4.

Преобразование

Лапласа

— Стилтьеса

от ф. р.

времени

ожидания

вызовом

приоритета

k в

установившемся

режи­

ме работы

равно

о)А. (s)

р0

• pl

•

+

nk~u

[s +

ak

—

akttkk(s)]

. : . p

! - * * » ( » )

F

( L 1 5 )

hkl

[s + ak

— ak^kk (s)J

где

(

L 1 6 )

p2 =

a A i -

(!-18)

З а м е ч а н и е .

В

теоремах 3 и 4 считаем, что

прерванный вызов

приори­

тета

k не

пропускает

вперед себя вызовов

одного с

ним приоритетного

класса.

Г. Условия

существования

стационарного

распределения.

Выпишем

условия

существования

стационарного

распределения

для

различных схем

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

с абсолютным

приоритетом

(условия

для &-того потока).

С х е м а

1 : дообслуживание прерванного

вызова

а і р п + . . .

f a k ß k

l < l ;

(1.19)

С х е м а

2: потеря прерванного

вызова

«ißn

;

~

П -

ß 2

К ) ] + • • • + -

^ -

[1 -

ß * ( о . - , ) ] <

i ;

(i-20)

С х е м а

3: а)

неидентичное обслуживание заново

«ißii-i- —

Г —-

l ] + - + - g ^ r

. J

. — l " l <

1;

(1.21)

0

l

[ ß2(0-!)

J

.ßftK_,)

J

'

б)

идентичное обслуживание заново

-г

- - - 4 M --о",)

U

•••

[ Р , ( - а / г _ 1 ) - 1 ] < 1 . (1.22)

Ol

§ 2. Совместное распределение виртуальных времен ожидания

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

А. Введение. В §

1 этой главы

виртуальное

время ожидания

—>

-*

для вызовов &-того потока в системе

M r | G r | l | o o

с разновидностя­

ми абсолютного приоритета получено в терминах

преобразований

Лапласа сведением системы

к системе

M | G | l | o o

с ненадежным

в свободном состоянии

прибором.

—»

—*

В настоящем параграфе

для

системы

M r | G r | l | o o с

дообслу-

живанием вытесненного вызова

находится

совместное

г-мерное

распределение виртуальных

времен ожидания

вызовами

разных

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

Б. Обозначим через wk(t)

промежуток времени, начинающийся

Поток катастроф г-того типа

— пуассоновый с

параметром

Si(Si>0).

Положим

О, s' = S;

sr

(i = 1, r);

функция sw(t) — скалярное произведение

векторов

s=(su...,

sr)

(2.1)

a

— знак свертки. Значение ïh(t)

задается

формулой

(2.1) гл. 3

при

r = k. Вызов называем і-плохим,

если за

время его

обслужи­

следних

(г—типов.

является {-пло­

С вероятностью

ßj(s') вызов

приоритета / не

хим. Вызов приоритета /—і-плохой

с вероятностью

1—ßj(s'). Поток

і-плохих

вызовов

приоритета /

— пуассоновый

с параметром

а3{1—ßj(sx)].

В то же время, ввиду того что суперпозиция независи­

j ^ a j l - ß ^ ) ] .

Соотношение (2.3),

переписанное в виде

г

е

1 = 1

--•= e~s4(ù(s,

t)

+

г

+ 2

JPf c (*)e

à

d [ l - e

- < s l

- s ^ ] ( l - ô t t ) ,

fr=0

о

му не поступали і-плохие

вызовы

приоритета

і(і=\,

г)

(вероят­

ность того, что для фиксированного

і за время t не поступят

{-пло­

хие вызовы приоритета і, равна ехр{—а^(1—ßi( s i ))0»

а ввиду

не­

зависимости і-плохих

вызовов

приоритета

і при

различных

і

иско­

мая вероятность

равна

П exp { - M

l - ß 4

(s'№

=

exp

{ - 2 a L

( l -

ßt

(s')) t) .

i=l

i=l

Для этого необходимо и достаточно, чтобы

либо

катастрофы

г'-того

типа

( г = 1 ,

г)

не

наступали

ни

за

г

время

t

(вероятность

|~] ехр {— stt}

=

exp

{—s1 *}),

ни

за

время

_

'

; =

1

_

oûj(^)

(вероятность

C Ù ( S I ,

. . . , sr;

t)—(ù(s,

t));

либо

в момент

х

наступила

первая катастрофа из

суммарного

потока катастроф всех типов (вероятность d[\—ехр{—slx}]);

си­

стема была свободна от вызовов

(вероятность

Ро{х)),

за

время

t—x

не

поступали

і-плохие

вызовы

приоритета

і,

t = l ,

/'

вероятность ехр | — ^

аі

( 1 — ßi (s 0)

— *)}) î

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

из сум­

марного потока катастроф первых k(k—\,

r—l)

типов

(вероятность

d[l—ехр{—(s1 -—sf t )x}])

и

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

вызов

приоритета

& + 1

(вероятность />Й+І ( Х ) ) , а за время

^—х не поступали

і-плохие

вы­

зовы

приоритета

г" (г = 1, г)

г

вероятность

ехр | — V

а{

( 1 — ß,- (s1))

(t

— л)j j .

Промежуток

времени

с момента

окончания

периода занятости

роятность того, что в момент времени t либо

система свободна,

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

k.

Для этого необходимо и достаточно, чтобы

либо

в момент u(u^t)

закончился п-ный k-этап (п~^\)

и

за

время /—и не поступали вызовы приоритета k и выше,

либо

вызовы приоритета k и выше не поступали за

время

t.

Соотношение

(2.4) очевидно. Формулы

(2.3) —

(2.5)

доказаны.

З а м е ч а н и е .

При подстановке в формулу

(3.3) Sh—s,

s\—

...

=Su-\

=

— Sh+\—

. . . = S r = 0 получаем

в преобразованиях Лапласа формулу

ft

[ s - V a ; ( l - ß ; ( s ) ) J n

(û A (s,

t)

=--: M e - S t 0 * ( < )

= e

' = 1

X

ft

x f l

- s

j Nk(x)e

г

= 1

( 2 . 6 >

ô

Преобразование Лапласа

от

функции Nh

(г)

можно получить

из уравнения (2.6) :

Г. Действительно, при

s > 0 ввиду

(2.2)

выполнено

s - J ]

fl/(l-fc(s))>0

1 , г ) .

Тогда при s > 0 ,

? > 0 ,

expjj^s—

£

щ (1 — ß; (s))

j

возрастает до

бесконечнос-

i = i

_

ти,

когда /-»-)-<хз, а

так

как в левой

части

ü>k(s,

t),

как вероятность

того,

что

за Wk{t)

не

наступила

катастрофа,

ограничена,

то

ft

jW f t (>:)e

"

i = i

d„ =

s-i.

;(2.7)

Полученное

уравнение

(2.7)

после

подстановки

s — £

а

і ' 0 —

ßt (s))l=

S

н а основа-

нии

уравнения

(2.1) гл.

3

переходит

в

искомое

i—i

j

e~SK

Nk

(x) dx

=

[s +

0FE

-

o-ftrtft

(5)] - i .

(2.8)

ô

Тогда из

(2.8)

и

(2.4)

имеем

j " e~sx

p ft M

dx

=

[s

[- o A _ !

—

с

т

^

я

^

(s)] - 1

—

Ö

- [ s - j - ( r t - a № ( s ) ] - i ,

при 6==2\7 ;

(2.9)

ОО

\

P0

(x) dx

=

[s 4- 0,

— оѵя,- (s)]

-

i .

(2.10)

о

2°. Соотношение (2.7) выводится также

из следующих соображений. Функ­

ция

Nk(x)

соответствует

вероятности

того,

что

в

момент

х

система

свободна

от

вызовов

для

аналогичной системы,

в которую

поступают

лишь

первые

k—1

потоков,

что

в

свою очередь

равно

той

же

вероятности

для

системы

MIG111 оо, причем

входящий

поток является

суперпозицией этих

k—1

потоков

(пуассоновый

с параметром Ол-і),

а ф. р. длительности обслуживания

равна

ft—1

i=\

Наконец,

вид функции со (s, t)

не зависит

от порядка

обслуживания внутри каж ­

дого приоритетного класса.

со (Sj, s2,

. . . , sr;

t)

=

со (s,

t)

= Me

r r

.

(2.11)

В частности,

(ùk (s,

t)

Mé~SWk^.

(2.12)

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

венство

co(s, t) = (o(sl f s2,

-f o1

— o1n1(s),...

, s r

+

ar_i — а,_іяг _і (s);

(2.13)

В частности,

cûft

(s, 0 = cofe

(5 - f ov_! — стй -іЛе-і (s); t).

(2.14)

Формулы для co(Si,..., sr;

t),

tùk(s,

t)

выписываются на

основании

(2.3),

(2.13)

и (2.6),

(2.14). Для

этого

в

(2.3)

и

(2.6)

заменяем

Si + Oi-i—Ci—iJtt—t (s) на 5

и s + ok-i—-.ou-i

Лк-i (s)

на

5.

Формула

для cofc(s, t)

имеет вид

m f c ( S | /) =

e-['s-aft+aftßft(s+aft-i-Oft-i^ft-i(s»^

x

X {1 -

(s ~

-

а*_ія*_, (s))j > Ä

(x)e -[ s -a ft+a ftp fc( s + ö ft-

- W f t - ^ » ^ } .

(2.15)

Найдем

распределение

времени

ожидания

в

установившемся

режиме для вызова приоритета k.

Положим

Llfe =

S +

Oft-! — Ok-iKk-l

(s).

(2.16)

Из формулы

(2.15) по правилу Лопиталя

выводим

coft(s) =

lim cöft(s,

t) =

H

lim Nk{t).

(2.17)

s — afc +

aftßft ([.ift)

/ - и - »

Из формулы (2.9)

и уравнения

(2.1)

гл. 3 находим

lim Nk

(t) =. lim s Г e~sx Nk

k

(x) dx ------ 1 — Y aßa.

(2.18)

Следовательно,

k

<M*)^

Т Т Г Т "

( 2 Л 9 )

§ 3. Метод вложенных цепей Маркова для схемы 2

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

ме­

пребывания на приборе вызова приоритета

k

обозначим

через

bk(s)

(k=ï,

г).

Производящую

функцию

от распределения

числа

вызовов, поступающих в систему за время

пребывания

вызова

приоритета k

на приборе, — через

Бк(х)=Бк(хѵ

...

,хг).

Для нахождения bk(s)

и

Bh(x)

(k=l,

г)

построим

функции

БЬк(х;

s) такие, что

Бѵк{\;

s) =

bk(s),

Bbk{x;

0)^Ek(x)

(k

=

T7?).

Л е м м а

1. Функции

Ebh(x,

s)

определяются

соотношением

Bbk

{x; s) =

ßf e (s + a - okx)

f [ 1 -

ßf t

(s +

0 -

akx)}

s-t

, g f e - ' *

akx

,

(3.1)

er —

где,

как и

ранее,

г

k

г

а = £ ak, okx = £ апхп,

akx = £

апхп.

k=\

л = 1

n=k

Д о к а з а т е л ь с т в о .

Справедливость

леммы

1 легко

прове­

ряется с помощью дополнительных

событий,

если

считать, что

Ebh(x;

s)

есть

вероятность того, что

за

время

пребывания

вызова

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

разве

лишь красные

вызовы.

С л е д с т в и е

1. 1) Преобразования Лапласа—Стилтьеса

от

ф.

р.

вре­

мени

пребывания на

приборе

вызовов

приоритета

k,

k = \,

г

для

схемы

2

опре­

деляются соотношением

М * ) =

Б М 1 ; s ) =

ß f c ( s - r - o V i ) + [ l - ß f t ( s

+

0Ä.i)]

•o-fc-i

2) первые

два момента

равны

[ l - ß * ( o * . i ) ]

( Ä > 2 ) ,

• [ b f t i - C * ]

( f t > 2 ) ,

где

C f e = f te

d ß f t ( r ) .

С л е д с т в и е

2. Интересно заметить, что введенные в

§

3

гл.

3

обозна­

чения

рді И Pk2 для схемы 2 примут

более компактный

вид:

k

я = 1

Pft = 1 —

Pfci,

Pr =

P .

(3.2)

ft

Pfcä =

^

« Я

&Л2

Ря-1 . Po =

1 •

я = 1

С л е д с т в и е

3.

і) Производящая

функция

Б ь ( х ) ,

k =

2,

г имеет

вид

Б* (x)

=

ßft (о -

a* x)

- j - [1 - ßft (о -

о* x)]

*

,

а —

акх

дЪк (х)

[ l - ß * ( a - o * * ) ]

(л < ft);

дхп

акх

а —

дѣ/г (х)

,

— о*х)

а

—ах

(n>k);

—

-

= апрк(а

а — аях

[ l _ ß f c ( o _ a * x ) ]

(3.3)

дЬг(х)

ßj (CT —

ox)

= ап

дхп

при

xn =

1 (n = I , л), т.

е. равно ап Ькі-

Б. Занумеруем вызовы в порядке их

пребывания на

приборе

и

рассмотрим

состояния

системы

в моменты, когда вызовы поки-