2. Системы массового обслуживания. Матвеев_ Ушаков (1984) (1186155), страница 21
Текст из файла (страница 21)
Далее, т требований из й имеют время обслуживания меньше х с вероятностью Со'" [В(х) ] '" [1 — В(х) ] ~ —, и при выполнении этого события х!,...,х независимы в сово- купности и одинаково распределены с ф. р. В(у)/В(х), ()<у< (х. Следовательно, Ме о!и = Я С!, [В(х)]'" [1 — В(х)]о — ПМе *"!е "~+! е=о /=1 е-яо(В(х) Ме — юк, ) е — ьк [1 — В (х)])о, но к Ме " = [В(х)]-т~е о!1В(у), значит, о Ме '"о!'! = е "у' (з, х), где у (з, х) = ] е-м г(В (у) + е — [1 — В (х)]. о Подставляя найденное значение Ме "о~ ! в (5), имеем о(з, х, д) = — ~ ! ~ д!",>(д) )с а=о)=! х [р! (з + а — ау (з, х)) — р! (д + а — ау (з, х))] =— ~~)~ ~[а„ (д, р (з + а — ау (з, х))) — Ь„ (д, [3(д + а — ау (з, х)))] . о — я п=о г).
Дисциплина дифференцированного обслуживания. Для данной дисциплины обслуживания справедливы следующие соотношения: ю ! 1+9 р(у,1)=~. ~, ~Г~ ~ е — 'и")х п=о!=!о=оо 115 х 11 "11 РСР'(1 — р)ел х л с~ с=о х В'и+и (1 -~- у — о) сй3<",> (и) Ы„Вп (о — и). . (6 ю ~ ~ 1+У )7(„,1)=~~ ~ ~'~ ~ е-'« "'х ь=е у'=1 и=о и=о е х 1~(' — еЛ ' м, о 1~1~ — 01'* ер ьр г=в х В*0 +'+и (1 + у — о) сй~<"> (и) й„В'~' (о в и) . (7 Переходя в (6) и (7) к преобразованиям Лапласа по 1 и преобразованиям Лапласа — Стилтьеса по у и произведя необходимые преобразования, получаем утверждение леммы 2 дляя дисциплины дифференцированного обслуживания.
До к аз а тельство леммы 3. а). Дисциплины 1.1ГО, К8 и разделения процессора. Пусть Р,Я вЂ” вероятность свободного состояния системы в момент времени 1, Р(и)Ни — вероятность .поступления требования в свободную систему в интервале (и, и+ди). Для всех рассматриваемых дисциплин справедливо соотношение 1Г (у, Г) = Р (1) В (у)+ ~ Р (и) )7 (у, 1 — и) ди, о откуда (8) о(е, Ч) =РеЮр(е) +РИ)б(е Ч) где РеМ) = ~е-"Р,ЯМ РМ =~е-"Р(1)й. о о Функция ро(д) одинакова для всех рассматриваемых дисциплин и совпадает с аналогичной функцией для дисциплин ы Р1ГО: Ро(д) = [д+а — ап(д)) где л(д) — преобразование Лапласа — Стилтьеса длительности периода занятости.
Найдем р(у). Так как о(0, д) =1/д, то д ' — (д+а — ал(дЦ-' и(о, д) (9 Из леммы 2 следует, что для всех рассматриваемых дисципли о(0,д) = д-' ~ (Ь„(д,!) — Ь.(о,б(д))). в=в 116 р(з пункта 2 доказательства леммы 1 следует, что й. (ч, б (у) ) =-й.. (у, 1) Кроме того, из определения последовательности функций Ь„(я, г) следует, что 1пп п„(Я, г) =Я(Я) и йс(Я, 1) = 1. Следовательно, о(0, д) = Подставляя найденное значение б(0, д) в (9), получаем р (д) = а [д+ а — ап (д) ] — '.
Теперь из (8) имеем о (я, а) = [д+ а — ая (о) ] -' (8 (я) + ао (я, о) ). б). Доказательство в случае дисциплины дифференцированного обслуживания аналогично. И Д о к а з а т е л ь с т и о теоремы 1. а). Дисциплины ).1ГО, КЯ и дифференцированного обслуживания. Утверждение теоремы получается после подстановки значений б(я, д), б,(я, д) н бя(я, д), полученных в лемме 2, в соотношения, связывающие о(я, а) с б(я, а) и о~(я, а) с б;(я, д) из леммы 3. б). Дисциплина разделения процессора. Утверждение теоремы является следствием лемм 2, 3 и соотношения о(я, о) = ] о (я, х, о) дВ(х). ~ о Следствие.
Пусть а~~(1. а). Для дисциплин 11РО, )тЬ и разделения процессора су- цествует предел Р(1) =~- 1', 1-~со, а для дисциплины дифференцированного обслуживания — пре- делы Р;(1) =~- 1'ь 1-~со, 1=1, 2, причем функции о' (я) = Ме , о; (я) = Ме '~~ определяются по формулам: а1) для дисциплины 1.1ГО о,' (я) = (1 — ар,) р (я) [ 1 — Х 5+ с — йг (5) 117 х ~, [Ь„(0, р(з+ а — ар(з))) — Ь„(0, 1)]~; — о а2) для дисциплины КЯ о' (з) = (1 — а[),) р (з) [!1 — [з (1 — р (з))] — ' х а[1 ои)] а х 1 Е [Ь. (О, Р(з+ у)) — и.
(О, Р(у))] с(у); о а о аЗ) для дисциплины разделения процессора о" (з) = (1 — а[),) [!р(з) — аз-' ~ ~ е-" х =о о х [Ь„(0, [) (з+ а — ау (з, х))) — Ь„(0, 8 (а — ау (з, х)))] НВ (х)]; а4) для дисциплины дифференцированного обслуживания о',(з) =(1 — К)8(з) ~1 — ' х о — ар + ар() (о) ° 0 х ~~)~ ~[Ь„(0, р (з)) — Ь„(0, р (ар — арр(з)))]~, а=о оо (з) = (1 — Ф~) Р (з) Х о — а(1 — р)+ а(1 — р) р(о) Х ~~~~ [Ь„(0, 8(з+ ар — арр(з))) — Ь„(0, Ф(а — ~Ф(з)))]~.
а=о 6). Среднее виртуальное время пребывания в системе стационарном режиме равно 61) для дисциплин (.1ГО и Й8 му=1,+ 'Ц 2 (1 — а~,) 62) для дисциплины разделения процессора Ю 1+ оа) х (1 — В (х)1 аВ(х) МУ = Я, + 2 (1 — аб,) ! + а~, бЗ) для дисциплины дифференцированного обслуживани для первого приоритета М(,, р ! аро !+арр1. ~2 (1 — а~,) 1+ а~~ 118 а р,.>0, 1=1, л, ~ р; =1. а б) В(х) = Я р;(1 — е '), ~=! Задача 4. Сравнить 0У при дисциплинах 1.1гО и КБ.
Литература: (2, 3, 1О, !5, 18]. для второго приоритета ай, 1+(1+р)ар, МУ,=„+ 2 (1 — аР,) 1+ ай, 5. Заключение. Предложенный в этом параграфе метод изучения систем с пакетной обработкой применим также к ана- лизу других характеристик, например длины очереди и других дисциплин обслуживания внутри пакета. Одна из таких дис- циплин в более общей системе, чем М1611~аа, будет рассмот- рена в следующей главе. 6. Задачи. Задача 1. Доказать сходимость рядов, фигурирующих в формулировках теоремы 1, лемм 2 и 3 и следствия.
3 а д а ч а 2. Найти 0У, 0У,. 3 адач а 3. Сравнить МУ при дисциплинах КБ и разделе- ния процессора, когда ьа а) В(х) = ~ — "е — айс, й)0; о Глава 3. Одноканальные приоритетные системы обслуживания с пуассоновскими входящими потокам В предыдущей главе были изучены СМО с различным дисциплинами обслуживания. Во всех этих системах неравно прввие требований ~возникало либо за счет того, что они посту пали ~в разные моменты времени, либо за счет разных реализа ций длительностей обслуживания. Вместе с тем существует широкий класс реальных систем в которых неравноправие требований предполагается заранее независимо от моментов поступления и длительностей обслу жевания.
Примерами могут служить телеграммы различны категорий срочности, междугородные и внутригородские теле фонные разговоры, отладочные и счетные программы на ЭВ и т.д. Математической моделью таких реальных систем служа системы массового обслуживания с приоритетами. К настоящему ~времени построена достаточно полная тео рия однока~нальных систем обслуживания с приоритетами пуассоновским~и ~входящими потоками. Анализу именно таки моделей и посвящена данная глава. В первых двух параграфах вводятся различные приоритет-' ные правила и анализируются наиболее важные случайны процессы, характеризующие функционирование системы обслу живания.
В $3 иллюстрируется применимость метода ~вло женных цепей Маркова к анализу приоритетных систем В 5 4 рассматриваются две дисциплины обслуживания в приоритетных системах, использующие информацию о реализация длительностей обслуживания. В последнем, пятом, параграфе главы решается простейшая задача об оптимальном назначении приоритетов. 5 1. СИСТЕМА М,)0,11)со.
ДЛИНА ОЧЕРЕДИ 1. Описание системы. В одноканальную систему обслуживания поступают г независимых пуассоновских потоков требований с интенсивностями аь аь,а, соответственно. Длительности обслуживания требований — независимые в совокупности случайные величины, стохастически эквивалентные для требований ~'-го,потока сл. в.
Во имеющей ф. р. В;(х) =Р(В;<х) и плотность распределения Ь|(х), 1=1, г. Требования ~'-го потока имеют более высокий приоритет, чем требования 1-го потока при 1<1. Мы будем рассматривать следующие приоритетные правила. 1. Относительный приоритет (схема О). Прерываний обслуживания не допускается. После окончания обслуживания сле- 120 дующим на .прибор ~из очереди выбирается требование |наивысшего приоритета. 2.
Абсолютный приоритет. Выбор требований из очереди после окончаний обслуживания происходит так же, как |при относительном приоритете. Кроме того, если во время обслуживания некоторого требования ~в систему поступает требование более ~высокого приоритета, происходит прерывание обслуживания, и прибор занимает поступившее требование. С требованием, обслуживание которого было прервано, можно поступать по-разному. Мы будем рассматривать следующие три возможности: 2а) прерванное требование теряется (схема А1), 2б) прерванное требование возвращается в очередь на первое место среди требований одного с ним приоритета к при новом поступлении на прибор обслуживается заново (с новой реализацией времени обслуживания) (схема А2), 2в) прерванное требование возвращается в очередь на первое место среди требований одного с ним приоритета и при новом поступлении на прибор дообслуживается (схема АЗ).
Итак, требования разных потоков обслуживаются в порядке, определяемом выбранной системой приоритетов. Требования же одного потока обслуживаются в соответствии с принятой дисциплиной обслуживания. В этом и ~в двух последующих параграфах мы будем ~рассматривать д|ве дисциплины: Г1ЕО (прямой порядок) и ПРО (инверсионный ~порядок). Если в формулировке какого-либо результата иет указания на дисциплину обслуживания, подразумевается, что он сараведли~в для любой из двух указанных дисциплин. 2.
Основные обозначения. Наличие требований разных приоритетов обусловливает необходимость более детального изучения соста|ва очереди, чем это было в предыдущей главе. Пусть 1-(1) =(Т-~(1).-,1 (1)), где Е;(1) — число требований 1-го потока (приоритета 1) в системе в момент времени б Положим Р(п, 1) = Р($. (1) =и), и= (пь .. и,), р (х, е) = )е е —" Мх'ю й(, х = (г,, ..., г,), о Р,(е) =Ме — 'еа, Дп=М(ри]У', о,=а1+...+аь о,=о, а'=а;+,+...+а„ (а, х);=а~г~+...+а;г„(а, х),= (а, г), (а, х)'=аемгим+...+а,г,.