Механики
 Скачать 4.29 Mb.
|
|
4.4.6. Анализ свойств разомкнутых СеМО Свойства разомкнутых СеМО определяются значениями узловых и сетевых характеристик , связанных между собой зависимостями , представленными в разделе 3. Наибольший интерес представляют свойства сети в целом , поскольку свойства отдельных узлов СеМО аналогичны свойствам соответствующих одноканальных и многоканальных СМО На рис . 4.13 показана зависимость основной сетевой характеристики РСеМО – среднего времени пребывания U заявок в сети от интенсивности 0 λ поступления заявок в сеть Зависимость ) ( 0 ' ' λ f U = аналогична зависимости среднего времени пребывания заявок в СМО от загрузки системы , изменение которой может быть обусловлено , в частности , изменением интенсивности поступления заявок в СМО Как и в СМО , имеется некоторое предельное значение интенсивности max ' 0 λ , при котором среднее время пребывания заявок в сети становится бесконечно большим , что свидетельствует о перегрузке в СеМО Выше ( см п .3.4.2) показано , что в РСеМО отсутствуют пе - регрузки , если они отсут - ствуют во всех узлах сети , то есть перегрузка в разомкнутой СеМО насту - пает в том случае , когда загрузка одного из узлов сети становится равной единице Такой узел назы - вается «узким местом» и характеризуется тем , что очередь заявок перед ним со временем растёт до 0 λ U 0 max " 0 λ max ' 0 λ ) ( 0 ' ' λ f U = ) ( 0 " " λ f U = Рис.4.13. Время пребывания заявок в РСеМО 146 Раздел 3. Аналитическое моделирование бесконечности и , как следствие , становится бесконечным число заявок в разомкнутой СеМО Для того чтобы избавиться в РСеМО от перегрузки , необходимо разгрузить « узкое место ». Это может быть достигнуто следующими способами : • увеличением скорости работы ( быстродействия ) обслуживающего прибора ; • увеличением числа обслуживающих приборов в узле Любой из этих способов позволяет увеличить производительность СеМО в целом и , как следствие , улучшить характеристики сети Зави - симость среднего времени пребывания U заявок в сети от интенсивности 0 λ поступления заявок в сеть принимает вид ) ( 0 " " λ f U = , то есть время пребывания заявок при одной и той же интенсивности 0 λ становится меньше ( поскольку сеть имеет б о льшую производительность ), а предель - ное значение интенсивности max " 0 λ , при котором наступает перегрузка СеМО , становится больше : max max ' 0 " 0 λ λ > При этом появляется новое узкое место в СеМО , и дальнейшее улучшение сети может быть достигнуто путём разгрузки нового узкого места Очевидно , что если СеМО является моделью реальной технической системы , разгрузка узкого места за счёт увеличения скорости работы обслуживающего прибора или числа приборов в узле означает увеличение стоимости реальной системы Существует ещё один способ разгрузки узкого места СеМО , заключающийся в уменьшении вероятности передачи заявок к узлу , являющемуся узким местом Этот способ часто используется в реальных системах и обычно не связан с увеличением стоимости системы Например , в вычислительной системе изменение вероятностей передач к накопителям внешней памяти может быть достигнуто за счет перерас - пределения файлов между накопителями : наиболее часто используемые файлы , расположенные в наиболее загруженном накопителе , переносятся в наименее загруженный накопитель При этом уменьшается количество обращений к загруженному накопителю ( коэффициент передачи соответствующего узла СеМО ). Характер зависимостей других сетевых характеристик ( времени ожи - дания , числа заявок в сети и в состоянии ожидания ) разомкнутой СеМО от интенсивности поступления заявок аналогичен показанному на рис . 4.13. Пример 4.3. Проиллюстрируем способы разгрузки узкого места и получаемый от этого эффект для четырёхузловой разомкнутой СеМО , рассмотренной в примере 4.2. Там же было показано , что интенсивность поступления заявок в разомкнутую СеМО , при которой в сети отсутствуют перегрузки , должна удовлетворять условию : 1 0 с 125 , 0 − < λ Раздел 3. Аналитическое моделирование 147 1. Рассчитаем сначала характеристики РСеМО , работающей в области загрузок , близких к 1, для чего положим , что интенсивность потока поступающих в сеть заявок равна 1 0 с 12 , 0 − = λ Тогда интенсивности потоков заявок в узлы РСеМО соответственно будут равны : 1 0 1 1 с 2 , 1 − = = λ α λ , 1 0 2 2 с 24 , 0 − = = λ α λ , 1 0 3 3 с 84 , 0 − = = λ α λ , 1 0 4 4 с 08 , 1 − = = λ α λ , а средние длительности обслуживания заявок , как и ранее , будут равны : 8 , 0 1 = b с ; 2 2 = b с ; 4 , 0 3 = b с ; 3 , 0 4 = b с Рассчитанные значения узловых и сетевых характеристик СеМО приведены в табл .4.3. Таблица 4.3 Характеристики Узел 1 Узел 2 Узел 3 Узел 4 СеМО Нагрузка 0,96 0,48 0,336 0,324 2,10 Загрузка 0,96 0,48 0,336 0,324 2,10 Время ожидания 19,2 1,85 0,202 0,144 198,4 Время пребывания 20 3,85 0,602 0,444 215,9 Длина очереди 23,04 0,44 0,170 0,155 23,8 Число заявок 24 0,92 0,506 0,479 25,9 Анализ представленных результатов показывает , что увеличение интенсивности поступления заявок в РСеМО всего лишь на 20% до значения 1 0 с 12 , 0 − = λ , привело к резкому росту значений сетевых характеристик В частности , среднее время пребывания заявок в сети выросло в 4 раза , а число заявок , находящихся в очередях – почти в 6,5 раз Это говорит о том , что СеМО работает в области больших загрузок , где незначительное увеличение нагрузки приводит к существенному изменению характеристик обслуживания заявок Наиболее загруженным узлом СеМО , то есть узким местом , является узел 1, загрузка которого много больше загрузок других узлов и составляет 96 , 0 1 = ρ Именно в этом узле характеристики обслуживания заявок выросли наиболее существенно : среднее время пребывания заявок в 5 раз ( с 4 до 20 секунд ), а средняя длина очереди – более чем в 7 раз ( с 3,2 до 23 заявок ). 2. Для улучшения характеристик обслуживания заявок в РСеМО необходимо разгрузить узкое место сети , которым является узел 1. Для этого увеличим скорость работы обслуживающего прибора в 2 раза , что , в конечном счете , приведёт к уменьшению длительности обслуживания заявок в 2 раза , которая станет равной 4 , 0 1 = b с Рассчитанные значения узловых и сетевых характеристик СеМО после разгрузки узкого места приведены в табл .4.4. Анализ представленных результатов показывает , что разгрузка узко - го места позволила существенно уменьшить значения сетевых характерис - тик : среднее время пребывания заявок в сети уменьшилось более чем в 9 148 Раздел 3. Аналитическое моделирование раз , а число заявок , находящихся в очередях – почти в 20 раз Отметим , что изменение длительности обслуживания заявок в узле 1 привело к изменению узловых характеристик только этого узла ; узловые характерис - тики остальных узлов не изменились Это является следствием независи - мого функционирования узлов экспоненциальной разомкнутой СеМО , что фактически и позволяет использовать метод расчёта характеристик сети , основанный на декомпозиции , то есть представлении сети в виде совокупности независимых СМО Таблица 4.4 Узловые характерстики Узел 1 Узел 2 Узел 3 Узел 4 СеМО Нагрузка 0,48 0,48 0,336 0,324 1,62 Загрузка 0,48 0,48 0,336 0,324 1,62 Время ожидания 0,369 1,846 0,202 0,144 10,1 Время пребывания 0,769 3,846 0,602 0,444 23,6 Длина очереди 0,443 0,443 0,170 0,155 1,21 Число заявок 0,923 0,923 0,506 0,479 2,83 3. Для сравнения выполним разгрузку узкого места другим способом , а именно : увеличим число обслуживающих приборов в узле 1 с одного до двух : 2 1 = K , сохранив прежнее значение длительности обслуживания одним прибором : 8 , 0 1 = b с Рассчитанные значения узловых и сетевых характеристик СеМО после разгрузки узкого места приведены в табл .4.5. Таблица 4.5 Узловые характерстики Узел 1 Узел 2 Узел 3 Узел 4 СеМО Нагрузка 0,96 0,48 0,336 0,324 2,10 Загрузка 0,48 0,48 0,336 0,324 1,62 Время ожидания 0,288 1,846 0,202 0,144 9,28 Время пребывания 1,088 3,846 0,602 0,444 26,78 Длина очереди 0,346 0,443 0,170 0,155 1,11 Число заявок 1,306 0,923 0,506 0,479 3,21 Сравним полученные значения сетевых характеристик со значения - ми , представленными в табл . 4.4 для первого способа разгрузки узкого места за счёт уменьшения длительности обслуживания заявок При втором способе разгрузки узкого места за счёт увеличения числа обслуживающих приборов ( 2 1 = K ; 8 , 0 1 = b с ) среднее время ожидания заявок в сети несколько уменьшилось по сравнению с первым способом ( 1 1 = K ; 4 , 0 1 = b с ). В то же время , среднее время пребывания заявок в РСеМО увеличились более чем на 10%, что обусловлено большей длительностью обслуживания заявок ( 8 , 0 1 = b с ) в каждом из приборов двухканального Раздел 3. Аналитическое моделирование 149 узла 1 по сравнению с одноканальным узлом при первом способе ( 4 , 0 1 = b с ). Как и в предыдущем случае , изменение числа обслуживающих приборов в узле 1 привело к изменению узловых характеристик только этого узла 4.5. Замкнутые экспоненциальные СеМО с однородным потоком заявок «Во всякой формуле константы (особенно те, которые взяты из технических справоч- ников) должны рассматриваться как пере- менные» (Универсальные законы …) 4.5.1. Описание замкнутых СеМО Рассмотрим замкнутую экспоненциальную сеть массового обслуживания с однородным потоком заявок при следующих предположениях : 1) замкнутая СеМО ( ЗСеМО ) произвольной топологии содержит n узлов ; 2) после завершения обслуживания в каком - либо узле передача заявки в другой узел происходит мгновенно; 3) все узлы замкнутой СеМО одноканальные; 4) в СеМО циркулирует постоянное число заявок; 5) длительности обслуживания заявок во всех узлах сети представляют собой случайные величины , распределенные по экспоненци- альному закону ; 6) ёмкость накопителя в каждом узле СеМО достаточна для хранения всех заявок , циркулирующих в сети , что означает отсутствие отказов поступающим заявкам при их постановке в очередь любого узла ( в частности , можно считать , что ёмкость накопителя в каждом узле равна числу заявок , циркулирующих в сети ); 7) обслуживающий прибор любого узла не простаивает, если в его накопителе имеется хотя бы одна заявка , причем после завершения обслуживания очередной заявки мгновенно из накопителя выбирается следующая заявка ; 8) в каждом узле сети заявки из накопителя выбираются в соответствии с бесприоритетной дисциплиной обслуживания в порядке поступления ( ОПП ) по правилу « первым пришел – первым обслужен » (FIFO – First In First Out). Для описания линейных замкнутых однородных экспоненциальных СеМО необходимо задать такую же совокупность параметров , как и для разомкнутых СеМО , с единственным отличием , заключающимся в том , что вместо интенсивности источника заявок следует задать число заявок , циркулирующих в ЗСеМО Таким образом , совокупность параметров для замкнутых СеМО будет иметь следующий вид : • число узлов в сети : n; 150 Раздел 3. Аналитическое моделирование • число обслуживающих приборов в узлах сети : n K K ..., , 1 ; • матрица вероятностей передач: ] , , 1 , 0 , [ n j i p ij K = = P , где ij p – вероятность передачи заявки из узла i в узел j; • число заявок M, циркулирующих в ЗСеМО ; • средние длительности обслуживания заявок в узлах сети : n b b , , 1 K На основе перечисленных параметров могут быть рассчитаны узловые и сетевые характеристики , описывающие эффективность функционирования соответственно узлов и ЗСеМО в целом Расчёт характеристик функционирования линейных замкнутых однородных экспоненциальных СеМО с одноканальными узлами бази - руется на так называемой « теореме о прибытии » и проводится с использованием метода средних значений в два этапа : • расчет коэффициентов передач в узлах замкнутой СеМО ; • расчет характеристик ЗСеМО 4.5.2. Расчет коэффициентов передач в узлах ЗСеМО Для замкнутой СеМО на первом этапе рассчитываются только коэффициенты передач Интенсивности потоков заявок в узлах ЗСеМО не могут быть рассчитаны , как в РСеМО , поскольку для ЗСеМО изначально не известна интенсивность 0 λ , которая является не параметром , задава - емым в составе исходных данных , а характеристикой , представляющей собой производительность ЗСеМО и определяемой в процессе анализа эффективности функционирования ЗСеМО Для расчёта коэффициентов передач n α α , , 1 K после некоторых преобразований можно воспользоваться той же системой линейных алгебраических уравнений (4.16). Для этого в левой и правой части выражения (4.16) представим интенсивности в виде 0 λ α λ j j = Разделив левую и правую часть выражения (4.16) на 0 λ , окончательно получим систему линейных алгебраических уравнений относительно n α α , , 1 K : ∑ = = = n i i ij j n i p 0 ) , , 1 , 0 ( K α α . (4.17) Полагая 1 0 = α , можно найти корни системы уравнений , численно определяющие значения n α α , , 1 K 4.5.3. Расчет характеристик ЗСеМО Характеристики ЗСеМО могут быть рассчитаны с использованием марковских процессов , поскольку количество состояний марковского процесса , в отличие от РСеМО , не бесконечно и равно числу сочетаний M n M 1 C − + , где n – число узлов в ЗСеМО и M – число заявок , циркулирующих в ЗСеМО При этом основная трудность заключается в определении веро - Раздел 3. Аналитическое моделирование 151 ятностей состояний сети ) , , ( 1 n M M P K в случае большой ее размерности ) 5 ; 5 ( > > M n , когда число состояний оказывается значительным При выполнении расчетов на ЭВМ это , во многих случаях , приводит к потере значимости в процессе промежуточных вычислений и , следовательно , к невозможности получения конечных результатов От указанного недостатка свободен метод средних значений, позволяющий вычислять средние характеристики функционирования экспоненциальных СеМО на основе сравнительно простых рекуррентных соотношений Положим , что замкнутая однородная СеМО содержит n одноканальных узлов , длительности обслуживания заявок в которых распределены по экспоненциальному закону со средними значениями n b b , , 1 K соответственно Пусть для каждого узла i сети известно среднее число попаданий заявки в данный узел за время ее нахождения в сети , то есть коэффициент передачи i α , который , если конфигурация сети задана матрицей вероятностей передач ] , , 1 , 0 , [ n j i p P ij K = = , определяется в результате решения системы линейных алгебраических уравнений (4.17). Обозначим : i u - среднее время пребывания заявки в узле i за время пребывания в сети ; i m – среднее число заявок в узле ) , , 1 ( n i i K = ; 0 λ – производительность замкнутой сети Очевидно , что эти величины зависят от числа заявок M , циркулирующих в замкнутой сети , то есть ) (M u u i i = ; ) (M m m i i = ; ) ( 0 0 M λ λ = Можно показать , что имеют место следующие соотношения : )] 1 ( 1 [ ) ( − + = M m b M u i i i ; (4.18) ∑ = = n i i i M u M U 1 ) ( ) ( α ; (4.19) ) ( ) ( 0 M U M M = λ ; (4.20) ) ( ) ( ) ( 0 M u M M m i i i λ α = , (4.21) где ) (M U – среднее время пребывания заявок в сети при условии нахождения в ней M заявок ; 0 ) 0 ( = i m Выражение (4.18) получено на основе так называемой теоремы о прибытии [1], утверждающей , что в замкнутой экспоненциальной сети с одноканальными узлами , в которой циркулируют M заявок , стационарная вероятность состояния любого узла в момент поступления в него новой заявки совпадает со стационарной вероятностью того же состояния рассматриваемого узла в сети , в которой циркулирует на одну заявку меньше , то есть ) 1 ( − M заявок Это означает , что в сети с M заявками среднее число заявок ) (M m i , находящихся в узле i в момент поступления в этот узел новой заявки , равно ) 1 ( − M m i Тогда среднее время пребывания 152 Раздел 3. Аналитическое моделирование 2 3 12 p 10 p 1 4 13 p «0» Рис.4.14. Граф замкнутой СеМО в узле i поступившей заявки будет складываться из среднего времени обслуживания всех ) 1 ( − M m i ранее поступивших и находящихся в узле i заявок и средней длительности обслуживания рассматриваемой заявки : )] 1 ( 1 [ ) 1 ( ) ( − + = + − = M m b b M m b M u i i i i i i В этом выражении учтено , что среднее время дообслуживания заявки , находящейся в приборе на момент поступления рассматриваемой заявки , равно средней длительности обслуживания i b в силу свойства отсутствия последействия , присущего экспоненциальному закону Среднее время пребывания заявки в узле i за время ее нахождения в сети , учитывающее число попаданий i α заявки в данный узел , равно ) ( ) ( M u M U i i i α = Выражения (4.19) и (4.20) представляют собой формулы Литтла для сети , а выражение (4.21) – для узла i, где ) ( ) ( 0 M M i i λ α λ = – интенсивность потока заявок в узел ) , , 1 ( n i i K = На основе рекуррентных соотношений (4.18) – (4.21) последователь - но для * , , 2 , 1 M M K = , где * M – заданное число заявок в замкнутой сети , могут быть рассчитаны средние значения характеристик замкнутой экспоненциальной СеМО Заметим , что приведенный метод расчета является точным для замкнутых экспоненциальных СеМО с одноканальными узлами |