2. Системы массового обслуживания. Матвеев_ Ушаков (1984) (1186155), страница 20
Текст из файла (страница 20)
о1 3. Совместное распределение времени начала обслуживания Х-го пакета и числа требований в нем. Функция Яя <н>(и), введенная:в п. 2, определяется по одним и тем же формулам .для всех, рассматриваемых дисциплин обслуживания внутри пакета и существенно используется прн определении виртуаль- ного времени пребывания в системе. Введем последовательность функций йо(я, г) =г, й„ы, Я,, г) =Р(Я+а — ай„(Я, г)), п)0. Л ем м а 1. Функции д (н>(я, г) определяются по формулам д~~~ (я, г) = й" (я, г) — й~, (я, 0), )т' > 1. Д о к аз а тел ь с т во.
Доказательство леммы разобьем на несколько этапов. 1. Докажем, что функции д (н>(я, г) удовлетворяют рекуррентным соотношениям ф~' (я, г) = д~'~ — и (я, р (я + а — аг)) — д~" — и (я. 0), овп (я, г) = г"' (1) $ Докажем первое соотношение (второе очевидно). Воспользуемся методом введения дополнительного события. Будем считать, что в систему поступает пуассоновский поток «катастРоф» с интенсивностью Я>0. Тогда дз <н~(Я) можно интеР- претировать ~как вероятность того, что Ж-й пакет состоит из / требований (при 1>1), до момента начала его обслуживания 108 система не освобождалась и в нее не поступали «катастрофы», при условии, что в момент <=О началось обслуживание нулевого пакета, который состоял из л> требований. Функция <Й>„<>«>(я) имеет следующий вероятностный смысл: это вероятность того, что после обслуживания (й> — 1)-го пакета система впервые освободилась, до этого <момента не поступалн «катастрофы», при условии, что нулевой пакет состоял нз и> требований ~и его обслуживание началось в момент <=О.
Справедливо соотношение а<я >( ) 1>1 а<л — и (я) ( е — <8~- >» (""),(В'! („) (2) <= ! <> Введем события А<=(й<<>«->>=1, до начала обслуживания (>у — 1)-го <пакета не поступали «катастрофы» и система не освобождалась, за время обслуживания (Л< — 1)-го пакета не поступали «катастрофы» и поступило / требований). Тогда, очевидно, А<ПА<=Я прн <Ф), М <. >( ) в (1 л>«» 7«о> >ж <=! Но при 1)1 Р(А>/й«о> и>, Т<о> 0) Таким образом, (2) доказано.
Умножая (2) на г> и суммируя по ! от 0 до оо, получаем (1). 2. Докажем теперь, что йя(я,г) =Йя >(я, р(я+а — аг)). (3) Воспользуемся методом:математической индукции. При й<=1 й,(я, г) =р(я+а — ай<>(я, г) ) =р(я+а — аг) = =Й<>(я, р(я+а — аг) ). Предположим, что (3) выполняется прн й<'=й, н докажем, что оно выполняется при й>=й+1. Действительно, й»(я, р(я+а — аг)) =р(я+а — ай» >(я, р(я+а — аг))). По предположению индукции Й>, >(я, р(я+а — аг)) =:й»(я, г). 109 Следовательно, Йо(з, р(з+а — аг)) =р(з+а — айо(я,г)), и, значит Йо(з, р(з+а — аг) ) =Йо-><(з, г).
3. Докажем теперь утверждение леммы. Воспользуемся ме- тодом индукции. При»<=1 из (1) имеем д <п(з г) д <о>(з на(Я+и )) д <о>( О) но д <о>(я, г) =г'", следовательно, <о>(з р(з 1 и иг) ) — (р(я < и иг)) т д <о>(з О) — 0 Далее, Й<(з, г) =р(з+а — аг), Йо(з, 0) =О. Следовательно, дщ<<> (3, г) = Й<~ (я, г) — Йо"' (3, 0) . Предположим, что для всех й(<о д<"> (я,г) =- й'*(я г) — Й"* (я 0) Докажем, что д<н+'> (з,г) = Йй+<(з,(г) — й" (я, О). Из (1) имеем д<н+'> (з, г) = <><н> (з, р (з+ а —,аг)) — <><н> (з, 0). В силу предположения индукции <)<н> (з, г) = Йн (з, г) — ЙР, (з, 0).
Следовательно, ч<н> (з,'р (з+ а — аг)) = Й'" (я р (я+ а — аг)) — Йй (з, 0), 4<н> (з> 0) = Йй" (з, 0) — й~ > (з, 0) . Ф Отсюда д<"+<> (з, г) = Ь'" (з, (> (з+ и — иг)) — Й'" (з. О). В силу (3), Йн(з, р(з+а — аг)) =Йн+<(з, г)' и, следовательно, с(<н+<> (я, г) = ЙД,, (я, г) — ЙД(з, О) и 4. Виртуальное время пребывания в системе в момент Т е о р е м а 1. а). Для дисциплины 11РО ,( д)= Р(') ~1+ ' >д (д+а — ап<д> 1 д — о — а+а(>(о) х ~~>~ ~Й„(д, р(з+ а — ар(з))) — Й„(д, р (д))]~ =о 1 1'0 г). Для дисциплины дифференцированного обслуживания аа о, (з, о) = ~~~~ (Ь„(в, ]3 (з)) — й„(о, Да+ар — арр (и)))],: о — +о рр( ) =о о*(з, у)— ($($) х о — +о(1 — р)- (1 — р)()( ) Х ~) ]6„(д,р(в+ар — арр(з))) — Ь„(ц,р(в+а — а])(з)))].
" а=о Лемм а 3. Для дисциплин 11РО, КЯ и разделения процессора о(з, д) = ]у+а — ап(д)] '(р(з)+аб(з, д)); для дисциплины дифференцированного обслуживания о;(з, д) = [д+а — ая(о)] '(б(з)+ад;(з, о)), 1=1, 2. Доказательство леммы 2. Рассмотрим каждую дисциплину отдельно. а). Дисциплина 1.1РО. Докажем справедливость соотношения ° е ав ю о с)-о У(у,() = ~'') ~'] ] е-'(" и х о=а)=~а=оо Х В'~о+и(8 + у — о) айг(",> (и) д„В'/ (о — и). (4) В левой части (4) стоит вероятность того, что виртуальное время пребывания в системе в момент ( меньше у и до момента ( система не освобождалась, при условии, что в момент (= =0 в системе было одно требование.
Это событие эквивалентно объединению следующих попарно непересекающихся событий А„ь (и'-зО, 1 а1):А„;=(в момент ( происходит обслуживание и-го пакета, состоящего из 1 требований, 0< р(1) <у, Е.(т))0, тен(0, ()/Е.(0) =1). Но так как функция распределения длительности обслуживания пакета, состоящего из 1 требований, есть В")(х) и время пребывания в системе виртуального требования складывается нз его времени обслуживания и длительностей обслуживания требований, поступивших после момента (, но до момента окончания обслуживания и-го пакета.
(а(а — !))а Х ВЧ "+И (( + у — о) г(Щ)",> (и) д,В' (о — и) . 112 ))з (4) находим и(е, с)) = ~~)) 1~~ ~~) ~ ~ е-осе-55 х О-Ос=< ~ОО О с с+о х С Г е — '<' — '> 1'(" )1 с(ОВ'<'+и (! + у — о) х .! <5) е) <н) м о с х с(<~<"> (и) с(„В" (о — и) с(!. Меняя порядок интегрирования, получаем О(5,<)) = ~~~~ ~ ~ ~ Е-ОСЕ-ст Х О=Ос=) О=ОО 5 5 х е <' — ') с(ОВ*<о+)> (! + у — о) с(<е("> (и) <1,В'! (о — и) с(!. Отсюда о(5,<)) = Я ~' '1 ~ ') е — <'+' — 'З<'>>" Х Х Е вЂ” <д — 5-5+по<с>)<>р (З) С(<Е<л> (и) СХ В'! (Π— и) <11, или )й (5) о — 5 — о+ой(5) ~ е с )<5> .1<5> о=ос=)о й х ~е — <'+' <><с)><' — "> — е — о< ")) с(()<") (и) <1 В'! (о — и) = д ~М 1Р ~,<.>(, ~(„.
а~(,))) ...(, ~(,))) о †5 †о(5) йо Воспользовавшись леммой 1, получаем о(5, с)) = ) ~(И„(<), р(5+ а — ар(5))) — И„(с(, ~(с)))). 5=0 б). Дисциплина ЯЬ. Для данной дисциплины Р(у, !) опре- деляется формулой в, ° с с->д Р(у,!) = ~; ~Г ). ~ ~ е-<-">х ~=ос=< о=оо с х . — (В((+ у — о) -<- В'((+ у — о) -<- ... + (о(о — о)15 ! ь! 1+1 113 + В*("+') (! -1- у — и)) ([(;)(.,") (и) (!ОВ")' (и — и).
Отсюда Ф о(з,()) = т' о~()'"!) (()) Х (д — 5)а[1 — 1)(5)1 О.О,[ О л=о)=! -55 -Ог) р( ( 5( )! ) ([Вч) (и) о Но О(! — В(5)) ! — ехр ( — а(1 — р(5! )О) (' =- е-т ([у, о Следовательно а[! — В(5)) й(5) ()(л) (Ч) Х (о — 5)а[! †()(5)1 ~ ~ Е о л=о;=! о(з, ()) = х ~ (е — (5+т)5 — е — (О+о)О) ([В'/ (и) ([у = ,! (О) о О[! — В(5)! 5 ~~) ~ (у1"'(у р (о+у)) — 41") (у 0 (у+у))ИЪ (Π— О) а( ! — р(5)1 о,=о и в силу леммы 1 О[! — В(5)! о(з у) =,, „,,и ~ ~~~, Р.(у.
1(а+у)) — йлИ р(у+у))) ~у. о л=о 5 5 5 ! !+а ')5(у, х, [) = !), ~~' ~) ) ~ е — '(' — ") х О=О)=(О=ОО Х Р (ОО (Х) ( ! -1- У вЂ” и) ([(~(л) (и) ([„Вч (и — и) . (а(о — О)1» Отсюда о(з,х,д) = ~ ~) '~ ~ ) ) е-"Х «=О)=)О=ОО О О 114 )в). Дисциплина разделения процессора. Пусть некоторый пакет состоит из а+1 требования, одно из которых имеет вре-~ мя обслуживания х (х-требование).
Обозначим через оо(х)! время пребывания х-требования в системе начиная с момента,' начала обслуживания пакета, которому оно принадлежит.! Тогда х е — '!" — !>е ! "! 1 " ")1 Ме "о!'а)~1!! (и)су Вл(о — и)е(!. (5) Найдем Ме "о'!. Случайную величину оо(х) можно найти следующим образом: если т из Й требований имеют время обслуживания меньше х (обозначим эти времена через хь...,х ) я Й вЂ” т больше или равно х, то оо(х) =х!+...+х„+ (/г+1 — т)х.