2. Системы массового обслуживания. Матвеев_ Ушаков (1984) (1186155), страница 19
Текст из файла (страница 19)
= А) =1, а=а !пп Ри(г) =Р(г), Р(1) =1, и Следовательно, используя уже доказанное утверждение а) тео- [ ремы, имеем (г — ! ) [)(а — аг) (рг+( ! — рВ Р(0) ! г — (рг+(1 — р) ) р (а — аа) Из условия Р(1) =1 находим Р(0): Р(0) =1 — р — а[)ь Я' 3 а м е ч а н н е. Из результатов теоремы 4 н следствия к ' теореме 2 следует, что стационарные распределения процессов! 1.(() н (Еь) не совпадают. 6.
Задачи. 3 ада ча1, Найти 0П, ОЕ, М((У н Ойу. 3 а д а ч а 2. Найти производящую функцию числа квантов,' обслуживания, выполненных.за период занятости. й 3. ДИСЦИПЛИНА РАЗДЕЛЕНИЯ ПРОЦЕССОРА 1. Описание дисциплины. Рассмотренный в предыдущем па-! раграфе частный случай дисциплины разделения времени несколько нскусствен. Его отдельное изучениеобъясняется,содной стороны, относительной простотой анализа н, с другой, — иными, интерпретациями этой системы обслуживания (одна нз которых указывалась в предыдущем параграфе), имеющими большнй самостоятельный интерес. Анализ систем обслуживания с дисциплиной разделения времени прн общих предположениях относительно распределе- 102 ния времени обслуживания и величин квантов обслуживания очень сложен.
В этом параграфе мы рассмотрим важный част- ный случай дисциплины разделения времени — дисциплину разделения процессора (в литературе ее также называют дис- циплиной равномерного разделения процессора или прибора). Неформально эту дисциплину обслуживания можно описать следующим образом: величина кванта обслуживания в дисцип- лине разделения времени, выделяемого каждому требованию, устремляется к нулю.
Это приводит к одновременному обслу- живанию всех находящихся в системе требований, причем если в течение некоторого времени Т в системе находится й требо- ваний, то оставшееся время обслуживания каждого из них убы- вает на величину Т(я. Другими словами, общий ресурс обслу- живающего прибора равномерно распределяется между всеми требованиями, имеющимися в системе. Более точно дисциплину разделения процессора можно опи- сать с помощью понятия скорости обслуживания (с помощью этого понятия можно ввести большое число дисциплин обслу- живания, представляющих значительный интерес при изучении работы вычислительных систем).
Скажем, что требование, поступившее в систему в момент 1, обслуживается со скоростью с(х), если время его пребывания в системе г' связано с временем его обслуживания В (при изу- чении описываемого класса дисциплин В чаще называют дли- ной требования) равенством ~+я ~ с(х)дх = В. Дисциплина обслуживания задается набором скоростей (с~п, сап, ..и спп', и=1, 2, ...), где схп — скорость обслуживания й-го по порядку поступления требования, когда в системе находится и требований, причем и Я с,„= 1.
Последнее условие означает, что ресурс прибора ~=1 постоянен и распределяется между имеющимися в системе требованиями пропорционально с;и. В множестве введенных дисциплин обслуживания изученная ранее дисциплина НГО, например, задается набором скоростей с~п=1, сап= ... =с„„=О. Дисциплина разделения процессора за- дается набором скоростей с,„=сз„= ... =с =1/и. 2. Основные результаты. Пусть 1.(1) — число требований в системе в момент времени 1, х,(1) — остаточные времена об- служивания требований, находящихся в системе в момент вре- мени 1 (1=1... и, если 1 (1) =и), Р и (1) = Р (1 (1) = й ), д" Рх (хо . хе 1) Р (1 (1) К х (1)(х ... хх(1)(хх) дх,, дхп 103 Случайные процессы Ь(!) и (1.(1), х»(!),...,хх!»!(!)) являются регенерирующнми, точками регенерации служат моменты окончания периодов занятости. Легко показать, что выполняются условия теоремы 4.4 Введения.
Отсюда следует существование пределов 1!гп Р»(!) =рм !пп Р»(х!,, хм !) =р»(х!, ..., х»), ! причем при а!)»(! Х р»=1. В силу равномерной ограниченности »=о (по !) Р»(хь ..., х», !) (которая следует из (1)) отсюда следует существование др»(х„... „х», !) »-в ао д! Пусть условие ар»(! выполнено. Переходя к пределу при 1-~со в (! ), имеем 1 чЧ др»(х», ..., х») — — = — ар„(х,, ..., х») + а Ь дх! /=! а %! + — о р (х, ..., х, х»+!.....
х») Ь(х!) + »=! »+! ~~) ' Р,+, (х„..., х; „О, хь ..., х,). (2) /=1 Так как р, = ~ ... ) р» (х„..., х») Ых!... г!х», Ь о то ~ р (х„..., х») о(х ... о(х», =1. (3) »=оа о Решение (2) записывается в виде р»(х», ..., х») = са» П !! — В(х!)) (4) »=! (это легко проверяется непосредственной подстановкой (4) в (2)). Из условия (3) находим с: с=! — ай!.
Как уже отмечалось, р» = ~ ... ) р»(х„..., х»)»(х!... »(х». а а 105 Подставляя сюда полученное в (4) выражение для рь(хь ... ...,хь), имеем ря= (1 — ар1) [ар1) Я. $4. ДИСЦИПЛИНЫ ПАКЕТНОЙ ОБРАБОТКИ ТРЕБОВАНИЙ 1. Введение. Описание дисциплин, Широкий класс дисциплин обслуживания, имеющих важное значение при моделировании реальных систем, образуют так называемые дисциплины пакетной обработки. Сущность дисциплин пакетной обработки заключается в следующем: ~все поступающие в систему требования объединяюгсй в группы требований — пакеты. Обслуживание пакетов происходит в порядке их формирования. Среди требований одного пакета принимается какая-либо дисциплина обслуживания. В этом параграфе мы рассмотрим следующие дисциплины внутри пакета: ШГО (инверсионный порядок), КЬ (случайный порядок), дисциплину разделения процессора и дисциплину дифференцированного обслуживания (точные определения будут даны ниже).
На функционирование системы обслужпванияс пакетной обработкой, помимо дисциплины обслуживания внутри пакета, существенное влияние оказывает способ формирования пакета. В данном па~ратрафе мы рассмотрим один из наиболее важных и распространенных способов — естественное формирование, которое заключается в следующем: требования, находящнеся,в системе в момент 1=0 (если они есть), образуют нулевой пакет. Если в момент 1=0 система свободна, нулевой пакет образует первое поступившее требование. Пакет с номером У .(А1)1) составляют требования, поступившие за время обслуживания (Л' — 1)-го пакета, а если ни одного требования за это время не поступило, первое требование, поступившее после окончания обслуживания (М вЂ” 1)-го пакета.
Как уже отмечалось, требования пакета с номером У вЂ” ! обслуживаются ~ра~ньше требований пакета с номером У. Для требований одного пакета будем рассматривать следующие дисциплины: ШГΠ— требования одного пакета обслуживаются в порядке, обратном их ~поступлению ~в систему; 1(Ь вЂ” требования одного пакета обслуживаются в случайном порядке, а именно: пусть пакет состоит из й требований. ,Тогда с вероятностью 1/й первым будет обслуживаться любое из иих, вторым — с вероятностью 1/(й' — '1) любое нз оставшихся и т. д.
дисциплина разделения процессора — все требования одного пакета обслуживаются одновременно со скоростью (относительно понятия скорости обслуживания см. $3) !/й, если одновременно обслуживаются й требований; дисциплина дифференцированного обслуживания — каждо~му требованию, входящему ~в пакет с вероятностью р, при- 106. сваи~вается первый приоритет и с вероятностью 1 — р — второй независимо от остальных требований. Требования первого приоритета обслуживаются раньше требований второго.
Требования одного приоритета обслуживаются в порядке их поступления в систему. 2. Основные обозначения. Пусть а — интенсивность входящего потока, длительности обслуживания требований — независимые ~в совокупности случайные величины, стохастически эквивалентные сл. в. В, р(з) =Ме-'о б>=МВ>, Т«> — момент начала обслуживания, а т«> — момент окончания обслуживания <его пакета, >><<о — число требований, входящих в >-й пакет, 1<(1) — виртуальное время пребывания,в системе в момент 1, т. е.
время, которое находилось бы в системе требование, если бы его поместили в систему ~в момент времени 1. При рассмотрении дисциплины разделения процессора будет также изучаться случайная величина У,(1) — виртуальное время пребывания ~в момент < для требования с временем обслуживания х, а прн рассмотрении дисциплины дифференцированного обслуживания †'У<(1) †,виртуальное время пребывания в системе в момент 1 для требований <что приоритета, >= =1, 2. Пусть Е(1) — число требований в системе в момент й Положим < >. <и>(и) =,Р(Т<><>(и 1<1<а>=( Т.(1)~0 <ен [Т<о> Т<л>) (И<о> т, Т<о> О) при 1> 1 <',>от<и>(и) =.Р(т<" '>(и, В(т<" '>) =О, Ь(<)чЕО, 1ен(Т<о>, <<а — '>) (Л><о>=т< Т<о>=0), д<>о>(з) = ~е — '"<(()<и>(и),<)<и>(з,г) ч)~ г>д<и>(з), / о 1' (й' г) = Р (к (г) < й) е (з, <1) = ~е-"Ме '"<'> <(1.
о Кроме того, для дисциплины 1разделения процессора р(у, х,() = Р(1> (1) (р), е(з, х, 1) = ~ е-пМе '><к<по(1, о а для дисциплины дифференцированного обслуживания Р<(р 1) =Р(Р (1) <р). 107 о, (, д) = ~ сон Ме ' о Пусть, далее, у(у,т) =Р(0<У(1) <у, А(т) >О, тяп [0,1) (1 (0) =1), Р(у, х, г) =Р(0<У.,(1) <у, Ь(т) >О, те:-[0,1) )Е(0) =1), Рс (у, 1) = Р (0< Ус (1) <у, У (т) > О, тен [О, 1) /1 (0) = 1), Ф о (я, у) = ~ екн М [е — '"сп 1 (ь (т) > О, т ен [О, 1))!Ь (0) = Ц дт, о а (я, х. д) = ~ е-" М [е ' 'и 1 (Е (т) > О, т ен [О, 1))/Е. (О) = ! ] с(1, о о (я, д) = ~ е-"М[е '~чо.((Е(т) > О, тен [0,1))/Е(0) = 1[й.