2. Системы массового обслуживания. Матвеев_ Ушаков (1984) (1186155), страница 30
Текст из файла (страница 30)
Соотношение (5) вытекает из следующих рассуждений. Событие, заключающееся в том, что первая «катастрофа» внутри 1-поколения, состоящего из 1 1-требований, поступила в момент, когда в системе не было «синих» требований, эквивалентно следующему событию: за первые т — 1 1-цикл, т=1, 1, не поступали «катастрофы» и не поступали «синие» 1-требования, 1=1, г, а первая «катастрофа» поступила в т-м 1-цикле, когда в системе не было «синих» требований. Так как совместное распределение длительностей обслуживания первых т 1-требований 1-поколения, состоящего из 1' 170 !-требований, имеет вид [! — В,(х )]'-"'!(В,(х,)...
!!В!(х,„) (1 — л!) ! где х! <х,< ... <х и Π— в противном случае, то ! ' ~л л р,;(х, з) = гт ~ ( ... ~ ' Х ехр [ — е,(х,з) ~!~ ~х,] г! [! — В;(х )]! Х с=-! р!"'>(х, х, з)ЫВ,. (х,)... г1В!(х ), где зр!!'">(х, х, з) — вероятность того, что первая «катастрофа» внутри !-цикла поступила в момент, когда в системе нет «синих» требований, при условии, что длительность обслуживания !'-требования, с которого начинается !-цикл, равна х .
Лналогично доказательству соотношения (4) показывается, что ! †! л р,""! (х, х, з) = Я Я ~ а,, (по и) ехр ( — (а+ си л — (а, х)'-') и);с г=! л!=! О Х г!' — и,'."!!! !(г, з) с1«Г!! .. (и,х,„) + ! — л!+! -~- ' [! — ехр[ — (з + о — (а, х))х ]. «+о — (а, л) Для доказательства теоремы осталось воспользоваться равенством и произвести элементарные преобразования в (5). 5.
Задачи. 3 ада ч а 1. Доказать утверждение леммы 1. Зада ч а 2. Доказать, что для дисциплины ).РТ остаются справедливыми утверждения теоремы 1 и следствия к ней с за. меной йл(х, з) на !!|(х, з), ул(х, з) на а» [1 — Вл(х)] [! — йл(х, з) ], е!„(х) на ] и'ЙВ«(и) . л !71 Здесь )гд(х, з) = Вд(х, рд(з)), рд(х, з) = ] е-'Ы, В,(х, !), о ( Вд (и)/]1 — В„(х)], и ) х, д(х,и) = — ~ О, и ~(х. 3 а д а ч а 3. Доказать, что среднее время ожидания в стационарном режиме для й — требований определяется по формулам; а) для дисциплины ЬРТ 2ид ] и(1 — Вд(и)! иВд(и) ! о Ргг ыо 2рд(2 рд-г — рд) Рд-г (.РТ Ю 2ид ] иВд(и)йВд(и) + рд-1 б) для дисциплины Раг 2р,(2рд, р,) 3 а д а ч а 4 (продолжение).
Показать, что ,о!, (о!ад! 1 оггд!)/2 ю ы <ог ы <ог д!, о ! г ! — ! 40 ~ е "*'"ЙВ,(х)]' 1! 2' ] ехр( — (з+ и-' — (а, г)'-')и) х г==! и,=! о Х а! ! (и, и) и,'"", г, (г, з) !)„Ги . ! (и, у) + ]1 — ехр( — (з 1- о — (а, г)) у)]) о(ВР(у). а+о — (а, а) 3 а д а ч а 6. Пусть Р! — стационарное время пребывания Втребования в системе, !', — число !'-требований в системе в 172 где оггд! — среднее время ожидания для й-требований в стационарном режиме в системе М„]6„)1~оо с относительным приоритетом и дисциплиной Р)ГО.
3 а д а ч а 5. Доказать, что первые два соотношения теоремы 2 справедливы для дисциплины ) РТ, а функция пи!и!(г, з) удовлетворяет соотношениям и!р! (г,з) = Я 1' )д)д>(з+ о' — (а, г)') 1 (г<Вг(у) + д=о)=! о стационарном режиме. Показать, что для дисциплин ЯРТ и (.РТ справедлива формула Литгла, т е МЕ;=а,М1/,.
$5. ОПТИМАЛЬНОЕ НАЗНАЧЕНИЕ ПРИОРИТЕТОВ 1. Постановка задачи. В предыдуших параграфах были достаточно полно изучены системы обслуживания М„(6„~1~со с относительным и абсолютным приоритетами. Интерес к таким системам обусловлен не только тем, что они довольно часто встречаются на практике, но также и тем, что эти приоритетные дисциплины являются оптимальными для некоторых критериев эффективности работы системы. В этом параграфе мы рассмотрим класс систем М„!6„!1)оо, в которых не допускается прерывания обслуживания, и докажем, что для определенного ниже критерия эффективности дисциплина относительного приоритета является оптимальной. Пусть аь ..., а„— интенсивности входящих пуассоновских потоков требований, В,(х), ..., В„(х) — ф.
р. длительностей обслуживания требований 1-го, ..., г-го потоков соответственно. Обслуживание требований организовано следующим образом. Если в момент поступления в систему некоторого требования прибор свободен, то оно сразу же начинает обслуживаться. Если какое-либо требование начало обслуживаться, то вне зависимости от изменения длин очередей оно будет обслуживаться до конца (т, е, прерывание обслуживания не допускается).
После завершения обслуживания требования выбор следующего производится на основании длин очередей в этот момент Точнее, каждому набору 1= (!» ..., 1,), 11+ ... +1„>0, сопоставляется число и(!), принимающее значения от ! до г, причем если и(!) =й, то !ь>0. Тогда если после 'завершения обслуживания какого-либо требования в системе остается !ь ..., 1„ требований потоков 1, ..., г, то следующим на обслуживание выбирается требование из потока с номером и(1). Требования каждого потока обслуживаются в соответствии с дисциплиной Р)РО.
Пусть с, — стоимость за единицу времени пребывания требования Ого потока в системе, 1'=1, г, с=(сь ..., с,); $.(!) = =(7.,(!), ..., Е,(!)), Ти(!) — число требований 1-го потока в системе в момент Е Если через 7(Е(!) =и) обозначить индикатор события (Е(!) =и), . ' 7П. (!) = ) = ! ' ! О, если Е(!) Фп; Х„(Т) = ~7(Е(!) =- п)Ж, о 173 то суммарные потери до момента Т равны (с, и) Х„(Т). ь=а Средние потери в единицу времени до момента Т равны М ( — ~~ (с, и) Х„(Т)) = — ~ у ! (с, п) М(Т ($.
(!) .= и)) с(! = п=О о а=О т т = — ) ~~1~ (с, и) Р ((. (!) = п) Ш = — ~, (с, М!. (1)) д1, о =о где М!.(!) =(Мг.,(!), ..., М1.,(1)). Для стационарного режима (т. е. когда 1.(!)=ь-Е гьри 1-~со) средние потери за единицу времени равны т У = Игп — ~ (с, М1. (!)) д! = (с, М!.), 1 т Т 3 о где М(.= (М1, ..., МВ,), МА; — математическое ожидание число требований бго потока в системе в стационарном режиме. Очевидно, значение Т зависит от выбора функции и(!) (будем называть ее функцией переключения). Наша задача заключается в том, чтобы выбрать такую функцию переключения и(!), при которой Т минимально.
В дальнейшем будем предполагать существование первых двух моментов длительностей обслуживания, т. е. для любого 1, !~!<с, М[В<'1'<со, 1=1, 2, где В; — сл. в. с ф. р. В;(х). Кроме того, будем предполагать, что 1 р„= ~Г афп < 1, [1,; = М [В ['. 1=! 2, Описание оптимальной функции переключения Теорем а 1. Положим К;=с;агро.
Пусть Яп М~;,) ... ~ )%, где (1ь 1ь ..., 1„) — перестановка чисел (1, 2, ..., г). Тогда оптимальная функция переключения имеет вид ~ 1,, если 1ц > О, 1,, если 1ь — — О, !ч >О, и(!) = [ 1,о если 1ц=...=б =-О, й >О, если/и=-...=П =О, 1; >О. 174 3 а м е ч а н и е. Указанная оптимальная функция переключения реализует дисциплину относительного приоритета, причем требования потока г! имеют наивысший приоритет, потока ! — следующий и т. д. Д о к а з а т е л ь с т в о теоремы 1. Чтобы не загромождать изложение, рассмотрим случай г=2. Общий случай составляет содержание задачи 1. Анализируя доказательство теоремы 1.1, видим, что при выводе соотношений Г р (х, з) = р, (з) + ~ ' ~ р, (х, х, з) !(х, =!о рг(х, х, з) = ]1 — В;(х) ] ехр ( — (а+о — (а, х) ) х) р; (х, О, з), Г Ф р, (х, О, з) = ~ г —,.
' (рг(х, х,з) т),(х)г(х+ Г=! а + 1 — (а+ о — (а, г) ) ро (з), ро(з) = ]а+о — ол(з) ]-' мы пользовались только тем, что не допускается прерывание обслуживания. Наличие дисциплины относительного приоритета использовалось только при выяснении характера зависимости рг(х, О, з) от гь ..., г„. Далее, при любом выборе функции переключения и(!) процесс 1.(1) является регенерирующим, у которого точками регенерации являются моменты окончания периодов занятости, Кроме того, длительность периода занятости не зависит от выбора и(1). Таким образом (см. 5 1, следствие к теореме 1.1), в силу теоремы 4.4.
Введения при р„г(1 для любой функции переключения и(1) существует предел 1. (!) =>-Е, г-)-оо, причем функция Р(х) =Мх" удовлетворяет соотношениям Г Р()=(1-р„)+У ' "" '*" Р.(). а — (а, г) ~=! Г ~ [1 — г;-' р, (о — - (а, г))] Р, (х) = ](а, х) — о] (1 — р„) . Рассмотрим случай г=2. Тогда Р(г) =Р(гог,), Р,(х) = =Р,(г!, гг), г=1,2 и ! — ()г(а! — а,г,+аг — аггг) Р (г„г,) = (1 — а, рг! — аг])г!) + Р, (г„г,) — + а! — агггч а,— а,гг ! — ()г(а! — а,гг+аг — аггг) + Р,(г,,г,) а! — аггг+аг — аггг 175 [! — х» р1(й» вЂ” а»х1+Й2 — Й2з2)[Р»(з», зг) + + [1 — гг — ' [)2(а, — а!з!+Йг — агаг)[ Рг(з», хг) = = [Й121 — Й»+йгзг — Й2[ (1 — Й1Р!! — Йгнг»).
Так как М»-! =- [г,=! и М»-г — [2,=1 дР(г„гг) дР(2„22) д21 1,=-1 (2) из (1) находим 2 2 М1., =- ~мх„+ ~,х, + 1~'! Р,(1,!)+ '~" Р (1, 1), 2 2 где хи= ' ' ~п 1, 1=1,2; 1=-1,2. дР (г 2) дг [„=1 1 Далее, дифференцируя (2) по а! в точке х!» гг=! и по хг в точке х! = гг = 1, получаем (! — Й»р!1) Р! (1, 1) — а!Рг!Рг(1, 1) = а!(1 — а»[)!! — Йгнг!) — агриР»(1, 1) + (1 — аг[)21) Рг(1, 1) =Йг(! — Й»Р» — агнг»). Из этих двух соотношений находим (4) + (айаг! — Й,агргг) аг+ ( ! — аг[!»и) хм+ ( — а»[)21 ) хгг= О, — агг а! Р! 2+ 2 ( — агр ! ! ) х» г+ 2 (1 — агрг») хгг+ + ( — 2+ 2агр㻠— агг ргг) аг = О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
