книги из ГПНТБ / Приоритетные системы обслуживания
..pdfлибо в некоторый момент произошло прерывание начального вызова поступившим вызовом приоритета выше k, до этого момен та не наступали катастрофы, не поступали синие вызовы приори тета k и ниже, поступали разве лишь хорошие вызовы приоритета выше k и первая катастрофа на отдельно взятом {k—1)-периоде наступила в момент S = (z, x).
С х е м а 2. Формула (4.4) следует из соотношения
|
shk(z, |
x,s)dx |
= zk[\ |
— Bk(x)] |
e-( [ o -Û Z ] ft+ < W*e~s *s dx |
+ |
||
|
|
|
со |
|
|
|
|
|
+ snk^ |
(z, x, s) dx j e-l*Ha-a*W |
|
[1 - Bk (t)] e-°^ |
CTfc_, - |
dt, |
|||
|
|
|
о |
|
|
|
|
|
которое доказывается так. |
|
|
|
|
|
|||
Пусть первая катастрофа внутри отдельно |
взятого |
k-цикла |
||||||
наступила в момент S = (г, х). Для этого необходимо и достаточно, |
||||||||
чтобы: |
|
|
|
|
|
|
|
|
либо |
начальный |
вызов |
красный, |
первая катастрофа |
наступила |
|||
через время х после начала его обслуживания, до этого |
момента |
|||||||
не поступали вызовы приоритета |
выше k и синие |
вызовы |
приорите |
|||||
та k и ниже; |
|
|
|
|
|
|
||
либо |
во время обслуживания |
вызова приоритета k раньше ката |
строфы и синих вызовов приоритета k и ниже поступил вызов прио
ритета выше k, прервавший обслуживание, |
а за отдельно взятый |
|||||
(&—1)-период первая катастрофа наступила |
в момент |
S—(z, |
х). |
|||
С х е м а |
3. а) неидентичное |
обслуживание |
заново. |
|
|
|
Отдельно взятый k-цикл |
может |
иметь |
начальный |
этап |
двух |
|
типов. Либо |
за время обслуживания |
начального вызова |
не посту |
|||
пают вызовы приоритета выше k и k-цикл, а также начальный |
этап |
|||||
оканчиваются с окончанием |
обслуживания |
этого вызова, |
либо |
обслуживание начального вызова прерывается поступлением вызо
ва более высокого приоритета (кончается начальный |
этап) и начи |
|
нается {k—1)-период, |
с окончанием которого |
((k—1)-периода) |
процесс начинается как бы заново. В первом случае говорим о кон
цевом |
начальном этапе, во |
втором — |
|
неконцевом. |
|
|
|||||||
Пусть <Pfc(0 |
и Gk(t) |
распределения |
|
концевого |
и неконцевого |
||||||||
этапов соответственно. Имеем |
|
|
|
|
|
|
|
|
|
||||
|
|
ФЙ 0) = |
ßft (s + |
|
а*_0, |
|
|
|
|
||||
|
ОО |
|
|
|
|
|
|
|
|
|
|
|
|
gk (s) = |
f e-* [1 - |
Bk(t)] |
e~°k-i |
4 - 1 dt |
|
= |
- |
^ |
- |
[1 - |
ßf t (s + |
о*_,)]. |
|
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
Вероятностными |
рассуждениями доказывается |
формула |
(4.8) |
||||||||||
|
|||||||||||||
|
shk (z, x, s) dx = zk |
[Фк (оо) — Фк |
(x)] é~la~az'lkx |
e~sxsdx |
+ |
||||||||
|
+ |
zk [Gk (oo) - |
Gk (x)] е - [ |
а |
- а г |
] |
ь х e-°* s dx |
+ |
|
151
+ |
*kSk (s -Ь [<т — аг]к) |
snk~i (z, x, |
s) dx + |
|
|||
+ g к (s + |
l a |
—а*\к) nk-\ (s J r |
[a — az]k) |
shk |
{z, x, s) dx, |
|
|
из которой следует |
(4.5). |
|
|
|
|
|
|
б) идентичное |
|
обслуживание |
заново. |
|
|
|
|
При условии, что длительность обслуживания начального вы |
|||||||
зова есть фиксированная величина т, из |
(4.5) |
получаем |
hk(z, s) |
||||
при фиксированном т. Теперь для |
вывода |
(4.6) |
достаточно полу |
||||
ченное выражение |
проинтегрировать от 0 до |
оо по мере |
dB(x). |
Г Л А В А 6. |
СИСТЕМА С ЧЕРЕДОВАНИЕМ |
ПРИОРИТЕТОВ |
На прибор поступают г независимых пуассоновых потоков вы |
||
зовов L i , . . . , L r |
с интенсивностями а.\,..., аг. |
Длительности обслу |
живания вызовов являются независимыми сл. в. с произвольными
ф. p. Bk(t) для |
вызовов А-того потока |
(k=l, |
г). |
|
|
|
Если вызов г'-того потока, приходя в систему, застает, ее пус |
||||||
той, то прибор сразу начинает обслуживать |
этот вызов. |
Вызовы |
||||
одного и того же класса |
обслуживаются в |
порядке поступления. |
||||
Дисциплина выбора на |
обслуживание |
среди |
различных |
потоков |
||
вызовов следующая. Пусть в некоторый момент времени |
прибор |
|||||
был свободен, |
и пусть |
первый поступивший |
в систему |
вызов |
является вызовом s-того потока, тогда прибор приобретает право приоритетного обслуживания для вызовов s-того типа (s = I , г). Это означает, что прибор в состоянии обслуживать вызовы других потоков лишь после того, как система полностью освободится от вызовов s-того потока (s = l , г). В тот момент, когда будет обслу жен последний из вызовов s-того типа, мы выбираем на обслужи вание вызов из класса с наименьшим номером среди имеющихся в данный момент (поэтому вызовы s-того типа называем вызовами приоритета s). Далее обслуживаются вызовы уже выбранного типа
до |
тех пор, пока их не останется |
в системе, затем процедура выбо |
||
ра |
повторяется и т. д. |
|
|
|
|
Таким |
образом, если прибор |
обслуживает вызовы |
приоритета |
і, то он не |
может переключаться |
на вызовы приоритета |
/(і=й=/) до |
тех пор, пока система не освободится от вызовов приоритета і, т. е. данная дисциплина приводит к наименьшему числу переключений
прибора. |
В случае, когда за переключение |
прибора приходится |
платить |
большой «штраф», подобная дисциплина более выгодна, |
|
чем какая-либо другая. Примером указанной |
дисциплины может |
служить мультипрограммная ЭВМ, где целесообразно, установив программу, обработать всю соответствующую этой программе информацию, после чего выбирать наиболее важную среди имею щихся на очередной цикл.
Вышеописанная система в § 1 исследуется методом вложен ных цепей Маркова [70].
153
§I. Метод вложенных цепей Маркова
А.Основные уравнения. Обозначения § 5 гл. 4 сохраняются. Положим также
|
|
{и'х) |
= (и, ... |
,и, |
|
хі+и |
. . . ,хг); |
|
|
|||
|
|
[хи1) |
= (хг, . . . , х г |
_ ь и, . . . , и); |
|
|
||||||
|
|
(игхѵ>) = |
(и, . . . ,и, |
хі+\, |
. . . , Xr-j, V, . . . ,v); |
|
|
|||||
|
|
{xvtx) |
= {x1, . . . ,Xi-u |
|
V, Xi+i, . . . |
,xv); |
|
|
||||
|
(u'xVjX) = ( « , . . . , u, xi+i, ... |
|
, Xj-u V, Xf+u . . . , xr); |
|
||||||||
|
|
ax = avxx + . . . + arxr |
|
|
(i = 1, v). |
|
|
|||||
|
При помощи дополнительного события выводятся |
уравнения |
|
|||||||||
х{Ріп+1 |
= |
[ Р , „ (О'-'х) - |
Pjn |
(0<х)] + [Pln (x) - |
Ріп (х0,х)] |
+ |
||||||
|
г |
|
|
|
|
|
|
|
|
|
|
|
+ |
S [P^-'xO^-P^O'xO^+^f-PAO^^ia-ax) |
|
|
(1.1) |
|
|||||||
и |
|
|
|
|
|
|
|
|
|
|
|
|
P{n(V-1xlr-4 |
= Pin{lr)<oin(al-a.xi)Ç>l(ai-aixi) |
|
( | x , | < 1). (1.2) |
|||||||||
|
Аналогично показывается, |
что условием |
существования |
ста |
||||||||
ционарного |
распределения является |
неравенство |
|
|
||||||||
|
|
|
Pf=<hhi+ |
••• + а Л і < 1 - |
|
(1.3) |
||||||
Тогда существуют пределы |
|
|
|
|
|
|
|
|
||||
|
lim Ріп (x) = Р , (x), lim Рп |
(x) = Р (x) |
( | xt |
| < 1, i = Î77) . (1.4) |
||||||||
|
п~>оо |
|
п -у оо |
|
|
|
|
|
|
|
|
|
При |
ЭТОМ |
|
|
|
|
|
|
|
|
|
|
|
|
|
р(х) |
= j ; P , ( X ) , |
І * І < І , |
Р ( І О = i . |
(1.5) |
||||||
|
|
|
|
(=1 |
|
|
|
|
|
|
|
|
Уравнения |
(2.1), (2.2) при я - * о о |
имеют вид |
|
|
|
£—1
= S[р>{0І;~ІХ) -р*(0^)]+ [р<{х) -р<{х0'х)] +
м?1х1)
+ |
[ Р У (0'->х03.х) - Р 3 . (0<хО;.х)] + |
Р (00, |
( 1.6) |
/ = н - і
154
|
|
Pt |
|
|
= |
|
P. (F) a>, (at -a{xt) |
ß, (a, - а |
Л |
) , |
|
(1.7) |
|||||||
где |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Ч- iflt — aixt) |
= 1 i m |
®rt K- — « Л ) . |
I |
К |
1 • |
|
|
||||||||||
Отсюда имеем соД+0) = 1, следовательно, |
W{(t) |
= |
lim W{n{t) |
есть |
|||||||||||||||
несобственная ф. р. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
Б. Нахождение Р(х). |
|
Суммируем |
(1.6) |
по |
і |
от |
1 |
до |
г. |
Полу |
||||||||
чаем |
суммарное |
уравнение |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
г |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
S *Tl{x\ |
= |
р w |
+ |
Г — |
- 1 > ( о о , |
|
|
(1.8) |
|||||||||
|
|
Лші pi (а — ax) |
|
|
|
|
\ |
a |
|
J |
|
|
|
|
|
||||
или |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
VI |
(*) |
|
[xt |
- |
ß( |
(a - |
ax)] |
= |
( - ^ |
|
l ) P |
(00, |
(1.80 |
||||
|
|
Pi (a — ax) |
|
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
справедливость которого для широкого класса |
систем |
(включаю |
|||||||||||||||||
щего и эту систему) |
была доказана ранее в § 5 гл. 4. |
|
|
|
|||||||||||||||
|
|
З а м е ч а н и е |
1. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Рі(х) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Pi (a — ах) [Xi — pi (a — |
|
ах)]+Рі(х0іХ) |
|
|
|
|
||||||||||
не зависит от первых і—1 |
координат, |
т. е. от |
х\,..., |
|
Хі-\. |
|
|
|
|
|
|||||||||
|
|
З а м е ч а н и е |
2. В |
§ |
5 гл. 4 доказано |
утверждение. Система функциональ |
|||||||||||||
ных уравнений |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
/ |
|
|
|
|
|
|
г |
|
|
|
|
|
|
|
|
|
|
|
|
|
Uki=^do — Uk-~Y^aixi) |
|
( t ' = l , |
£ — 1 ) |
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
ft-l |
|
|
|
|
|
|
|
|
|
(1.9) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
"ft |
|
|
|
|
|
|
|
|
|
|
|
|
в |
области 2 a j R e |
* j < |
2 |
a J |
и |
м е е т |
единственное |
аналитическое |
решение |
иы = |
|||||||||
= |
«fti |
• . • , *г) |
такое, |
что |
| щі |
I < |
1 (t = |
1, г ) , а |
также при |
р < |
1 |
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
ft-i |
|
|
|
|
|
|
|
|
|
|
|
|
lim |
|
u f c (x A , |
. . . |
,xr)= |
|
У\аі. |
|
|
|
|
|
(1.10) |
(/ = Â77)
Теперь РДх) можно выразить через Р(00 таким образом. Положим
Хі = "/•! ( * г ) . • • • • |
= Urr-l |
ixr)- |
155
Тогда |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
xc — ßc(o — ах) = ип— |
ߣ |
(а — ur |
— arxr) |
= |
0 |
(i=\,r—1); |
|
(1.11) |
|||||||||
|
|
|
хг — ß r |
(а — ах) = xr — ßr(a |
— ur — |
arxr). |
|
|
|||||||||
Из уравнения (1.8) и (1.11) получим |
|
|
|
|
|
|
|
|
|||||||||
|
|
— |
|
|
і — [х, — ßr (cr — ur |
— arxr)\ |
= Gr(xr), |
(1.12) |
|||||||||
где |
|
ß„ (о — «, — аг л:Л ) |
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Gr |
(xr) = |
g f* ' P (0r ). |
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
CT |
|
|
|
|
|
|
|
|
Вспомнив замечание |
1, согласно |
которому |
|
|
|
|
|
||||||||||
|
|
|
ß , (CT — |
ox) |
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
ß , ( o — ur |
— arxr) |
[xr — ßr{o — ur — arxr)] + |
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
+ P r ( « r l , |
. . . . U r r - x , 0) = Ф,(А:,), |
| X , | < 1 |
(i = |
Г77) |
(1.13) |
||||||||||
есть |
функция, |
зависящая |
только |
от хг; |
из (1.12) |
имеем соотношение |
|||||||||||
Фг (хг) — Рг |
(иа,... |
|
, Urr-i, |
0) = |
P f |
( x ) |
|
[хг ~ßr(a |
— ах)} |
+ |
|||||||
|
|
|
|
|
|
|
|
|
Рг (ст — ах) |
|
|
|
|
||||
|
|
-і-РДхО,) — Р , ( и г 1 , |
. . . . И г г - ь |
0)=Gr(xr). |
|
|
(1.14) |
||||||||||
Как |
видно из (1.14), для нахождения |
Рг(хг) |
нужно |
знать |
Рг(хОг). |
||||||||||||
|
Л е м м а . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
РГ (*0Г ) = |
ФД2Г ) + |
-a^rzРr( 0 ' ) , |
|
|
|
(1.15) |
|||||||
где |
|
|
|
|
|
|
|
|
|
|
ст |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
г—1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
г, = |
я , ( 2 ^ 0 |
— **)}. |
К - К 1 |
|
( і = 1 , г — 1 ) , |
|
|||||||||
|
|
|
|
і=і |
|
|
|
|
|
|
|
|
|
|
|
|
|
а ят |
(s) |
преобразование |
|
Лапласа |
— |
Стилтьеса |
от ф. p. |
Tlr(t) |
|||||||||
периода |
занятости |
системы |
M | G111 оо с интенсивностью |
входящего |
|||||||||||||
потока, |
равной |
аг, |
и ф. р. длительности |
обслуживания |
Br(t). |
||||||||||||
|
Утверждение |
(1.15) |
следует из (1.13), если положить там |
||||||||||||||
|
|
|
|
|
|
|
|
г—1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
• хг |
= я , { £ а , ( 1 — * , ) ) , |
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
І = І |
|
|
|
|
|
|
|
|
|
и того |
факта, |
что |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
nr(s) |
= |
ß r ( s + ar |
— а,яг (в)). |
|
|
|
|
156
Теперь |
из соотношения (1.14) получаем следующее функциональ |
|||||||||
ное уравнение |
относительно неизвестной функции |
Ф г ( х г ) : |
|
|||||||
где |
|
Фг{хг) |
= Фг&) + Ѵг(Хг), |
|
|
|
|
(1.16) |
||
|
|
|
|
|
|
|
|
|
|
|
|
|
zr = лг (о>_і — ur(хг)), |
оѵ-1 = |
at, |
|
|
||||
|
|
yr (Х ) = |
+ |
|
р( 0 Г ) _ |
|
|
|
|
|
|
|
|
|
О |
|
|
|
|
|
|
Таким образом, мы можем теперь выразить Рг(х) |
через |
Р(0Г ) из |
||||||||
(1.13) и |
(1.15): |
|
|
|
|
|
|
|
|
|
|
|
Гг(х)-Тг(пг) |
|
р ( |
о |
_ а |
х ) |
і |
(1-17) |
|
где |
|
жг — р г (а — ах) |
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
Г, (x) = Г г (х1 ( .. . , хг) = Фг (xr) + |
- |
^ |
, |
|
|||||
|
|
Y r (Xzr) |
= Гг (Xlt |
. . . , Xr-u |
zr). |
|
|
|
||
Вообще, |
чтобы |
найти Pk(x), |
положим |
|
|
|
|
|
|
|
|
|
i |
|
|
|
|
|
|
|
|
Xj, = |
"fci (Xk, |
. . . ,Xr), . . . |
, Xk-\ = |
Ukk-i |
{xkt |
. . . yxr) |
|
( k - - l , r ) . |
||
Тогда |
|
|
|
|
|
|
|
|
|
|
*t — Pi (a — a x |
) = 4i — ß/ [a — uk — £ |
aixi) |
— 0 |
(t |
= |
1. * — |
1), |
|||
|
|
|
|
|
г |
|
|
|
|
|
|
xi — ßi (о — a*) = |
— ß( (<* — " Л — |
£ |
a,-*,) |
(i = k,r). |
|||||
|
|
|
|
|
i=k |
|
|
|
|
|
Из |
равенства (1.8) имеем |
|
|
|
|
|
|
|
p{0r)uk+[ax]k-o |
= y |
a
P t ( î ^ ^ [ |
p ( o _ |
[ a x ] } ] = |
ß,- (a — и й — [ax]f e ) |
|
|
_ |
P f c ( « A - 1 , * ) _ |
[ |
X f t _ ß e |
( a _ U |
f t _ [ a |
x ] f t ) ] ) |
( 1 л 8 ) |
|
ßFE(0 — wfe— [ax]fe) |
|
|
|
|
|
|||
.где ( |
|
[a*]f t = akxk |
+ ... |
+ arxr, |
|
|
||
|
|
|
|
|||||
Pk (Ф-"Х) |
= Pfc |
( Ц И , |
. . • , Ukk-U |
xr, . . . |
,xr). |
|
||
В силу замечания |
1 для i > & |
|
|
|
|
|
||
P i ( x ) |
[xt-p-{{o-ax)] |
+ Pt№{x) |
= |
|
||||
ßi (0 — |
ax) |
|
|
|
|
|
|
' |
157 |
|
P * ( « ( f t l)x) |
.[Xl-p{{a-uk-[ax]k) |
f |
|
|
|
|
ßi (a — Uk— [ax]k) |
|
|
|
|
|
|
+ P(. ( H < * ~ » xO]x) = Ф, (*l f . . . , x r ), |
|
(1.19) |
|||
где по аналогии |
с (2.13) |
Ф((х{, ... |
,хг) есть |
функция, зависящая |
||
только от х{, . . . , хг |
|
|
|
|
|
|
Р, (u<k-UxOtx) |
= Р( (uA l , . . . , uÉ É_b |
. . . , |
0 , X j + i . |
. . . , хг). |
|
|
Из выражения (1.19) можно получить выражение для |
Pt(xQtx), |
ана |
||||
логичное (1.15) |
|
|
|
|
|
|
Р, (хОсх) = Ф, (z,*,+ 1 |
хЛ ) + — - Р (00, |
|
( 1.20) |
|||
г |
|
|
|
о |
|
|
|
|
|
|
|
|
|
где г£ = я , - а ; - ( 1 — л г 3 ) | , |
a я,-(s) |
является |
преобразованием Лап- |
|||
/=і |
|
|
|
|
|
|
ласа — Стилтьеса от ф. р. периода занятости системы M | G ) 1 | оо с ин тенсивностью входящего потока, равной at, и ф. р. времени обслу живания B{(t). Отсюда имеем рекуррентные функциональные соотно шения:
г |
г |
|
|
|
|
|
|
£ Фс(х£, |
... ,хг) = '£Ф1(г{,хш,...,хг) |
|
+ Чк(хк,... |
,xk), |
(1.21) |
||
где |
|
|
|
|
|
|
|
z{ |
= nt(o — at — uk— [ax]k -f- atxt) |
{i > k, k = Ï77), |
|
||||
|
|
|
|
r |
|
|
|
|
|
|
|
+ 2 ß i Z ( — a |
|
|
|
|
Wk (xk, |
...,хГ) |
= |
<=*- |
P (00. |
|
|
|
|
|
|
0 |
|
|
|
Из (1.19) |
с учетом (1.20) имеем |
|
|
|
|
||
|
Pk{x)= |
|
|
$k(o-ax) |
( Ä = l , r ) , |
(1.22) |
|
где |
|
Xk — Pk (о — ax) |
|
|
|
||
|
|
|
|
|
|
|
|
Tf c |
(x) = rk (xlt |
. . . ,хГ) |
= Фк (xk, ... |
, xr) + Ä |
p (00, |
|
|
|
Tk (xzkx) |
= Tk (xv |
. . . , Xk-u zk, xk+i |
xr). |
|
Значение P(00 для всех приоритетных систем без прерывания одно и то же (при заранее фиксированных интенсивностях входя щих потоков и ф. р. длительностей обслуживания вызовов), мы уже находили его для системы с относительным приоритетом.
158
В. Нахождение Wk(t). Определим теперь функции coÄ(s) =
оо
=^ <Мk(t). Из формулы (2.7) следует, что
о
" * ( * ) = — |
— |
— |
( | l - S a - ' | < l ) , |
(1.23) |
|
ûfe |
|
Pfc (s) |
|
|
|
откуда, имея в виду |
(1.22), |
получаем |
|
|
|
щ (s) = |
о { Г к ( 1 * ) - Г к ( 1 * - 1 , |
1-saj1, |
V~k)) |
|
|
|
s — ak + af e ßf t (s) |
— |
|
||
|
|
|
|
||
а < Ф * ( 1 г ~ й + 1 ) - Ф * ( 1 - * * г Л r - A ) } + s P ( 0 0 . |
2 4 |
s — aft-T-af t ßfe (s)
Отсюда по правилу Лопиталя можно вычислить первый момент времени ожидания для вызова приоритета k.
§2. Виртуальное время ожидания
А.Предварительные сведения. Рассмотрим СМО M'|G|1 с па раметром а поступающего потока и ф. p. B(t) длительности обслу живания вызовов.
Вначальный момент в системе k вызовов (k^O). Выполнено условие существования стационарного распределения
|
|
|
a ß i < 1- |
|
(2.1) |
|
Обозначим через |
(t) возможное время ожидания, начинающееся с |
|||||
момента t. Положим |
|
|
|
|
||
|
|
|
ю<*> (s, t) = Ше-™(к) «> |
|
(2.2) |
|
и обозначим |
через |
Poft) |
(t) вероятность |
того, что в момент t |
систе |
|
ма свободна |
от |
вызовов. Просто |
выписываются |
уравнения |
||
со№ (s, t) = els~a+a^V |
{[ß (s)]* — s J |
e-r*-e+««s>]* p<*> (x) dx}, |
(2.3) |
|||
|
00 |
|
о |
|
|
|
|
|
|
|
|
|
|
|
f |
P?> (X) dx = ms + a-an(s))}\ |
( |
2 > 4 ) |
||
|
J |
|
s + |
a— ait (s) |
|
|
|
о |
|
|
|
|
|
я (s) = ß(s + a — ал (s)), R e s > 0 , | j t ( s ) | < 1, |
|
(2.5) |
которые определяют возможное время ожидания вызовом, посту пающим в момент t.
Обозначим через w^(t) безусловное возможное время ожида ния, начинающееся с момента t, причем во всем промежутке (0, t) прибор занят. Имеет место соотношение
159
|
|
<D<*> (s, t) = |
(s, |
0 + |
J co<°> (s, z1 |
— u) d [U (u)]*, |
(2.6) |
|
где |
|
|
|
|
|
|
|
|
|
|
со' (s, |
t) |
= |
Me-sw(k){t\ |
|
(2.7) |
|
а П ( / ) |
— ф. p. периода |
занятости |
системы |
M | G | 1 . Доказательство |
||||
(2.6) |
проведем, использовав |
поток катастроф. Пусть за возможное |
||||||
время ожидания, начинающееся с момента t, не наступала |
ката |
|||||||
строфа |
(с вероятностью |
o#)(s, |
/ ) ) . Для этого необходимо и |
доста |
||||
точно, чтобы |
|
|
|
|
|
|
||
либо |
во всем промежутке |
[0, t) прибор был занят и за |
время |
с момента t до первого момента освобождения системы от вызовов,
поступивших до t, не |
было |
катастроф |
(вероятность co(fe)(s, |
t)), |
||||
либо |
в какой-то момент |
u(u^Lt) |
система освободилась |
от вы |
||||
зовов (с вероятностью |
d|TI («)]*) |
и за |
возможное |
время ожидания |
||||
wW)(t—и) |
не было катастроф |
(вероятность со( 0 ) (5, |
t—и). |
|
||||
Б. В |
дальнейшем |
предполагается, что выполнено неравенство |
||||||
|
|
fllßu |
+ |
. . . |
+ f l r ß r l < l . |
|
(2.8) |
В данном пункте выводятся функциональные соотношения, определяющие Pj(t) — стационарные вероятности того, что обслу живаются вызовы приоритета і и в начале промежутка занятости обслуживанием вызовов приоритета і (t-промежуток) в очереди ожидали / заявок приоритета і ( / ^ 1 ) .
Положим
Ф;(%> = Ѵ Р Д / ) 4 |
(2.9) |
Очевидно, что при выводе соотношений для Фь(хь) вызовы пер вых k—1 потоков можно объединить в один пуассоновый поток с параметром Oh-i = ßi + .. . + ak-\. Обозначим через Qh-i(Xh-i, Xk) производящую функцию
Qfc_! (Xk-u xk) = 2 р ч 4 - і 4 > |
(2 - 1 0 ) |
і>1 />0
где Рц — стационарная вероятность того, что обслуживаются вы зовы приоритета выше k и в начале этого периода занятости обслу живанием вызовов приоритета выше k в системе і вызовов приори тета выше k и j вызовов приоритета k.
Окраской вызовов доказываются соотношения
1 - S а ' ßa 1 + S Ф і ( Я ( Л |
- а***> - я ( / ) Ю > + |
і=і j=k+i
^60