Механики
 Скачать 4.29 Mb.
|
|
время пребыва- РСеМО РСеМО ЗСеМО «0» «0» а в б 2 3 4 1 1 2 2 1,2 1,2 г Рис .3.7. Виды СеМО 92 Раздел 3. Математические модели дискретных систем ния заявок в ЗСеМО рассматривается как промежуток времени между двумя соседними моментами прохождения заявки через нулевой узел Замкнуто - разомкнутая СеМО ( комбинированная ) представляет собой комбинацию ЗСеМО и РСеМО , в которую , кроме постоянно циркулирующих в сети * M заявок , из внешнего независимого источника поступают заявки такого же или другого класса , при этом суммарное число заявок в сети * M M ≥ 4. По типу циркулирующих заявок различают СеМО : однородные , в которых циркулирует один класс заявок ( одно - родный поток заявок ); неоднородные , в которых циркулирует несколько классов заявок ( неоднородный поток заявок ), различающихся хотя бы одним из следующих факторов : длительностями обслуживания в узлах ; приоритетами ; маршрутами Маршруты заявок разных классов задаются путем указания номеров классов заявок на соответствующих дугах сети ( рис .3.7, г ). 3.3. Параметры и характеристики СМО «Чем больше ожидание, тем больше веро- ятность, что вы стоите не в той очереди» (Принцип очереди) 3.3.1. Параметры СМО Для описания СМО используются три группы параметров : • структурные ; • нагрузочные ; • функциональные параметры ( параметры управления ). К структурным параметрам относятся : • количество обслуживающих приборов K, равное 1 для однока - нальной СМО и K >1 для многоканальной СМО ; • количество k и ёмкости накопителей E j ) , 1 ( k j = ; • способ взаимосвязи накопителей с приборами ( в случае многока - нальных СМО ), например в виде матрицы связей Нагрузочные параметры СМО включают в себя : • количество поступающих в систему классов заявок H, которое равно 1 для СМО с однородным потоком заявок и H >1 для СМО с неоднородным потоком ; • закон распределения ) ( τ i A интервалов времени между поступаю - щими в систему заявками класса H i , 1 = или , по - крайней мере , первые два момента распределения , задаваемые , например , в виде интенсивности i λ и коэффициента вариации i a ν интервалов ; Раздел 3. Математические модели дискретных систем 93 • закон распределения ) ( τ i B длительности обслуживания заявок класса H i , 1 = или , как минимум , первые два момента распределения , в качестве которых обычно используются средняя длительность i b или интенсивность i i b / 1 = µ обслуживания и коэффициент вариации i b ν Задание двух первых моментов нагрузочных параметров зачастую оказывается достаточным для оценки характеристик обслуживания заявок на уровне средних значений Отметим , что для описания простейшего потока достаточно задать только интенсивность поступления заявок в систему Функциональные параметры задаются в виде конкретных стратегий управления потоками заявок в СМО , определяющих правило занесения заявок разных классов в накопители ограниченной ёмкости ( дисциплина буферизации ) и правило выбора их из очереди на обслуживание ( дисциплина обслуживания ). 3.3.2. Обозначения СМО ( символика Кендалла ) Для компактного описания систем массового обслуживания часто используются обозначения , предложенные Д Кендаллом [9], в виде : A/B/N/L , где A и В – задают законы распределений соответственно интервалов времени между моментами поступления заявок в систему и длительности обслуживания заявок в приборе ; N – число обслуживающих приборов в системе ) ..., , 2 , 1 ( ∞ = N ; L – число мест в накопителе , которое может принимать значения 0, 1, 2, … ( отсутствие L означает , что накопитель имеет неограниченную ёмкость ). Для задания законов распределений А и В используются следующие обозначения : G (General) – произвольное распределение общего вида ; М (Markovian) – экспоненциальное ( показательное ) распределение ; D (Deterministik) – детерминированное распределение ; U (Uniform) – равномерное распределение ; Е k (Erlangian) – распределение Эрланга k- го порядка ( с k последовательными одинаковыми экспоненциальными фазами ); h k (hipoexponential) – гипоэкспоненциальное распределение k- го порядка ( с k последовательными разными экспоненциальными фазами ); Н r (Hiperexponential) – гиперэкпоненциальное распределение порядка r ( с r параллельными экспоненциальными фазами ); g (gamma) – гамма - распределение ; P (Pareto) – распределение Парето и т д Примеры : М / М /1 – одноканальная СМО с накопителем неограниченной ёмко - сти , в которую поступает однородный поток заявок с экспоненциальным 94 Раздел 3. Математические модели дискретных систем распределением интервалов времени между последовательными заявками ( простейший поток ) и экспоненциальной длительностью обслуживания заявок в приборе M/G/3/10 – трёхканальная СМО с накопителем ограниченной ёмкости , равной 10, в которую поступает однородный поток заявок с экспоненциальным распределением интервалов времени между последовательными заявками ( простейший поток ) и длительностью обслуживания заявок , распределённой по закону общего вида D/ Е 2 /7/0 – семиканальная СМО без накопителя ( ёмкость накопителя равна 0), в которую поступает однородный поток заявок с детерминированными интервалами времени между последовательными заявками ( детерминированный поток ) и длительностью обслуживания заявок в приборе , распределённой по закону Эрланга 2- го порядка Для обозначения более сложных СМО дополнительно могут использоваться обозначения , описывающие неоднородный поток заявок и приоритеты между заявками разных классов 3.3.3. Режимы функционирования СМО СМО может работать в следующих режимах : • установившемся или стационарном , когда вероятностные характеристики системы не изменяются со временем ; • неустановившемся , когда характеристики системы изменяются со временем , что может быть обусловлено : началом работы системы , когда значения характеристик функционирования , меняясь со временем , стремятся в пределе к стационарным значениям ( переходной режим ); нестационарным характером потока заявок и обслуживания в приборе ( нестационарный режим ). Кроме этого , в некоторых системах , например в СМО с накопителем неограниченной ёмкости , неустановившийся режим функционирования может быть обусловлен перегрузкой системы , когда интенсивность поступления заявок превышает интенсивность обслуживания , и система не справляется с возлагаемой на нее нагрузкой ( режим перегрузки ). При этом характеристики функционирования СМО с течением времени растут неограниченно В частности , длина очереди перед прибором с течением времени становится всё больше и в пределе стремится к бесконечности Обычно исследование СМО с накопителем неограниченной ёмкости проводится в предположении о существовании установившегося режима , непременным условием которого является требование отсутствия перегрузок , для чего необходимо , чтобы интенсивность поступления заявок была меньше , чем интенсивность обслуживания Это требование записывается для одноканальных СМО в виде условия : µ λ < или 1 < b λ Раздел 3. Математические модели дискретных систем 95 Для многоканальных СМО аналогичное условие имеет вид : µ λ K < или 1 < K b λ , где K – число обслуживающих приборов, а значение µ K представляет со- бой суммарную интенсивность обслуживания заявок в K-канальной СМО В СМО с накопителем ограниченной ёмкости превышение интен- сивности поступления заявок над суммарной интенсивностью обслужива- ния не приводит к неограниченному росту длины очереди, что обусловле- но потерей заявок. Следовательно, в СМО с накопителем ограниченной ёмкости перегрузки не приводят к работе системы в неустановившемся режиме, а приводят лишь к росту числа потерянных заявок. При этом потеря части поступающих в систему заявок при наличии накопителя ограниченной ёмкости может рассматриваться как один из механизмов борьбы с перегрузками. 3.3.4. Характеристики СМО с однородным потоком заявок Характеристики систем со стохастическим характером функциони- рования являются случайными величинами и полностью описываются соответствующими законами распределений. На практике при моделиро- вании часто ограничиваются определением только средних значений (математических ожиданий), реже – определением двух первых моментов этих характеристик. В качестве основных характеристик СМО с однородным потоком заявок используются следующие величины: • нагрузка системы: b y λ µ λ = = / ; (3.6) • коэффициент загрузки или просто загрузка системы, определяе- мая как доля времени, в течение которого система (в случае одноканальной СМО – прибор) работает, то есть выполняет обслуживание заявок; загрузка может быть рассчитана как отношение среднего времени р T работы одного прибора многоканальной СМО, к общему времени наблюдения T : T T p T ∞ → = lim ρ ; (3.7) время p T для СМО с K обслуживающими приборами определяется путём усреднения времени работы по всем приборам : ∑ = = K i i p T K T 1 1 , где i T - время работы прибора K i , 1 = ; подставляя последнее выражение в (3.7) окончательно получим: 96 Раздел 3. Математические модели дискретных систем ∑ = ∞ → = K i i T T KT 1 1 lim ρ ; очевидно, что 1 0 ≤ ≤ ρ ; • коэффициент простоя системы: ρ η − = 1 ; (3.8) • вероятность потери заявок: ) ( ) ( lim T N T N п T п ∞ → = π , (3.9) где T – время работы системы (наблюдения за системой); ) (T N – число заявок, поступивших в систему за время T; ) (T N п – число потерянных заявок за время T; • вероятность обслуживания заявки, то есть вероятность того, что поступившая в систему заявка будет обслужена: ) ( ) ( lim ) 1 ( 0 0 T N T N T п ∞ → = − = π π , (3.10) где ) ( 0 T N – число обслуженных в системе заявок за время T, причем ) ( ) ( ) ( 0 T N T N T N п = + и 1 0 = + п π π ; • производительность системы, представляющая собой интенсив- ность потока обслуженных заявок, выходящих из системы: λ π λ π λ ) 1 ( 0 ' п − = = ; (3.11) для СМО с накопителем неограниченной ёмкости, при условии отсутствия перегрузок, вероятность потери заявок 0 = п π и, следовательно, произво- дительность системы совпадает с интенсивностью поступления заявок в систему: λ λ = ' ; • интенсивность потока потерянных (не обслуженных) заявок из-за ограниченной ёмкости накопителя: λ π λ π λ ) 1 ( 0 " − = = п ; (3.12) очевидно, что сумма интенсивностей потоков обслуженных и потерянных заявок должна быть равна интенсивности входящего в систему потока заявок: λ λ λ = + " ' ; • среднее время ожидания заявок в очереди: w; • среднее время пребывания заявок в системе, складывающееся из времени ожидания w и времени обслуживания b: b w u + = ; (3.13) • средняя длина очереди заявок: w l ' λ = ; (3.14) • среднее число заявок в системе (в очереди и на обслуживании в приборе): u m ' λ = . (3.15) Раздел 3. Математические модели дискретных систем 97 Нагрузка и загрузка являются важнейшими характеристиками СМО, определяющими качество функционирования системы. Нагрузка b y λ = представляет собой интегральную оценку, объеди- няющую два нагрузочных параметра: частоту использования некоторого ресурса (прибора СМО), задаваемую в виде интенсивности λ поступления заявок в СМО, и время использования этого ресурса, задаваемое в виде средней длительности b обслуживания заявок в СМО. Нагрузка показыва- ет количество работы, которую необходимо выполнить в системе. Если значение нагрузки 1 < y , то заданная нагрузка может быть выполнена одним обслуживающим прибором, то есть одноканальная СМО будет работать без перегрузки. Если 1 > y , то реализация заданной нагрузки в одноканальной СМО приведет к режиму перегрузки, означающему, что с течением времени всё большее число заявок будет оставаться не обслуженным, и в случае накопителя неограниченной емкости очередь заявок будет расти неограниченно. Для того чтобы система работала без перегрузок необходимо использовать многоканальную СМО, количество приборов которой должно быть больше, чем значение нагрузки: y K > В общем случае для любой СМО (с накопителем ограниченной и неограниченной ёмкости) загрузка системы может быть рассчитана через нагрузку следующим образом: − = 1 ; ) 1 ( min K y п π ρ , (3.16) где K – число обслуживающих приборов в СМО; п π – вероятность потери заявок. Последнее выражение можно трактовать следующим образом: K y п ) 1 ( π ρ − = , если СМО работает без перегрузки, и 1 = ρ , если СМО перегружена. Покажем, что выражение (3.16) соответствует определению (3.7). Рассмотрим достаточно большой промежуток времени ∞ → T , в течение которого работает СМО. За это время в систему поступит в среднем T λ заявок, где λ – интенсивность поступления заявок в СМО, из которых будут обслужены системой T п λ π ) 1 ( − заявок ( T п λ π заявок будут потеряны из-за ограниченной ёмкости накопителя). Обслуживание всех этих заявок будет длиться в течение времени Tb T п р λ π ) 1 ( − = , если СМО – одноканальная, и в течение времени K Tb T п р λ π ) 1 ( − = , если СМО – многоканальная и содержит K обслуживающих приборов. Здесь b – средняя длительность обслуживания заявки в приборе. Подставляя выражение для р T в (3.7), получим: 98 Раздел 3. Математические модели дискретных систем K b K b KT Tb T T п п T p T ' ) 1 ( ) 1 ( lim lim λ λ π λ π ρ = − = − = = ∞ → ∞ → , (3.17) где λ π λ ) 1 ( ' n − = – интенсивность обслуженных в СМО заявок. Отметим, что загрузка системы, в отличие от нагрузки, определяется через интенсивность только обслуженных заявок, поскольку потерянные заявки не обслуживаются в приборах и, следовательно, не загружают систему. Рассмотрим теперь СМО с накопителем неограниченной ёмкости и вспомним, что при возникновении перегрузок такая система не справляется с работой, что выражается в неограниченном росте очереди с течением времени. Если T T р < , то это означает, что система справляется с работой, то есть работает без перегрузок. Если же время K Tb T р λ = , которое требуется для обслуживания всех заявок, окажется больше, чем время наблюдения за системой T T р > , то это означает, что система не справляется с нагрузкой, то есть работает в режиме перегрузки. В этом случае загрузка системы 1 = ρ (составляет 100%), а коэффициент простоя соответственно равен нулю. Выражение (3.16) записано с учётом указанного обстоятельства. Получим ещё одну полезную формулу для расчёта вероятности потери заявок по известному значению загрузки СМО. Из (3.11) следует, что вероятность потери заявок в СМО с накопителем ограниченной ёмкости может быть рассчитана как λ λ λ λ λ π ' ' 1 − = − = n В то же время из (3.17) вытекает, что интенсивность обслуженных заявок b K ρ λ = ' Подставляя последнее выражение в предыдущее, получим: K y b K n ρ λ ρ π − = − = 1 1 , (3.18) где b y λ = – нагрузка системы. Вероятность обслуживания поступившей в систему заявки: K y n ρ π π = − = 1 0 Выражение (3.18) оказывается полезным при расчёте характеристик обслуживания заявок в марковских моделях систем и сетей массового обслуживания (см. примеры в разделе 5). |