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

Откуда

Ä

=

? i L b i L

.

(3.14)

1 — РА—и

Теперь, если akhkl<^\,

то из (3.14)

- ^ [ 1

—ßf e (°ft-i)] <1 — Pft - u

И Р Й < 1 .

Мы доказали не только утверждение пункта б), но и получи­

ли п!{\.

Имея hki, легко вычислить по (3.13) яь _ ц .

§

4.

Системы с прерыванием. Схема 3 (обслуживание заново).

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

Т е о р е м а

1.

Для

схемы

3 с

неидентичным

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

заново

а)

К (s) =

ßf t (s +

oÉ _0

j 1 -

J1 _

ßf c (s +

fffc_0]

(s))'1 -

(4.1)

о й я й

(s) -

а х я А 1 (s) +

. . . H - aknkk

(s),

(4.2)

я** (s) =

ftfc

(s - f aft — aknkk

(s)),

(4.3)

«fc< (s) =

я*-» (s - r ak — aknkk

(s)),

(4.4)

причем

эта система

рекуррентных

функциональных

уравнений

определяет единственные

функции

hk(s),

nki(s),

n,k(s),

t = l , k,

k—\, г, аналитические

в

полуплоскости

Res>0,

в

которой

|ftfc(s)|<l,

\nhi(s)\<i,

|jtft(s)

I < 1 ;

б)

если

fllßu

+ - ^ - Г—

11

... + -

^ -

Г 1 Г Т І — -

—

11 <

1, (4.5)

mo

hk-\-\ (0) =

яе { - (0) = nk (0) = 1 ; в противном

случае

0 < й А + , ( 0 ) < 1 , 0 < я / г і . ( 0 ) < 1 , 0 < я й ( 0 ) < 1 ;

в)

положим

ï

р*1 = a l ß l l +

—

M

Ol

6 Зак. 64

ftl

рк„ =

о

,

0

I

c^sPi

...

ckakpk__[

Рі(рі — р2 )

алр,9

+

I

{

„ г о / — М О

Г О / —

\ 1 9

h

I К й

I I 14

1

_

1

Pfe-l (Pfe-i — PA)

(PI — Ра)2

(pfe_i — p*)2

)

1

I • • *

Г~

/ ï

стА_!

а2

ak

j

=

(4.6)

< №

= %

(4.7)

Pk

h

1

( 4 - 8 )

h < o ^ - - \ | '

»

_

і

] П + J ^

L

. _ L

[ 1 П

1 _

- i l

. (4.9)

ak-\Pk-\

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

т е о р е м ы

1.

Пусть

за

промежуток

времени, начинающийся

с

момента

начала

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

вызова

тета выше k

(напомним еще,

что вызовы одного приоритета об­

служиваются

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

порядке), не произошла

катастрофа

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

чего есть

hh(s)).

Для этого необходимо

и

достаточ­

но, чтобы

либо за

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

пило «нежелательное»

событие следующего суммарного

потока

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

ßf t (s+'CTf t

_,)) ;

приоритета

k произо­

либо за

время обслуживания вызова

шло «нежелательное»

событие (вероятность

1—%(s + Oh-\)),

при­

чем таким «нежелательным» событием оказалось

появление вызо-

ва приоритета выше k

вероятность

,

и для

того

что-

К (s)

=

ßf t (s +

а,-!)

+

[1 -

ßf t

(s + о*-!)]

° k ~ l

я*_, (s) hk (s),

s +

°k-i

т. е. доказана

формула

(4.1).

" Остальные соотношения ничем не отличаются от аналогичных

соотношений,

приведенных

в

теореме

§

3.

Дальнейшие

рассужде­

ния проводятся по обычной схеме.

Подобные результаты имеют место и в случае идентичного

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

заново. Они приводятся

ниже

без

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

Т е о р е м а

2. Для

схемы

3

с идентичным

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

за­

ново:

а) рекуррентные

соотношения

ОО

hk

(s) -

f erb+°k.J*

Г 1

^ = L _ (1 -

e - (

s + ( W ) Я А _ , (s)]"1

dBk

(X)

(4.10)

и

система

(4.2) — (4.4)

определяют

единственные

функции

hK(s), ,

nki(s),

nk(s),

i = l,k,k—\,r

вполне

монотонные

при

s > 0 ,

для

которых

I hk

(s) |

<

1,

I яы

(s) | < 1,

| nk

(s) | <

1

при

Re

s >

0;

б) если ß„- (s) аполитичны

в

правой

полуплоскости,

содержащей

прямую

Re s =

— Oj~i,

j =

2,

k,

и

flißu +

+ . . . +

[ßA ( _

afe) -

1 ] <

1,

mo rtfe+i (0)

= nkt

(0) =

я к

(0) =

1 ;

в противном

случае

0 < r t f e + 1 ( 0 ) < l , 0 < л ь . ( 0 ) < 1 ;

0 < я , ( 0 ) < 1 ;

в)

положим

Р*і -

ßißu

+

- J -

[ß8 ( -

-

1] + . . .

+

[ß2 ( - аЛ ) -

1];

Pfc2 = «lßl2 +

j

P l ( P l

—

P 2 ) .

,

Pfc_l (Pfe_i

— Pfe)

2

°1

a 2 ( C 2 + 2 ß 2 1 ) P l

^ ( С і + г р ^ р ^

a 2

[ ß a ( _ 2 a 1 ) - 2 ß , ( - o r 1 ) + l ] +

С, = §іеаі-і*

dBt(t).

о

Пусть ßj (s) аналитичны

в правой

полуплоскости,

содержащей пря­

мую Res = —о,--! (/ = 2, k) и

pfti<I .

Тогда

<ѴЪі

-P*L;

(4.11)

ЗД2==-^-;

(4.12)

л * ^

5 - 4 —

№« ( - а * - 0 - 1 ] ;

(4•1 3)

ufe—î^ft—î

+

№ « ( -2 < " - i ) ^ 2 P» ( - <"-•) - 4 } •

<4 -14 >

§ 5. Совместное распределение периода занятости и числа

обслуженных за этот период вызовов

А. Обозначения

и определения.

Напомним,

что

ßi-периодом

называли

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

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

вызовов приоритета

k

и выше, начавшийся

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

вызова

приоритета i

(i=\,k).

Введем некоторые предварительные обозначения, годные для

всех схем. Пусть в момент

^о = 0 начался период

занятости

(какой-

либо

схемы);

ф(« ь

nr, t)

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

период за­

нятости

(г-перирд)

было

обслужено

пх

вызовов

приоритета

1,

Пг вызовов приоритета

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

длился вре­

мя

фь(«ь

пи,

t)

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

того, что за

fe-пернод

было

обслужено П\ вызовов

приоритета 1,

nk

вызовов

приоритета

k,

что ^-период начался с обслуживания вызова приоритета i

(i—\,k)

(ßt-период),

то указанную вероятность обозначим через фй,-(«і, ...

nh; t).

Обозначим еще через

Hk(n\,

nh-\\

t) вероятность

того, что за

промежуток времени,

начавшийся с

момента

поступ­

зовов

приоритета

1,

пи-\ вызовов приоритета

k—1,

причем

этот

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

zT)

и п =

Если

имеются

два

вектора

размерности

r ( z = ( z b

=

(П\,

пт)),

то

положим

. . . znTr =

г";

\п\

=пх

-\-

. . .

+

пт.

Составим

производящие

функции

Ф(г; t)

=

£

ф (n t , ...,n,;t)г,"'

. . . г ? '

= ^ ] ф ( л ;

0z»;

(5.1)

| л і >0

л > 0

Ф* (г; 0:=

£

Ф/е ("і,

...

,nk;t)z1l...

ф

= £фк(п;

t) г«;

(5.2)

ІЯ|>0

п>0

Ф « (г; 0

=•• £

Ф« К ,

• • • , Ч;

t) zï . . .

znkk =

J

ф „ (п; t) г»;

(5.3)

ілі>0

я > 0

Я , (г;

* ) = * * £

НЦп^

0 2? . . .

^

-

2fc £

Я ,

(я;

0 2".

|n|>0

л > 0

(5.4)

Каждый вызов приоритета і будем считать красным

с

вероятно­

стью

Zi и синим

с дополнительной

вероятностью 1—г* независимо

от

цвета

остальных

вызовов.

Тогда

ф ( я 1 (

. . . ,nr;

t

) . .

.

zjjr

есть вероятность того, что за период занятости

(г-период)

было

обслужено п\

вызовов

приоритета

1,

пг вызовов приоритета

г;

все

эти

вызовы

— красные

и

r-период

длился

время

Ф (z,

t)

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

того, что за

r-период были обслужены лишь

красные

вызовы,

причем /"-период

длился

время

Вероятностную интерпретацию можно дать и

функциям

Oh(z,t),

Фы(г,

t)

и

Hhfat).

Oh(z,t),

Фм(г,

t)

и

H~k(z,

t)

имеют тот же смысл, что и Ф(г,

t), но для ^-периода,

fei-периода

и

промежутка

времени,

начинающегося

с поступления в свободную

от

вызовов систему вызова приоритета

k

и кончающегося первым

оо

ф(г; s)•=

j e - s ' d Ô > ( z ; t),

s > 0 ;

(5.5)

о

00

ф й (z; s) =

j e-«dÔ>k

(z; t),

s >

0;

(5.6)

oo

фА і . (г; s) =

j er* аѢы

(z;

t),

s >

0;

(5.7)

hkt (2; s) = J e-s< dtffe (2; 0, s > 0.

(5.8)

ô

тастрофы,

поток

которых

является пуассоновый

с

параметром

s>0; ф(г; s)—вероятность

того, что за период

занятости

не на­

ступали катастрофы и обслуживались лишь красные

вызовы. Ве­

личины

фй(г; s),

фы(г; s),

hu{z; s)

имеют тот же смысл,

что и

ф(г; s),

но за ^-период, £і-период, промежуток времени, начавший­

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

приори­

тета k и кончающийся первым после этого моментом

освобожде­

ния системы от нашего вызова приоритета k и вызовов

приоритета

выше чем k.

Основываясь

на

вероятностной

интерпретации

указанных

функций,

аналогично

доказательству

теорем о

периодах

занято­

Б. Т е о р е м а

1. а)

Функциональное

уравнение

для

схемы

4 и 1

г

оф (z; s) =

V atzßt

(s + о -

аф (z; s))

(5.9)

определяет

единственную

функцию

(z; s),

аналитическую

в обла­

сти Re s>C,

| 2 і | < 1 ,

(zr)

< 1 ,

в

которой

|ф(2; s) | < 1 ;

б) если

a i ß n + ... + a r ß r l ^ l ,

то ф ( 1 г ; 0) = ф ( 1 ,

1; 0) = 1;

в противном

случае

ф ( 1 г ;

0) есть единственный

корень

уравнения

p =

2 a , M a - a p ) ,

(5.10)

лежащий в (0, 1);

в) пусть

а$п

+

. . . + a r

ß r l

<

1;

положим

Рі = a i ß l l + • • • Г ar$rv

р2

= ßißi2 +

• • • + a r

ß r 2 .

Рз = а$ія + .. • + a А з .

P =

1— Pii

тогда первые три

момента

числа

обслуженных

за период

занятос­

ти вызовов приоритета

&ф<А), фр,

ф^> равны.

ф < * > = ^ 4

(5.11)

(5.12)

Фіх) =

«ftp!

.

3

aftßftiP2

.

4?з

,

agßli

2ap5

2

ap*

бстр4

op

2cp3

2ap3

op2

6ap

6.

(5.13)

1

1

З а м е ч а н и е

1.

ф(г;

0)

является

производящей

функцией

числа

обслу­

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

вызовов.

З а м е ч а н и е

2.

иначе

можно

получить

из

следующих

соображений.

Из § 2 настоящей главы средняя длина щ периода занятости известна.

Проме­

жуток времени между

двумя

соседними

освобождениями системы от

вызовов

пуассоновости суммарного поступающего

потока вызовов (всех

приоритетов)

равна I/o и

из средней длины периода занятости. Тогда средняя

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

регенерации

равна

Рі

, 1

1

ap

а

ар

1

ф{*> =

а к - ар '

что совпадает с (5.11).

В. Т е о р е м а

2.

а)

Система

функциональных

уравнений

для

схемы

2

І К (2;

s) = zkPk

(p

f

0ь_і) f

P "Г Ok-l

[1 — ßft (s

+

-t-

Ok-i)] фк-і (z; s)

(5.14)

Фйк(г; s) = hK(z,

s +

aft

— ak$kk

(z; s)),

(5.15)

Ф*і (г ; s ) = Фк~и (z, s + aK

— аккфкк(г;

s)),

i<Zk

(5.16)

°кФн (z; s) = ахфк1{г;

s) +

. . . + акфкк

(z; s)

(5.17)

определяет

единственные

функции

hk (z; s); фы

(z; s); cpK (z; s), i — 1, k ;

é = l , r

аналитические

в

области

Re s >

0;

| гг

\<C I, • • . , \zk

К

1,

где

\hk(z;s)\<l,

I ф А /

(z; s) К

1, | фк | (г; s) | <

1;

б)

если

P*i = flißn + - ^ - [ [ 1

-

ß, К ) ]

f

. . • +

- ^ - [ 1 -

ß* (aÄ _,)] <

1,

0<hk+i(lr;

0 ) < 1,

mo hk+i(lr;

0) =

ф ^ О ' ; 0) =

фк(1г;

0) --=

I ; в

противном

случае

0 < Ä * + 1 ( 1 ' ; 0 ) < 1 , 0 < ф , ( . ( 1 л ; 0 ) < 1 , 0 < ф А ( К ; 0 ) < 1;

в)

если

pf c l <

1 u pfc -= 1 — p k l

,

то

(5.18)

АЙ =

M

* (о*-,) +

[1 -

ß* (ал-i)].

(5.19)

Здесь

обозначено:

ф$,

Aj^> —

среднее

число

вызовов

приоритета

j ,

обслуженных

за

k-nepuod

и за

промежуток

времени,

начавший­

ся

с поступления

в

свободную

от вызовов

систему

вызова

приори­

тета k и кончающийся

первым

после

этого моментом

освобождения

системы

от нашего

вызова

приоритета

k

и

вызовов

приоритета

выше

чем

k;

öjh — символ

Кронекера;

аи-\ — а\+ • •• + « А - Ь

Г. T е о р e M а

3.

а)

система

функциональных

уравнений

(5.15) — (5.17)

для

схемы

3

(неидентичное

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

заново)

и

hk

(z, s) -

zkßk

(s -f <rA_0

1

Jk-\

[1 — ß f c (s

г О И

) ] ф ы

(z; s)

(5.20)

определяет

единственные

функции

hk {z; s),

фкс

(z; s),

фА (z; s),

i =

1, k,

k=l,r,

аналитические

в

области

R e s > 0 ;

| z1

j < 1,... , ! zk

I <

1,

где | Ä k ( z ; s ) | < l ;

\фы&s)\<\;

| ф л

(г; s) К

1 ;

б) если

Р*і =

«iß*!

+

Ol

ß»(o)

-- 1

1

<

1,

mo Afc+i(lf ; 0) =

ф « ( 1 г ;

0) = ф & ( 1 ' ; 0) =

1; в

противном

случае

0 <

< А Л + 1 ( 1 ' ; 0 ) < 1 , 0 < ф ы ( 1 ' ; 0 ) < 1 , 0 < ф , ( F ; 0 ) < 1 ;

в) если

pfe

=

1 —pf t l

и pf e l <C 1, то

(5.21)

(5.22)

a

Al'?, ф і ь

ô-fc имеют

тот

же смысл,

что и в теореме

2.

(5.15)

Д. Т е о р е м а

4.

а) система

функциональных

уравнений

— (5.17)

для схемы

3

(идентичное

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

заново)

и

оо

-%dBk(x)

Л, (z; s) =

Г e - ^* - i ) ) C f 1

(1 -

e - <**W*) ф ^ ,

(z; s)

(5.23)

Г Л А В А 4.

СИСТЕМА С ОТНОСИТЕЛЬНЫМ ПРИОРИТЕТОМ

Настоящая

глава посвящена обобщениям системы M | G | l | o o

очереди,

а второй — /-тым. Ясно, что /

равно

t + 1 ,

уменьшенному

на число

вызовов,

покинувших систему в промежутке времени

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

последовательных

вызовов,

поэтому / ^ л + І .

Переставим

эти

два

вызова. Тогда

(условно)

первый

вызов

в момент

поступления

оказывается