2. Системы массового обслуживания. Матвеев_ Ушаков (1984) (1186155), страница 14
Текст из файла (страница 14)
Это связано с тем, что многие важные случайные процессы, характеризующие поведение системы обслуживания, становятся немарковскими. Одним из способов исследования таких систем обслуживания является сведение изучения ее характеристик к другим, которые описываются марковскими процессами. Наиболее распространенными такими методами являются метод дополнительных компонент, ме~од вложенных цепей Маркова, метод виртуального времени ожидания. Все эти методы оказываются наиболее эффективными в случае однолинейных систем с пуассоновскими входящими потоками, изучению которых и посвящена данная глава. Функционирование любой системы обслуживания помимо ее параметров (входящего потока, длительностей обслуживания, числа приборов, ограничений на длину очереди, время пребывания и ожидания и т.
д.) существенно зависит от способа организации обслуживания (дисцнплины обслуживания). ДисЧиплина обслуживания указывает, в каком порядке обслуживаются поступающие в систему требования и каким образом влияет на данное требование наличие в системе других. В этой г,заве будет рассмотрен ряд дисциплин обслуживания, которые имеют большое значение при изучении реальных систем, в частности вычислительных комплексов. Таковыми являются, например, дисциплины пакетной обработки, дисциплины разделения времени и процессора. Многие из них позволяют организовать более эффективное функционирование системы (в определенном смысле), чем просто обслуживание в порядке паступлени.я й ь дисциплины гчго и ыго 1.
Описание дисциплин. Наиболее простыми и легко реализуемыми на практике дисциплинами обслуживания являются следующие: Е(ЕО ' — требования обслуживаются по одному в том порядке, в котором они поступают в систему; прерываний Ьбслу- ю Часто используются также обозначения ГСГЗ вЂ” Игьт соте, Пгь| ьегте н 'кСГо — 1аь1 соте, Пги кегле. 73 живания не допускается, наличие других требований в системе не влияет на длительность обслуживания данного требования: ПРО * — каждое поступающее в систему требование становится в начале очереди, которая есть в системе в момент его поступления; после окончания обслуживания требования следующим на прибор поступает то, которое находится на первом месте в очереди; остальные предположения те же, что и для дисциплины Г)ГО. 2.
Описание системы. Основные обозначения. Система обслуживания состоит из одного обслуживающего прибора, на который поступает пуассоновский поток требований с интенсивностью а. Длительности обслуживания — независимые в совокупности случайные величины, стохастически эквивалентные случайной величине В, имеющей функцию распределения В(х) =Р(В(х). При доказательстве некоторых утверждений мы будем предполагать существование плотности распределения времени обслуживания 6(х). Число мест для ожидания неограничено.
Если не указано противное, будем предполагать, что в начальный момент времени 1=0 система свободна. Основными объектами изучения будут следующие случайные процессы; Е(1) — общее число требований в системе в момент 1; )Р(1) — виртуальное время ожидания в момент времени 1, т е. время, которое ждало бы до начала обслуживания требование, если бы его поместили в систему в момент 1; У(() — виртуальное время пребывания в системе в момент времени 1, т.
е. время, которое находилось бы в системе требование, если бы его поместили в систему в момент (; В'„, 'г'„— соответственно время ожидания до поступления на прибор и время пребывания в системе п-го требования (нумерация требований в каждом случае оговаривается особо). Требование, которое мы помещаем в систему в момент 1 при определении В'(1) и У(О, является фиктивным, в том смысле, что оно берется не из входящего потока. Положим Р(п, 1) = Р(В(1) =-и), Р(п, х, 1) = — Р(В(г) = я, х(г) ( х), д дк где х(1) =О, если в момент 1 система свободна, и в противном случае х(1) равно времени, которое прошло до момента 1 с на- чала обслуживания требования, находящегося в момент 1 на приборе, р (г, з) = ~ е-нМг"'ЬИ, Р, (1) = Р (О, 1), р„(з) == р ((), з), о 74 р(г, х,'з) = — ) е — иМ '(гсиУ (х(1) ( х)1ш'.
дк о й( ) =М -", б,=МВ. 3. Период занятости. Одной из важных характеристик функционирования системы обслуживания является период занятости П, т. е. промежуток времени, начинающийся с поступления в свободную систему требования и кончающийся в момент первого после начала периода занятости освобождения системы. Помимо того что период занятости имеет самостоятельный интерес (в основном для проектировщиков системы), он существенно используется при определении многих других характеристик системы обслуживания.
Наряду с периодом занятости П мы будем использовать следующие промежутки занятости системы: Пео — период занятости, начавшийся со случайного числа требований ч, — промежуток времени, в начале которого в сисгсме находится ч требований, одно из которых начинает обслуживание, и кончающийся, как только система станет свободной; П, — период занятости со случайной задержкой й. Сл.в. Пь определяется следующим образом: в течение времени ~ поступающие требования ие обслуживаются (накапливаются в очереди), в начале отсчета ~ система свободна. П, начинается с началом ~ и заканчивается, как только закончится 5 и система станет свободной. Положим П (х) = Р (П ( х), Пеа (х) =.
Р (Пел < х), П! (х) = Р (П1 < х), п(з) .=- Ме — '" псн(з) ==Ме — ейм п1(х) =- Ме Т е о р е м а 1. а) Функция п(з) является единственным решением функционального уравнения л(з) =р(в+а — ап(з)), аналитическим в области Вез>0. б) Если ан <.1, то н(+О) =П(+со) =1, в противном случае з (+ О) < 1, П (+со) < 1. в) Если а~~) 1, то МП=оо, в противном случае МП = ~~/ (1 — а~~), рп-= р (! — а(3,1' (! — а(3,)' Доказательство теоремы 1 основывается на следующих двух ~симах, представляющих и самостоятельный интерес.
Л е и м а 1. а). Функциональное уравнение <1(з) =)3(в+а — а~р(з) ) олределяет единственную функцию гр(з), аналитическую в обшсти Вез>0, в которой ~~р(з) (<1. Если а(3~ ~1, то ~р(+О) =1, в противном случае с~(+О) <1. 75 б). Функция ~р(з) может быть представлена в виде р(з) = ~е — ис6Э(1), о где Ф(1) — неубывающая функция ограниченной вариации, причем при ар,<1 Ф(+оо) =1, при ар»>1 Ф(+оо) <1. 3 а м е ч а н и е. Часть утверждений леммы 1 не понадобит- ся нам для доказательства теоремы 1. Такие свойства, как аналитичность п(з) при Кеэ>0, представление и (3) = 1 е — н дп (О, о вытекают из вероятностного смысла П(1) и п(з). Однако ме- тоды доказательства всех утверждений леммы 1 понадобятся нам в главах 3 и 4.
Л е м м а 2. Справедливы следующие соотношения; а) П=В+Пы), где т — число требований, поступивших за случайное времяВ; при фиксированном значении т В и П< ) независимы; б) П~»~=П~+ ... +П», Пь ..., П» независимы в совокупности и стохастически эквива- лентны П; в) П,=$+П<ю, где 1» — число требований, поступивших эа время К; при фикси- рованном значении 1»~ и Пио независимы, При З=В отсюда следует Пв=П. Д о к а з а т е л ь с т в о леммы 1, а). Возьмем любое комп- лексное число з, такое, что Вез>0, и рассмотрим уравнение г = р (э+ а — аг) . (2) Левая и правая части этого уравнения аналитичны в некоторой области, содержащей круг )г)<1, При (г(=1 имеем Ке(з+ +а — аг) >О.
Поэтому /д(э+а — аг) / <~(Ке(э+а — аг)) <1= ~г1. По теореме Руше отсюда следует, что функции г и г — р(з+ +а — аг) имеют одинаковое число нулей в области ~г(<1, т. е. по одному нулю. Мы показали, таким образом, что урав- нение (2) имеет для любого з, такого, что Кез>0, единствен- ное решение г=<р(з), причем )~р(з) ~ <1. По теореме о неявной функции Ф(з) — аналитическая функция в области Вез>0. б). Рассмотрим»р(з) для действительных э>0. Построим .последовательность ~р„(э), полагая ~рь(э) =О, ~р„„1 (э) = р (э+ а — аф„(э) ) . (3) Очевидно, 0<»р (з) кзр„ы(э) ~1, и ~р„(э) — вполне монотонная.
функция (см, Приложение 3.2) при и> 1. Из монотонности по- следовательности ~р„(з) и соотношения (3) следует, что к(э) = . 76 =1пп~р„(з), и так как ~р„(з) вполне монотонны, то и ~р(з) впали не монотонна. Отсюда вытекает существование неубывающей функции Ф(г), такой, что <р (з) = ~ е — а г(Ф (!). (4) о Используя принцип аналитического продолжения, убеждаемся, что представление (4) справедливо в области Кез>0.
Далее, так как существует конечный или бесконечный предел !ппФ(Г) =Ф(+со), то существует !нпср(з) =<р(+О), и при этом 510 <р(+О) =р(а — акр(+О)). Легко видеть (так как а~, — значение производной функции !1(а — аг) в точке г= 1 — О), что уравнение г=р(а — аг) (5) при ар,~ ! имеет единственное решение на отрезке [О, 11, рав- ное 1, при ар,>! — два решения г~=р и гз=1, 0<р<1. Заме- тим, что уравнение (5) в круге !г~.<! на комплексной плос- кости имеет только действительные решения и, значит, совпа- дающие с найденными. Итак, при ар1(! Ф(+со) =<р(+О) =1, При ар,>! имеются две возможности р(+О) =1 и ~р(+О) =р.
На самом деле справедлив второй случай. Это следует из того, что любой корень уравнения (5) больше корня уравнения гр(е) =р(е+а — а<р'(е)) при любом е>0. Доказательство леммы 2. Утверждения а) и в) являются тривиальными следствиями определения сл.в. П, П!'>, Пь Докажем б). Легко видеть, что длительность промежутков П, Пы>, П, не зависит от того, в каком порядке обслуживаются требования.
В частности, можно считать, что принята дисциплина обслуживания 11гО. Промежуток П(М начинается с обслуживания одного из й имеющихся в системе требований (назовем нх начальными). В силу того что принята дисциплина 1!ГО, следующее начальное требование сможет поступить на прибор только тогда, когда в системе останутся й — 1 (начальные) требования.
Так как эти й — 1 начальные требования пе влияют на длительность интервала между поступлением на прибор первого и второго начальных требований, этот интервал имеет то же распределение, что и П. Таким образом, П<м=П+П<х — 1!, причем в силу свойства отсутствия последействия у пуассонов- ского потока и независимости длительностей обслуживания 77 разных требований П и Па-'1 независимы, Отсюда следует б) Доказательство теоремы 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
