1. Введение в теорию массового обслуживания. Гнеденко_ Коваленко (2-е изд) (1987) (1186154), страница 55
Текст из файла (страница 55)
Для оценки зффектпвности подобных систем существенно изучение картины явления в условиях, когда интенсивность входящего потока намного меньше, чем критическое значение, после которого уже не будет стационарного режима. Далее, важно знать не только численное значение зффек- й 5.Ь СИСТЕМЫ С МАЛОИ ЗАГРУЗКОЙ 289 при любом фиксироеанноза Т ) О(-~ — символ сходимосги по ве- роятности), то случайные еееичины ер (Л) ги гр (Л) (е — й), осимптотически независимы и асимптотически показательны с па- рамстрозе 1. Доказательство. Пусть )е'(з) — число потерянных требо- ваний до момента времени, когда переменная Лх(Т) достигла зна- чепич з. Тогда, независимо от процесса функционирования си- стемы, 1е'(з) есть число событий простейшего потока с парамет- ром 1 в интервале длины з.
В силу монотонности функции х(5) яз (1) следует, что на любом конечном интервале с вероятностью, сколь угодно близкой к 1, Т вЂ” е ~ Лх (Т/ез (Л) ) ~ Т + е. (2) Пусть з, — момент й-й потери требования в переменной г. В силу (2), если з„лежит в ограниченном интервале, !ер(Л)Г,— зе! - е, т. е. поток О,) — результат бесконечно малого смещения событий простейшего потока с параметром 1. Отсгода следует утвержде- ние леммы. 3. Исследование процесса Лх(1). Пусть у(~) — индикатор собы- тия Ь(г)= т+г), где ч(г) — число требований в системе в мо- мент й Тогда х(1)= ~ у(и) аи.
(8) о ЕО Б, В. Гнезенно, П. Н. Кованенно тивности при определенном наборе значений параметров (таких, как интенсивность входящего потока требований), но также поведение зффектнвности, как функции параметров, при переменных значениях последних. Это необходимо для оптимального выбора характеристик системы. В настоящем параграфе изложим один из возможных подходов к решению данной задачи. 2. Постановка задачи. Имеется система зз~б~т~г с интенсивпостью Л входящего потока и функцией распределения В(х) длительности обслуживания, т = ) хс)В(х) <, оо, Обозначим через о момент ес-й потери требования.
Необходимо исследовать предельное распределение случайных величин Ги 1„... прп Л вЂ” О. Задача имеет много полезных интерпретаций: в теории надежности, в теории расчета памяти ЭВМ и др. Поставленная задача немедленно сводится к другой посредством следующей леммы. Лемма. Пусть х(Т) — суммарное время из (О, Т), на протяжении которого все места для ожидания заняты.
Тогда, если для некоторой функции ц1(Л) Лх(Т~ер(Л» Т Гл, з пгимеиенпе Более ОБщих ьтетодов 290 Если у(г)= 1, то текущему состоянию т+г процесса т(8) предшествовала некоторая цепочка переходов Π— 1 — ... — т + г, никакое промежуточное состояние которой не равно О. Цепочка может быть монотонной: Π— 1 — 2 — ... — т+ г — 1 — т+ г либо немонотонной. В первом случае положим у,(г) = 1, у1(г)= О, во втором случае у,(г) = О, у~(г) = 1. Пусть ь — интервал занятости системы.
Тогда Р (1 ) г) <« «< Р (ь* ~ г), где ь* — соответствующий интервал в системе ЛХ~©1. Действительно, в первом случае длительности обслуживания гв перекрываются, во втором располагаются последовательно во времени; за избыточное время могут поступить другие требования, что еще увеличит ье. Согласно гл. 4 Мье=т/(1 — )т). Если В" (х) = Р (~* < х), ра (Г) = Р ( (1) - О), то 1 — р, (1) Х ~ В* (~ — х) Ох < ) Мье = йт~(1 — г.т). О Отсюда р,(1) ~ 1 — ),т/(1 — ) т).
(4) Обозначим через А(ц Л) вероятность события (у,(и)=1, 1 < и < г+ Л). Переходы О - 1 - ... — т + г, приведшие к текущему состоянию, могли произойтн в моменты т, < 12 «... 1„+, < < 8; между моментами го ц,..., 8„+„, 1 других требований не было; в момент 1, система должна была быть свободна.
Дифферент~- — х(~,„+„-с,) циал вероятности такого события равенрз(т,)) е А1ю .. ...см Далее, обслуживания, начавшиеся в моменты 1О ..., г,„, должны продлиться до момента г+ Л. Итак, ) "'А(г,Л)=) ...) ре(1,)е +" 'В(с+ст — 8,).. ° ... В (1 + Ь вЂ” 1,„) И8, ... г($ е„, (5) где область интегрирования была определена выше.
Из формулы (5) сразу получаем две полезные оценки. Заменив экспоненту и р, (й) единицей, получим верхнюю оценку. С другой стороны, — вр +„" — В)— обозначив Ве(х)=е 'В(х), будем иметь е В(Г+ Л— — г,)... В (т + Л вЂ” 1„) =в В, (1+ д — 1,) ... В, (1+ Л вЂ” 1 ). Для р,(1,) возьмем оценку (4). В обоих случаях приходим к интегралу от функции, симметричной относительно 1„..., 1 и +$ ° ° 1 гт+г.
Таяна~ образом, можно взять интеграл по области (О < Г +~ < В О < 1, < ~„+е 1 < е < т; т „< 8, < 1„т+ 2 < е < т + г), Разделив выражение на т((г — 1) й В результате получаем Ф 5.7. стгстемы с мАлОЙ 3АГРузкои 291 то — х х 7п "х" '5(х( ) Вт(х+ у+ Л) г(у) 5(х(» 1 — Ат / О О (т((г — 1)! А ! +МА(г, Л) ~ Ю /С вЂ” х '~ 3х (~х" ~~ ~ В(х+ у+ Л)ду~ 5(х, г. »1.
(6) О О Прп г=О имеем !-х т ~ В,(у+ Л)яу ~,и )„- А(, Л)< О х ! Ох ").,) .,о 'х о Предположим, что о Мх, (г) — —,т г'" 1, (11) г=О, (12) где в обоих случаях ) - О, г- . Оценим Муо(!)уо(! + Л). Если у (!)=У,(1+ Л)=1, то одно из двух: либо у,(и)=1 при Г~ и~ ~ !+ Л, либо в интервале (г, г+ Л) начался интервал занятости. Отсюда Муо(!)Уо(1+ Л)~ ~(!1 Л) + А*И 0) А*(!+ Л О) (10) где х(о(й, 0) — верхняя оценка А(й, О) в силу (б), (7). !ео В(х)~ох-о, х) О, где р ) 1 + гlги. Тогда, как легко видеть, !!Ст (ги((г — 1)! Х ' +"А(8, Л)) = т — Ои = '! хг 'В (х+ Л)5)х, г' 1, (9) о Пгп (т)Л ~А(й, Л)) = В (Л), г = О, (10) ь ол где В (х) = ) В (!) 5(!.
Пусть х;(г) = ( уг(и) Ни, ! = 0,1. Так как х о Муз (!) = А(г, О), то 292 Гл. 5, пггмгнеыик Более Овщих мктодоз Следовательно, в*2)2)~ ) А*),0)А ) А 222, '1О где Х= „',, Л"+" ~х"-'~В-(х+ Л) 8Л (х,г)1; о о Х= — Л ~ В(Л) 5(Л, г = О. о (15) (16) Первое слагаемое в правой части (14) согласно предыдущему эквивалентно (Мх(1))', выражение Л-' +")Х ограничено при оценке (8), где р )1+(г+1)/т. Таким образом, при последнем условии (0хр (1))/(Мхр (5)) = О (1)2 если 5Л +'-, Л- О. Итак, скажем, при г=О Лх,(1)/~~Л"+'т-) ' О (Л 0,1- Из (18) находим (18) Лх,(Т/1р(Л) ) — Т (19) при 2р(Л)=Л +)т"'/т!. Аналогично, (19) выполняется при г~1, Л++ ) *=и 1Вм ( о Рассмотрим теперь случайную функцию х, (5).
С вероятностью 1 х)(2) не превосходит суммарной длины интервалов за нятости, начавшихся в (О, 1), на протяжении каждого из которых обслужено не менее т+г+1 требований. Действительно, если траектория Π— 1 — ... — т+ г немонотопна, то она содержит не менее т+ г+ 1 скачков вверх. Итак, Мх, (т) ( Л5Ма, (20) где а — длина интервала занятости, если в пом обслужено не менее т+ г+ 1 требований, и нуль в противном случае.
Выше уже отмечалось соотношение между интервалами ваня= тости в системах М~С~т~г и /и ~6~1. При установленном соответствии, как легко видеть, в последнем случае в интервале ваня- тости обслуживается не меныпее число требований, чем в первом. Отсюда Ма(МО*, где а* — аналогичная а величина для системы М(6! 1. 5 5.8. ТЕОРЕМА ЛИПЛА И ЕЕ СЛЕДСТВИЯ 293 Рассмотрим вероятностную структуру случайной величины оо. Расположим подряд длительности обслуживания цо ..., Т) +, первых т+г требований. Пусть г=ц,+...+о1 +,. Если представить себе ипверснонный порядок обслуживания как в $ 4.3, то к интервалу длины г будут примыкать интервалы занятости о о "„..., Ы, коль скоро в интервале длины л поступит не менее );+ т+ г — 1 требований ((о >1).
При фиксированном значении г матс матическое ожидание о* составляет е ы ~ — (г+ (1 — т — г+ 1) т/(1 — Хт))( '~х (Хо) зло+о ( — (г + (т + г) т,~(1 — Хт)). (21) Если ) х"+"+~ИВ(х)( со, то Мгоо+"+гх.. со, и тогда, усреднив о (21) по распределению г, получим опенку Ма' = О () +"). (22) Из (20) теперь следует Мх (г) = 0(Л +"+'г), Мх,(Т~~р(Х))„,0. (23) Из (19) и (23) получаем Хх(Т/~в(А) ) 1. (24) По лемме, доказанной в и. 2, заключаем, что поток потерь в пре- ДЕЛЕ ПРОСтЕйШИй; СЛУЧайНЫЕ ВЕЛИЧИНЫ ОР() )ге ~Р(А) (го — г,), ...
имеют асимптотически показательное распределение с параметром 1. ()стается заметить, что условие (8) следует из существования (ьт+ с+1)-го момента распределения В(х). В самом деле, х'"+о ыВ (х) ( ( ум+"+ИВ (у) о- О. х х о е 5.8. Теорема Литтла и ее следствия 1. Общие положения. Пусть имеется система массового обслуживания произвольного вида. Обозначим через н время пребывания и-го требования в системе, т(о) — числе требований в системе в момент г, У(г) — число требований, поступивших в интервале (О, г). Суммарное время, проведенное требованиями в системе в т интервале (О, Т), равно ) т (г) пг.
Это время отличается о 224 ГЛ. Е ПРПМЕНЕНПЕ БОЛЕЕ ОБЩНХ МЕТОДОВ от и, +... + ив„, не больше, чем на суммарное время Л пребывания тех требований, которые находятся в системе в момент Т. При достаточно общих условиях  — величина с ограниченным математическим ожиданием; следовательно, при больших Т Н1Г) 1. Г тс(т) — ' ) о(1) о'1 ж — ' — пю т,) т у (т) я-'А 1=1 Таким образом, если Л и г' — среднее стационарное число требований в системе и среднее время пребывания требования в системе, аХ = Пш )т (Т))Т, то г Аналогично, су1гмарное время ожидания требований в интервале (О, Т) равно ~ т (~)111, где т,(1) — число требований, находяо щихся в очереди (не обслуживаемых) в момент й Отсюда Л,=ХИг, (2) где 1., — среднее стационарное значение Р,(8), Иг — среднее время ожидания требования. Утверждение, содержащееся в формулах (1) и (2), носит название теоремы Литтяа. Примем следующие предяоложення: 1.
Пусть Ж(Т) — число событпй входящего потока в интервале (О, Т) при Т ) О н в интервале (Т, О) прн Т ( О. Тогда 2. Процесс т(1) и последовательность (о„) стациопарны и эргодичны. 2. Теорема Литтла. Теорема. При условиях 1 п. 2 выполняется равенство (1). Д о к а з а т е л ь с т в о. Моменты 11 поступления требований упорядочим так, что ... ~ 1-1 ~ 80 ~ О ( 1, -'= 11 <...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
