Добавил:
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

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

..pdf
Скачиваний:
3
Добавлен:
25.10.2023
Размер:
15.93 Mб
Скачать

 

 

ft—'.1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

+

2

«-нХ

+

іі-агЪ)

<

"

*

i

Z '

S )

)

"

^

<"<(Z'

S))>'

 

<4" 16>

 

i

=1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

где

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

«*(s) = <Ms) +

z*d(s)-£*(s),

 

 

 

 

 

 

a

функции

фА (в) «

^ ( s ) находятся,

 

как

и

в

случае

1:

 

 

 

 

 

 

 

ÄÄ (s)

=

 

Ф* ( И * ч («))

 

 

_

t

 

 

 

 

( 4 Л 7 )

 

 

 

 

 

 

 

 

1 — d (iXA-i (s))-g* ({AA-i

(s))

 

 

 

 

 

 

б)

идентичное

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

заново.

 

 

 

 

 

 

 

 

 

 

 

 

Функции

hh(z,

s)

и hh(s)

вычисляются

из (4.16) и

(4.17),

если

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

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

вызова

приоритета

k

 

предположить

константой

х

и полученные

выражения

проинтегрировать

от О до

оо

по

мере

 

dBh(x).

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

Моменты

возвращения

системы

в

сво­

бодное и исправное состояние являются моментами

регенерации

процесса.

Вероятность

x(s)

того, что за отдельно взятый

период

регенерации не было катастроф, задается

равенством

 

 

 

 

x{s)=

_ 1 — e

+

a)j q

„ ( s ) +

e ( g _ | _ g ) y ( s

+

g

_

an(s)).

(4.18)

 

 

 

 

s +

о*

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Заметим, что

(p(s + a — ал (s)) =

я (

Ф і Г )

(г, s)

(см. лемму

4 § 2

гл. 4).

 

Формула

(4.1)

непосредственно

вытекает

 

из

формулы

 

 

 

 

 

Р ( 2, x, s) =

[1 T ( S )

] - 1

je-<s +°>*[l — Е(х)]

- f

 

 

 

 

, 1 — e (s + a)

 

,

 

\

i

/

i

 

\

 

 

/

\ 1

 

 

 

 

-1

 

H

 

0 1 1

( z '

*> s ) +

e Xs

+

°) я ( Ф , г)

{г,

x,

s) L

 

 

 

 

 

 

s + o-

 

 

 

 

 

 

 

 

 

 

 

 

 

 

J

 

 

которая просто доказывается на основе вероятностных соображе­ ний, будучи представлена в виде

 

sP (z, x,

s) dx =

[ 1 — E (x)] e~ax

• e~sx • s dx +

 

 

 

со

 

 

 

 

+

sn{z,x,

s)dx-

j [ l — C(t)]

e~st-e-at-o

dt

- f

 

 

 

о

 

 

 

 

+ e (s -f- a)-sn( V i r )

(z, x, s) dx +

т(s)- sP (z,

x,

s) dx.

С л у ч а й

1. Отдельно

взятый k-цикл

может

иметь начальный

этап двух типов. Либо вызов приоритета k обслуживается до кон­

ца

(начальный этап

без потери), либо он теряется вследствие

поломки прибора во

время его обслуживания (начальный этап

с потерей).

 

16

Зак. 64

241

Пусть Ф/І(0 и Gh(t) — распределения длительностей назван­ ных этапов соответственно.

Тогда

 

 

оо

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

4>ft(s )-

\ e~st[l—С

 

(t)]dBk(t)—вероятность

 

 

того,

что

k-цикл

 

состо-

 

 

о

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ка­

ит из

начального

этапа без

потери и

за этот

этап

не

наступали

тастрофы;

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

оо

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ëk (s )

=

j e~st

П ~

Bk (0]

dC (t) — вероятность

того,

что

k-цикл

содер-

 

 

о

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ко*

жит

начальный

этап

с

потерей

и

за

этот

этап

не

наступали

тастрофы.

 

 

 

 

k-цикл

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Отдельно

взятый

можно рассматривать

как

отдельно

взятый (as, k—I)-цикл,

 

где

период

блокировки

есть

начальный

этап.

 

 

 

 

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

катастроф

 

 

 

 

 

Пусть

а/г (s)

за

началь­

ный этап

k-цикла.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Теперь

формула

(4.8)

очевидна.

 

 

 

 

 

 

 

 

 

 

 

Пусть

s-aft (г, x,

s)dx

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

наступления

первой

ка­

тастрофы на

отдельно

взятом

периоде

блокировки

а&

 

в

момент

5 = (г,

х).

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Справедливо

соотношение

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

а,(z,

х,8)

= гк[1к(x)

 

-Gk(х)]

 

е-(*+°-^х

+

 

 

 

 

 

 

 

+ gk(s

+ o — az)-[l—D

(х)] gr-o-H»-«)*,

 

 

 

(4.19)

которое

нетрудно доказать, записав в виде

 

 

 

 

 

 

 

 

 

 

 

sa^, (z, x,

s) dx

=

zh

к(оо)

— Фк(х)]

er®-™*e~sx-s-dx

 

-{-

 

 

 

 

 

 

 

+

Zft [Gk (oo) — Gft (x)] er®-02*

 

e~sx

sdx

+

 

 

 

 

 

 

 

 

 

-t- gk

(s - f a — az)

[ 1 — D (x)] е~^~аг*

e~sx s

dx.

 

 

 

 

 

Формулу

(4.4)

 

получаем,

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

(4.19)

 

по

х

от 0

до оо и воспользовавшись леммой 4 § 2 гл. 4.

 

 

 

 

 

 

 

 

С л у ч а й

2.

Пусть

поступает

рекуррентный

поток

ф. р.

C(t)),

 

называемый

потоком

прерываний,

и

dCn(t),

 

 

 

dd(t)—веро­

ятности rt-го и какого-нибудь прерывания

в

промежутке

[t,

t + dt]

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Тогда

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

оо

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

cn(s)

= $er«dCn(t)

=

 

[c(s)?,

 

 

 

 

(4.20)

 

 

 

 

 

 

 

 

 

о

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

оо

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

g*(s)

=

f e - s ' d g ( 0

=

 

-

.

 

 

 

 

(4.21)

 

 

 

 

 

 

 

 

J

 

 

 

1 — с (s)

 

 

 

 

 

 

 

242

Обозначим через Rn(t) вероятность того, что до момента t было ровно п(п^О) прерываний.

Имеем

rn

(s) =

1 - ~ c ( s )

[с(s)]",

 

 

 

 

(4.22)

r (z,

s) = J e-« R (z, t) dt = V Ç e-^ Rn

(t) z-dt

=

 

! — ^ £ L

 

 

0

 

n > 0

0

 

 

 

 

s [1 —zc(s)]

 

 

 

 

 

 

 

 

 

(4.23)

 

 

 

 

 

 

 

 

 

 

 

 

Пусть d — длительность одного восстановления прибора. Бу­

дем называть

прерывание хорошим,

если

за

(d,

k1)

цикл

не

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

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

вызовы

 

приоритета

k

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

плохим.

 

 

 

 

Каждое

прерывание хорошее

с

вероятностью d(\ik-\{z,

s))

и

плохое

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

1—d([ifc_i(z,

s)),

 

 

 

 

 

 

 

где

 

 

 

 

 

 

 

 

 

 

 

 

 

M-fcî {z, s) =

nf e _! (s +

[a — az]k),

\ik-\

(s) =

s +

afc _i — afc _i

(s).

 

Функция

R[d(\ih-i(z,

s)),

t]

задает

вероятность

того,

что

до

момента t наблюдались разве

лишь

хорошие

прерывания.

 

 

Обслуживание вызова приоритета k может прерываться выхо­ дом прибора из строя, т. е. протекать поэтапно. В этом случае промежуток, отсчитываемый с начала обслуживания до первого прерывания, назовем начальным этапом, а от момента последнего возвращения нашего вызова на прибор до конца обслуживания —

концевым этапом.

 

С каждым этапом связан некоторый (a, k\)-цикл,

период

блокировки а которого в случае концевого этапа равен длине этого

этапа, а

в случае неконцевого

длине этапа

плюс

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

одного восстановления прибора.

 

 

 

 

 

 

 

Будем различать этапы (0,0), (0,1), (1,0), (1,1). Этап

(0,0)

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

а

осталь­

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

 

 

 

 

Этап

(0,1)

есть

начальный

этап, (1,0)

— концевой, (1,1) —•

неначальный

и

неконцевой. Связанные

с

указанными

этапами

(a, k—\)

 

циклы

называем

(0, 0)-циклом,

(0, 1)-циклом

и т. д.

Пусть независимо от функционирования системы и наступле­

ния катастроф поступает пуассоновый поток

вызовов с парамет­

ром Я > 0

(і-вызовы).

 

 

 

 

 

 

 

 

 

 

def

0 0

[1 С {t)]e~%tdBk(t)

 

 

 

 

 

 

 

 

ф£0 , 0 ) (А)

=

j

есть

вероятность

того,

что

за

 

 

 

о

 

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

 

 

 

 

 

 

 

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

не

наступали

Я-вызовы

и

не было

прерываний.

 

 

 

 

 

 

 

 

 

 

def

0 0

 

 

 

 

 

 

 

 

 

 

 

gk'l)

=

J e~u

[1 — Bk(t)] dC(t)

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

наличия

прерываний

 

 

о

 

 

 

 

k

 

 

 

 

 

 

за время

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

приоритета

и

того,

что

до

первого

прерывания (на (ОД)-этапе)1 не поступали Х-вызовы.

 

 

 

 

16*

 

 

 

 

 

 

 

 

 

 

 

243

 

оо

t

 

ф°>(Ыг,8)=

\dBk{t)

f é-»b-^s>-u-R[d{Vik-i(z,s)),u]

X

x [1 — C ( t — u)] e-4t-u). d (/it., (z, s)) d © (и)

есть вероятность того, что за время обслуживания вызова прио­ ритета k были прерывания, до начала концевого этапа не было катастроф и не поступали синие вызовы приоритета k и ниже, а на концевом этапе не поступали /Ѵвызовы

 

 

оо

t

 

gilA)(llz,

s) -

\dBk{t)

- j e~^(z-s)uR[d

(p.,-! (z, s)), и] X

 

 

0

u=0

 

 

 

 

t—u

 

 

X

d (uf c _, (z,

s)) d<£(u) j

(y)

t)=0

есть вероятность того, что за время обслуживания вызова приори­ тета k было не менее двух прерываний, до начала некоторого (1.1)-этапа не было катастроф и не поступали синие вызовы прио­ ритета k и ниже, а за этот этап не поступали Х-вызовы.

По формуле полной вероятности имеем

shk

(z, x, s) dx =

sn((J)(o,o)w fe_1} (2, x, s) dx

+

 

k

*

 

 

 

k

'

 

 

 

+ S J t ( e ( » . » ( W 2 , S ) , fe-1) (Z » *• S )

 

( 4 - 2 4 )

где на основании

леммы 4 § 2 гл.

4 положено

 

 

я(о,о)(x,,fe-,)(2. *. s) =

z, [ O f 0 )

(оо) -

ФГ> (X)] e-(s+°-"*)x

+

 

 

+ ^(p . Q )( W > fe - i ) ( z .

*>»>

 

(4.25)

«( g (0,l)( M ,fe-l) (2. *,

S) =

Ч [Gi°'l) (ОО) -

О Г ° (X)] е - ^ + а - а г ) ,

+

+ Ч gï°'X)

(s +

o — az)[[—D

(x)] e -(s+(T-^

+

 

 

+

Щаы.^л)

w.fe-i) (z. x, 's),

 

(4.26)

244

я,(<ä>(,''0)(Vz,s),ft-i) (z, x, s) =

zk [Фр> (оо /г,

s) - ФГ 1 } ( X / Z ,

s)]

X

 

 

X

с(s+aаг)х _j-

 

 

 

(z, .x, s),

 

 

 

(4.27)

"{ g <U>(V*.s).fr-i>

(z - x - s )

=zJGl'' 1 ) (oo/2 ,

S) G 1 M ) ( X / Z , S)]

x

 

X

e-(s+o-az)x

+

2 ä

^0.1) (s

J _ G

_ а 2 / г > s )

[1 —

D (x)]

 

_|_

 

 

 

 

 

 

 

 

 

(z,

x, s).

 

 

 

(4.28)

Здесь

большими

буквами

обозначены

ф. р., преобразованию

Лап­

ласа—Стилтьеса

которых

(по параметру

X) соответствуют

те же

малые

буквы.

 

 

 

 

 

 

 

 

 

 

 

 

Подставляя

выражения

(4.25) — (4.28)

в (4.24)

и

интегрируя

hh(z, x, s) по x от 0 до оо, получаем

окончательный

результат.

Формула

(4.15)

интерпретируется

непосредственно.

 

 

 

С л у ч а й

3

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

В

этом

случае k-цикл может иметь начальный этап двух типов. Либо за

время

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

строя

(начальный этап — концевой), либо выходит

(начальный

этап — неконцевой). Длительности этих этапов

фи и gk соответст­

венно

имеют ф. р.,

определяемые из (4.6) и (4.7). Тогда

k-цикл

начинается

либо с

(фь, k—\)-цикла,

совпадающего

с

k-циклом,

либо с

(Àfe,

k—\)-цикла,

после

которого процесс

начинается зано­

во, т. е. начинается

fe-цикл, вкладывающийся

в

первоначальный.

Здесь

сл. в.

(период

блокировки)

— сумма

независимых сл. в.

gh и d, т. е.

 

 

 

 

 

 

 

 

 

 

 

 

 

Xk(s) =

d(s).gk(s).

 

 

 

(4.29)

Функция Kh(s) есть вероятность отсутствия катастроф за случай­

ное время

Àft.

 

 

 

 

 

 

 

 

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

 

 

 

 

 

shk(z, x, s) dx = sn^k, fc_1}

(z, x, s) dx + sn( X f t > k-i) (z, x,

s)dx +

 

+

Щ\к,fe-i)(s +

[o az\k)-shk

(z,

x, s) dx,

 

из которого

имеем

 

 

 

 

 

 

 

.

,

.

Л ( ф А , й - 1 ) ( 2 >

* • s)+K(Xk,k-\)(Z'

х< s)

(4.30)

nk(z,

x, s) =

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1 ~ N

O - K ,

fe-l)(H-f°

az]k)

 

Легко показать

(см. лемму

4 § 2 гл. 4)

 

 

 

Я(фА . к-» (2,

s) =

гк к (оо) — фк (х)] e - ( s + ° - ° ^

+

 

 

 

+

<7й. fe-i) (z,

x,

s),

 

(4.31)

245

 

 

*-,) (z, x,

s) = zk

[Gk (oo) -

Gk (x)] e-(»+o-«)*

+

 

 

+ 48 k (s г

от — az) • [1 — D (x)] eri>+<>-°*)*

+

zkq4, fc_„

(г, x,

s).

 

 

значения Щфк, k-n(z>x>s)и

 

 

(4.32)

Подставим

nak,k-i)(z>

x>

s) и з (4.31)

(4.32) в (4.30),

откуда

 

 

 

 

 

 

 

 

 

 

hk(z,

x, s) =

{1

^ . - É - I ) (s + [a — az]*,)}-1 X |

 

X {zf t e-<s +—>* • [ 1 -

Фк

(x) -

G, (x)] + gk(s

+ a-az)[l-D

(x)] - f J J

 

 

 

 

+ g(aA . fe-l) (Z,

X, S)},

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

(4.33)

где

ak (s) =

(s) + zkd (s)-gk (s) — вероятность отсутствия

катастроф

за

промежуток

ak.

что верна формула

 

 

 

 

 

Заметим, наконец,

 

 

 

 

 

 

 

 

Л * ( s > =

Ï — «

Гч '

 

 

( 4 - 3 4 )

 

 

 

 

 

 

1 " n(Xk,

k—l)(s>

 

 

 

 

которая просто

интерпретируется, будучи записана в виде

 

 

 

 

К (s) = Щфк,fe-i)(s) + л ( Ч і fe_i) (s) • hk (s).

 

 

Ч А С Т Ь IV

О Д Н О Л И Н Е Й Н Ы Е С И С Т Е М Ы М Н О Г О Э Т А П Н О Г О О Б С Л У Ж И В А Н И Я С П Р И О Р И Т Е Т О М

 

 

Г Л А В А

10.

СИСТЕМА

С

ПРИОРИТЕТОМ

 

 

 

 

§ 1. Описание и характеристики

 

системы

 

Рассмотрим

систему,

состоящую

из входящего

потока вызо­

вов, обслуживающего

устройства

(прибора)

и

бункера

ожидания.

Входящий

поток

вызовов

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

поток

с

параметром

а, т. е. вызовы поступают в систему

в моменты

tu

t2,

относи­

тельно которых

известно, что интервалы времени

 

 

 

 

 

 

2Й = tk

— 4—ь

£ > 1 » 4 — 0'

 

 

 

есть

независимые

в

совокупности,

 

одинаково

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

сл. в.,

причем

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

<^{zk<t}

=

l — e-at,

 

k>\,

 

а > 0 .

 

 

Будем считать, что в систему поступают вызовы N различных

видов, при этом в каждый

из

моментов

поступления вызовов

t\, І2,

... (их

будем

еще

называть

«вызывающими»

 

моментами)

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

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

 

 

 

З а м е ч а н и е 1. Этот же поток вызовов можно представить как супер­ позицию N пуассоновых потоков вызовов, каждый из которых содержит вызовы

лишь одного

из

видов

1, N

с

параметрами

аи a%,

aN

соответственно.

 

 

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

если

 

вызовы

вида

н, і2,

in,

образуют

группу

 

п

 

 

 

 

 

 

 

 

 

 

 

 

Ап,

° л = ^

аі

> а Pitt)

е

с т ь

вероятность

поступления

в

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

і вы-

зовов из группы Ап,

за

t,

то покажем, что распределение вероятностей

Pi(t)

для

каждого

из входящих

потоков

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

одинаковыми соотношениями.

 

Для суперпозиции

потоков, очевидно,

 

 

 

 

 

247

Д л я входящего единого потока с последующим розыгрышем вида вызова

Таким образом, поступления вызовов из класса Ап

происходят

независимо

от поступлений вызовов других видов.

 

 

Обслуживающий

прибор. Поступившие

в систему

вызовы

должны пройти обслуживание на приборе. Считаем, что обслужи­ вание вызова вида і разбивается на г, независимых последовательных этапов. Длительность обслуживания р-го (p = l , n ) этапа вызова вида і полагаем случайной величиной с функцией распре­

деления

B(itP)(t),

ß(i, р)(0) < 1 ;

несколько

первых

моментов

B(i,p)(t) предполагаем

конечными.

 

 

 

Бункер

ожидания.

 

Все поступающие в систему вызовы перво­

начально

поступают

в

некоторое

устройство

(бункер),

который

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

функции:

 

 

 

1) определяет порядок обслуживания вызовов прибором; дру­ гими словами, управляет работой системы;

2) накапливает те вызовы, которые вынуждены ожидать своей очереди поступления на прибор. Объем бункера неограничен.

Допускаются нарушения обслуживания последовательных этапов при поступлении в систему более срочных вызовов, или, другими словами, вызовов более высокого приоритета, которые немедленно начинают обслуживаться. А вызов, обслуживание ко­ торого было прервано, возвращается в бункер и ожидает своей очереди. Естественно считать, что при поступлении вновь на при­ бор вызов начнет обслуживаться не с первоначального этапа, а с первого необслуженного этапа.

Как только закончится обслуживание некоторого вызова, на прибор поступает очередной вызов из бункера, если такой имеется. Предполагается, что все пересылки в бункер и из бункера на при­ бор осуществляются мгновенно.

Вызовы вида і как обслуживающиеся на р-м этапе, так и те,

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

начаться с р-го

этапа,

если

они

ожидают в очереди или только

что закончилось

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

на предшествующем этапе, будем называть вызовами

типа

(t, р),

р = 2, ГІ = 1, N. Вызовы вида і,

которые из-за

прерывания

обслу­

живания до завершения первого этапа либо повторно обслужива­

ются на первом этапе, либо им предстоит

вновь

поступить на

первый этап, будем называть вызовами типа

(г, Г ) . Вызовы, впер­

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

этапа,

и

те,

которым

это предстоит, будем называть вызовами типа (г, 1),

і = 1 ,

N.

Установим взаимно-однозначное соответствие, указав каждой паре чисел (/, р) целое число ѵ:

(і, р ) ~ ѵ ,

248

р = 1, 1', 2, rt, i=\, N, v=

Приоритетные правила налагают некоторые условия на такое со­ ответствие.

При определении большинства характеристик системы не имеет смысла различать вызовы типа (і, 1) и (t, 1'), так как их

характеристики

совпадают.

Поэтому

в дальнейшем

изложении

вызовы типа (і,

1')

будут

выделяться

особо в тех случаях, когда

соответствующая

им

характеристика отличается

от характеристи­

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

(і, 1 ).

 

 

 

 

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

вызовов,

при

этом для

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

Вызовы типа

(г, р)

или, другими словами, вызовы

типа ѵ,

где

v ~ ( t , р), будем

еще

называть вызовами приоритета

(і, р)

или

соответственно приоритета ѵ и говорить, что вызовы типа ѵ имеют

более высокий

приоритет

по отношению к

вызовам

типа

ѵ, если

ѵ < ц . Вызовы

приоритета

ѵ имеют преимущество перед вызовами

приоритета

и,(ѵ<|і);

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

заключается в

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

с меньшими

потерями

на

ожидания

одних

вызовов

по

сравнению

с другими.

 

 

 

 

 

 

 

 

 

 

 

Предполагается,

что

при

переходе к

последующим,

этапам

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

приоритет

вызова повышается. Вызовы типа

(і, 1),

і = 1, N

упорядочены таким образом,

что если

(і, 1 ) ~ ѵ ,

(/,

1)—\і,

i<j, то

v < j i .

Поэтому о

вновь

поступивших

в систему

вызовах

будем говорить, что вызовы вида і имеют более высокий приори­ тет, чем вызовы вида /, если і < / .

Среди вызовов, ожидающих начала обслуживания, вызовы высшего приоритета поступают на освободившийся прибор раньше вызовов низшего приоритета. Для вызовов одного приоритета, как правило, будем рассматривать прямой порядок обслуживания, т. е. вызовы одного типа обслуживаются в порядке поступления: первым пришел •— первым обслужился. Если во время обслужи­ вания некоторого вызова в систему поступает вызов более высо­ кого приоритета, то существуют различные приоритетные правила

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

рассматриваются

разные

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

Рассмотрим

три

схемы.

С х е м а

1. Абсолютный приоритет.

Если во время

обслужи­

вания вызова

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

поступает

вызов

более

высокого приоритета, то обслуживание вызова, находящегося на приборе, прерывается и начинается обслуживание поступившего вызова; когда система освободится от вызовов более высокого приоритета, чем прерванный вызов, последний обслуживается с начала прерванного этапа обслуживания без учета имевшегося ранее времени обслуживания на этом этапе.

С х е м а

2. Относительный

приоритет.

При

поступлении в си­

стему вызова

более высокого

приоритета,

чем

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

вызов, прерывание обслуживания может произойти лишь по завер­ шении начавшегося этапа обслуживания; когда система освобо-

249

дится от вызовов более высокого приоритета, чем прерванный вызов, последний обслуживается, начиная с этапа, следующего за тем, после завершения которого произошло прерывание.

 

Будем

считать, что в схемах обслуживания

1 и

2

всегда

вы­

полняется

условие: если

v ~ ( i , р),

и.~(/, q),

то

ѵ<( і

при

і < /

Для

любых

р

и [q, т. е. на

всех

этапах

 

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

вызовы

 

вида і

имеют

более

высокий

 

приоритет, чем вызовы вида /.

 

 

 

 

 

 

С х е м а

3.

Смешанный

приоритет. Разобьем

все

поступающие

в систему

вызовы

более

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

чем

вызовы

 

типа ѵ,

на

классы

А

ѵ

,

О ѵ и

Б ѵ

. При

этом

предполагается,

что

все

вызовы

из

класса

А

ѵ

имеют

более

высокий

приоритет,

чем

любой

вызов

из

класса

О

ѵ

,

а вызовы

из класса

 

О ѵ имеют

более

высокий

прио­

ритет,

чем

вызовы

из

 

класса

Б ѵ .

Приоритет

 

понимается,

 

как

оче­

редность поступления

 

вызовов из бункера на свободный

 

прибор

для

обслуживания. Кроме

того, установим

следующие

возмож­

ности

для

поступающих в систему вызовов из класса А ѵ

 

и

О ѵ ,

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

 

 

 

 

 

 

 

 

 

 

вызов

из класса А ѵ прерывает обслуживание вызова

 

типа ѵ

так же, как при абсолютном приоритете;

 

 

 

 

 

 

 

 

 

 

вызовы

из

класса

О ѵ

обладают относительным

приоритетом

перед вызовами типа ѵ, т. е. они не могут прервать

обслуживае­

мый этап

вызова

типа

ѵ,

но

после

завершения

 

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

этого

этапа

(если

он

 

не будет прерван поступлением

в

систему

вызова

из

класса

А ѵ

)

вызовы из класса О ѵ прерывают

обслужи­

вание вызова, находившегося на приборе.

 

 

 

 

 

 

 

 

 

 

При поступлении вновь на прибор прерванный вызов начинает

обслуживаться с начала первого необслуженного этапа.

 

 

 

 

 

Поступление в

систему

вызовов

из класса

 

Б ѵ

не

может

вы­

звать прерывания ни обслуживаемого этапа вызова типа ѵ, ни обслуживания вызова после завершения этого этапа. Поэтому можно сказать, что поступление в систему вызовов из класса Б ѵ происходит без прерывания обслуживания вызова типа ѵ.

В схеме обслуживания 3 вызовы вида / могут иметь на неко­ торых этапах своего обслуживания более высокий приоритет, чем

вызовы вида і на отдельных этапах, даже

если

/ > і .

 

 

 

В рассматриваемой здесь системе в

классы Б ѵ ( О ѵ

)

могут

входить лишь те вызовы

вида

k,

для

которых

вызовы

типа

т, т~(&, 1 ) имеют более высокий

приоритет,

чем

вызовы

типа

V, ѵ ~ ( і , р),

и более низкий (соответственно высокий

для

О

ѵ ) , чем

вызовы типа

ц, u.~(t,

 

 

 

 

 

 

 

 

Схемы 1 и 2 являются

частными случаями

схемы 3, если един­

ственные непустые классы

для

вызовов

всех

типов

в системе —

классы А или О соответственно и вызовы вида і имеют более вы­

сокий приоритет,

чем вызовы вида / на

всех этапах,

если

і < / .

З а м е ч а н и е

2. На основании введенных порядков обслуживания можно

заметить, что одновременно в системе может

находиться не

более

одного вы­

зова каждого вида, обслуживание которого уже началось, но было прервано; прерывание обслуживания могут вызвать лишь вновь поступившие в систему вызовы.

250

Соседние файлы в папке книги из ГПНТБ