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

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

заня­

тости прибора.

Если

задана

последовательность моментов

tk

(в

которые обслуживающий прибор переходит

из

занятого

состояния

в свободное)

и

tu

(в

которые

прибор из

свободного

состояния

переходит в

занятое),

то разность между tk

и

наибольшим

из

не

превосходящих

его

tk'

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

занятости

прибора.

мени

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

вызовов потока L k есть сл. в. с ф. p.

Bk(t)T

k—\,

г. Допускается

неограниченная очередь.

вызовы потока

имеют более высокий приоритет

по

отношению

к вызовам потока

L3-, если /'</ . При этом вызовы

приоритета і

имеют преимущество перед вызовами приоритета / (i<j).

Это пре­

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

остальных.

П р и м е р . Имеются г ящиков, занумерованных

числами 1, г. Поступаю­

зи с этим мы будем

различать

следующие

схемы

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

с преимуществом.

С х е м а

1. Если

во время

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

вызова поступает

вызов более

высокого приоритета, то прерывается

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

С х е м а

2. То же, но прерванный вызов «теряется».

С х е м а

3. То же, но прерванный вызов обслуживается зано­

затратить время, равное /.

С х е м а 4.

Если

вызов

начал обслуживаться, то он обслужи­

вается до конца, несмотря

на поступления вызовов более высоко­

го приоритета

(прерывания

не происходит).

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

всех схем:

Tl(t) — ф . р. периода занятости системы;

Пи (t)—ф.

р. периода

занятости системы

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

зовов приоритета k и выше, т. е. длительности

промежутка време­

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

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

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

i ( і = 1 , k),

то

ука­

занную ф. р. будем обозначать через Щ , ( 0 -

Ясно, что

U(t)

=

= П ,(0-

Д л я схемы 4 справедлива

важная

Т е о р е м а .

г

а) а л (s) = £

аД . (s +

а — а я (s)),

(2.1)

І=І

причем

это функциональное

уравнение

определяет

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

функцию

Tc(s), аналитическую

в полуплоскости Res>0, в кото­

рой \n{s)

I < 1 ;

б)

если

афи

+

— + ß r ß r i ^ 1,

0 < я ( +

0 ) < 1 ;

то я ( + 0) =

1; в

противном

случае

в)

если

a i ß u +

... + a r

ß r

l < l ,

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

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

то первые

три момента

ф.р.

П (0

оя1=-^,

(2.2)

Р

™ , = -g-,

(2.3)

™з

=

~ ^

+

з | - ,

(2.4)

где

Рі = a i ß i i +

• • • +

arßrv

Рг = a ißxa +

• • •

+ arß/-2>

Рз = a ißi3 +

. . . +

a r ß „ ,

p = 1 — P l .

Теорема верна при любом порядке обслуживания

вызовов.

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

т е о р е м ы . А. Независимо от

эволюции

системы

наступают

катастрофы,

поток

которых — пуассоновый с

параметром

s>0 .

При

перестановке любых

двух

вызовов

в очере­

вания этого

вызова до следующего момента освобождения систе­

мы от этого

вызова и вызовов, поступивших после него.

Периоды

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

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

—

j

+

• • • +ar

J

и ofl—Jt(s)]

соответственно;

поэтому

суммарный

поток — тоже

пуассоновый

с

параметром

s + o — o n ( s ) . Отсюда

следует

форму­

ла (2.1).

Б. Положим

ß(s)==Sf~Ms)-

Так как функции ßi(s) вполне монотонны,

то

и

ß(s)

—

вполне

монотонная функция (см. § 8 доп.). Далее

ß(0) = 1. Теперь

утвер­

ждение б) теоремы следует из теоремы

1 § 2 гл. 1, если

заметить,

что параметр

а

заменен на

а

и

aßi = ß i ß n +

... + a r

ß r I .

Теорема

доказана.

З а м е ч а н и е .

Легко видеть,

что

период

занятости

в

схеме

1 совпадает

вызова). Период занятости

Т е о р е м а .

Для

схемы

2.

а)

система

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

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

уравнений

A*(s) =

ßf c (s

+

or*-i) +

- ^ = 1 - [ l - ß * ( s

+ a4 _I )]nft_i(s), ^

(3.1)

«ftfc(s)

=

hk(s

+

ak — aknkk(s)),

}

(3.2)

я «

(s)

=

Hft_u(s

Ь ak

— aknkk

(s)),

(3.3)

oknk (s)

=

axnkl

+ . . . +

aknkk

(s)

(i <

k)

,

(3.4)

определяет

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

функции hk(s^)nki{s),

nk(s),

i=l,k,

k

=

=

1, г,

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

в

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

Re s z> 0,

где \ hk'(s)

| <

1,

| K W ( S ) | < 1 ,

\ nk

( s ) | < l ;

б)

если

a^n

+

f-

[1 -

ß2

(a,)]

+ . . .

+

[1 -

ßf c (aÄ _l } ]

<

1,

(3.5)

mo

hk+i (0) =

я^- (0) =

nk

(0) =

1 ;

в

противном

случае

0 < Ä * + i ( 0 ) < 1 , 0 < я й ( 0 ) < 1 , 0 < я к ( 0 ) < 1 ;

б)

положим

pkl

= a-ßn

+ — [1 — ß2(Oj)]

+ . . .

• • • +

-*tr

[ l

~

ß * ( 0

f t

- l ) ] '

P k

=

1 -

p

* i '

Pfe2 = a A i

+ 2

Û2 C 2 P i -

ak Ckpk~i

Jk-\

H

(Pi

•Pi)

P*-i

Jk-\

Гогда при p f t l

< 1

выполнено

9ki

(3.6)

9k

9k2

(3.7)

Pi

1

(3.8)

*k-\Pk-\

lÉ2

- ß f t ( ^ - l )

,

9k—12

i-ß*(ff*_i)

(3.9)

J A - 1

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

т е о р е м ы . А. Докажем

сначала

форму­

лы (3.1) —(3.4).

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

системы

наступают катастрофы,

поток которых

является

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

се

раметром s>0. Величина

ßf e (s -f ak-i)

= J ег-^+ак-і)1

dBk(t)—

веро-

o

ятность того, что за длительность

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

вызова

приорите­

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

Суммарный поток катастроф и вызовов приоритета

выше k

(см. § 1 доп.) — пуассоновый

с параметром

s + Oh-i- Каждый вы­

зов суммарного потока

независимо от остальных

вызовов с вероят­

ностью

Jk-\

принадлежит

к

потоку

вызовов

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

s + °k-i

ше k.

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

[1 — ßfe (s +

Oft—i)]

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

того, что обслуживание

вызова

приоритета

k

прервано, до момен-*

та же прерывания катастрофы не наступали.

Формула

(3.1) вытекает из следующих

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

Пусть

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

обслу­

живания вызова приоритета k и кончающийся

первым

моментом

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

системы от вызовов

приоритета выше k и этого вы­

ступают, то с окончанием £ кончается и первоначальный

&&-период.

Если за

время

| вызовы приоритета k поступали, то с каждым из

этих вызовов связан £&-период, лишь после окончания

которых

(&&-периодов) первоначальный fefe-период кончается.

Вызов приоритета k называем плохим,

если

за

период, свя­

занный с ним, наступила

катастрофа. Каждый вызов приоритета k

независимо от остальных вызовов является плохим

с

вероятно­

стью 1 — t t f c f c ( s ) . Поток плохих

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

—

пуассоно-

вый с параметром аи{\—nkh(s)).

Поток

плохих

вызовов

приори­

тета k и катастроф — пуассоновый с параметром

s +

a^—aknkh(s)-

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

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

ttftfc(s)),

необходимо и достаточно,

чтобы

за

время \

не

наступали

катастрофы и не поступали

плохие

вызовы

приоритета

k

(вероят­

ность hh(s

+ ak—ahnhk(s))-

Этим доказана

формула (3.2). Формулы

(3.3) и (3.4) доказываются аналогично.

Формулы

(3.1) — (3.4)

доказывались

при s>0 .

По

принципу

Б. Укажем, как для вычисления Jtb(s) 'пользоваться

системой

(3.1) — (3.4)

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

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

уравнений.

Пусть

сг0 = 0 и k>\. Тогда из

(3.1)

имеем A i ( s ) = ß i ( s ) .

Фор­

мула

(3.2)

дает

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

уравнение

яц($)

=

ßi(s + a1—

—uirtn(s)),

определяющее

Я Ц ( А ) .

Далее,

= я ц ( s ) .

Допустим,

что

мы

определили

hk-i(s),

nk-i(s),

nk-n(s)

( i = l ,

k—1).

Тогда

по

формуле (3.1) вычисляется hk(s),

и из

(3.2)

— JtAft(s). Используя

значения nuk(s)

и

nk-n(s)

( i = l ,

k—1),

по (3.3) вычисляем

я ^ ( з )

( t ' = l ,

k—1).

Теперь осталось подста­

вить значения

7iki(s)

(i—l,k)

в (3.4).

В. Докажем методом математической индукции, что уравне­

ния

(3.1) — (3.4)

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

функции

hk(s),

nk(s),

itki(s)

(i =

l ,

k)

при

s>0,

являющиеся

вполне монотонными

функ­

циями,

причем

hk(s)<\,

я ь ( $ ) < 1 ,

Я А * ( А ) < 1

( І = 1 ,

k).

При

k=\

утверждение

верно (см. доказательство

теоремы

§ 2 гл. 1). Пред­

положим, что утверждение верно для всех j<k,

докажем его спра­

ведливость при j = k.

По предположению индукции функции hk-i

(s),

Пк-i (s),

nk-u (s)

(i =

1, k — 1) — вполне монотонны при s >

0, где hk-\

(s) < 1, nk~\ (s)<

<

l,Uk-u(s)<

1. Вполне

монотонной является

также

функция

00

a " ~ l

[1 -

h (s +

fffc-i)]

= Г а ^ к г - ^ - м х

[ l _

Bk (t)] dt.

Тогда вполне

монотонна

функция — — — [ 1 — ß e ( 5

+

Ok-i)]

Jtk—i (s)

s + °k-i

(св. 1, п. А,

§8 доп.) как произведение двух вполне

монотонных

сомножителей.

Наконец,

из (3.1) следует, что hh(s)

как сумма

двух

вполне

монотонных

слагаемых вполне

монотонна. При Л Й _ І ( А ) < 1

из (3.1)

имеем hk(s)<l.

Как и при доказательстве теоремы

§ 2 гл. 1, по­

казывается, что существует единственное решение nhk(s)

уравне­

ния (3.2), являющееся вполне монотонной функцией

при s>0, где

Jlftfe(s) < 1 .

По св. 2 вполне монотонных

функций

вполне

монотонны

функции nki(s)

( і = 1 , k—1).

Действительно,

функция

s + ak—

—ûfenftft(s)

имеет

вполне

монотонную производную

пы (s) = Jtft-w (s +

ak — aknkh

(s)) <

nk-u

(s) <

1, s > 0.

| & f t ( s ) | < l , | n f t ( s ) | < l ,

I « w ( s ) K 1-

Функция

hk(s)

как вполне монотонная

функция

при

s > 0

представима

в виде

hk{s)

= ]e-«dHk{t),

(3.10)

о

где Hh(t)

— некоторая

мера на [0, оо]. Берем

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

про­

должение

функции

hh{s),

заданной в

форме

(3.10),

в

области

Res>0. Из единственности аналитического продолжения

hh(s) в

область Res>0

и

из

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

(3.10)

из (3.1)

имеем

| f t f c ( s ) | < l .

Kfefe (s)

представима в виде

Аналогично

|nfeft(s)|<l

при

Res>0

также

следует из теоремы

§

2

гл. 1.

Аналитичность

же

nui(s)

( i = l ,

k—1)

и

л*(s)

и

условия

|nft,-(s)|<l,

Ijtfe(s)

I <

1

получаются

по

предположению

индукции

из

(3.3),

(3.4).

Г. Пусть rtfe(O)—0. Тогда по теореме § 2 гл. 1 при выполне­

нии

условия

ßft«fei^l

из

(3.2)

следует,

что

nhk(0)

= l;

в

против­

ном

случае

0 < Я А Ь ( 0 ) < 1 .

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

af t /zfti^l

на

основа­

нии

(3.1),

(3.3),

(3.4)

я «

(0) =

я , (0) = hk+x

(0) = 1

(І =

Т7Ъ);

в

противном

случае

0<nki(0)<\,

i=\,k,

0 < я ь ( 0 ) < 1 ,

. 0 < A f t + i ( 0 ) < l .

Пусть

0 < f t f t ( 0 ) < l .

Тогда

0 < я я і ( 0 ) < 1 ,

і = І 7 ~ £

0 < Я Й ( 0 ) < 1 ,

0<hh+i

(0) <

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

методом

математиче­

ской

индукции

доказывается,

что

при

замене условия

(3.5)

на

üjhji^l

( / = 1 ,

k)

утверждение

пункта

б)

теоремы

справедливо.

Осталось

заметить,

что

(3.5)

и

а ^ і ^ І

(j = l , k)

эквивалентны.

Действительно, обозначим

Ы

= flißu

+

[1 -

ß2 Ы\

+ . . . +

[1 -

ßf c (aÄ -0],

P f t = l —

Pfti-

(3.11)

Из

соотношений

(3.2) — (3.4)

следует

соотношение

a**k

( S )

=

°"А-ІЛА _І (s + ak — aknkk

(s)) + aknkk

(s),

продифференцировав которое по s и воспользовавшись

при s = 0

значением первого момента лини получаем

1 +

oytf e

(s) =

- — Ц — ( 1 + <т*_ія*_і (s)).

(3.12)

'С

другой

стороны, из

(3.1)

легко

вычислить

hkl=

1 ~ Ы а ь - і

)

[I +

a f e - ^ _ „ ] .

(3.13)

Подставляем

значения

1 +

о А я й 1

и

1 +

Gk-\nk-n

из

(3.13)

в

(3.12)

и

находим

1 —ß*(Ofc_l)

1

=

l - ß f e _ , ( c T , _ 2 )

+

• -—

a.k-\

a f t - 2

ö l

- [ 1 - ß i t - i

(a*_2 )]

1 — Pft-

ft—2