Механики
 Скачать 4.29 Mb.
|
|
П (каналов), обслуживающих заявки З, поступающие в систему, и 78 Раздел 3. Математические модели дискретных систем накопитель Н, в котором находятся заявки, образующие очередь О и ожидающие обслуживания (рис.3.1). Заявка (требование, запрос, вызов, клиент)– объект, поступающий в СМО и требующий обслуживания в обслуживающем приборе. Совокупность заявок, распределенных во времени, образуют поток заявок Обслуживающий прибор или просто прибор (устройство, канал, линия ) – элемент СМО, функцией которого является обслуживание заявок. В каждый момент времени в приборе на обслуживании может находиться только одна заявка. Обслуживание – задержка заявки на некоторое время в обслуживаю- щем приборе. Длительность обслуживания – время задержки (обслуживания) заявки в приборе. Накопитель (буфер) – совокупность мест для ожидания заявок перед обслуживающим прибором. Количество мест для ожидания определяет ёмкость накопителя. Заявка, поступившая на вход СМО, может находиться в двух состояниях: в состоянии обслуживания (в приборе); в состоянии ожидания (в накопителе), если все приборы заняты обслуживанием других заявок. Заявки, находящиеся в накопителе и ожидающие обслуживания, образуют очередь заявок. Количество заявок, ожидающих обслуживания в накопителе, определяет длину очереди. Дисциплина буферизации – правило занесения поступающих заявок в накопитель (буфер). Дисциплина обслуживания – правило выбора заявок из очереди для обслуживания в приборе. Рис.3.1. Система массового обслуживания П Процесс : Поступление Ожидание Обслуживание заявок (З) в очереди (О) в приборе (накопителе – Н) Описание : Поток ДБ ДО Поток входящих выходящих заявок Приоритеты заявок З Н (О) Раздел 3. Математические модели дискретных систем 79 Приоритет – преимущественное право на занесение (в накопитель) или выбор из очереди (для обслуживания в приборе) заявок одного класса по отношению к заявкам других классов. Таким образом, СМО включает в себя: • заявки, проходящие через систему и образующие потоки заявок; • очереди заявок, образующиеся в накопителях; • обслуживающие приборы. Существует большое многообразие СМО, различающихся структур- ной и функциональной организацией. В то же время, разработка аналити- ческих методов расчета характеристик функционирования СМО во многих случаях предполагает наличие ряда предположений, ограничивающих множество исследуемых СМО. Ниже при рассмотрении СМО, если не оговорено другое, будем использовать следующие предположения: • заявка, поступившая в систему, мгновенно попадает на обслужи- вание, если прибор свободен; • в приборе на обслуживании в каждый момент времени может находиться только одна заявка; • после завершения обслуживания какой-либо заявки в приборе очередная заявка выбирается на обслуживание из очереди мгновенно, то есть, другими словами, прибор не простаивает, если в очереди есть хотя бы одна заявка; • поступление заявок в СМО и длительности их обслуживания не зависят от того, сколько заявок уже находится в системе, или от каких- либо других факторов; • длительность обслуживания заявок не зависит от скорости (интенсивности) поступления заявок в систему. 3.1.2. Сеть массового обслуживания Сеть массового обслуживания (СеМО) – совокупность взаимосвязанных СМО, в среде которых циркулируют заявки (рис.3.2,а). Основными элементами СеМО являются узлы (У) и источники заявок (И). Узел сети представляет собой систему массового обслуживания. Источник – генератор заявок, поступающих в сеть и требующих определенных этапов обслуживания в узлах сети. Для упрощенного изображения СеМО используется граф СеМО. Граф СеМО– ориентированный граф, вершины которого соответствуют узлам СеМО, а дуги отображают переходы заявок между узлами (рис.3.2,б). Переходы заявок между узлами СеМО, в общем случае, могут быть заданы в виде вероятностей передач. Путь движения заявок в СеМО называется маршрутом. 80 Раздел 3. Математические модели дискретных систем 3.1.3. Поток заявок Совокупность событий распределенных во времени называется потоком . Если событие заключается в появлении заявок, имеем поток заявок. Для описания потока заявок, в общем случае, необходимо задать интервалы времени 1 − − = k k k t t τ между соседними моментами 1 − k t и k t поступления заявок с порядковыми номерами ) 1 ( − k и k соответственно ( 0 ...; , 2 , 1 0 = = t k – начальный момент времени ). Основной характеристикой потока заявок является его интенсивность λ – среднее число заявок , проходящих через некоторую границу за единицу времени Величина λ / 1 = a определяет средний интервал времени между двумя последовательными заявками Поток , в котором интервалы времени k τ между соседними заявками принимают определенные заранее известные значения , называется детерминированным Если при этом интервалы одинаковы ( τ τ = k для всех , 2 , 1 = k ), то поток называется регулярным Для полного описания регулярного потока заявок достаточно задать интенсивность потока λ или значение интервала λ τ / 1 = . Поток , в котором интервалы времени k τ между соседними заявками представляют собой случайные величины , называется случайным Для полного описания случайного потока заявок , в общем случае , необходимо задать законы распределений ) ( k k A τ всехинтервалов k τ ( , 2 , 1 = k ). П α λ , П П 1 П N а Рис .3.2. Сеть массового обслуживания 1 2 3 б « И » « У 1 » « У 2 » « У 3 » « И » Раздел 3. Математические модели дискретных систем 81 Случайный поток , в котором все интервалы 1 τ , 2 τ , … между заявками независимы в совокупности и описываются функциями распределений ) ( 1 1 τ A , ) ( 2 2 τ A ,…, называется потоком с ограниченным последействием Случайный поток , в котором все интервалы 1 τ , 2 τ , … распределены по одному и тому же закону ) ( τ A , называется рекуррентным Поток заявок называется стационарным , если интенсивность λ и закон распределения ) ( τ A интервалов между последовательными заявками не меняются со временем В противном случае поток заявок является нестационарным Поток заявок называется ординарным , если в каждый момент времени k t может появиться только одна заявка Если в какой - либо момент времени может появиться более одной заявки , то имеем неординарный или групповой поток заявок Поток заявок называется потоком без последействия , если заявки поступают независимо друг от друга , то есть момент поступления очередной заявки не зависит от того , когда и сколько заявок поступило до этого момента Стационарный ординарный поток без последействия называется простейшим Интервалы времени τ между заявками в простейшем потоке распределены по экспоненциальному закону с функцией распределения λτ τ − − = e A 1 ) ( , (3.1) где 0 > λ – параметр распределения , представляющий собой интенсивность потока заявок Простейший поток часто называют пуассоновским , поскольку число заявок k, поступающих за некоторый заданный промежуток времени t, распределено по закону Пуассона : t k e k t t k P λ λ − = ! ) ( ) , ( , (3.2) где ) , ( t k P – вероятность поступления ровно k заявок за некоторый фиксированный интервал времени t; λ – интенсивность потока заявок. Здесь k – дискретная случайная величина, принимающая целочисленные значения: , 2 , 1 , 0 = k , а 0 > t и 0 > λ – параметры закона Пуассона. Следует отметить, что пуассоновский поток, в отличие от простейшего, может быть: • стационарным, если интенсивность λ не меняется со временем; • нестационарным, если интенсивность потока зависит от времени: ) (t λ λ = В то же время, простейший поток, по определению, всегда является стационарным. 82 Раздел 3. Математические модели дискретных систем Аналитические исследования моделей массового обслуживания часто проводятся в предположении о простейшем потоке заявок, что обусловлено рядом присущих ему замечательных особенностей. 1. Суммирование (объединение) потоков. Сумма H независимых стационарных ординарных потоков с интенсивностями H λ λ , , 1 K образует простейший поток с интенсивностью ∑ = = Λ H k k 1 λ (3.3) при условии, что складываемые потоки оказывают более или менее одинаково малое влияние на суммарный поток. На практике суммарный поток близок к простейшему при 5 ≥ H . Очевидно, что при суммировании независимых простейших потоков суммарный поток будет простейшим при любом значении H. 2. Вероятностное разрежение потока. Вероятностное (но не детерминированное) разрежение простейшего потока заявок, при котором любая заявка случайным образом с некоторой вероятностью p исключается из потока независимо от того, исключены другие заявки или нет, приводит к образованию простейшего потока с интенсивностью λ λ p = ' , где λ – интенсивность исходного потока. Поток исключенных заявок – тоже простейший с интенсивностью λ λ ) 1 ( '' p − = 3. Простота Предположение о простейшем потоке заявок позволяет для многих математических моделей сравнительно легко получить в явном виде зависимости характеристик от параметров Наибольшее число аналитических результатов получено для простейшего потока заявок Анализ моделей с потоками заявок , отличными от простейших , обычно усложняет математические выкладки и не всегда позволяет получить аналитическое решение в явном виде Свое название « простейший » поток получил именно благодаря этой особенности 3.1.4. Длительность обслуживания заявок Длительность обслуживания – время нахождения заявки в приборе – в общем случае величина случайная и описывается функцией ) ( τ B или плотностью ) ( ) ( ' τ τ B b = распределения В случае неоднородной нагрузки длительности обслуживания заявок разных классов могут различаться законами распределений или только средними значениями При этом обычно предполагается независимость длительностей обслуживания заявок каждого класса Часто длительность обслуживания заявок предполагается распределенной по экспоненциальному закону , что существенно упрощает аналитические выкладки Это обусловлено тем , что процессы , протекающие в системах с экспоненциальным распределением интервалов времени , являются марковскими ( см раздел 5). Раздел 3. Математические модели дискретных систем 83 Величина , обратная средней длительности обслуживания b, харак - теризует среднее число заявок , которое может быть обслужено за единицу времени , и называется интенсивностью обслуживания: b / 1 = µ Во многих случаях аналитические зависимости могут быть получены для произвольного закона распределения длительности обслуживания заявок При этом для определения средних значений характеристик обслуживания , зачастую , как будет показано ниже , достаточно задать , кроме математического ожидания b, второй момент распределения ( дисперсию ) или коэффициент вариации b ν длительности обслуживания Время T 0 , оставшееся до завершения обслуживания заявки , находящейся в приборе , от момента поступления некоторой заявки в систему , и учитывающее , что на момент поступления в системе может и не оказаться заявок , то есть учитывающее простои системы , называется временем дообслуживания Математическое ожидание этого времени [9]: 2 / ) 1 ( ] [ 2 2 0 b b T M ν λ + = , (3.4) где λ – интенсивность простейшего потока заявок , поступающих в систему 3.1.5. Стратегии управления потоками заявок Стратегия управления потоками заявок в моделях массового обслуживания задается в виде : дисциплины буферизации ( ДБ ); дисциплины обслуживания ( ДО ). ДБ и ДО могут быть классифицированы по следующим признакам : • наличие приоритетов между заявками разных классов ; • способ ( режим ) вытеснения заявок из очереди ( для ДБ ) и назначения заявок на обслуживание ( для ДО ); • правило вытеснения или выбора заявок на обслуживание ; • возможность изменения приоритетов Одна из возможных классификаций дисциплин буферизации в соответствии с перечисленными признаками представлена на рис .3.3. Дисциплины буферизации (ДБ) Бесприоритетные Приоритетные БВЗ ВЗДК ВЗНК ВЗГК ВСЛ ВПЗ ВДЗ Рис .3.3. Классификация дисциплин буферизации 84 Раздел 3. Математические модели дискретных систем В зависимости от наличия или отсутствия приоритетов между заявками разных классов все ДБ могут быть разбиты на две группы : бесприоритетные ; приоритетные По способу вытеснения заявок из накопителя можно выделить следующие классы ДБ : без вытеснения заявок ( БВЗ ) – заявки , поступившие в систему и заставшие накопитель заполненным до конца , теряются ; с вытеснением заявки данного класса ( ВЗДК ), то есть такого же класса , что и поступившая ; с вытеснением заявки самого низкоприоритетного класса ( ВЗНК ); с вытеснением заявки , принадлежащей группе низкоприори - тетных классов ( ВЗГК ). Два первых класса относятся к бесприоритетным ДБ , а остальные – к приоритетным ДБ могут использовать следующие правила вытеснения заявок из накопителя : вытеснение случайное ( ВСЛ ); вытеснение последней заявки ( ВПЗ ), то есть поступившей в систему позже всех ; вытеснение « долгой » заявки ( ВДЗ ), то есть находящейся в накопителе дольше всех Часто ёмкость накопителя в моделях предполагается неограничен - ной , несмотря на то , что в реальной системе соответствующая ёмкость ограничена Такое предположение оправдано в тех случаях , когда вероят - ность потери заявки в реальной системе из - за переполнения ограниченной ёмкости накопителя меньше 10 -3 , поскольку в этом случае ДБ практически не влияет на характеристики обслуживания заявок На рис .3.4 представлена классификация дисциплин обслуживания заявок в соответствии с теми же признаками , что и для ДБ Дисциплины обслуживания (ДО) Бесприоритетные Приоритетные Одиночного режима Группового режима Одиночного режима Группового режима ОЦП АП ЧП Комбиниро - ванного режима ОР ОПП ООП ОСП ОП СП Рис .3.4. Классификация дисциплин обслуживания Раздел 3. Математические модели дискретных систем 85 В зависимости от наличия или отсутствия приоритетов между заявками разных классов все ДО , как и ДБ , могут быть разбиты на две группы : бесприоритетные ; приоритетные По способу назначения заявок на обслуживание ДО могут быть разделены на дисциплины : одиночного режима ; группового режима ; комбинированного режима В ДО |