Механики
 Скачать 4.29 Mb.
|
|
E 0 : k = 0 – в системе нет ни одной заявки; E 1 : k = 1 – в системе находится 1 заявка (на обслуживании в приборе); E 2 : k = 2 – в системе находятся 2 заявки (одна – на обслуживании в приборе и вторая ожидает в накопителе); … E k : k – в системе находятся k заявок (одна – на обслуживании в приборе и ) 1 ( − k – в накопителе). … 4. Размеченный граф переходов случайного процесса представлен на рис.5.11. В один и тот же момент времени может происходить только одно событие: поступление заявки в систему с интенсивностью λ или заверше- ние обслуживания заявки с интенсивностью µ . Размеченный граф переходов содержит бесконечное число состояний. λ λ λ E 0 E 1 E 2 µ µ µ Рис . 5.11. Граф переходов марковского процесса E 0 E 1 E 2 E k λ λ µ µ 204 Раздел 5. Численное моделирование 5. Система уравнений . Не выписывая матрицу интенсивностей переходов, составим по графу переходов систему уравнений для определения стационарных вероятностей: = + + + + + + = + + = + + = + = + − 1 ) ( ) ( ) ( 2 1 0 1 1 3 1 2 2 0 1 1 0 K K L L k k k k p p p p p p p p p p p p p p p µ λ µ λ µ λ µ λ µ λ µ λ µ λ Несмотря на то, что система содержит бесконечное число уравнений и, соответственно, бесконечное число неизвестных , нетрудно методом математической индукции получить аналитическое решение в явном виде для расчета вероятностей состояний одноканальной экспоненциальной СМО с однородным потоком заявок и накопителем неограниченной ёмкости при условии, что нагрузка системы 1 < y : ) , 2 , 1 , 0 ( ) 1 ( ) 1 ( K = − = − = k y y p k k k ρ ρ , где µ λ ρ / = – загрузка системы, совпадающая с нагрузкой, причём 1 < ρ , что гарантирует существование установившегося режима в системе. Таким образом, вероятность нахождения марковского процесса в состоянии Е k или, что то же самое, вероятность того, что в произвольный момент времени в системе находится k заявок, распределена по геометри- ческому закону с параметром, равным загрузке (нагрузке) системы. 6. Расчет характеристик СМО . Для расчета характеристик СМО можно воспользоваться следующи- ми математическими зависимостями: 1) нагрузка b y λ µ λ = = / ; 2) загрузка b p λ ρ = − = 0 1 и совпадает с нагрузкой ; 3) коэффициент простоя системы ρ η − = = 1 0 p ;;;; 4) среднее число заявок в очереди ρ ρ − = − = ∑ ∞ = 1 ) 1 ( 2 1 k k p k l ; 5) среднее число заявок в системе ρ ρ − = = ∑ ∞ = 1 0 k k p k m ;;;; 6) вероятность потери заявок 0 = π ; 7) производительность системы при отсутствии потерь совпадает с интенсивностью поступления заявок в систему: λ λ = ' ;;;; 8) интенсивность потерянных заявок 0 '' = λ ;;;; Раздел 5. Численное моделирование 205 П1 П2 µ λ 1 = r ' λ " λ Рис . 5.12. Двухканальная СМО 9) среднее время ожидания заявок ρ ρ λ − = = 1 b l w ; 10) среднее время пребывания заявок b w u + = или ρ λ − = = 1 b m u Полученные выражения совпадают с формулами для расчёта характеристик экспоненциальной СМО, представленными в п.4.1.1. Детальный анализ свойств таких систем выполнен в п.4.1.5. 5.4.5. Многоканальная СМО накопителем ограниченной ёмкости (M/M/2/1) Рассмотрим многоканальную СМО с отказами, в которую поступает однородный поток заявок. Все приборы системы являются идентичными, и поступившая в систему заявка занимает любой свободный прибор. Заявка, поступившая в систему и заставшая все приборы занятыми, заносится в накопитель ограниченной ёмкости, если он не заполнен до предела. В про- тивном случае, заявка получает отказ и покидает систему не обслуженной. Таким образом, в системе, кроме входящего потока заявок с интенсив- ностью λ , образуются еще два потока заявок: поток обслуженных заявок с интенсивностью ' λ и поток необслуженных заявок (получивших отказ в обслуживании) с интенсивностью " λ . Очевидно, что λ λ λ = + " ' 1. Описание системы (рис.5.12). 1.1. Система двухканальная - содержит два обслуживающих прибора. 1.2. В систему поступает однородный поток заявок. 1.3. Приборы – идентичные , то есть время обслуживания заявок в приборах одинаково. 1.4. Перед прибором имеется накопитель единичной ёмкости : 1 = r 2. Предположения и допущения . 2.1. Поступающие в систему заявки образуют простейший поток с интенсивностью λ 2.2. Длительность обслуживания заявок в приборе распределена по экспоненциальному закону с интенсивностью b / 1 = µ , где b – средняя длительность обслуживания заявок в приборе. 2.3. Дисциплина буферизации – с потерями : заявка, поступившая в систему и заставшая накопитель заполненным, теряется. 2.4. Дисциплина обслуживания – в естественном порядке : заявка, поступившая в систему и заставшая прибор свободным, принимается на обслуживание. 3. Кодирование состояний случайного процесса . В качестве параметра, описывающего состояние случайного процес- са, будем рассматривать количество заявок k, находящихся в СМО. 206 Раздел 5. Численное моделирование Е 0 Е 2 E 1 λ µ Е 3 Рис .5.13. Размеченный граф переходов λ λ µ 2 µ 2 Система в любой момент времени может находиться в одном из следую- щих состояний: E 0 : k = 0 – в системе нет заявок (оба прибора простаивают); E 1 : k = 1 – в системе (на обслуживании в одном из приборов) находится 1 заявка; E 2 : k = 2 – в системе (на обслуживании в обоих приборах) находятся 2 заявки; E 3 : k = 3 – в системе находятся 3 заявки: две – на обслуживании в приборах и одна – в накопителе. 4. Размеченный граф переходов случайного процесса представлен на рис.5.13. В один и тот же момент времени может произойти одно из двух событий, которые приво- дят к изменению состояния слу- чайного процесса, протекающего в системе: • поступление заявки в систему с интенсивностью λ , приводящее к переходу в соседнее состояние с б о льшим номером, причем если случай- ный процесс находится в состоянии E 3 , то его состояние не изменится, что соответствует отказу в обслуживании поступившей заявке; • завершение обслуживания заявки в одном из приборов с интенсив- ностью µ , при этом случайный процесс переходит в соседнее состояние с меньшим номером с интенсивностью µ , если работает один прибор, и с интенсивностью µ 2 , если работают оба прибора. 5. Расчет характеристик СМО . Не выписывая матрицу интенсивностей переходов и систему уравне- ний для определения стационарных вероятностей, запишем формулы для расчёта характеристик СМО: 1) нагрузка: b y λ µ λ = = / ; 2) загрузка: 2 / ) 2 2 ( 3 2 1 p p p + + = ρ ; 3) среднее число работающих приборов: ρ 2 ) 2 2 ( 3 2 1 ' = + + = p p p k ; 4) коэффициент простоя системы: ρ η − = 1 ; 5) среднее число заявок в очереди: 3 p l = ; 6) среднее число заявок в системе: ' 3 2 1 3 2 k l p p p m + = + + = ; 7) вероятность потери заявок: 3 p = π ; Задание на самостоятельную работу: используя выражение (3.18), доказать , что вероятность потери заявок равна вероятности того , что система заполнена , то есть в накопителе нет свободных мест для вновь поступающих заявок . 8) производительность системы (интенсивность потока обслуженных заявок): ) 1 ( ' π λ λ − = ; Раздел 5. Численное моделирование 207 9) интенсивность потока потерянных заявок: π λ λ = '' ; 10) среднее время ожидания заявок: ' / λ l w = ; 11) среднее время пребывания заявок: b w m u + = = ' / λ 5.4.6. Одноканальная СМО с неоднородным потоком заявок и относительными приоритетами Рассмотрим одноканальную СМО, в которую поступает неоднородный поток заявок. Ожидающие обслуживания заявки разнесены по разным накопителям ограниченной ёмкости. Между заявками разных классов установлены относительные приоритеты (ОП), означающие, что всякий раз из накопителей на обслуживание выбирается заявка с самым высоким приоритетом. При этом при поступлении в систему высоко- приоритетной заявки обслуживание низкоприоритетной не прерывается. При заполненных накопителях поступившая заявка теряется. 1. Описание системы (рис.5.14). 1.1. Система одноканальная 1.2. Входящий поток заявок – неоднородный : в систему поступает два класса заявок. 1.3. Накопители для заявок каждого класса – ограниченной ёмко - сти : 1 2 1 = = r r 1.4. Дисциплина буферизации – без вытеснения заявок: если при поступлении в систему заявки любого класса соответствующий накопитель заполнен до конца, то заявка теряется 1.4. Дисциплина обслуживания – с относительными приоритетами : заявки первого класса имеют приоритет по отношению к заявкам второго класса. 2. Предположения и допущения . 2.1. Поступающие в систему заявки двух классов образуют простейшие потоки с интенсивностями 1 λ и 2 λ соответственно. 2.2. Длительности обслуживания заявок каждого класса распре- делены по экспоненциальному закону с интенсивностями 1 1 / 1 b = µ и 2 2 / 1 b = µ , где 1 b и 2 b – средние длительности обслуживания заявок класса 1 и 2 соответственно. В СМО всегда существует стационарный режим, так как не может быть бесконечных очередей. 3. Кодирование состояний случайного процесса . Для описания состояний марковского процесса будем использовать распределение заявок между прибором и накопителями. Закодируем состояния следующим образом: (П/О 1 ,О 2 ), где П = {0, 1, 2} – состояние обслуживающего прибора, задаваемое классом заявки, находящейся на П 1 2 1 = = r r 1 λ 2 λ 2 1 , µ µ ДО ОП Рис .5.14. СМО с неоднородным потоком заявок 208 Раздел 5. Численное моделирование обслуживании («0» – прибор свободен; «1» или «2» – на обслуживании в приборе находится заявка класса 1 или 2 соответственно); О 1 , О 2 = {0, 1} – состояние накопителей 1 и 2 соответственно («0» – означает отсутствие заявки в накопителе, «1» –означает наличие одной заявки в накопителе соответствующего класса). При выбранном способе кодирования система может находиться в следующих состояниях: E 0 : (0/0,0) – в системе нет ни одной заявки; E 1 : (1/0,0) – на обслуживании в приборе находится заявка класса 1; E 2 : (2/0,0) – на обслуживании в приборе находится заявка класса 2; E 3 : (1/1,0) – на обслуживании находится заявка класса 1 и одна заявка класса 1 ожидает обслуживания в первом накопителе; E 4 : (1/0,1) – на обслуживании находится заявка класса 1 и одна заявка класса 2 ожидает обслуживания соответственно во втором накопителе; E 5 : (2/1,0) – на обслуживании находится заявка класса 2 и одна заявка класса 1 ожидает обслуживания в первом накопителе; E 6 : (2/0,1) – на обслуживании находится заявка класса 2 и одна заявка класса 2 ожидает обслуживания во втором накопителе; E 7 : (1/1,1) – на обслуживании находится заявка класса 1, и по одной заявке каждого класса ожидают обслуживания в соответствующих накопителях; E 8 : (2/1,1) – на обслуживании находится заявка класса 2, и по одной заявке каждого класса ожидают обслуживания в соответствующих накопителях. Отметим, что при кодировании случайных процессов могут быть применены различные способы кодирования. В рассматриваемом примере состояния случайного процесса вместо представленного выше способа можно закодировать, например, следую- щим образом: (П,О), где П = {0, 1, 2} – состояние обслуживающего при- бора, задаваемое классом заявки, находящейся на обслуживании («0» – прибор свободен; «1» или «2» – на обслуживании в приборе находится заявка класса 1 или 2 соответственно); О = {0, 1, 2, 3} – состояние нако- пителей 1 и 2 соответственно («0» – означает отсутствие заявок в обоих накопителях; «1» –наличие в первом накопителе заявки класса 1; «2» – наличие во втором накопителе заявки класса 2; «3» – наличие в первом и втором накопителях по одной заявке соответственно класса 1 и 2). Представленные способы кодирования не применимы, если для заявок обоих классов используется общий накопитель ёмкостью 2 = r . В этом случае количество состояний случайного процесса увеличится, поскольку в накопителе могут находиться 2 заявки одного и того же класса и состояние накопителя может быть представлено следующим образом: О = {0, 1, 2, 11, 12, 22}, где «0» – означает отсутствие заявок в накопителе; «1» – наличие в накопителе только одной заявки класса 1; «2» – наличие в Раздел 5. Численное моделирование 209 накопителе заявки класса 2; «11» – наличие в накопителе двух заявок класса 1; «22» – наличие в накопителе двух заявок класса 2 и «12» – наличие в накопителе одной заявки класса 1 и одной заявки класса 2. Заметим, что состояние «12» не различает, в какой последовательности эти заявки поступили в систему, что обусловлено наличием относительного приоритета между ними – независимо от момента поступления на обслуживание первой всегда будет выбрана заявка класса 1. В случае бесприоритетного обслуживания, когда заявки разных классов выбираются на обслуживание в порядке поступления, следует ввести ещё одно состояние накопителя – «21», означающее, что заявка класса 2 поступила в систему раньше заявки класса 1, в то время как состояние «12» означает, что в систему раньше поступила заявка класса 1. 4. Размеченный граф переходов случайного процесса представлен на рис.5.15. В каждый момент времени может произойти только одно событие (или поступление заявки какого-либо класса, или завершение обслужива- ния заявки, находящейся в приборе), поскольку вероятность появления двух и более событий в один и тот же момент времени равна нулю. При наличии в накопителях заявок первого и второго классов (состояния Е 7 и Е 8 ) после завершения обслуживания некоторой заявки в приборе случайный процесс переходит в состояние Е 4 , означающее, что на обслуживание всегда выбирается высокоприоритетная заявка класса 1. По графу переходов составим систему уравнений для определения стационарных вероятностей: Е 0 (0/0,0) 1 λ 1 λ 1 λ 1 λ 1 λ 2 λ 2 λ 2 λ 2 λ 2 λ 2 µ 2 µ 1 µ 1 µ 2 µ 2 µ 1 µ 1 µ Рис .5.15. Размеченный граф переходов |