2. Системы массового обслуживания. Матвеев_ Ушаков (1984) (1186155), страница 26
Текст из файла (страница 26)
Следовательно, 1 1 — пьь! (д) р,(д) — ~, [1 — р; (рь ь! (д))] р![(д) = О, й = О, г, 1=в+и Докажем, что (3) Для этого заметим, что длительность промежутка (Рь(1) не изменится, если требования приоритетов 1, Кпоступившие до( и оставшиеся в системе к этому моменту времени, будут обслуживаться раньше требований этих потоков, поступивших после 1, т.
е. если поступающие после 1 требования могут начать обслуживание (в порядке, определяемом системой приоритетов и дисциплиной обслуживания) только после окончания промежутка й!ь(1). Используя это замечание, (3) легко доказывается методом введения дополнительного события. Соотношение для определения ыь"'(з, д) в этом и во всех остальных случаях является непосредственным следствием соотношений, определяющих оь(з, 1).
Схема О. Дисциплина 1.1ЕО. Заметим прежде всего, что длительность промежутка Ф!,(1) не зависит от того, какая дисциплина — НГО или 1.1ГΠ— выбрана среди требований приоритетов 1,я — !. Поэтому можно считать (при определе- !45 В соотношениях (1) и (2) неизвестными остаются функции Ра(х) и Р;(х) (1=1, !). Покажем, как их найти непосредственно из уравнения (2).
Так как функция (от з) з — Я а!(1— 1=1 — р!(з))-~оо при з — со, существует зо, такое, что при з>за з — Я а! (1 — р, (з) ) > О. нни оь(з, Г) и ио'( з, а)), что среди требований каждого и~( потоков 1,Й вЂ” 1 принята дисциплина Р!ГО. Пусть йо,(з, !)~ имеет тот же смысл, что и раньше. Тогда нз последнего наше-' го предположения следует, что го»,(з, 1) определяется формулой (2). Далее, легко показать, что о)»(з, 1) = ⻠— ~ (й»~~ (з), 1) . + )г Р, (и) ехр ( — а» (1 — Й» (з)) (1 — и)) г(и х о М х ~ [1 — П», (х — и)) д (1 — е — "). и (4) В левой части (4) стоит вероятность события С(з, 1) =(за время ! не поступали «плохне» требования приоритета Й). Событие С(з, 1) эквивалентно объединению следующих событий: а) «Катастрофы» не поступали за время !+Ю'о(1) вероятность этого события равна е — иыо(з, 1)); 146 Отсюда вытекает утверждение теоремы в случае относительного приоритета.
б) Схемы А1, А2, АЗ. Дисциплина Р1РО. Доказательство для всех схем проводится одинаково. Назовем Й-циклом, свя-' занным с данным требованием приоритета Й, Й-цикл, который с него начинается. Требование приоритета Й назовем «хорошим», если за связанный с ним Й-цикл не поступали «катастрофы», и «плохим» вЂ” в противном случае. Тогда каждое требование приоритета Й является «хорошим» с вероятностью,: Йо(з) и «плохим» вЂ” с вероятностью 1 — Йо(з)' независимо от остальных требований. Следовательно, потоки «хороших» и «плохих» требований приоритета Й являются пуаосоновскими с интенсивностями аойо(з) и а» [! — Йо(з) [ соответственно. Далее, так как требования приоритетов Й+1, г не оказывают ни-.
какого влияния на время ожидания требований приоритета Й, это время будет тем же самым, если рассматривать систему, в которую поступают только первые Й потоков. В остальной части доказательства это предположение будем считать выполненным. Пусть Ро(!) — вероятность того, что в момент времени ! система свободна; Р,(х)Йх — вероятность того, что в интервале времени (х, х+о(х) произошло поступление требования из. потоков 1,Й вЂ” 1 в свободную систему (т.
е. в этом интервале начался с поступления требования в свободную систему й — 1-период). Докажем следующее соотношение:, ехр( — а»(! — Й„(з)) !) = е — "в (з, 1) + + ) Р, (х) ехр ( — а (1 — Й„(з)) (! — х)) о( (! — е — '*) + о б) первая «катастрофа» поступила в интервале (х, х+Нх)', х<1, в момент х система свободна, и за время 1 — х не поступали «плохие» требования приоритета й (вероятность ранна о ) Р,(х)ехр( — а„(1 — й,(з))(1 — х))д(1 — е *))1 о в) первая «катастрофа» поступила в интервале (х, х+сКх), х)0, во время е — 1-периода, начавшегося в интервале (и, и+ +Ни), и<1, с поступления в свободную систему требования приоритета выше Й, й за время 1 — и не поступали «плохие» требования приоритета й (вероятность равна ') Р, (и) ехр( — ао(1 — Ьо(з)) (1 — и)) г)и х о Х )е (! — По ~ (х — и)) й (1 — е — )).
» Соотношение (4) доказано. Из него после несложных преобразований получаем выражение для во(з, 1), указанное в формулировке теоремы. Осталось найти функции Р,(1) и Р,(1). Что касается р, (д) = ~ е — «о Р, (1) с)1, то она была найдена в предыдущем параграфе (при изучении длины очереди). Так же, как при нахождении функций Р,(х) в случае относительного приоритета, имеем ехр( — (з — ໠— аой»(з))х)Р,(х)сХх+ о "() Х 5 о О х ~ехр( — (з — по+ аоа,(з))х) Р,(х)о(х = з — '. о Положим д=з — а»+а„Ь»(з), тогда з=-а+໠— а,л»о(о)) н 1 — ио о(о+ по — аоиы(д)) д+ ໠— а»и»о(д) о х ~е — о«Р,(х)дх = (д+ ໠— аолы(д))-'.
о Отсюда определяется р,(д). 147 Рассмотрим теперь случай дисциплины (-!ГО в системс с абсолютным приоритетом. Пусть Р„(!) и Р,(и) имеют тот же смысл, что и в случае дисциплины Г1ГО (очевидно, в случае дисциплины 1.1ГО они определяются по тем же формулам, что и при Г(ГО), а Р,(и)йи — вероятность того, что в интервале (и, и+с!и) началось обслуживание требования приоритета й и тем самым в этом интервале начался некоторый й-цикл. Назовем ий-периодом, связанным с данным требованием приоритета Й,И-период, начинающийся с обслуживания этого требования. Требование приоритета й будем называть «хорошим», если за И-период, связанный с ним, не наступали «ка-, тастрофы».
В противном случае требование будем называть «плохим». Соотношение ! ° О ы»(з, !) = Р,(1) + ) Р, (и) Ни ') ехр( — (з+ а„— а»пы(з)) х о Ф вЂ” « Ю х (о+ и — !))«ЕП« ~(о) + ~ Р,(и) «!и ~ ехр( — (з+ аз— 1 — и — а,пы(з)) (о + и — г)) г(Н»(о) вытекает ~из следующих рассуждений. Для того чтобы за вре- ' мя (!Ух(!) не поступали «катастрофы» (вероятность чего равна, вх(з, 1)), необходимо и достаточно, чтобы: 1) либо в момент времени ! система была свободна (с ве-1 роятностью Р,(!)); тогда Ю'х(1) =О, а «катастрофы» за интер- ~ вал времени нулевой длины поступить не могут; 2) либо в момент ! протекает й — 1-,период, который начался в интервале (и, и-)«(и), и<1, с поступления в свободную систему требования приоритета выше й и продолжается до момента времени, лежащего в интервале (о+и, о+и+да), о)! — и; за время о+и — ! не поступали «катастрофы» и плохие требования приоритета й (вероятность равна Р,(и)г!и ~ ехр( — (з + а„— а„пы(з)) (о — ' и — 1))йП»,(о)); о 1 — « 3) либо в момент ! протекает А-цикл, который начался в интервале (и, и+да), и<1, и продолжается до момента времени, лежащего в интервале (о+и, о+и+да), о)! — и, за время о+и — Г не поступали «катастрофы» и плохие требования приоритета Й (вероятность равна ) Р,(и)ди ) ехр( — (з — а„— а„п„„(з)) (о —; и — Г)) йН»(о)).
0 1 — « Для доказательства теоремы осталось показать, что Рг(Ч) =(1 — чро(Ч) — (1 — пз ~(ч))Р1Ц))(1 — й,(Ч)) '. (5) Это равенство можно доказать разными способами. Продемонстрируем один из иих. Для функции ыг' (з, а) справедливо соотношение (иепосредствеиио вытекающее из формулы для определения ам(з, 1)) ггг" (з, д) =Рг(д)+ [д — з — аг+аглгг(з)1-'Х Х (Р~ (д) [лг 1(з+ ад — аглгг (з) ) — лг-~ (Ч) 1 + +Рг(Ч) [лгг(з) — йгй)1. 1ак как имеем что эквивалентно (5).
Заметим, что мы доказали утверждения теоремы при а>0 и з>зо>0, однако, используя принцип аналитического продолжения, получаем их справедливость для всех з и д, таких, что Кез>0, Ке а>0. Утверждения следствия можно получить предельным переходом при ~- оо в соотношениях, определяющих оь(з, г). Д о к а з а т е л ь с т в о теоремы 2. Утверждения теоремы 2 вытекают из следующих свойств процесса гг(г).
Для системы с относительным .приоритетом Гг(1) = [Р'~ (1) +Вы где Вг — длительность обслуживания требования приоритета К для которого ищется время пребывания. Для системы с абсолютным приоритетом: схема А! Гг (~) = Ф, (~) + пни [Вы А г[, где Вг — время обслуживания требования приоритета а, Аг— интервал времени между поступлением двух последовательных требований объединенного потока требований приоритета выше lг; схемы А2, АЗ )г~ (г) = ))гг (г) + Оы где Вг — длительность А-цикла, который начинается с требования приоритета а, для которого ищется время пребывания. 3. Задачи. 3 а дача 1. Найти ем(з) предельным переходом при ~- ао в соотношениях, определяющих ыг(з, ~).
доказательства тео 3 ад ач а 2. Найти МЯУ», 1»1Р», А=1,г. 3 ад ач а 3. Доказать соотношения (из ремы 2): а) для схемы О У» (1) = (Р» (1) +В»', б) для схемы А! У»(1) = (Р»(1) +ппп(В» А»); в) для схем А2, АЗ У» (1) = (Р» (1) + Н» $ 3. МЕТОД ВЛОЖЕННЫХ ЦЕНЕН МАРКОВА 1. Определения и обозначения. Метод вложенных цепе Маркова„использованный при анализе распределений длин очереди и времени ожидания в системе М16!1(оо, без сущест. венных изменений применим и к приоритетным система М„) 6„(1(оо.
В этом параграфе мы ограничимся изучением системы с от носительным приоритетом. Занумеруем все поступающие тре бования в том порядке, в котором они поступают на обслужи вающий прибор, т. е., так как не допускается прерываний об служивання, в том порядке, в котором они покидают систему Пусть 1м ()У=1, 2, ...) — момент ухода из системы У-го требо.
ванна, г,=0, тн=(~ — (н ь У)1, Ь»а=1.»(!а+О), где Е»(!) число требований»что приоритета в системе в момент (; ьл=(Епн,...,ь н), )Р»н — время ожидания до начала обслуживания )У-'го требо ванна прн дисциплине Р1ГО при условии, что оно являетс требованием приоритета й рм (й) = Р (Ен = 'к), Рт (х) = Мх ", р»(к) = Р(Е»=йй(»»"-е требование имеет приоритет 1)), Р»»г(х) = М '!х м!()У-е требование имеет приоритет 1)], Р»оо (1»" >, ..., й<">, иь ..., и„) = Р(1.» = 1»п>, 150 связывающие виртуальные времена ожидания и пребывания В1 системе для требований й-го приоритета. 1 3 ад ач а 4. Показать, что при р»1(1 существуют пределы~ У»(!) =~Ум ! — «оо, А=1, г.
1 Ме '~»,МУ»,0У». 1.~+„!=й'"!, те<и!,, ти+ -!<и„), где (й]!! А~!!) 1 1 п л рД! (х! и,..., х'"', з„..., з,) = М ~ П ]хп' ]" н ! ! ' х л х ехр] — ~' з!тнч ! !]], 1=! )Р'сн(и) = Р(йт!и < и), е!сн(з) = Ме (О;х') = (О, ..., О, хеь„ ..., х,), О, = (О, .; ., 0), (О!х') = х . ! Будем использовать обозначения и результаты предыдущих параграфов данной главы. 2. Основные результаты. Те о р е м а 1. а). Функции Рн(г), Р!и(х) и е! и(з) определяются из рекуррентных соотношений г Рн(х)= ~]" ~Рн ! (О, !г!-!) — Рн ! (О!г!)] х 1-! Г м х; !(1!(о — (а, г)) + Рн ! (0,)~ — !р!(о — (а, х)), У)~2, (1) о Г=! Р, (х) = 9 —" р! (о — (а, х)), дф о !=! Рсн (х) = 1Рн ! (О, гг!-!) — Рн ! (О!г!)] х (2) х х,†.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
