Основы проектирования систем
 Скачать 1.88 Mb.
|
|
, (15) причем условие отсутствия перегрузок в системе с неоднородным потоком заявок имеет вид: 1 R ; коэффициент простоя системы: R 1 среднее время ожидания W и среднее время пребывания U заявок объединенного потока в системе: H i i i w W 1 ; H i i i u U 1 , (16) где / i i – коэффициент, учитывающий долю заявок класса i в суммарном потоке, который может трактоваться как вероятность того, что поступившая в систему заявка принадлежит классу i; суммарная длина очереди и суммарное число заявок в системе: H i i l L 1 ; H i i m M 1 . (17) Можно показать, что для характеристик объединенного потока справедливы те же фундаментальные соотношения, что и для однородного потока, а именно: B W U ; W L ; U M , (18) где H i i i b B 1 – среднее время обслуживания заявки объединенного потока. 3.2. Сетевые модели Сетевые модели представляют собойсети массового обслуживания (СеМО), содержащие совокупность взаимосвязанных СМО, в среде которых циркулируют заявки. Сетевые модели могут быть изображены в виде графа СеМО (рисунок 18). Основными элементами СеМО являются узлы (У), представляющие собой СМО разных классов. В общем случае заявки поступают в сеть из внешней по отношению к СеМО среды с интенсивностью 0 λ и случайным образом перемещаются между узлами. По завершению обслуживания заявки в СеМО она возвращается во внешнюю среду. Путь движения заявок в СеМО Рисунок 18. Граф СеМО разомкнутой (а) и замкнутой (б) У 2 У 3 У 4 У 1 У 2 У 3 У 4 У 1 а) б) «0» «0» «0» 12 p 23 p 24 p 13 p 24 p 12 p 13 p 23 p 42 p 41 p 71 называется маршрутом, который описывается с помощью вероятностей передач: ) , 1 , ( n j i p ij – вероятность того, что после обслуживания в узле i заявка перейдет в узел j , где n – количество узлов в СеМО. 3.2.1. Типы сетевых моделей В зависимости от структуры и свойств исследуемых систем, их моделями могут служить СеМО различных классов (рисунок 19). Из всего множества различных сетевых моделей для решения задач системного анализа и проектирования будем в дальнейшем использовать стохастические линейные замкнутые и разомкнутые однородные СеМО. Использование стохастических моделей обусловлено случайным характером процессов формирования нагрузки в реальных системах, в частности, процессов обработки и передачи данных в вычислительных системах. В терминах сетевой модели это означает, что интервалы времени между поступающими заявками и/или длительности их обслуживания в узлах представляют собой случайные величины, описываемые соответствующими законами распределений. Линейность СеМО означает, что интенсивности поступления заявок в узлы сетевой модели связаны линейной зависимостью с интенсивностью поступления заявок в сеть (интенсивностью источника заявок) 0 : ) , 1 ( 0 n i i i , где n – количество узлов в сети. СеМО является линейной, если заявки в сети не теряются (например, из-за ограниченной емкости накопителя в узле) и не размножаются. Принадлежность сетевой модели к классу разомкнутых или замкнутых сетевых моделей определяется числом циркулирующих в сети заявок. В разомкнутой (открытой) СеМО (РСеМО) одновременно может находиться любое число заявок, в том числе и сколь угодно большое, т.е. от 0 Стохастические сетевые модели ВС Замкнутые Комбинированные Разомкнутые Нелинейные Однородные Неоднородные Экспонен- циальные Неэкспонен- циальные Бесприори- тетные Приори- тетные Рисунок 19. Классификация сетевых моделей Линейные 72 до бесконечности. С РСеМО связана внешняя среда, содержащая один или несколько внешних независимых источников заявок, которые генерируют заявки независимо от числа заявок, находящихся в сети. После завершения обслуживания в сети заявки возвращаются во внешнюю среду. Внешняя среда в РСеМО обычно обозначается как дополнительный нулевой узел "0" (рисунок 18,а). Замкнутая (закрытая) СеМО (ЗСеМО) не содержит внешних независимых источников заявок и характеризуется тем, что в ней циркулирует постоянное число заявок М. На графе ЗСеМО из физических соображений, связанных с конкретным представлением процесса функционирования исследуемой реальной системы, обычно выделяется особая дуга, отображающая процесс завершения обслуживания заявок в сети и мгновенного формирования новой заявки с такими же параметрами обслуживания, что и завершившая обслуживание. Такая трактовка позволяет рассматривать завершившую обслуживание заявку как новую заявку, поступившую в сеть из зависимого источника заявок. По аналогии с РСеМО на выделенной дуге ЗСеМО отмечается условная точка "0" (рисунок 18,б), рассматриваемая как нулевой узел и трактуемая иногда как СМО с нулевой длительностью обслуживания или как зависимый источник заявок, генерирующий заявки только в момент поступления некоторой заявки на вход источника. Выделение нулевого узла в ЗСеМО преследует двоякую цель: во-первых, достигается однозначность в представлении и математическом описании РСеМО и ЗСеМО и, во-вторых, обеспечивается возможность определения временных характеристик ЗСеМО относительно выделенного узла "0". В частности, время пребывания заявок в ЗСеМО рассматривается как промежуток времени между двумя соседними моментами прохождения заявки через нулевой узел. Однородность сетевой модели означает, что в СеМО циркулирует один класс заявок (однородный поток заявок), в отличие от неоднородного потока заявок, предполагающего наличие нескольких классов заявок. Заявки в сетевой модели относятся к разным классам, если они различаются хотя бы одним из следующих факторов: длительностями обслуживания в узлах; приоритетами; маршрутами. 3.2.2. Параметры сетевых моделей Для описания линейных разомкнутых и замкнутых однородных экспоненциальных СеМО используется следующая совокупность параметров: число узлов в сети: n; число обслуживающих устройств в узлах сети: n K K , , 1 ; матрица вероятностей передач: ] , , 1 , 0 , [ n j i p ij P , где ij p – вероятность передачи заявки из узла i в узел j; 73 интенсивность 0 источника заявок, поступающих в РСеМО, или число заявок M, циркулирующих в ЗСеМО; средние длительности обслуживания заявок в узлах сети: n b b , , 1 В случае неэкспоненциальных разомкнутых СеМО дополнительно необходимо задать законы распределения или, по крайней мере, вторые моменты распределения интервалов времени между заявками, поступающими в разомкнутую сеть, и длительностей обслуживания заявок в узлах сети. В случае неоднородных СеМО необходимо дополнительно задать количество классов заявок H в сети и для каждого класса – матрицы вероятностей передач P(h), интенсивности поступления заявок в РСеМО ) ( 0 h λ или число циркулирующих в ЗСеМО заявок ) (h M , средние длительности обслуживания заявок в узлах сети ) (h b i ) , 1 ; , 1 ( n i H h , а для приоритетных СеМО – дисциплины обслуживания заявок в узлах и дисциплины буферизации, если емкости накопителей ограничены. При необходимости могут быть заданы законы распределения интервалов между поступающими в РСеМО заявками и длительностей обслуживания заявок разных классов в узлах сети. 3.2.3. Характеристики сетевых моделей Характеристики СеМО делятся на два класса: узловые, описывающие эффективность функционирования узлов; сетевые, описывающие функционирование СеМО в целом. Состав узловых характеристик СеМО такой же, как и для базовых моделей (СМО) и для узла n j , 1 включает в себя: нагрузкуузла: j j j j j b λ α b λ y 0 , где j α – коэффициент передачи, определяемый в процессе решения системы линейных алгебраических уравнений : n i i ij j n i p 0 ) , , 1 , 0 ( ; (19) загрузку узла: ) 1 ; / ( min j j j K y ρ , где j K – число устройств в узле j ; среднее время ожидания заявок в очереди узла j : j w ; среднее время пребывания заявок в узле j : j j j b w u ; среднюю длину очереди заявок в узле j : j j j w λ l ; среднее число заявок в узле j : j j j u λ m В состав сетевых характеристик входят: среднее число заявок, ожидающих обслуживания в сети, определяемая как сумма длин очередей заявок по всем узлам: n j j l L 1 , (20) где j l – средняя длина очереди заявок в узле j ; среднее число заявок, находящихся в разомкнутой сети: 74 n j j m M 1 , (21) где j m – среднее число заявок в узле j ; в замкнутых СеМО число заявок Mзадано в качестве параметра и не может рассматриваться как характеристика сети, при этом выражение (20) может быть использовано для проверки правильности выполненных расчетов; среднее время ожидания заявок в сети: n j j j w α W 1 , (22) где j w – среднее время ожидания заявок в узле j ; j α - коэффициент передачи для узла j , показывающий среднее число попаданий заявки в узел j за время ее нахождения в сети; среднее время пребывания заявок в сети: n j j j u α U 1 , (23) где j u – среднее время пребывания заявок в узле j ; производительность замкнутой СеМО 0 λ определяемая как интенсивность потока обслуженных заявок, проходящих через выделенный нулевой узел замкнутой сети: ) , , 1 ( / 0 n j α λ λ j j ; U M / 0 . (24) Последняя формула представляет собой формулу Литтла для СеМО. Для неоднородной СеМО перечисленные характеристики (20) – (24) определяются как для каждого класса в отдельности, так и для объединенного потока заявок. 3.2.4. Эквивалентные и толерантные преобразования сетевых моделей Один и тот же объект, рассматриваемый на разных уровнях детализации, можно представить различными сетевыми моделями, характеристики которых одинаковы или отличаются на величину, не превосходящую заданной погрешности. При выполнении определенных условий такие модели легко преобразуются друг в друга. Две сетевые модели эквивалентны, если сравниваемые характеристики этих моделей не отличаются друг от друга. Две сетевые модели толерантны (подобны), если значения определенных характеристик отличаются друг от друга на величину, не превосходящую заданную. Использование свойств эквивалентных и толерантных моделей позволяет упростить расчет характеристик моделей путем замены сложных сетевых моделей более простыми. Эквивалентными могут быть сетевые модели одного типа (например, две замкнутые сети), толерантными – модели как одного, так и разных типов. 75 Эквивалентное преобразование разомкнутых сетей. Примером эквивалентного преобразования может служить преобразование разомкнутой однородной экспоненциальной сетевой модели в совокупность независимых СМО типа М/М/1, число которых равно количеству узлов РСеМО. При этом в качестве параметров СМО n j , 1 используются: интенсивность потока заявок, рассчитываемая через коэффициент передачи j α : 0 λ α λ j j ; длительность обслуживания заявок, совпадающая с длительностью обслуживания в соответствующем узле СеМО: j b Характеристики СМО (среднее число заявок в очереди и системе, среднее время ожидания заявки в очереди и пребывания в системе, среднее число занятых устройств и т. д.) рассчитываются независимо друг от друга и являются узловыми характеристиками сети. Затем на их основе с использованием формул (20) – (24) определяются сетевые характеристики. Толерантные преобразования. Определим условия, при которых ЗСеМО могут быть представлены в виде РСеМО. Такое преобразование позволяет пользоваться при расчете сетей более простыми математическими зависимостями. Для определения условий преобразования выявим особенности РСеМО и ЗСеМО и путь нивелировки этих особенностей. РСеМО состоит из n СМО и неограниченного источника с постоянной интенсивностью потока заявок, не зависящей от состояния сети, т.е. от числа заявок и их распределения в сети. Число заявок, находящихся в РСеМО, – случайная величина, распределенная в диапазоне от 0 до бесконечности. Интенсивность поступающего в сеть потока заявок совместно с матрицей вероятностей передач однозначно определяет интенсивности входящих потоков в каждый узел сети. В результате, вероятности состояний каждого узла зависят только от его параметров (интенсивности входящего потока и среднего времени обслуживания), но не от параметров других узлов. Замкнутая сеть состоит из n узлов и не содержит источника заявок неограниченной емкости, поэтому заранее не известны интенсивности потоков, входящих в каждый из узлов. Вероятности состояний отдельных узлов зависят от параметров всей сети в целом, т. е. от параметров других узлов сети. Распределение заявок между узлами сети случайно, но их общее число М постоянно. В такой сети источником может считаться любой узел, но емкость каждого источника, т. е. число заявок в нем, ограничена. Так как параметры узлов сети различны, то в одних узлах будет скапливаться больше заявок, а в других меньше. Наибольшее число заявок будет скапливаться в наиболее загруженном узле. Поэтому такой узел – узкое место сети. Пусть узел j , содержащий К j устройств со средним временем обслуживания b j в каждом из них, является узким местом сети. Чем больше загрузка узла j , тем большая доля всех заявок М скапливается в нем и тем выше вероятность того, что все устройства данного узла заняты обслуживанием заявок. Можно показать, что при бесконечно большом числе заявок М в 76 многоканальном узле, являющимся узким местом сети, даже при неограниченно большом числе устройств скапливается с единичной вероятностью большое число заявок. Загрузка каждого из устройств данного узла стремится к единице, а интенсивность потока на его выходе – к величине j j b K / . Следовательно, замкнутая сеть становится подобной разомкнутой сети, в которой источником с постоянной интенсивностью j j b K / является узел j . Таким образом, узел j замкнутой сети будет потенциальным источником, если его загрузка максимальна. Учитывая, что j j j j K b / и 0 j j , получим условие толерантности замкнутой и разомкнутой сети: ) , , 1 ( 1 ) / ( max / 0 , 1 0 n j K b K b i i i n i j j j j . Если в замкнутой сети имеется несколько узлов, для которых выполняется данное условие, то сеть также преобразуется в разомкнутую. Интенсивности потоков в узлах рассчитываются, как и при одном источнике, на основе равенства 0 j j . Часто оказывается, что даже при конечном числе заявок М замкнутую сеть можно представить как разомкнутую. Условием, при котором замкнутая сеть может рассматриваться как разомкнутая, т. е. условием толерантности замкнутой и разомкнутой сети является выполнение неравенства 1 ) / max( i j для всех n i , , 1 , кроме j i . Индекс j выделяет наиболее загруженную систему сети, а соотношение y x означает, что x по крайней мере на порядок больше y. При достаточно большом числе заявок М в сети это условие значительно ослабляется. Уже при M > 20 замкнутую сеть можно рассматривать как разомкнутую, даже при условии: 1 ) / max( i j |