МАТЕМАТИКА

УДК 519.21

Э. А. Даниелян, Э. А. Симонян

Обобщение закона сохранения Клейнрока

(Представлено академиком А. А. Терзяном 8/V 2003)

   В классе консервативных дисциплин модели Mr |Gr|1 действуют универсальные законы сохранения. К их числу относится закон сохранения работы Л. Клейнрока, связывающий средние стационарные времена ожидания вызовов различных потоков (см. [1], с. 138), при недопущении прерываний обслуживания. В настоящей работе данный закон сохранения обобщен на случай допущения прерываний обслуживания и применен к дисциплине абсолютных приоритетов.
   В одноканальную систему обслуживания с ожиданием поступают независимые пуассоновские потоки 1-вызовов, ..., r-вызовов с параметрами a1 > 0, ..., ar > 0 соответственно. Длительности обслуживания вызовов независимы, не зависят от процесса поступления и для k-вызовов, k =
, имеют функцию распределения (ФР) Bk(x), Bk(+0) = 0.
   В рамках описанной модели Mr  |Gr|1 рассмотрим класс консервативных дисциплин, для которых внутри потоков действует дисциплина FIFO (first in - first out). Дисциплина обслуживания консервативна, если внутри модели работа (время обслуживания) не возникает и не исчезает, а лишь привносится в модель поступлением вызовов. Обозначим
R = r1 + r2 + ... +rr,    W0 = 1
2
r
е
k=1 
akbk2,
где
rk = akbk1,    bki =,   k =,  i = 1,2.

   Если консервативная дисциплина обслуживания задается на первом периоде занятости модели Mr  |Gr|1 и в точности повторяется на последующих периодах занятости, то в работах [2,3] развит метод доказательства существования при R < 1 вводимых ниже стационарных характеристик. В настоящей работе рассмотрен именно такой подкласс консервативных дисциплин.
   Нас интересуют следующие средние стационарные характеристики:
   Wk, k =, - среднее стационарное время ожидания k-вызова до момента первого его поступления на прибор;
   Vk, k =, - среднее стационарное время ожидания k-вызова в очереди до момента ухода его из модели обслуженным;
   Uk, k =, - среднее стационарное время пребывания k-вызова в модели, т.е. время с момента поступления k-вызова в модель до момента ухода его из модели обслуженным;
   Hk, k =, - среднее (условно) стационарное время пребывания k-вызова на приборе, т.е. среднее время, начинающееся с момента первого поступления k-вызова на прибор и завершающееся моментом ухода его из модели.
   При недопущении прерываний обслуживания Wk = Vk, Hk = bk1, а в общем случае
Uk = Wk + Hk = Vk + bk1,    k =
(1)

   При недопущении прерываний обслуживания закон сохранения работы Л. Клейнрока в предположении R < 1 записывается в виде

r
е
k=1 
rk · Wk = RW0
1 - R
.
(2)

   Закон сохранения (2) позволяет сделать следующее обобщение.
  Теорема. При R < 1 в рассматриваемом подклассе консервативных дисциплин (с прерываниями или без прерываний обслуживания) модели Mr  |Gr|1 имеет место следующий закон сохранения:
r
е
k=1 
rk · Wkm+ r
е
k=1 
ak · bk2
2bk1
Hk = W0
1-R
.
(3)

   Если прерывания обслуживания не допускаются, то (2) следует из (3). Действительно, в данном случае Hk = bk1, k =, и

r
е
k=1 
ak · bk2
2bk1
Hk = W0,

откуда и из (3) следует (2).
   Примером консервативной дисциплины с прерываниями обслуживания, для которой справедлива формула (3), является дисциплина абсолютных с дообслуживанием приоритетов (см., например, [2]). Именно, i-вызов, поступая в модель, замещает j-вызов на приборе при i < j. Прерванный j-вызов возвращается в очередь и при новом попадании на прибор дообслуживается. В очереди i-вызовы становятся впереди j-вызовов при i < j.
   Из (3) вытекает следующий известный результат: при R < 1 и дисциплине абсолютных с дообслуживанием приоритетов в модели Mr  |Gr|1
Wk = W0k
(1 - Rk-1)(1 - Rk)
,   k =
(4)
где
Rk = r1 + r2 + ... + rr,    W0k = 1
2
k
е
i=1 
aibi2,  k =    R0 = 0.

   Действительно, отметим, что стационарное время пребывания k-вызова на приборе hk представимо в виде

(5)

где символ d указывает на совпадение ФР обеих частей равенства. Здесь: bk - случайное время обслуживания k-вызова; одинаково распределены с периодом занятости обслуживанием -вызовов (1- вызовов, ..., (k-1)-вызовов); vk - случайное число -вызовов, поступающих в модель за bk, не зависящее от {}.
   Переходя в (5) к математическим ожиданиям, по формуле Вальда получаем
Hk = bk1 · {1 + sk-1 · Pk-1},
(6)
где sk-1 = a1+...+ak-1, Pk-1 - среднее периода занятости обслуживанием -вызовов. Pk-1 совпадает со средним периода занятости модели M  |G|1 с параметром sk-1 поступления и с ФР

k-1
е
i=1 
(ai/sk-1)Bi(x),   x і 0,

времени обслуживания вызовов. Поэтому sk-1Pk-1 = Rk-1/(1-Rk-1). Подставляя эти равенства в (6), находим

Hk = bk1
1 - Rk-1
,   k =
(7)

   Поскольку при каждом k = потоки (k + 1)-вызовов, ..., r-вызовов не влияют на величины Wi и Hi, i =, то для абсолютных с дообслуживанием приоритетов из (3) и (7) следует система уравнений

k
е
i=1 
riWi + k
е
i=1 
aibi2
2 · (1 - Ri-1)
= W0(k)
1 - Rk
,    k =
(8)
   Вычитая из k-того уравнения (8) (k-1)-ое, находим
rkWk = W0(k) · м
н
о
1
1 - Rk
- 1
1 - Rk-1
ь
э
ю
= rk · W0(k)
(1 - Rk-1)(1 - Rk)
,    k =

что равносильно (4).
   Набросок доказательства теоремы дан в приложении.
   Приложение. В любой момент времени в модели есть не более одного прерванного вызова каждого потока.
   Обозначим: Nk(t) - число еще не тронутых обслуживанием k-вызовов в модели в момент t; Tk(t) - число k-вызовов в модели в момент t, успевших побывать на приборе; Lk(t) равно единице, если в момент t обслуживается k-вызов, и равно нулю в противном случае.
   Введенные процессы являются регенерирующими. К ним применима теорема из [3], с. 430. Как и в [4], при R < 1 и t ® +Ґ для них существуют стационарные аналоги Nk, Tk и Lk. При этом
P(Lk = 1) = P(Tk = 1) = rk > 0,    k =
(9)

где P- знак вероятности.
   Пусть: xik - длительность обслуживания i-того k-вызова из числа Nk(t); yk(t) - условное остаточное время обслуживания тронутого в момент t обслуживанием k-вызова при условии Tk(t) = 1.
   Из временной оси выкинем промежутки, за которые не было тронутых обслуживанием k-вызовов, и уплотним временную ось. На временной оси каждому моменту t соответствует на уплотненной временной оси момент u = zk(t). Из уплотненной временной оси выкинем промежутки, за которые на приборе находится k-вызов, и образуем дважды уплотненную временную ось. Каждому моменту u на уплотненной оси соответствует момент v = xk(u) на дважды уплотненной.
   В силу (9), по усиленному закону больших чисел,

lim
t®+Ґ 
zk(t) = +Ґ,    
lim
t®+Ґ 
xk(zk(t)) = +Ґ       почти всюду.
(10)

   Величина yk(t) интерпретируется как остаточное время восстановления в момент xk(zk(t)) на дважды уплотненной временной оси для процесса восстановления {xk(i)}, где xk(i), i і 1, независимы и имеют ФР Bk(t). Поэтому существует стационарный при t ® +Ґ аналог yk величины yk(t) (см. (10)), причем
Myk = (bk2/2bk1),    k =
(11)
где M - знак математического ожидания. Справедливо равенство
w(t) = r
е
k=1 
ж
з
и
Nk(t)
е
i=1 
xik + м
н
о
yk(t),
если   Tk(t) = 1
0,
если   Tk(t) = 0
ц
ч
ш
,    t і 0,
где w(t) - накопленная и не выполненная к моменту t работа.
   Отсюда по формуле Вальда (Nk(t) не зависит от будущего),
Mw(t) = r
е
k=1 
(bk1 · MNk(t) + P{Tk(t) = 1} · Myk(t)).
(12)

   Поскольку существуют предел [(W0)/(1-R)] = Mw(t) (см., например, [2]) и стационарные Nk, Tk и Myk, k =, то, переходя к пределу t ® +Ґ в (12), с учетом P{Tk = 1} = MTk и (11), получаем

W0
1 - R
= r
е
k=1 
bk1 · MNk + r
е
k=1 
bk2
2bk1
MTk.
(13)
   По формулам Литтля для средних характеристик, используя (1), имеем
MNk = akWk,  M(Nk + Tk) = akUk = akWk + akHk,    k =.
   Подставляя последние равенства в (13), выводим (3).

   Ереванский государственный университет

Литература

   1. Клейнрок Л. Вычислительные системы с очередями. М. Мир. 1979. 600 с.
   2. Климов Г. П. Стохастические системы обслуживания. М. Наука. 1966.
   3. Феллер В. Введение в теорию вероятностей и ее приложения. Т. 2. М. Мир. 1984. 751 с.
   4. Даниелян Э. А., Хачикян Т. З.- Уч. зап. ЕГУ. 2001. N1. С. 4-22.