Моделирование

Министерство науки и высшего образования Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего образования РЯЗАНСКИЙ ГОСУДАРСТВЕННЫЙ РАДИОТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ имени В.Ф. Уткина Кафедра электронных вычислительных машин Конспект лекций по дисциплине «Моделирование» Направление 090301 – Информатика и вычислительная техника Направленность – Вычислительные машины, комплексы, системы и сети Квалификация выпускника – бакалавр Форма обучения – заочная Рязань 2020 г. 1 Оглавление Введение ........................................................................................................................................4 Моделирование как метод познания и метод решения технических задач .................4 Классификация моделей ........................................................................................................5 Этапы моделирования ............................................................................................................6 1 Аналитическое моделирование вычислительных систем ...............................................8 1.1 Цель моделирования .........................................................................................................8 1.2 Понятие и классификация случайных процессов ......................................................9 1.3 Основные типы или физический смысл трактовки состояний ВС ......................10 1.4 Потоки событий. Их параметры и свойства ..............................................................11 1.5 Простейший поток событий ..........................................................................................13 1.6 Потоки Эрланга ...............................................................................................................15 1.7 Марковские процессы ....................................................................................................16 1.7.1 Марковский процесс с дискретным временем .......................................................17 1.7.2 Марковские процессы с непрерывным временем .................................................20 1.8 Модели типовых СМО ...................................................................................................29 1.8.1 Классификация (обозначение) типовых СМО .......................................................29 (символика Кендалла) ..........................................................................................................29 1.8.2 Порядок (алгоритм) формирования аналитической модели СМО ....................30 1.8.3 Схема гибели и размножения .....................................................................................30 1.8.4 Модели СМО с отказами в обслуживании заявок .................................................31 (Многоканальная СМО без очереди. СМО M/M/n/0) .....................................................31 1.8.5 Одноканальная система массового обслуживания с очередью (с ожиданием). СМО M/M/1.............................................................................................................................35 1.8.5.1 Разделение очереди на конечную и бесконечную части ....................................38 1.8.5.2 Графические иллюстрации основных зависимостей СМО M/M/1 ................39 1.8.5.3 Дисперсии основных характеристик СМО M/M/1 .............................................40 1.8.6 Многоканальная СМО с очередью. СМО М/М/n ..................................................42 1.8.7 Многоканальная СМО с конечной очередью. СМО M/M/n/k .............................45 1.8.8 СМО M/G/1 с заявками N типов................................................................................48 1.8.9 СМО с приоритетными дисциплинами обслуживания ........................................52 1.8.9.1 СМО M/G/1 с относительными приоритетами ...................................................53 1.8.9.2 СМО M/G/1 с абсолютными приоритетами ........................................................56 1.8.10 Закон сохранения среднего времени ожидания. ...................................................58 Закон Л. Клейнрока ..............................................................................................................58 1.8.11 Примеры расчѐта СМО с приоритетами ..............................................................59 2 Моделирование ВС, представленных стахостическими сетями массового обслуживания .............................................................................................................................61 2.1 Примеры моделей, используемых при анализе ВС ..................................................62 2.2 Разомкнутые и замкнутые стохастические сети (СС) ..............................................65 2 2.3 Методика моделирования сложных систем, представленных стохастическими сетями ......................................................................................................................................68 3 Имитационное моделирование ............................................................................................72 3.1 Логика работы GPSS ......................................................................................................72 3.2 Основы имитационного моделирования ....................................................................73 3.3 Структура имитационной модели. ...............................................................................75 3.4 Способы формализации объектов моделирования ..................................................75 3 Введение Моделирование как метод познания и метод решения технических задач Моделирование - это: 1. Исследование каких-либо явлений, процессов и систем объектов путѐм построения и изучения их моделей. 2. Использование моделей для:  определения или уточнения характеристик явлений, процессов, объектов;  поиска наиболее рациональных способов построения вновь разрабатываемых процессов и объектов. При моделировании происходит замещение оригинала моделью (рис.). Моделирование является одной из основных категорий теории познания и методов познания, в частности, моделирование используется в научных исследования. Различают предметные и знаковые модели, Предметнгыевоспроизводят геометрические, физические, динамические или функциональные характеристики или свойства оригинала. Знаковые модели - это некоторые абстрактные модели, такие, как схемы, чертежи, формулы, предложения в некотором алфавите, программы и т. п. Наиболее важная из знаковых моделей – математическая модель. Модель всегда беднее оригинала, который всегда более многообразен. Области применения моделирования: 1. С помощью моделирования изучается нужное конкретное свойство оригинала. В зависимости от того, какие конкретно свойства интересуют исследователя, можно построить совершенно разные модели одного и того же оригинала. Пример: оригинал – вычислительная система, модели – модель надѐжности (T, ламбда), тепловая модель (t0C), информационная модель (ERдиаграмма), модель безопасности (субъекты, объекты, доступы), если нас интересует процесс защиты информации в этой системе, модель обслуживания решаемых ВС задач – модель в виде СМО (система массового обслуживания). В частности,простейшая СМО состоит из двух частей: υ λ λабс … ||| |< ω > | OA λотк u = ω + υ – время нахождения заявки в системе. 2. Моделирование как метод познания, исследования. В этом случае оно применяется для разработки сложных технических систем, выявления 4 ошибок проектирования, слабых мест, оптимизации некоторых параметров оригинала. 3. Применение моделирования как системы управления. внешнее воздействие объект управления выходная характеристика управляющее воздействие система управления модель объекта управления Например объект управления – завод, систем управления - заводоуправления, имеющее представление о производстве в виде его молели. 4. В ряде случаев при проектировании и исследовании сложных систем или процессов не существует иных методов исследования, кроме моделирования. Например, прогноз погоды. Классификация моделей Признаки классификации: 1. Материальная сущность. 2. Степень абстракции. 3. Назначение – область применения. 4. Иерархический уровень моделирования оригинала. 1. Классификация по материальной сущности: физические и математические модели. Физическим соответствуют предметные модели, а математическим – знаковые. Физическая модель имеет одну и ту же физическую природу с оригиналом. Достоинства физических моделей: отсутствие необходимости составлять математическое описание объекта, физическая модель может быть более точной, так как всякое математическое описание – идеализация и неполный учѐт свойств. Недостатки: трудность перестройки, сложность изготовления. Физические модели чаще всего применяются при невозможности применить достаточно точные математические модели (аэродинамическая труба + модель ЛА). 2. По степени абстракции различают аналитические и имитационные модели. Аналитические получают математическим методом и разрешаются 5 относительно искомых характеристик. Иногда получают математические уравнения в форме, неразрешимой относительно искомых характеристик, но и такие математические уравнения могут быть решены численными методами. Имитационные модели включают описание оригинала на некотором языке (программа работы), которое включает описания элементов, связей и алгоритмов функционирования. Имитационная модель работает как бы точно так же, как и оригинал. События в имитационной модели происходят в той же хронологии, что и в оригинале. Эти модели имитируют поведение оригинала в рамках исследуемых свойств (характеристик). Иногда имитационная модель воспроизводит оригинал не только по поведению, но и по структуре. Имитационные модели бывают детерминированными и вероятностными. Наиболее часто в имитационных моделях есть детерминированные и случайные элементы. В имитационных моделях могут быть подмодели. В общем случае могут использоваться комбинационные модели: имитационно-аналитические или аналитически-имитационные (Пример). 3. По назначению модели бывают экономические, технические (конструкция, функционирование, надежность, информационная безопасность, …), социальные и т.д. 4. По уровню моделирования оригинала зависит от того, какие иерархические свойства оригинала находят представление в модели. При проектировании вычислительных систем (ВС) различают следующие уровни: 1) Системный (СМО – производительность, задержка в обслуживании, надежность, безопасность). 2) Операционный (система команд, способы адресации, регистровая модель). 3) Логический (отдельные микрооперации, элементы памяти и т.д.). 4) Элементный (отдельные логические элементы). Этапы моделирования Процесс моделирования в значительной степени является не наукой, а искусством, т.е. сколько специалистов столько и методик моделирования и разбиения процессов моделирования на этапы. Большинство специалистов выделяют этапы: 1. Формировка и постановка цели моделирования. 2. Разработка концептуальной модели. 3. Выбор типа модели, ее параметров и характеристик. 4. Разработка математической (формальной) модели. 5. Выбор средств и языков. 6. Программирование модели на выбранном языке. 7. Проверка адекватности модели. 8. Калибровка модели. 9. Планирование модельного (машинного) эксперимента. 6 10. Модельный эксперимент (серия элементарных опытов с моделью). 11.Обработка и интерпретация результатов моделирования. 12.Оформление документации. Последние 3 пункта называются анализом результатов моделирования. На 1-ом этапе даются ключевые определения и сам этап имеет определяющее значение для всех последующих значений. На этом этапе происходит изучение оригинала и готовятся исходные данные оригинала. На 2-ом этапе концептуального моделирования отражается общий замысел и план построения модели. Концептуальная модель – это чисто абстрактная модель, которая определяет состав и структуру системы, ее свойства, причинно-следственные связи, присущие оригиналу. Первоначально концептуальная модель возникает в сознании исследователя. Процесс создания концептуальной модели практически не формализуется, так как модель ориентируется на определенные свойства оригинала и их выявление в соответствии с целями, то концептуальная модель является сущностью системы для достижения целей моделирования. Разработка концептуальной модели требует нестандартного подхода и глубоких знаний об оригинале. Надо: - обосновывать не только то, что должно войти в модель, но и что может быть удалено из модели без существенных искажений результатов; - выбрать уровень детализации модели (составляющие элементы и взаимодействия между ними); - описать работу модели. Функционирование системы – это выполнение процесса преобразования информации, вещества, энергии и т.п. Разработанную концептуальную модель необходимо подвергнуть независимой экспертизе. Содержание 3-его этапа зависит от цели моделирования, от требуемых уровней детализации и от характера моделирования. В состав параметров и характеристик модели включаются те, для которых нужно выяснить взаимную зависимость. 7 1 Аналитическое моделирование вычислительных систем 1.1 Цель моделирования Цель моделирования – построение эффективных методов анализа и проектирования вычислительных систем (ВС), предназначенных для обработки высокоинтенсивных потоков данных в реальном времени. Целями моделирования на системном уровне является установление следующих характеристик и зависимостей: 1. производительность системы; 2. время пребывания заявки на обслуживание в системе; 3. время ожидания заявки в буфере (очереди); 4. интенсивность отказов в обслуживании из-за переполнения буфера как функция от емкости буфера; 5. длительность обслуживания заявок или информационных сообщений; 6. закон распределения длительности обслуживания; 7. число информационных каналов системы; 8. время наблюдения системы для получения статистически верных результатов; 9. длина очереди и т.д. В качестве базовой модели на этом уровне моделирования ВС используют системы массового обслуживания (СМО) и соответствующий математический аппарат - теорию СМО. Пример простейшей СМО. Известно λ,µ,Тср , ̅ ;̅̅̅ - ? СМО λ ̅̅̅ О ̅ ОА λ λ – интенсивность потока заявок на входе СМО,λ[ ], [ ]; Тср= – время поступления заявок; µ- интенсивность обслуживания или число заявок, которые аппарат обслуживает за 1 секунду, µ[ ]; v= - среднее время обслуживания,[c]. w - средне время ожидания в очереди.  *v < 1 , или  <1- основное условие работы системы в стационарномрежиме.  Очередь появляется из-за двух случайных процессов: 8  процесс прихода заявок,  процесс обслуживания. ρ =  *v , η = 1- ρ, ρ– коэффициент загрузки ОА, ρ=0÷1; η –коэффициент простоя ОА. l   * w , (формула Литтла) l –средняя длина очереди. u  wv , u -среднее время пребывания заявки в системе. ml , m - коэффициент мультипрограммирования системы, т.е. среднее число заявок, находящихся внутри СМО. m   *u . В общем случае простейшая СМО может быть СМО с отказом(отказ в обслуживании заявки, когда очередь имеет максимальную длину). Если очередь имеет ограничение, то λ = λобсл + λотк. λ lmax О ̅ ОА λобслуж λотказ Для большинства СМО характерно наличие случайностей ее функционирования. Для моделей СМО характерны два основных класса случайных процессов: 1. процесс появления заявок на входе систем, моменты появления случайны; 2. процессы обслуживания заявок системы, время обслуживания заявок случайно. 1.2 Понятие и классификация случайных процессов Случайный процесс X(t) – случайная величина, изменяющаяся во времени. Различные значения случайной величины связываются с различными состояниями исследуемой ВС, поэтому S(t) ≡ X(t). Случайный процесс (СП) – это переход системы во времени из состояния в состояние. Если S(t) принимает счетное множество значений, то состояние дискретное, иначе непрерывное. Если S(t) изменяется дискретно во времени, то этот процесс называется процессом с дискретным временем, иначе - с непрерывным. 9 Приведем классификацию СП: СП СП с дискретным состоянием S0,S1,…,Sk СП с непрерывным состоянием S(t) СП с дискретным временем t0,t1,…,tn СП с непрерывным временем t≥0 1.3 Основные типы или физический смысл трактовки состояний ВС Приведем основные типы или физический смысл трактовки состояний ВС: 1. Состояния Siявляются этапами обработки информации; 2. Состояния Siхарактеризуют число отказавших элементов системы; 3. Состояния Si– число занятых элементов ВС при обработке заявок, или более точно, суммарное число заявок, находящихся в СМО в данный момент. Приведем примеры различных типов или физических смыслов Siв виде графа перехода системы из состояния в состояние. Пример первой трактовки ВС может находится трех состояниях: S0 - ожидание (простой), S1 - счет, S2 - ввод/вывод. простой счет P01 P00 S0 В/В P12 S1 P10 P22 S2 P21 P11 P20 Р- вероятность перехода из одного состояния в другое, Р02=0. Пример второй трактовки – выч. система с резервированием (2 ПК для увеличения надежности).ВС работает пока работает хотя бы один ПК. ПК1 ПК2 10 Si–i отказавших элементов: S0 – ни один ПК не отказал, S1 –один из ПК отказал, S2 – оба ПК отказали. λ – интенсивность отказов ПК; µ–интенсивность ремонта; λ λ отказ отказ S0 S1 S2   ремонт ремонт Третья трактовкахарактерна для СМО: λ ̅ Сmax=0 ОА1 λобсл ̅ ОА2 λотк λобсл= λ(1- Pотк); S0 – в системе 0 заявок, S1 – в системе 1 заявка в одном из ОА, S2 – в системе 2 заявки, оба ОА заняты. Ротк = Р2. λ – интенсивность прихода заявок на вход системы; µ=1/vср–интенсивность обслуживания, где vср–время обслуживания заявки. Граф состояний имеет вид: λ λ S0 S1  S2  1.4 Потоки событий. Их параметры и свойства Событие – это любое изменение состояний системы или переход системы из одного состояния в другое. 11 Поток событий – это последовательность событий, следующих одно за другим в общем случае в случайные моменты времени. t0 t1 t2 t3 t τ3 τ1 τ2 Интервал между событиями Т> 0 – непрерывная случайная величин, Ti– еѐ конкретные реализации. Среднее значение интервала (МО): n ̅=  i может обозначаться как средний период Тср= ̅. n Интенсивность потока событий (число событий в ед. времени) есть величина обратная ̅, то есть λ[1/с]= 1/ ̅. В общем случае λ как ̅ могут меняться во времениλ(t) =1/ ̅(t). В качестве базовой характеристики произвольного случайного процесса может быть использована P(m,τ,t) – вероятность появления ровно m событий на интервале длиной τ, начинающегося в момент времени t. Потоки событий могут быть конечными и бесконечными. Свойства потоков событий: 1. ординарность – отсутствие одновременности появления нескольких событий; 2. стационарность – независимости от времени, характеристик потока; 3. отсутствие последействия–вероятность появления события в момент времени t* не зависит от факта (или его отсутствия) появления события в предшествующие моменты времени t 1 для любого t. τ→ 0 Потоксобытий называется стационарным, если его вероятностные характеристики не изменяются во времени. Для таких событий вероятность появления ровно mсобытий за интервал времени  является постоянной величиной, не зависящей от места расположения интервала  на оси времени, а зависит только от величины  . i 1 P(m, )  P(m, , t ) t3  tp  t В частности, для стационарных потоков событий λ(t) = λ и ̅(t) = ̅. Поток является потоком без последействия, если для любых непересекающихся временных интервалов чис ло событий, попадающих на один из 12 них, не зависит от числа событий попавших на другие.Это свойство - отсутствие влияния прошлого на будущее, то есть отсутствие памятив потоке или в развитии событий. Случайная величина T(интервал между событиями) полностью характеризуется функцией плотности распределения FT(τ) = P(T<τ), где τ – конкретное детерминированное значения интервала между двумя событиями. Физический смысл события T<τ, через вероятность которого определяется FT(τ ), есть то, что на интервале τ произошло хотя бы одно событие, т.е. закончился хотя бы 1 случайный интервал T. Физический смысл обратного события T ≥ τ , есть то, что на интервале τ не произошло ни одного события (нет окончания интервала в пределах τ). Вероятности обратных событий связаны как P(T ≥ τ) = 1- P(T<τ). FT(0) = 0,FT(∞) = 1 – накопленная вероятность. P(0,τ,t) = P(T ≥ τ) и соответственно P(T<τ) = 1- P(0,τ,t). dF Функция плотность распределения связана с F(τ) как: f    ; d Для ординарных потоков событий вероятность появления событий на интервале τраспределена по закону Пуассона: P(m,τ,t) =    t    Р(m, )  m! m e  t  , где  t  - интенсивность событий. Для стационарных потоков λ(t) = λ и P(m,τ,t) =   m  P(m, )  e m! . Пример для τ =1с при λ =1[1/c] 1) m=0 - не произойдет ни 1-го события, (1*1)0 1 1 e  e  0,37 , т.е. 37 %. Более одного - 0.63 0! (1*1)1 1 e  0,37 . 2) m=1 -ровно 1 событие: P(1,1)  1! 3) m>1- более одного события, P( 2,1)  1  0.37  0.37  0.26 . P(0,1)  1.5 Простейший поток событий В теории СМО важнейшую роль играет поток событий, который обладает всеми тремя основными свойствами, его называют простейшим потоком событий (ППС), т.е. ПС который ординарен, стационарен и обладает отсутствием последействия. Простейший поток событий примечателен наличием следующих свойств: 1. сумма любого числа ППС является ППС; 2. при суммировании большого количества (n=4÷5) любых потоков событий, в результате получаем поток, который по свойствам стремится к ППС; 13 3. при случайном прореживании ППС получается ППС; 4. интервал времени между любым моментом времени t и моментом наступления ближайшего события имеет экспоненциальное распределение с тем же математическим ожиданием (МО) М ( )   , что и интервал времени между двумя соседними событиями. Получим функцию распределения для ППС: t T F ( )  P(T   ) Если T   , то на интервале  Если T   , то на интервале  наблюдается хотя бы одно событие, т.е. заканчивается хотя бы 1 период T. Тогда вероятность противоположного события равна P(T   )  1  P(T   ) , не произошло ни одного события. ( ) ) Используя формулу Пуассона ( при m = 0, по- лучим ( ) ( ) ( ) ( ) . F(t)= Найдем функцию dF f ( )    * e  d плотности распределения вероятности: Положение МО  на оси τсвязано с пятым свойством ППС: 5. ППС (несмотря на то, что он простейший) представляет для ВС, обслуживающих этот поток, наиболее сложный режим работы. 14 Вычислим вероятность появления событий, интервал которых меньше МО  :     M ( )    f ( )d   e   d  1    1  ., 1 P(     )  F (  )  F ( )  F ( )  F (0)  F ( )  1  e1  0.63 , что больше 0,5.  для ППС называют экспоненциальным Часто закон распределения  законом распределения. Замечание (ко второму свойству): Большинство реальных потоков событий являются простейшими или очень близкими к ним по свойствам. Вычислим дисперсию интервала вокруг МО.   1 1 2 D( )   (   ) f ( )d   (   )*  * e  d  2 ;    ( )  D( )  1       1  т.е. МО равно СКО. Очень часто в теории СМО используется относительно приведенный коэффициент вариации (разброса вокруг МО)случайной величины(СВ):   στ . τ Для большинства не ППС   1 ,   0 1 .   1 - для ППС;   0 - для детерминированного ПС. 1.6 Потоки Эрланга Это потоки, у которых   1 , и это значение может регулироваться. Потоки Эрланга, вобщем случае, не являются потоками без отсутствия последействия. Для этих потоков случайные интервалы времени  i и  k между соответствующими парами событий не являются независимыми случайными величинами. Потоки Эрланга могут быть получены из ППС путем прореживания событий, но не случайного события, а закономерного. Поток Эрланга К-го порядка получается из ППС путем вычеркивания подряд k-1событияподряд и оставлением k-го события. При k=1- не вычеркивается ничего, поэтому поток Эрлангапервого порядкеесть ППС. Т.е. чем больше k, тем меньше случайность в интервалах между событиями. При достаточно больших k интервалы практически постоянны. 15 k        1 ; k  1 k Приведем формулы для основных статистических характеристик:  k   M [O]    f ( )d  ;   D( )   (   ) 2 f ( )d   ( )  D  k  2  k  k 2 ; . С ростом порядка растет МО и дисперсия, но СКО растет медленнее МО, поэтому, чем больше k, тем меньше степень разброса  k  1   *  . m  k k При k   , коэффициент разброса   0 . При больших k период следования событий становится стабильным и практически не изменяется. Регулируя k=1,2,3…, можно регулировать степень случайности потока событий, от   1 до   0 . 1.7 Марковские процессы СП с дискретными состояниями S0,S1,…,Sk называется Марковским процессом(МП) или Марковской цепью, если вероятность того, что в мо- tn 1 процесс (система) будет находиться в состоянии S j , зависит только от его состояния Si в предыдущий момент времени t n и не зависит от способа (траектории), каким процесс попал в это Si состояние. мент времени Формальный вид определения: 16 P ( X (tn 1 )  S j X (t0 )  Sl , X (t1 )  S m ,..., X (tn )  Si )   P ( X (tn 1 )  S j X (tn )  Si ) Таким образом, МП являются процессами без памяти (процессы с отсутствием последействия), в них следующее состояние S j зависит только от текущего состояния и не зависит от предистории попадания в это состояние. Для многих ВС можно использовать МП. Далее рассмотрим 2 вида МП: 1. МП с дискретным временем; 2. МП с непрерывным временем. 1.7.1 Марковский процесс с дискретным временем МП с дискретным временем полностью определяется множеством возможных состояний процесса S={S0 ,S1 ,S2 ,...,Sk } и матрицей Р вероятностей переходов из состояния в состояние, P  {Pij }k 1,k 1 . Строки матрицы соответствуют состоянию, из которого выходит процесс, столбцы – состоянию, в которое процесс входит. Pij (t ) - вероятность перехода из состояния Si в S j в момент времени t . Существует более удобная (наглядная) форма представления МП – в виде графа. Вершины графа представляют собой состояния, вес дуги – вероятности перехода. Чаще всего в МП вероятности переходов известны, вероятности нахождения системы в i-ом состоянии необходимо найти; Pi ?, . k Очевидно, что Р0  Р1  Р2  ...  Рк  1  Р i 0 i  1. P02 P01 P00 S0 P0 P1 P12 S1 P10 S2 P21 P11 P22 P3 P20 Приведем основные формулы для свойств матрицы Р: Рассмотрим состояние S 2 : Р20  Р21  Р22  1 ,т.е. сумма элементов каждой строки матрицы равна 1 в любой момент времени, тогда ∑ ( ) , формула верна для каждой строки, . 17 Формула для нахождения вероятности попадания в какое-то j-ое состояние восполняется формулой полной вероятности: ( ) ∑ ( ) ( ) где событие А – попадание в j состояние. Тогда Pj (t  1)  k Р j 0 j k  P (t ) P (t ) i 0 i ij  1, (*) сумма в формуле собирается не по строке, а по столбцу матрицы. Для каждого j свое уравнение, . Мы получили систему уравнений, которая позволяет, зная с какой вероятностью система находилась в том или ином состоянии в начальный момент времени t=0 и, пользуясь формулой (*), шаг за шагом t=1,2,3… найти вероятность нахождения системы в любом состоянии в любой момент времени. Если в МП существует предельное распределение вероятности Р j (t ) при t j   , для всех , то такой МП называется статистически устойчивым или эргодическим. Для такого процесса lim Pj (t )  Pj , t  . В этом случае система уравнений (*) упрощается: k Pj   PP i ij , i 0 k Р j 0 j 1 (**) Система уравнений (**) справедлива для стационарного эргодического процесса. Рi - установившееся значение вероятности нахождения системы в iсостоянии. Если матрица вероятностей переходов Рможет быть разбита на подматрицы ABCD, то матрица называется приводимой. A B P  , C D Рассмотрим важный частный случай приводимых матриц: A 0 P  - для таких матриц состояния, входящие в А и в D не сооб 0 D щаются между собой; 0 P C B  - таким матрицам соответствует периодическая смена состоя0 ний, входящих вС и В. Остаться в каком-то состоянии – невозможное событие; 18 A B P  - стартовав из состояния группы А, система через некоторое  0 D время попадает в состояние группы D, из которого она вернуться уже не сможет. Невозвратное состояние – для которого процесс после некоторого числа переходов покидает его и больше не возвращается. Поглощающее состояние – для которого процесс, достигнув его, не возвращается, не покидает его. Представляет интерес определение среднего времени нахождения системы в том или ином состоянии.Будем считать, что квант времени постоянен и равен q для любого i: ti 1  ti  q . Среднее время нахождения системы в состоянии j определяется: j  q 1  Pjj , где 1  Pjj - это вероятность ухода системы из состояния,  jr - среднее время пребывания системы вне j-го состояния, которое определяется по следующей формуле: ( ̅ ) ( , а средний период ) j  jr Sj вне Sj ( . Пример: Рассмотрим вычислительную систему, которая может находиться в двух состояниях:S0- ожидание, S1-состояние счета. P01  0.2 P00  0.8 0.8 0.2 P ,  0.1 0.9 S0 P0  ? P  0.1 10 S1 P11  0.9 P1  ? Р00+Р01=1, Р10+Р11=1. Составим систему уравнений: n Pj   Pij Pi , j  0, n i 0 j=0, 1(берем коэффициенты по столбцу): 19  P0  P0  P00  P1  P01   P1  P0  P01  P1  P11 ; P  P  1  0 1 1  P1  0.8  (1  P1 )  0.1 P1 1  0.8  P1  0.8  P1  0.1 P1 ,  P 0  0.8  P0  0.1 P1  0.2  0.3  P1 ,  P  1  P 1  0 2 P1   0.6 , 3 1 P0  . 3 Вероятность нахождения счета в два раза превышает состояние ожидания. Зададим q=1 (c): 0  q 1   5(сек ), 1  P00 0.2  0r  q  1  2  P00  P0 2  0.8  0.33 0.87  1   13(сек ), P0  (1  P00 ) 0.33  0.2 0.066 q 1   10(сек ), 1  P11 1  0.9  1r  q  2  P11  P1 2  0.9  0.66 0.44    6.66(сек ). P1  (1  P11 ) 0.66  0.1 0.066 1.7.2 Марковские процессы с непрерывным временем В этих процессах переход системы из состояния в состояние может произойти в любой заранее непредсказуемый момент времени. Таким образом, получаем, что случайная величина Х(t)=S(t) в момент времени t изменяется скачком в момент времени t, но сам момент времени t случаен. Нельзя задаваться вероятностями перехода Рij(t), так как в любое мгновение t эта вероятность равна нулю Рij(t)=0. Но если взять некоторый интервал времени t и рассмотреть вероятность перехода из состояния в состояние в рамках этого интервала, то она будет отличаться от нуля pij(t1 < t < t2) ≥ 0 . Обозначим через pij(t +  t)  0 - вероятность перехода из i-го в j-е состояние в момент времени t за интервал  t, то есть ( ) ) ) ( ( | ( ) В таком случае при обозначение ( ) будет соответствовать вероятости перехода в течении нулевого промежутка времени или, иначе говоря, вероятность того, что система одновременно (в момент t) находится и в состоянии и в состоянии . Следовательно 20 ( ) ( ( ) | ( ) ) { (1) Используем вероятность перехода, дадим определение плотности вероятности перехода системы из i-го в j-е состояние или интенсивность перехода из i-го в j-е состояние: ( ( ) ) ( ) ( ). (2) ( ) моЭто определение противоречит формуле (1), так как в соответствии с ней жет принимать только два значения 0 или 1, а значит ( ) может равняться толко -1, 0 и 1. Поэтому в числителе предела имеется в виду изменеие вероятности за интервал . Может быть лучше ( ( ) ) ( ). Но тогда не получится формула (3). Используя выражение (1), получаем: ( ) { ( ) ( ) (3) Тот факт, что интенсивность перехода может быть величиной как положительной, так и отрицательной, требует объяснения. Поскольку интенсивность можно рассматривать как производную от вероятности перехода, еѐ знак показывает направление изменения вероятности этого перехода с ростом времени. Вероятность перехода в иное состояние, естественно, растѐт. Вероятность же остаться в том жe состоянии со временем падает. Из выражения (3) можно прийти к следующим приближѐнному равенству для малых ( ) ( ) { (4) ( ) В общем случае интенсивность зависит от времени t. Если ( ), не зависит от момента времени t, с которого начался промежуток времени , то ( ) есть , то процесс называется однородным (аналогичное определение было и для процесса с дискретным временем). Далее мы будем рассматривать именно однородные процессы. В отличие от марковских процессов с дискретным временем марковские процессы с непрерывным временем полностью определяются матрицей интенсивности переходов Λ: S0  00 S1  10  ...  ...  Sn n 0 S0 01 ... 0 n  11 ... 1n  ... n1 S1 ...   ... nn  ... S n ... (аналог матрицы переходных вероятностей). Рассмотрим еѐ свойства. 1) Как мы уже показали, диагональные элементы этой матрицы неположительны. остальные элементы - неотрицательны: { (5) 2) Сумма элементов каждой строки матрицы Λ равняется 0, то есть 21 ̅̅̅̅̅. ∑ (6) Докажем это свойство. Действительно, строка i в матрице интенсивности отвечает за переходы из состояния Si; во все возможные состояния, включая и Si. Сумма вероятностей таких переходов за некоторый промежуток времени равна 1: ̅̅̅̅̅ или выделяя диагональный элемент матрицы ∑ ( ) = 1, ∑ ( ) ( ) P: . Переходя от вероятностей к интенсивноетям всоответствии с (4), получаем: ∑ , или ∑ Разделив на , получим (6). Учитывая свойство 1), диагональные элементы матрицы Λ со знаком минус равны сумме всех остальных элеметов для каждой строки. n   (t )  0, j 0 ij n  j 0 j i ij i  0, n ,  ii , i  0, n. (7) Получение систем уравнений Колмогорова Система уравнений Колмогорова — это система дифференциальных уравнений, описывающих динамику поведения вероятностей всех состояний для марковского процесса с непрерывным временем. Пусть Pi(t) - вероятности того, что в момент времени t система будет находиться в состоянии Si. Тогда вероятность того, что в момент t + t система окажется в состоянии Sj следует определять по формуле полной вероятности n P( A)   P( H i )  P( A ) , где суть события A – попадание в состояние Sj, гипотеH i 0 i за Hi – нахождение в предыдущий момент времени в состоянии Sj, условная вероятность ( ⁄ ) – вероятность перехода из i в j состояние. S0 Sj-1 ... Sj Sj+1 Sn Переходя в формуле полной вероятности к обознаяениям в НМП, с учѐтом того, что попадание Sj может ироизойти либо в результате перехода из других состояний, либо в результате того, что система, находясь в состоянии Sj, в этом состоянии и осталась получим 22 ) ∑ ( ) ( ); j ̅̅̅̅̅ ( ) ( ) при и ( ) ( ) при , выделив из суммы одно слагаемое, когда получим: ( Учитывая, что ( Перенеся получим ) ∑ ( ) ( ) ∑ ( ) ( )( ( ) ) ( ) влево и разделив левую и правую часть равенства на ( ) Переходя к пределу при ( ) ∑ ( ) ( ) , ( ) ( ) , получим  dPj (t ) n   ij (t )  pi (t ), j  0, n   dt i 0 - система дифференциальных уравнений  P (t )  P (t )  ...  P (t )  1 1 n  0 Колмогорова (8) Обратим внимание на то, что правые части уравнений системы Колмогорова являются произведениями вектора распределения вероятностей на соответствующие столбцы матрицы интенсивностей. Это позволяет записать систему Колмогорова в векторно-матричной форме: В общем случае, это система с переменными коэффициентами. Решение системы уравнений заключается в определении вероятности нахождения системы в j-м состоянии, как функции от времени. Для того, что бы найти частное решение, необходимо знать начальное условие: P0 (0)  P0 , P1 (0)  P1 , .......... Pn (0)  Pn .  P  1. i Предельный стационарный режим Часто бывает необходимым найти не поведение вероятностей во времени, а только установившееся значение распределений вероятностей по состояниям. Если установившееся значение есть, то система эргодическая. В этом случае есть предельное распределение вероятностей при большом времени: ̅̅̅̅̅ ( ) 23 ̅̅̅̅̅. или (В Все производные становятся равными нулю: ( ) , матричном виде) ̅ 0, где ̅ = (p0, р1, ..., рn). То есть в этом случае система из дифференциальных уравнений превращается в систему линейных алгебраических уравнений (СЛАУ):  n  ij Pi  0, j  0, n  i 0  n  P 1 i  i 0 (9) Замечание по составлению системы уравнений: каждое уравнение составляется по соответствующему j-му столбцу матрицы Λ. Задача 1. Вычислительная система без резервирования состоит из одной ЭВМ. Среднее время безотказной работы Tнаработки на отказ = 1000 часов, среднее время ремонта отказавшей машины ̅ часов. Найти вероятность нахождения системы в неисправном состоянии. отк  рем  ОА 1 v рем Где соответствующие интенсивности определяются как 1 1 отк отк   3  103[ ]; Т пар.на.отк 10 час 1 соб  101[ ]. 10 час Граф состояний системы будет иметь вид: S0 – ни одного отказа (система исправна); S1 –один отказ (система не исправна или находится в состоянии ремонта).  рем    S0 S1   Приведем матрицу интенсивности переходов системы из одного состояния в другое:      ,     По столбцам матрицы Λ составляем систему уравнений (9) для po и p1 в установившемся режиме. j  0 :  P0   P1  0 j  1:  P0   P1  0 P0  P1  1 24 P0 - вероятность нахождения в исправном состоянии S0; P1 - вероятность нахождения в неисправном состоянии S1. Выразим из 1-го уравнения P0 : P0  уравнение:  P и подставим в последнее  1 1     , P0  1  P1  . P1  P1  1  P1      1  ; P0 ≈ 1 - 0,01 = 0,99 Задача 2. Изменим условие задачи 1. Пусть вычислительная система (ВС) имеет двукратное резервирование, т.е. ВС состоит из двух ЭВМ. Обе ЭВМ равноценны. Система работает, пока работает хотя бы одна из двух ЭВМ. Интенсивности событий отказа и ремонта те же: 1   ЭВМ ;   v рем Числовые данные также остаются прежними. То есть интенсивность отказов и ремонта каждой ЭВМ соответственно:   103 ,   101 . При отказе обеих машин, они ремонтируются параллельно двумя бригадами. ЭВМ ЭВМ ВС vРЕМ vРЕМ ВС  F (i)  (n  i)ЭВМ , где i – число отказавших машин. Найти вероятность того, все обе ЭВМ находятся в рабочем состоянии. Найти вероятность нахождения ВС неисправном состоянии. Найти среднее число неработающий ЭВМ ̅. Сколько из них находится в состоянии ремон̅ , среднюю длину очереди ̅ та R (среднее число занятых бригад ̅ ) ЭВМ ожидающих ремонта, коэффициент загрузки каждой бригады , среднее время ожидания ЭВМ в очереди на ремонт ̅, среднее время пребывания ЭВМ в неисправном состоянии ̅. Система может находиться в трѐх состояниях. Состояния имеют следующий физический смысл: S0 – ни одного отказа (обе ЭВМ работают); S1 – 1 отказ (отказ какой-то из двух ЭВМ); 25 S2 – 2 отказа (отказ системы); Состояние S2 – состояние отказа всей ВС с вероятностью P2 = Pотк . Составим граф перехода системы из состояния в состояние. 2  S0 S1  S2 2 2 0   2    (   )   , Матрица  будет иметь вид:  0 2 2   По столбцам матрицы составляем систему уравнений (9). 2 P0   P1 0 2 P0  (   )  2 P2  0  P1  2 P2  0 P0  P1  P2  1 Используя обозначение относительной интенсивности , из первого уравнения выразим P1 через P0, из третьего P2 через P1 и далее через P0. Р1  2 Р0 ; Р2   2 Р0 ; Подставим эти выражения в последнее уравнение. Р0  2 Р0   2 Р0  1. Выразим из последнего уравнения P0 : . Этот результат сразу можно было получить по формулам схемы гибели и размножения не составляя матрицу Λ и не решая СЛАУ. Там же p1 = 2ρ = 0,0196 P2 = Следовательно РоткВС  P2  2  0,98*104. 1  2  2 2 Это почти в 100 раз меньше, чем в системе без резервирования (задача 1). Среднее число неработающих ЭВМ ̅ ∑ . Найдем, сколько из них находится в состоянии ремонта (среднее число занятых бригад) ̅ ∑ ( ) , где n – максимальное значение номера состояния, равное числу ЭВМ, то есть двум, а Z – число ремонтных бригад, по условию задачи также равное двум. Поэтому ̅ . ̅ Средняя длина очереди ЭВМ ожидающих ремонта равна ̅ ̅ 26 Коэффициент загрузки каждой бригады Среднее время ожидания ЭВМ в очереди на ремонт ̅ находиться из формулы Литтла ̅ ̅, где – интенсивность обслдуживания отказавших ЭВМ, равная Таким образом, ̅ ̅ Среднее значение пребывания ЭВМ в неисправном состоянии ̅ ̅ ̅ Вывод. Для ремонта ЭВМ нецелесообразно иметь две бригады, так как коэффициент загрузки каждой бригады очень мал - меньше 1 %. .Задача 3. Станция технического обслуживания (СТО) автомашин может одновременно проводить техническое обслуживание (ТО) не более n= 2 автомашин. Третья автомашина, прибывшая на СТО, может занять специальную площадку для ожидания ТО. Если на СТО уже три машины (две на ТО и одна в очереди), то следующая автомашина, прибывшая на СТО, покинет еѐ без ТО. Входящий поток автомашин — простейший поток событий (ППС) с интенсивностью , время ТО одной автомашины — случайная величина, распределѐнная по экспоненциальному закону со средним значением маш ̅ . Соответственно интенсивность ТО . ̅ час Найти вероятность отказа в обслуживании , вероятность обслуживания (прохождения ТО) , интенсивность потока автомашин прошедших ТО , интенсивность потока автомашин не прошедших ТО , среднюю длину очереди ,̅ коэффициент загрузки СТО R, среднее число занятых каналов обслуживания СТО ̅ , коэффициент загрузки каждого канала обслуживания СТО , среднее число автомашин на СТО ̅, среднее время ожидания в очереди ̅, среднее время пребывания в СТО ̅. Для ответа на все эти вопросы необходимо в первую очередь определить̅̅̅̅̅ и их количеством n. И ся с физическим смыслом состояний СТО Si, далее найти вероятности pi нахождения СТО в каждом состоянии Si. Так как случайные величины: интервал прихода заявок на обслуживание и интервал обслуживания распределены по экспоненциальному закону, то процессы прихода и обслуживания марковские и для решения задачи можно пользоваться математическим аппаратом марковских процессов с непрерывным временем. Составим множество состояний СТО Si – на станции находится ровно i автомашин. S0 – на СТО нет автомашин (простой); S1 – на СТО 1 автомашина проходит ТО; S2 – на СТО 2 автомашины проходят ТО; S3 – на СТО 2 автомашины проходят ТО и одна стоит в очереди. Рассмотрим граф перехода системы из состояния в состояние. 27 Так как процесс поступления заявок на обслуживания марковский (без памяти), то интенсивность перехода из состояния Si в состояние Si+1 не зависит от состояния и равна λ. Интенсивность обслуживания растет, пока не будут заняты все (оба) канала обслуживания. Поэтому в состоянии S1 (работает один канал обслуживания) интенсивность обслуживания равна μ, а в состояниях S2 и S3 (работают оба канала) интенсивность обслуживания равна 2μ. В соответствии со свойством матрицы интенсивностей переходов (сумма элементов каждой строки матрицы равна нулю) петли имеют отрицательную интенсивность, равную сумме интенсивностей всех исходящих из данного состояния дуг. Составим матрицу интенсивностей переходов из состояния в состояние. ( ( ) ( ) ) По столбцам матрицы составляем систему уравнений (9). -λp0 + μp1 = 0; λp0 – (λ + μ)p1 + 2μp2 = 0; λp1 – (λ + 2μ)p2 + 2μp3 = 0; λp2 – 2μp3 = 0; p0 + p1 + p2 + p3 = 1. Используя обозначение , из первого уравнения выразим P1 через P0, из второго P2 через P1 и далее через P0, из четвертого P3 через P1 и далее через P0: ; ; Подставим эти выражения в последнее уравнение. . Выразим из последнего уравнения P0 : ( ) Соответственно 28 Вероятность отказа в обслуживании , то есть 19 % пришедших на ТО автомашин не будет обслужено. Соответственно вероятность обслуживания (прохождения ТО) . Интенсивность потока автомашин прошедших ТО , интенсивность потока автомашин не прошедших ТО . Среднее число автомашин на СТО ̅ ∑ ̅ . Из них находится в состоянии ТО, остальные ̅ ̅ находятся в очереди. Коэффициент загрузки каждого канала обслуживания СТО ожидания в очереди ̅ ̅ ̅ ̅ ̅ ̅ . Среднее время . Среднее время пребывания в СТО . Вопрос. Почему когда в среднем загружено R = 1,215 каналов обслуживания, из 2-х имеющихся на СТО (т.е. 2 - 1,215 = 0,785 каналов простаивают), а каждый канал загружен на 60,75% и простаивают почти 40% времени, при этом 19% автомашин остаются не обслуженными? 1.8 Модели типовых СМО 1.8.1 Классификация (обозначение) типовых СМО (символика Кендалла) Для компактного описания систем массового обслуживания часто используются обозначения, предложенные Д. Кендаллом, в виде: СМО A/B/N[/L], где A и В – задают законы распределений соответственно интервалов времени между моментами поступления заявок в систему и длительности обслуживания заявок в приборе (обслуживающем аппарате); N – число обслуживающих приборов в СМО (N=1, 2, 3, ...); L – не обязательный параметр, равный числу мест в очереди, которое может принимать значения 0, 1, 2, … (отсутствие L означает, что накопитель имеет неограниченную ѐмкость). Для задания законов распределений А и В используются следующие обозначения: G (General) – произвольное распределение общего вида; М (Markovian) – экспоненциальное (показательное) распределение; D (Deterministik) – детерминированное распределение; U (Uniform) – равномерное распределение; Еk (Erlangian) – распределение Эрланга k-го порядка; hk (hipoexponential) – гипоэкспоненциальное распределение k-го порядка (с k последовательными разными экспоненциальными фазами); Нr (Hiperexponential) – гиперэкпоненциальное распределение порядка r (с r параллельными экспоненциальными фазами); g (gamma) – гамма-распределение; 29 P (Pareto) – распределение Парето и т.д. Пример 1. СМО M/G/2 – двухканальное СМО с экспоненциальным законом распределения входного потока заявок (на входе СМО простейший поток событий - ППС), каждый канал (обслуживающий аппарат имеет произвольный закон распределения длительности обслуживания заявок), число мест в очереди потенциально бесконечно. Пример 2. СМО M/M/1/24 – одноканальное СМО с экспоненциальным законом распределения входного потока заявок, обслуживающий аппарат имеет также экспоненциальный закон распределения длительности обслуживания заявок, число мест в очереди равно 24. 1.8.2 Порядок (алгоритм) формирования аналитической модели СМО 1. Определить физический смысл состояний системы Si. Обычно физический смысл это, то, что номер состояния i совпадает с числом заявок, находящихся внутри СМО: S0 – простой системы (ноль заявок в СМО);S1 – в СМО одна заявка;…Si– в CМО i-заявок (в очередях и ОА в сумме); … 2. Представить систему в виде графа переходов между состояниями и определить веса λij всех дуг графа. 3. Составить матрицу  - матрицу интенсивности перехода из состояния Si в ∑ состояние Sj. Диагональные элементы . 4. Составить систему уравнений по столбцам матрицы  . 5. Добавить к ней уравнения ∑ исключив из системы любое одно из уравнений. 6. Решить систему относительно pi. 7. Найти коэффициент мультипрограммирования (среднее число заявок в СМО как математическое ожидание дискретной случайной величины (ДСВ) ∑ i: ̅ 8. Найти остальные характеристик СМО с учетом еѐ структуры: ̅ ̅̅̅ ̅ , и т.д. Замечание. Порядок (алгоритм) формирования аналитической модели СМО упрощается в случае возможности применения схемы гибели и размножения (см. следующий параграф). Пункты с 3 по 6 не выполняются, вместо них используются формулы схемы гибели и размножения. 1.8.3 Схема гибели и размножения В частом случае, когда граф переходов между состояниями имеет вид цепочки (цепи Маркова), то есть когда имеются переходы только между состоянием Si и Si+1 и Si+1 и Si, для всех i от 0 до n-1, получено общее решение системы алгебраических уравнений (9). 30 Для данного случая граф переходов с произвольными интенсивностями переходов из состояния в состояние может быть представлен в следующем виде: 0 1 S0 S1 Sn-1 S2 3 2 1 n 1 n  2 2 n 1 Sn n Данная схема называется схемой гибели и размножения. Данное название связано с тем, что с еѐ помощью можно моделировать процесс развития некоторой популяции биологических объектов, где и – соответственно интенсивность рождаемости и смертности, когда размер популяции равен i, то есть когда она находится в состоянии Si. Основные формулы схемы гибели и размножения для определения вероятностей нахождения системы во всех состояниях в установившемся режиме: ( …+ ) ; ̅̅̅̅̅. В общем виде: ∑ ( ∏ ∏ ) ; ̅̅̅̅̅. Как упрощается порядок (алгоритм) формирования аналитической модели СМО в случае возможности применения схемы гибели и размножения. Пункты с 3 по 6 не выполняются, вместо них используются формулы схемы гибели и размножения (Г-Р). 1.8.4 Модели СМО с отказами в обслуживании заявок (Многоканальная СМО без очереди. СМО M/M/n/0) Рассмотрим очень важный случай, когда очередь заявок отсутствует, а для обслуживания заявок используется n-канальная СМО. Структурная схема имеет вид: 31 n-канальная СМО Ист. заяв.  ОА1 ОА2 …… v обс v   обс  отк v ОАn отк Каждая заявка может быть обслужена любым свободным ОА, среднее время обслуживания  одинаково. Если все каналы заняты, то пришедшая заявка тут же покидает СМО и формирует поток заявок, которому отказано в обслуживании. Будем считать, что все процессы в этой системе Марковские, т.е.: 1) Входной поток заявок с интенсивностью  является простейшим, интервал между 2 событиями случайный и распределен по экспоненциальному закону; 2) Время обслуживания заявок является случайной величиной  , само обслуживание является марковским процессом, случайная величина  распределена по экспоненциальному закону. Так как оба процесса марковские, то и вся система в целом Марковская, т.е. можно пользоваться результатами предыдущей лекции. Примером подобных систем может служить АТС, n – число пар абонентов, которых можно одновременно соединить или коммутатор мобильной связи. В системе известны  , ,   1  . Найти вероятности обслуживания заявки и отказов в обслуживании заявок Робс , Ротк ; обс , отк  ?, k  ?, R1  ? k - среднее число загруженных каналов, 0  k  n ; R 1 - коэффициент занятости 1-го канала. Очевидно, что обс   Робс ; отк   Ротк ; Робс  Ротк  1. Тогда среднее число загруженных каналов: k  обс  (1  Ротк )  ;   k . n Для составления матрицы  - матрицы интенсивности перехода из состояния в состояние, нужно определиться со всеми состояниями системы и Коэффициент занятости 1-го канала: R1  32 дать им физический смысл, после чего нужно представить систему в виде графа состояний и переходов между ними. Si , , физический смысл i – число заявок, находящихся внутри СМО. S0–простой (ноль заявок в СМО); S1–в СМО одна заявка в каком-то ОАi; S2–в СМО две заявки в любых двух ОАi; ……… Sn– CМО полностью загружена, в ней n-заявок. Составляем граф переходов: интенсивность захвата каждого свободного автомата одна и та же и равна входной интенсивности. Интенсивность обслуживания увеличивается, вероятность отказа в обслуживании совпадает с вероятностью нахождения системы в Sn состоянии, Pотк  Pn .  P0 S0   P1  P2 S1 Pn-1 Sn-1 S2 3 2  (   )  (n  1)  Pn Sn n  n (  2  ) Нет петли в Sn-1 с весом –(λ + (n-1)μ) Очевидно, что . Применяем формулы Г-Р: ( | ) …+ | ∑ ; ∑ Пример 1: Специализированная ЭВМ пункта ПВО имеет 3 независимых канала наведения ракет на цели, каждый канал может наводить одну ракету. Среднее время наведения   3 минуты (по сути, это время обслуживания), распределенное по экспоненциальному закону. Поток целей так же простейший с интенсивностью   1 цель . мин Данному примеру соответствует СМО M/M/3/0 с отказами в обслуживании, так как цель, появившаяся в момент занятости всех каналов, остается не атакованной, т.е. не обслуженной. Нужно найти все основные характеристики. Модель СМО имеет следующий вид: 33 Ист. заяв.  ОА1 ОА2 …… v v   обс  отк v ОА ОАn3  3 Pотк  2 1    Pобс  1  Pотк 3! 3   обс отк 1   ;    3.   3 1 27 6  0,35 (т.е.35% целей не обслуживается). 1  3  4,5  4,5 2! 3!  0, 65 , обс   Pобс  0, 65 , отк   Pотк  0,35 ,  0,65 k  обс   1,95 , т.е. в среднем занято два канала из трех.  0,33 k 1.95 R   0.66 , т.е. каждый канал занят на 66%. n 3 Из-за наличия и сложения двух случайных процессов (прихода и обслуживания целей) при наличии в среднем одного свободного канала 35% целей не обслуживается.Это происходит когда цели приходят часто, а обслуживание их длится долго. Простой получается, когда цели идут редко, а каналы обслуживают быстро. Пример 2. Две ЛВС (ЛВС1 и ЛВС2) взаимодействуют друг с другом через спутник связи (рисунок). Обмен производится информационными пакетами. Среднее время передачи пакета ̅ . Время передачи случайное и распределено по экспоненциальному закону. Спутник имеет три независимых полудуплексных каналов передачи пакетов, т.е. n = 3. Буферизация передаваемых пакетов отсутствует. Интенсивность генерации пакетов для передачи каждой ЛВС . Потоки пакетов простейшие и случайный интервал времени между передачей двух пакетов распределен по экспоненциальному закону. Так как законы распределения случайных интервалов экспоненциальные, то процессы прихода пакетов (заявок на обслуживание) и их обслуживания марковские. Очередь передаваемых пакетов отсутствует. Имеем СМО M/M/3/0. Найти все еѐ основные характеристики. 34 Решение. Концептуальная модель СМО такая же, как в предыдущем примере. Так как ЛВС1 и ЛВС2 работают на передачу параллельно, то интенсивность общего потока пакетов через спутник . ̅ . Дальнейшее решение полностью совпадает с примером 1. Пример 3. АЗС имеет три колонки, т.е. n =3. По направлению движения автомашин недалеко от данной АЗС есть ещѐ одна, поэтому водители, зная это, застав все три колонки занятыми не становятся в очередь, а проезжают дальше. Процесс прибытия автомашин на заправку марковский с интенсивностью . Процесс заправки также марковский со средним временем заправки 6 мин. Имеем СМО M/M/3/0. Найти все еѐ основные характеристики. Решение. Относительная интенсивность событий ̅ . Поэтому дальнейшее решение полностью совпадает с примером 1. Самостоятельно решить Пример 4. Пункт мобильной связи может одновременно связать пар абонентов. Интенсивность вызовов (звонков) . Среднее время разговора (связи) двух абонентов ̅ . Все процессы марковские. Имеем СМО M/M/10000/0. Найти самостоятельно все еѐ основные характеристики. Замечание. Значение i! При i > 20 можно вычислять по формуле Стирлинга √ ( ). 1.8.5 Одноканальная система массового обслуживания с очередью (с ожиданием). СМО M/M/1 В этих системах заявка, застав все каналы в СМО занятыми, не покидает систему, а становится в очередь, где какое-то время будет находиться в состоянии ожидания обслуживания. Это время называется временем ожидания в очереди w . Будем считать, что число мест в очереди бесконечно или с большим запасом достаточного, что бы в ней не было переполнения, т.е. отказов в обслуживании нет. Далее рассмотрим одноканальную СМО. СМО M/M/1 Обычно заданными величинами являются  ,  или  , v . v - среднее время обслуживания; интенсивность обслуживания Необходимо найти: ̅ ; 35  - коэффициент загрузки ОА:    v (по формуле Литтла). Условие  <1 является условием стационарного режима работы системы. Если  >1, то СМО не справляется с входным потоком заявок, и длина очереди перед ОА не будет иметь среднего установившегося значения. В этом случае она будет постоянно увеличиваться во времени по мере работы СМО. При этом на выходе СМО не будет потока с интенсивностью λ, а лишь с интенсивностью . ̅ w - среднее время ожидания в очереди; u - среднее время пребывания заявки в СМО;  -средняя длина очереди; m - коэффициент мультипрограммирования СМО или среднее число заявок находящихся внутри СМО; Определим очевидные соотношения параметров СМО: ̅ ̅ ̅; m  ; m  u ;   . Построим модель данной СМО в виде графа состояний Si, i–число заявок, находящихся в СМО. S0- простой; S1- одна заявка в ОА; S2- две заявки в СМО: одна в ОА, другая в очереди; S3 - три заявки в СМО: одна в ОА, две в очереди; и т.д.    S0 S1  S2 S3      Sk   (   ) Начиная с состояния S1 вес петель на графе везде –(λ + μ). Применяем формулу Г-Р: ( | …+ | ) . ∑ Следовательно P0  так как 1  1  ;   i i 0 36   i эта - сумма представляет собой геометрическую прогрессию i 0 S a0 , a0  1(i  0) . a0 = 1; q =ρ. 1 q S Прогрессия сходится, когда q<1 1 , тогда 1  1  1    p0  1   ; 1 1    1   - коэффициент простоя. Зная вероятность Р0, можно найти остальные вероятности по формуле: Pi   i (1   ) . (график pi от i – решетчатая убывающая функция, т.к. ρ < 1). Чем больше номер состояния, тем меньше вероятность попадания в это состояние. Найдем остальные характеристики: M i   m ; M  x   X   xi pi - классическая формула для нахождения МО;    i 0 i 0 i 0 m   iPi   i  i (1   )  (1   ) i  i .   i Вычислим отдельно i (*) , обозначим ее через S1: i 0 ∑ Обозначим   (i  1)*  i ∑( ) ∑( ) | ∑ | через S 2 и последовательно проинтегрируем и про- i 0 d ∫ f ( x)dx  f ( x) ): dx дифференцируем по  (по принципу ∫∑ ∑ ( ) ( ∑ |∑ ) ( | ) ( ) ( ) ( ) . И так S 1  1 1 m   1    . 1  1  (1   )2 1   Найдем среднее время пребывания заявки в системе u : m  v ̅ u   .= ;   (1   )  (1   ) Более эффектная формула ̅ ( Среднее время ожидания в очереди ) . w: 37 v v v v  v  v  w  u v  v   w . 1  1  1  1  2 Средняя длина очереди:  2v 2 2 l  m    w   . 1  1  1.8.5.1 Разделение очереди на конечную и бесконечную части В некоторых задачах анализа работы СМО M/M/1 потенциально бесконечную очередь О условно разделяют на две части: - конечную Ок длиной k, непосредственно примыкающую к ОА; - бесконечную Об, которая непосредственно примыкает к конечной слева и является еѐ продолжением. Таким образом, очередь О является конкатенацией очередей Об и Ок. Приведѐм два примера. 1. При работе вычислительной системы (ВС) очередь задач О к процессору (ОА) делится на Ок, которая организуется в оперативной памяти (ОП) и ограничена по длине, и Об, которая храниться во внешней памяти и потенциальна бесконечна. Но на еѐ обслуживание тратятся больше времени. 2. Железнодорожная сортировочную станция, на которую поступает случайный поток составов для переформирования. Обслуживание (переформирование) состава длится случайное время. В сортировочном парке станции имеются k путей, на которых могут ожидать обслуживания прибывающие составы. Если все внутренние пути сортировочной станции заняты, составы вынуждены ждать обслуживания на внешних путях или на других станциях. В этом случае придѐтся платить штраф. Найдѐм среднее число заявок в Об, то есть ̅ – среднее значение длины очереди бесконечной части очереди Об. Аналогично выводу формулы (*) для нахождения среднего числа заявок в СМО ̅ имеем ̅ ( и так как ̅ получим ̅ ̅ ) ̅ ∑ ( ) . Вероятность переполнения конечной очереди Ок, то есть вероятность появления заявок в Об по формуле геометрической вероятности равна ̅ ( ) ̅ ( ) = . Если в условиях задачи задано максимально допустимое значения вероятности переполнения конечной очереди Ок, то еѐ длина определяется как . 38 1.8.5.2 Графические иллюстрации основных зависимостей СМО M/M/1 Рассмотрим зависимость среднего времени пребывания заявки в системе и среднего времени ожидания в очереди от коэффициента загруженности: Если   0  w  0;   0  u  v , так как даже одной заявке нужно время на обслуживание. Зависимость среднего числа заявок, находящихся внутри СМО и средней длины очереди от коэффициента загруженности: На рис. стрелка для = ̅ ̅ должна быть вертикальная.   0  m  0, l  0. Если рассматривать эти графики с точки зрения качества обслуживания, мы должны иметь небольшое время ожидания в очереди и небольшую длину очереди. Так как все графики – близки к гиперболе, то весь диапазон  можно разделить на два участка. На участке I w растѐт медленнее, на участке II небольшое приращение  приводит к большим приращениям w . Если удалось снизить коэффициент загрузки до 70%, то дальнейшие вклады в увеличение производительности ОА не дадут значительных результатов. При большом коэффициенте загрузки примерно 90% нужно стремиться увеличить быстродействие системы, чтобы снизить коэффициент нагрузки. 39 1.8.5.3 Дисперсии основных характеристик СМО M/M/1 Кроме средних значений этих величин нужно знать зависимость степени разброса их вокруг МО, которое характеризуется дисперсией D или среднеквадратическим отклонением (СКО) √ . Найдем дисперсию для времени пребывания u: Du  D[u] . Случайная величина u распределяется по экспоненциальному закону, поэтому 1 1 v 1 1 1 ;  u  u     Du  2 (   )   1    (1   )  (1   )     v2 Du  . (1   )2  1 Dv  2 . 2 ; (1   )  Время ожидания в очереди w не распределяется по экспоненциальному закону, но ее дисперсию можно вычислить следующим образом: Дисперсия для случаых величин m и v: Dm  Dw  Du  Dv  v2  v 2 (2   ) 2  v  . (1   )2 (1   )2 Соответственно СКО  w  Dw  v  (2   ) . При высокой загрузке (1   )   1: v2 , т.е. дисперсия времени ожидания будет совпадать с дисперсией (1   )2 времени пребывания.  Базируясь на формуле l   (i  1)  i (1   ) , можно получить дисперсию i 1 длины очереди Dl . Или, используя формулу Литтла ̅ ̅ ( ( ) ) ( ( ̅ получим ) ) . Дисперсии Dm, Dl, Du, Dw очень сильно растут при 1, то есть при большой загрузке ОА степень случайности (непредсказуемости поведения) случайных параметров m, l, u, w очень значительная, особенно параметров очереди l и w. Пример СМО М/М/1. оп . Средняя трудоемкость одной заявки, с проходящей через систему   8*106 оп . На вход СМО поступают три ППС с 1 1 1 интенсивностями 1  2 ; 2  5 ; 3  3 ; с с с Быстродействие ОА: B  106 40 1 2 v  ОА О 3 Потенциально бесконечную очередь О условно разделяем на две части: - конечную Ок длиной k=2, непосредственно примыкающую к ОА; - бесконечную Об, которая непосредственно примыкает к конечной слева и является еѐ продолжением. Найти все основные характеристики СМО. 1 c Определим интенсивность заявок на входе:   1  2  3  10 ; Среднее время обслуживания: v   B  8*104  0.08c . 106 Если коэффициент загрузки  окажется равным или больше 1, решение на этом заканчивается, так как стационарный режим отсутствует.    * v  0.8  1 .  0.8  4. 1   1  0.8 В очереди в среднем находится заявок: l  m    4  0.8  3.2 . v 0.08   0.4c . Среднее время пребывания в системе u : u  1   0.2 Среднее время ожидания в очереди w : w  u  v  0.4  0.08  0.32c . Находим среднее число заявок в системе m : m   Средняя длина бесконечной части очереди Об: ̅ . Средняя длина конечной части очереди Ок: ̅ ( ) ( ) = 1,152. Вероятность переполнения Ок, то есть вероятность появления заявок в Об равна . Если в условиях задачи задано максимально допустимое значения вероятности переполнения конечной очереди Ок, например, , то еѐ длина определяется как = 21 или 31 соответ- ственно. Дисперсия для времени пребывания заявки в системе: Du  v2 0.0064   0.16c 2 ;  u  Du  0.4c . 2 (1   ) 0.04 41 Дисперсия случайной величины m: Dm   0.8   20 ;  m  Dm  4.5 2 (1   ) 0.04 заявок. Значение  m - это степень колебания вокруг среднего, равного 4, т.е. очень часто в системе бывает малое число заявок и реже бывает очень много заявок. Дисперсия времени ожидания в очереди:  v 2 (2   ) 0.8*0.0064*1.2 Dw    0.15c 2 ;  w  0.15  0.37 с. 2 (1   ) 0.04 Сравните с ̅. Дисперсия длины очереди: ( ) ( ) 15,36. . Сравните с .̅ √ ( ) ( ) Дисперсия времени обслуживания по сути дела известна из условий задачи, так как процесс обслуживания марковский и закон распределения случайной величины экспоненциальный. Поэтому ̅ . ̅ СКО с. 1.8.6 Многоканальная СМО с очередью. СМО М/М/n Структурная схема системы представлена на рисунке. Процессы поступления и обслуживания заявок марковские (интервалы прихода заявок и длительность их обслуживания случайные величины, распределѐнные по экспоненциальному закону). На вход СМО поступают заявки с интенсивностью λ. Очередь общая для всех ОА. Она потенциально бесконечна. Все ОА равноценны, среднее время обслуживания одно и тоже ̅ . Пришедшая из очереди заявка захватывает любой свободный ОА. Очередь образуется только тогда, когда все ОА заняты. Условие стационарного режима ρ = ̅ < n.  v ОА1 О  (при усл.   n ) v ОА2 …… v ОАn Составим граф переходов системы из состояния в состояние:  S0  S1  Sn-1 S2 2 --------------------   (n 1)  Sn n  Sn+1 n n Очередь пуста --------------- | очередь растѐт  42 Физический смысл i – число заявок, находящихся внутри СМО. S0 – постой (ноль заявок в СМО); S1 – в СМО одна заявка в каком-то ОАi; S2 – в СМО две заявки в двух любых ОАi и ОАj; ……… Sn – CМО полностью загружено, в ней n-заявок . Sn+1 – все каналы загружены, в них n-заявок и одна в очереди; Sn+2 – все каналы загружены, в них n-заявок и две в очереди и т.д. Далее либо по схеме гибели и размножения либо по системе уравнений, составленных по матрице   ij  , ищутся Pi . Результирующие решение будут иметь вид: 1  n i  n 1  P0     ;  i 0 i ! n !(n   )  Через вероятность P0 вычисляется w: P0  n w . (n  1)!  (n   ) 2   n - условие стационарной работы системы. Если это условие не выполняется, система не справляется с потоком, очередь перед ней будет расти до , и не будет иметь установившегося значения. Остальные параметры вычисляются по очевидным формулам: u  w v, l   w, m  l    u , k  , R1  ОА. k . n Где ̅ - среднее число занятых ОА, R1 - коэффициент загрузки одного Приведѐм формулы для важного частного случая двухканальной СМО n=2: 2  2v P0  , w . 2  4  2 Пример: СМО М/М/2. Быстродействие ОА B  106 ходящей через систему ̅ оп ; средняя трудоемкость одной заявки, прос 1 1 1 оп.; 1  2 ; 2  5 ; 3  3 ; Найти все с с с основные характеристики СМО. 43 1 2 3 ОА1   10 v  0.08 О ОА2 v  0.08 1 c Интенсивность заявок на входе:   1  2  3  10 . Среднее время обслуживания: v   B  8*104  0.08c . 106 Коэффициент загрузки  : ρ = ̅ = 0,8 < 2. Вероятность нахождения системы в нулевом состоянии или состоянии 2  0.8  0.37 . (Для n=1 было 1 – ρ = 0,2) 2.8 0.64*0.08 Среднее время ожидания в очереди w : w   0.015c .(Для n=1 бы4  0.64 простоя: P0  ло 0,32 с) В очереди в среднем находится заявок: l   * w  0.15 . (Для n=1 было 3,2) Находим среднее число заявок в системе m : m  l    0.95 .(Для n=1 было 4) Среднее время пребывания в системе u : u  v  w  0.08  0.015  0.095c . (Для n=1 было 4 с) ̅ Среднее число заявок в обработке . Коэффициент загрузки каждого ОА .. Графики для времени ожидания ̅ при n = 1 и n = 2 выглядят следующим образом: \ 44 1.8.7 Многоканальная СМО с конечной очередью. СМО M/M/n/k Результаты этого папаграфа можно использовать для одноканальной СМО с конечной очередью, положив n = 1 (СМО M/M/1/k). Система с конечной очередью имеет следующий вид:  lmax  k О ОА1 k v обс(при усл.  n) …… ОАn v отк Даны λ, ̅ или , n – число каналов (число ОА), k – число мест в ̅ очереди. Необходимо найти основные характеристики СМО: ̅ ̅ ̅ ̅ где – интенсивность обслуженных заявок, – интенсивность потока заявок, которым отказано в обслуживании из-за того, что в очереди нет места для вновь прибывшей и соответственно – вероятность обслуживания и – вероятность отказа в обслуживании. Очень часто на практике приходиться решать так называемую обратную задачу, когда заданы λ, ̅ или и - заданная (требуемая) вероят̅ ность отказа в обслуживании. При этом необходимо найти ту минимальную длину очереди k, при которой вероятность отказа в обслуживании . Придерживаемся вышеизложенного порядок формирования модели СМО. Построим граф переходов системы из состояния в состояние. В состоянии Si - в СМО i заявок. Максимальное значение i = n + k, n в ОА и k в очереди. При этом вероятность отказа в обслуживании будет равнятся вероятности нахождения в состоянии Sn+k, то есть . Коэффициент загрузки СМО ̅ может быть как меньше или равен n, так и больше. Стационарный режим обеспечивается наличием потока заявок, которым отказано в обслуживании из-за переполнения очереди.  S0  S1  Sn-1 S2 2   (n 1) Очереди нет   Sn n Sn+1 n Sk+n n Рост очереди 45 Используя формулы гибели и размножения, получим вероятность простоя СМО: 0∑ ( ) ( ⁄ ) )+ ( (1) { 0∑ + и вероятности нахождения СМО в состоянии Si { (2) Вероятность отказа в обслуживании . Вероятность обслуживания . Интенсивность обслуженного потока заявок . Интенсивность не обслуженного потока заявок . Коэффициент мультипрограммирования (среднее число заявок в СМО) ̅ ∑ При больших значениях n + k расчѐт ̅ удобнее вести по следующим выражениям, где сумма посчитана по формулам геометрической прогрессии ⁄ ) ( ⁄ ) ( . / ⁄ ) ( ̅ ( ) . / { Среднее число занятых каналов . Коэффициент загрузки одного (каждого) канала . Средняя длина очереди ̅ ̅ . Среднее время ожидания в очереди по формуле Литтла ̅ Среднее время пребывания в СМО ̅ ̅ ̅ . ̅ ̅ ̅ . ̅ или по формуле Литтла Рассмотрим решение обратной задачу, когда заданы λ, ̅ или и ̅ - заданная вероятность отказа в обслуживании. Надо найти значение длины очереди k, при которой . В общем случае выразить значение k из уравнений (1) и (2) для достаточно сложно. Поэтому рассмотрим важный практический случай подбора значения k, когда необходимо обеспечить достаточно малые значения . При этом, в первую очередь необходимо обеспечить неравенство . При этом второе слагаемое в (1) ( ) ( ( ⁄ ) ) ( ) при больших значениях k. То есть, пользу46 ясь этим приближением, мы завышаем немного и тем самым по формуле (2). Таким образом, расчѐт необходимой длины очереди будет осуществлѐн с некоторым запасом. 0∑ Из неравенства (∑ ( ) ) ( ( ] выразим ) ,. Логарифмируя неравенство, с учетом ) отрицательного значения логарифма в левой части, получим необходимую длину очереди, при которой ( (∑ ( ) ) ) . ( ⁄ ) (3) Пример. Возьмѐм данные предыдущего примера СМО М/М/2, только ограничим очередь одним местом, то есть рассмотрим СМО М/М/2/1. Число каналов n=2, число мест в очереди k=1. Интенсивность заявок на 1 c входе:   1  2  3  10 . Среднее время обслуживания: v   B  8*104  0.08c . 106 Коэффициент загрузки  : ρ = ̅ = 0,8 2. Вероятность нахождения системы в нулевом состоянии или состоянии простоя: * ( ) ( )+ . (Было 0,37. Увеличи- лась, т.к. часть заявок не обслуживается). . . . Вероятность обслуживания Интенсивность обслуженных заявок = 0,943. . Интенсивность не обслуженных заявок . Коэффициент мультипрограммирования (среднее число заявок в СМО) ̅ . (Было 0,95. Уменьшилось, т.к. часть заявок не обслуживается). Среднее число занятых каналов из n=2. (Было 0,8. Уменьшилось, т.к. часть заявок не обслуживается). Коэффициент загрузки одного (каждого) канала . ̅ ̅ Средняя длина очереди . (Было 0,15. Уменьшилось, т.к. часть заявок не обслуживается. Их некуда поместить). Среднее время ожидания в очереди по формуле Литтла ̅ ̅ . (Было 0,015. Уменьшилось, т.к. часть заявок не обслуживается). 47 Среднее время пребывания в СМО ̅ ̅ ̅ с. (Было 0,095. Уменьшилось, т.к. часть заявок не обслуживается). Для решения обратной задачи зададим значение два возможных значений . Для из (3) получим ( (∑ ( ( Для ) ) ) . Выбираем k = 3. ⁄ ) получаем Выбираем k = 6. 1.8.8 СМО M/G/1 с заявками N типов М – поток Марковский, закон распределения интервала между двумя заявками на входе экспоненциальный; G–закон обслуживания заявок произвольный, но как минимум должны быть известны его некоторые статистические оценки: математическое ожидание и дисперсия случайной величины  . В идеале должна быть известна функция плотности распределения f(  ) случайной величины  . Это первое обобщение СМО M/M/1. 1 –обслуживающий аппарат один. Второе обобщение СМО M/M/1 – рассматриваются заявки N типов. На вход СМО приходит N потоков заявок, каждый из потоков имеет свой физический смысл, свои i ,  i , дисперсия  i i=1,N . Здесь все потоки одного приоритета, т.е. дисциплина обслуживания безприоритетная. СМО имеет следующий вид: 1 v О 2 ОА  (Если R<1) N N Интенсивность заявок на входе СМО:    i . i 1 Каждый поток имеет свою долю в загрузке ОА:  i  i i  N N i 1 i 1 i i 1 ( i  ) . i Общая загрузка: R    i   i i Обязательным является неравенство R<1 – условие стационарной работы системы. От каждого i-го потока в общей очереди есть своя очередь заявок i-го типа, с длиной i  i wi  i w , где wi - среднее время ожидания заявок i-го 48 типа, Но w = wi . То есть не зависит от индекса. Среднее время ожидание общее для всех потоков. Каждый поток имеет своѐ время пребывания в СМО: ui  w  i . Коэффициент мультипрограммирования по каждому потоку: mi  iui  i (w  i )  i  i . Общее число заявок в СМО: N N N N i 1 i 1 i 1 i 1 m   mi   ( i   i )   i    i    R , где  - общая длина очереди. Математическим аппаратом маркоских процессов пользоваться нельзя, так как в СМО процессы обслуживания не марковские. Ключом к расчетам является нахождение w . Будем считать, что для заявки i-го типа время ожидания в очереди  i складывается из времени дообслуживания заявки, находящийся в ОА на момент прихода рассматриваемой заявки i-го типа, и времени на обслуживание всех заявок, стоящих в очереди: N i  T0   T j , j 1 где Т0- время дообслуживания заявки, находящейся в ОА; Тj- время обслуживания заявки j-го типа, поступившей раньше нашей заявки в систему, и находящейся уже в очереди. От случайных значений перейдем к их математическому ожиданию: N M[i ]  M [T0 ]   M [T j ] ; (*) j 1 Математическое ожидание T j равно: ̅ ̅ [̅ ] Подставим в формулу (*), получим: ̅ ̅ ̅. N wi  M (T0 )    j w j . j 1 Для любого потока из N, среднее время ожидания в очереди одно и то же, поэтому индексы j в правой и i в левой части выражения при ̅ можно опустить: N w  M[T0 ]  w  j j 1 w  M [T0 ]  wR   M [T0 ] . 1 R Найдем математическое ожидание (МО) Т 0 . При приходе j-ой заявки в среднем для обслуживания той i-ой заявки, которая сейчас находится в ОА, остается в среднем половина времени ее обслуживания, то есть vi времени дообслуживания. Кроме этого нужно учи2 тывать вероятность, с которой заявка j-го типа, приходя в СМО, застанет в 49 ОА заявку i-го типа: Pi  i  i * vi . То есть она равна коэффициенту загрузки ОА заявками i-го типа. Чтобы усреднить Т 0 по всем i воспользуемся формулой для МО дискретn ной случайной величины ( M x   xi * i ), тогда i 1 N M ' [T0 ]   i 1 vi i . 2 Учтем, что i  i * vi и получим ∑ – это усреднениепо потокам (по типам заявок). Далее эту величину нужно еще усреднить по случайной величине . Из теории вероятности известно, что если y  y( x) и f ( x) - функция плот ности случайной величины х, то, МО функции у равно: M [ y]   y( x) f ( x)dx .  N i * vi2 i 1 2 В нашем случае х=νi и y( x)    N M [T0 ]    0 i 1  v 2 i i * vi2 2 N f (vi )dvi   i 1 : i  v 2 2 i f (vi )dvi . f (vi )dvi - это центральный момент второго порядка  2 (vi ) : N i * 2 (vi ) i 1 2 M [T0 ]   Зная МО случайной величины  2 (vi )  Dv  12 (vi ) . . vi , дисперсию Dv , можно найти i i  2 (vi )  Dv  vi 2  vi 2 (1  i Введем обозначение  i  v i vi Dvi vi 2 ). - коэффициент вариации vi или относитель- ное СКО приведенное к МО. Используя это обозначение, получим  2 (vi )  vi 2 (1   i 2 ) . МО времени дообслуживания будет иметь вид N i * vi 2 (1   i 2 ) M [T0 ]   . i 1 2 Таким образом, мы получили формулу Поллачика - Хинчина, среднее время ожидания в очереди будет иметь вид N w  *v i 1 i i 2 (1   i 2 ) 2(1  R) (*) 50 Зная w , посчитаем u и v . Среднее время пребывания в системе u m  u : . Среднее время обслуживания по всем потокам заявок v  u  w. v : СМО М/М/1 является частным случаем системы M/G/1. Для экспонен-  v 1/    1 - для простейших потоков событий.  i  0 1 vi 1/  для остальных потоков;  i  0 - неслучайный процесс, заявки обслуживаются циального закона  i  i за определенное время. Рассмотрим случай, когда  i  1 , подставим в формулу (*): N wM / M /1   i * vi 2 i 1 1 R N    *v i i 1 1 R i  [ N  1]   *v . 1  Для экспоненциального закона: M [T0 ]   * v . Заметим, что закон распределения случайных величин l и u в явном виде определить не удастся. Может быть полезной для максимальной длины очереди формула: D[ w]  w2  Пример:  *  3 [v ] . 3(1   ) СМО M/G/1 1 2 3 v  О ОА  ( R  1) Имеются следующие данные: 1  2; v1  0.1;  1  0; 2  5; v2  0.06;  2  1; 3  3; v3  0.1;  3  2. Найдем R:    i  2  5  3  10 1  1 * v1  0.2 2  0.3  R=  i  0.8  1 , 3  0.3 т.е. система успевает обслужить все 3 потока. Найдем среднее время нахождения заявки в очереди w : 2*0.12 *(1  02 )  5*0.062 *(1  12 )  3*0.12 *(1  2 2 ) 0.206 w   0.515c . 2*(1  0.8) 0.4 Средняя длина очереди: l   * w  10*0.515  5.15 , 51 l1  1 * w  2*0.515  1.03, l2  2 * w  5*0.515  2.575, l3  3 * w  3*0.515  1.545. Среднее время пребывания в системе заявок каждого типа: u1  w  v1  0.515  0.1  0.615, u2  0.515  0.06  0.575, u3  0.515  0.1  0.615. Среднее число заявок каждого типа: m1  l1  1  1.03  0.2  1.23, m2  l2  2  2.575  0.3  2.875, m3  l3  3  1.545  0.3  1.845. m   mi или m  l  R  5.15  0.8  5.95 , m 5.95 u   0.595c.  10 Среднее время обслуживания потоков: v  u  w  0.595  0.515  0.08c. 1.8.9 СМО с приоритетными дисциплинами обслуживания В СМО с приоритетными дисциплинами обслуживания весь поток заявок так же делится на несколько потоков, которые будем нумеровать 1,2,…,n, но в отличие от предыдущих случаев каждому типу заявок назначается свой приоритет, который определяет преимущественное право обслуживания. Заявки типа 1 будут самого высокого приоритета, заявки типа n – самого низкого. Для каждого типа заявок организуется своя отдельная очередь, и выбор заявки на обслуживание в ОА осуществляется диспетчером. Чаще всего диспетчеры и очереди организуются программно. Временем работы диспетчера будет пренебрегать. Структура СМО будет иметь вид: 1 O1 2 O2 n On . . . . Диспетчер  ( R  1)  ОА 52 ∑ Очередь O1 - с самым высоким приоритетом, очередь On - с самым низким. Различают две приоритетных дисциплины обслуживания: 1) дисциплина обслуживания с относительными приоритетами (ДО ОП); 2) дисциплина обслуживания с абсолютными приоритетами (ДО АП). Для ДО ОП диспетчер учитывает приоритеты заявок только при выборе очередной заявки из очереди только при окончании обслуживания предыдущей заявки в ОА. Заявка выбирается из k-ой очереди тогда и только тогда, когда все предыдущие очереди более высокого порядка пусты. Для ДО АП при поступлении в СМО заявки более высокого приоритета, чем та, которая находится на обслуживании в ОА, ее обслуживание немедленно прерывается и она возвращается в свою очередь (пунктир на рисунке), где будет находиться в состоянии ожидания дообслуживания. При этом заявка более высокого приоритета немедленно занимает ОА. 1.8.9.1 СМО M/G/1 с относительными приоритетами Основная цель анализа данной систмы - нахождение wк , т.е. среднего времени ожидания заявки в очереди k-го приоритета. Все остальные характеристики СМО ( k , u k ,mk ) рассчитываются так же как и в системе без приоритетов M/G/1. За основу расчѐта wk возьмѐм следующую аддитивную формулу: k k 1 i 1 i 1 wk  T0   Ti   Ti ' (1) Т0- время дообслуживания заявки в ОА, которая там находилась, когда пришла заявка рассматриваемого k-го приоритета (аналогична бесприоритетной дисциплине обслуживания (БП ДО): n T0    i 1 i 2 i (1   i2 ) 2 , где  - коэффициент вариации длительности обслуживания; k  T - время обслуживания заявок i 1 i данного k-го приоритета и более вы- соких приоритетов (с 1 до k-1) уже имеющихся в очередях – они будут обслужены до рассматриваемой нами заявки k-го приоритета; k 1 T i 1 i ' - время обслуживания заявок более высоких приоритетов (с 1 до k-1), чем рассматриваемого k-го, которые ещѐ только придут в СМО за время wk ожидания в очереди рассматриваемой заявки. 53 Переходя к математическому ожиданию и пользуясь формулой Литтла, получаем значения Ti и Ti ' : Ti  i i  i i wi  i wi , Ti '  i ni  i i wk  i wk . ni - среднее число заявок i-го типа, которые придут в СМО за время ожи- дания wk . Подставим полученные выражения в формулу (1), получим: ̅ ∑ ̅ ̅ ̅ ∑ (2) Введѐм дополнительное обозначение для коэффициента частичной загрузки ОА заявками высшего приоритета с 1 по S: S S i 1 i 1 R s  1   2  ...   s    i   i i R0 - загрузка системы от нуля потоков. n Частные случаи: R0  0, R1  1 , R2  1  2 , R  Rn    i - полная загрузка. i 1 Rk  Rk 1   k , k 1 С учѐтом этого обозначения,   i  Rk 1 . i 1 k k 1 i 1 i 1 Формула (2) является рекурсивной. Учтѐм, что  i wi  k wk   i wi . k 1 Тогда wk  T0   i wi i 1 1   k  Rk 1 Вместо  k запишем разность Rk-Rk-1, тогда получим k 1 wk  T0   i wi i 1 (3) 1  Rk Получим частные виды формулы (3) для k=1,2,3. k = 1, т.е. для самой приоритетной заявки: ̅ ̅ ̅ ( )( k = 2: w2  T0  1w1  1  R2 ) T0 T0 (1  R1 ) T0 (1  R1  R1 ) ;   1  R2 (1  R2 )(1  R1 ) (1  R2 )(1  R1 ) T0  R1 k = 3: 54 w3  T0  1w1   2 w2  1  R3 T0  R1 T0 T0  ( R2  R1 )  1  R1 (1  R2 )(1  R1 )  1  R3 T0 (1  R2  R1  R1 R2  R1  R1R2  R2  R1 ) (1  R1 )T0   (1  R3 )(1  R2 )(1  R1 ) (1  R3 )(1  R2 )(1  R1 )  T0 . (1  R3 )(1  R2 ) Очевидно, что общая формула для wk  Подставляя ̅ wк будет иметь вид: T0 ; (1  Rk )(1  Rk 1 ) кончательно получим: n wk    i 1 i i 2 (1   i2 ) (4) 2(1  Rk )(1  Rk 1 ) Вывод: По сравнению БП ДО, где в знаменателе (1-Rn), в ДО ОП (1-Rk-1) отражает влияние заявок более высокого приоритета на увеличение времени ожидания заявки k-го приоритета; (1-Rk) отражает уменьшение времени ожидания заявки k-го приоритета, т.к. суммарный частичный коэффициент загрузки Rk меньше полного Rn. В числитель входят заявки всех типов, т.к. обслуживание заявки, занявшей ОА, не прерывается. Для каждого k  1, n на графике зависимости wk  f ( R) своя кривая. Чем больше приоритет (меньше k), тем ниже кривая. wk k=n k=n-1 БП k=2 k=1 i 1 R  Rn По сравнению с БП ДО уменьшается время обслуживания высокоприоритетных заявок за счет увеличения времени ожидания низкоприоритетных. Точки на графике на асимптоте означает, что СМО устойчива при перегрузке (более чем 100 % загрузке) для заявок высоких приоритетов. Даже при R  1 высокоприоритетные заявки будут иметь конечное время ожидания очереди. Пусть все i   , n  4 , тогда качественно графики времени ожидания в очереди в зависимости от приоритета выглядят следующим образом: 55 wk k=3 k=4 i 00 2 1 k=1 k=2 3 4 R У каждого приоритета своя асимптота по значению коэффициента загрузки. 1.8.9.2 СМО M/G/1 с абсолютными приоритетами Здесь еще больше уменьшается время ожидания высокоприоритетных заявок за счет еще большего увеличения времени ожидания низкоприоритетных, т.к. высокоприоритетные не ждут окончания обслуживания низкоприоритетных. Поэтому время ожидания заявки k-го приоритета можно представить как сумму двух составляющих: wk  wk н  wk п (5) где wk н - время ожидания обслуживания в очереди до первого захвата ОА; wk п - время ожидания в прерванном состоянии. Первое слагаемое может быть получено из формулы (4) для ДО ОП, при этом следует учесть, что заявки более низкого приоритета от k+1 до n не оказывают никакого влияния на заявки k-го приоритета. Поэтому в числителе сумма должна вычисляться только от 1 до k: к wk н    i 1 2 i i (1   i2 ) 2(1  Rk )(1  Rk 1 ) . (6) Второе слагаемое - время нахождения в прерванном состоянии определяется как суммарное время обслуживания более высокоприоритетных заявок с 1, 2,…, k-1 приоритетами, поступающих за время  k , т.е. за время обслуживания заявки k-го приоритета. Число заявок приоритета большего k (i < k) за время  k можно определить по формуле Литтла: ri(1)  i k , где индекс i относится к заявке i-го приоритета, индекс (1) – первая итерация оценки количества более приоритетных заявок. Тогда на их обслуживание уйдет время:  i(1)  ri(1)i  i ki   i k . Просуммировав время по всем приоритетам выше k (i < k), получим: 56 k 1 k 1 i 1 i 1 k 1 T (1)   i(1)    i k   k   i  Rk 1 k ; i 1 Но за это время T в СМО поступят ещѐ ri заявок с приоритетом выше k. Их число будет определяться как: ri(2)  iT (1)  i Rk 1 k . На их обслуживание будет потрачено время:  i(2)  ri(2)i  i Rk 1 i k  i Rk 1 k. Время на обслуживание всех заявок с приоритетом i < k будет определяться: (1) (2) k k 1 i 1 i 1 T (2)   i( 2)  Rk 1 k   i  Rk21 k и т.д. На j-ом шаге получим: T ( j )  Rkj1 k , Тогда среднее время ожидания в прерванном состоянии   R  n ( j) wk   T  k  Rk( j 1)  k 1 k , (7) 1  Rk 1 j 1 j 1 Сумма сходится при Rk-1 < 1 (геометрическая прогрессия). Есть еще один более простой вариант получения этой формулы. Вспомним, что для системы СМО M/M/1 ̅ ̅ Просто для расчета времени ожидания в прерванном состоянии надо учитывать загрузку ОА заявками более высоких приоритетов, чем k-ый, то есть ρ = Rk-1, за впемя обслуживания рассматриваемой заявки, то есть ̅ = ̅ k. Окончательная формула для ДО АП будет иметь вид: k wk    2 i i (1   i2 ) Rk 1k (8) 2(1  Rk )(1  Rk 1 ) 1  Rk 1 i 1  Первое слагаемое существенно меньше при малых k, чем в ДО ОП, так как в числителе сумма не до n, а до k < n. Для самого низкого приоритета k = n первое слагаемое совпадает с результатом для ДО ОП. Второе слагаемое равно 0 для заявок высшего приоритета k = 1 и постепенно растѐт с ростом k. Так что, для k = n оно добавляет большую долю к времени ожидания по сравнению с ДО ОП. Все остальные формулы для основных параметров те же, что и для БП ДО. Графики зависимостей ̅ ( ) имеют вид: 57 БП k=n-1, АП k=n, АП wk k=2,ОП k=2,АП k=1,ОП k=1,АП i 1 R Если рассматривать зависимость ̅ ( ), k  1, n при некоторой фик* сированной загрузке R  R < 1, то получим семейство графиков зависимости времени ожидания ̅ ( ) от номера приоритета, k  1, n для разных ДО. Площади под графиками будут равны в том случае, если k   . wk АП ОП БП w 1 2 3 4 n-1 n K 1.8.10 Закон сохранения среднего времени ожидания. Закон Л. Клейнрока Закон Л. Клейнрока: При изменении дисциплины обслуживания (ДО), среднее время ожидания системы, усредненное по всем очередям (приоритетам), остаѐтся постоянной или меняя ДО, невозможно изменить сумму парных произведений коэффициента загрузки на время ожидания в очереди: n wср   k wk  const , для любой ДО. k 1 Если учесть, что ρk– есть вероятность занятости ОА (но не всей СМО) заявками k-го типа (k-го приоритета для приоритетных ДО), то закон Клейнрока можно сформулировать таким образом: 58 Математическое ожидание времени ожидания в очередях, вычисленное по вероятности захвата ОА, нельзя изменить меняя ДО. Здесь ̅ k – дискретное значение случайной величины принимаемое с вероятность pk = ρk. Или более кратко: МО времени ожидания в очередях, вычисленное по вероятности захвата ОА, не зависит от выбора ДО. ∑ ̅ ̅ = Const для , то есть ̅ инвариантно относительно ДО. Этот закон справедлив для СМО, отвечающей следующим требованиям: 1) Отсутствие отказов в обслуживании; 2) Система простаивает только в том случае, когда нет заявок в СМО; 3) Все входные потоки k  1, n независимы и имеют экспоненциальное распределение, т.е. они простейшие; 4) Отсутствие прерываний в системе или если они есть, то остаток времени при обслуживании прерванной заявки должен быть случайным и распределѐн по экспоненциальному закону. Последнее требование не выполняется для ДО АП. Поэтому для этой ДО этот закон выполняется приближѐнно, сумма несколько отличается от сумм для БП ДО и ДО АП. Если на предыдущем графике по оси ординат отложить не ̅ , а произведение ̅ , то в этом случае площади под графиками равны (для АП приблизительно). Меняя ДО, какие-то ̅ увеличиваются за счѐт уменьшения других ̅ .  k * wk АП ОП БП 1 2 3 4 n-1 n K 1.8.11 Примеры расчѐта СМО с приоритетами Пример: ДО ОП. Данные из предыдущего примера для БП ДО: 1  2; v1  0.1;  1  0; 2  5; v2  0.06;  2  1; 3  3; v3  0.1;  3  2. 59 1 , v1 ,  1 2 , v2 ,  2 О1 v О2 3 , v3 ,  3  ОА О3 Для сравнения из предыдущей лекции ̅ =0,515 с. 2*0.12 *(1  02 )  5*0.062 *(1  12 )  3*0.12 *(1  22 ) 0.206   0.129c ; 2(1  0.2) 2*0.8 0.206 w2   0, 258c ; 2*(1  (0, 2  0,3))*(1  0, 2) 0.206 w3   1.03c ; 2*(1  0.8)*(1  0.5) l1  1 * w1  2*0.129  0.26; w1  l2  2 * w2  5*0.258  1,3; lобщ  4,66 з. ( lБП  5,15 ). l3  3 * w3  3*1, 03  3,1. Остальные параметры СМО расчитываются как: ui  wi  vi ; mi  i * ui , m   mi ; u  m ;  ̅ ∑ . 3 Проверим закон Клейнрока. Для БП: wср   к * w  0.515*0.8  0.412c ; к 1 3 ОП: wср   к * wk  0.2*0.129  0.3*0.258  0.3*1.03  0.412c . к 1 ДОАП: w1  2*0.12 *(1  02 ) v1 * R0 0.01    0.0125c ; 2(1  0.2) (1  R0 ) 0.8 ; w3  v *R 0.206  3 2  1.13c ; 2*(1  0.8)*(1  0.5) (1  R2 ) l1  1 * w1  2*0.0125  0.025; l2  2 * w2  5*0.31  1.55; lобщ  4.965 с. l3  3 * w3  3*1,13  3,39. Остальные параметры СМО расчитываются как: ui  wi  vi ; mi  i * ui , m   mi ; u  m ;  ̅ ∑ . Проверим закон Клейнрока. 3 АП: wср   к * w1  0, 2*0, 0125  0,3*0,31  0,3*1,13  0.435 . к 1 Не выполняется абсолютно точно, а лишь приблизительно, так как не выполняется требование 4. 60 Для освоения лекций по СМО M/G/1 решить следующую задачу. Задача. В систему обработки телеметрической информации поступают сигналы трѐх типов A, B и C. Сигналы типа A поступают в среднем через секунды, сигналы типа B – через секунды, сигналы типа C – через секунды. Обработка одного сигнала типа A занимает в среднем ̅ секунды, сигнала типа B – ̅ секунды, сигнала типа C – ̅ . Интервалы времени между сигналами, и время обработки сигналов являются случайными величинами, распределѐнными по экспоненциальному закону. Предлагаются три варианта дисциплины обслуживания (ДО) сигналов: а) бесприоритетная (БП) ДО; б) ДО ОП; в) ДО АП. При обслуживании с приоритетами более высокий приоритет должны иметь сигналы, требующие меньшего времени обработки. Требуется найти основные характеристики системы для всех трѐх ДО, проверить закон Клейнрока и выбрать ДО, обеспечивающую минимальное среднее время обработки всех сигналов ̅. Вариант 1 2 3 4 5 6 7 8 1 2 0,5 1 0,3 3 1 6 2 4 0,2 0,2 0,9 1 2 1 3 6 0,1 0,1 0,1 0,5 3 3 ̅ 0,2 0,8 0,15 0,3 0,09 0,6 0,1 1,8 ̅ 0,6 1,2 0,08 0,06 0,27 0,3 0,4 0,25 ̅ 1,2 1,2 0,01 0,02 0,03 0,15 1,5 0,75 2 Моделирование ВС, представленных стахостическими сетями массового обслуживания В предыдущих разделах были рассмотрены вопросы анализа (определение характеристик) отдельных типовых СМО: 1. Многоканальное марковское СМО без очереди - СМО M/M/n/0. 2. Многоканальное (одноканальное n = 1) марковсое СМО с неограниченной очередью - СМО M/M/n. 3. Многоканальное марковское (одноканальное n = 1) марковское СМО с ограниченной очередью - СМО M/M/n/k. 4. Одноканальное СМО с разнотипными потоками заявок с БП ДО и произвольным законом длительности обслуживания - СМО M/G/1. 5. Одноканальное СМО с разнотипными потоками заявок с ДО ОП и произвольным законом длительности обслуживания - СМО M/G/1. 6. Одноканальное СМО с разнотипными потоками заявок с ДО АП и произвольным законом длительности обслуживания - СМО M/G/1. Теперь настала очередь разработки моделей более сложных систем, которые могут быть представлены совокупностью произвольно соединѐнных типовых СМО, которые называются стохастическими сетями (СС). 61 К таким сложным системам могут быть отнесены вычислительные системы (ВС). При этом СС обеспечивают необходимый уровень стратификации ВС, т.е. разбиение на отдельные простейшие модели СМО. 2.1 Примеры моделей, используемых при анализе ВС Процессор – ОП – ВУ (Внешние Устройства), представленный в виде СМО M/G/1 с обратной связью через ввод-вывод. В процессоре выполняется n программ, процессором моделируется в виде ОА, v - случайная величина для каждой программы. Очередь О осуществляет размещение нескольких программ, которые находятся в состоянии ожидания выполнения в процессоре. Программа v 1 2  О ОА  P PВв / Выв n Вв/Выв Источник заявок Функционирование такой модели соответствует многопрограммному режиму работы вычислительной системы. В очереди находится совокупность программ, готовых к выполнению. Интенсивность поступления заявок  определяется суммарной интенсивностью пополнения списка готовых к выполнению программ из внешнего источка, и программ, для которых завершен процесс ввода-вывода. Далее рассмотрим варианты ВУ. 1. Модель мультиплексорного канала (МК). С его помощью осуществляется параллельное и независимое подключение различных устройств, такими устройствами являются УВВ. 62 УВВ1 МК УВВ2 УВВs В качестве модели МК используется параллельное соединение многоканальных СМО. Если считать, что система является системой без потерь в обслуживании, то 1  2  ...  S   . ОА11 О1  1 ОА1k О2 2 ОА21 ОА2n Оs S ОАs P1  P2  ...  PS  1 . 2. Модель селекторного канала (СК). В отличие от МК СК работает в монопольном режиме, т.е. занят обслуживанием только одного устройства. Но самое главное – у СК обычно существенное время занимает этап подготовки к передаче/приему информации – доступ к нужной порции информации (магнитофон, стример, модем и в общем случае взаимодействие через сеть – в первом прибличении при способе функционирования на основе коммутации каналов: Передача сообщения начинается после довольно длительной фазы установления соединения, во время которого отдельные ЛС коммутируются в единую физическую цепь между абонентами. Недостатками данного способа являются: длительная подготовительная фаза и ЛС между абонентами занимается ими на длительное время. CK УВВ1 УВВs 63 Концептуальную модель СК можно представить в виде двух-фазной СМО с несколько независимыми входными потоками этапов обработки, так как подготовительные операции во внешнем устройстве могут вестись параллельно во всех устройствах. И так: первая фаза – длительная подготовка, вторая – скоростная передача большого объема информации 1) Передача информации через канал, т.е. СК нужно представить в виде последовательного соединения двух СМО. УВВ1 1этап  О1 v1 - время подготовки 2этап ОА1 О v - время передачи ОА  О1 vS s    i i 1 - время подготовки ОА1 УВВs 1этап Приведѐм стохастическую сетевую модель ВС, состоящую из одного процессора, одного мультиплексного канала с одним типом УВВ в двух экземплярах и одного селекторного канала, к которому подключены два УВВ. Пр ОП   0 1 Р01 О1 v1 ОА1 1 Р10 v2 МК О2 ОА21 Р21 2 2 ОА22 v2 Р51 5 v5 ОА5 СК 2эт О5 Р35 5 Р45 ОА31 ОА4 v3 О3 v4 О4 СК 1эт Р12 Р13 3 Р14 4 Вероятности Pij - это вероятности перехода заявки из i-ой в j-ую систему. Обычно они при моделировании системы известны, индекс «0» соответствует внешней СМО, т.е.S0 – СМО представляющая внешний мира для ВС. Таким образом, матрица перехода заявки из i-ой в j-ую систему будет иметь вид: 64 S0 S0  P00 …. P=   Sn  Pn 0 …... Sn P0 n    Pnn  Эта матрица для конкретного примера будет иметь вид: 0 P  10 0 P 0 0   0 1 0 0 P12 1 0 0 0 P13 P14 1 0 0 0  1 1  0 Свойства матрицы – сумма элементов каждой строки равняется 1: n P j 0 ij P10  P12  P13  P14  1  1, i  0, n ; Имея матрицу Р можно по столбцам составит СЛАУ для нахождения интенсивности потока заявок СМО. i , i  0, n , которая проходит через каждую i-ю n  j   Pij i , j  0, n , i 0 где 0 - заданная величина. Составим систему уравнений, начиная с j=0: 0  P101        2 5  1  2  P121  3  P131  4  P141  5  3   4 Зная 0 , легко решаем систему уравнений, находим все интенсивности  j . После этого переходим к индивидуальному анализу каждой СМО. 2.2 Разомкнутые и замкнутые стохастические сети (СС) На практике встречаются сети разомкнутого или замкнутого характера. В предыдущем параграфе в качестве примера была приведена система разомкнутого типа. Разомкнутые сети применяются в качестве моделей тех систем, в которых находятся на обработке переменное число заявок (например, ВС ре65 ального времени, ВС с квантованием времени). В таких системах от пользователя (внешнего мира для СС), поступают запросы на обслуживание для выполнения отдельных работ. 0 -задание на обработку. 0 S0 Источник заявок 0 (если Ri< ni) Стохастическая сеть отк Сеть замкнутого типа используется для моделирования работы ВС, в которых ведется обработка фиксированного числа заявок (т.е. по сути, система S0 является составной частью сети). Примером таких сетей может быть система, обрабатывающая задание в диалоговом режиме. Пользователь, посылая задание на обработку, получая ответ, обрабатываетего и посылают следующее задание. Пользователь рассматривается как один из элементов стохастической сети – как одно из СМО сети. S0 v0 0 0 Источник заявок Стохастическая сеть В сетях замкнутого типа находится постоянное количество заявок и интенсивность 0 их циркуляции через сеть является не заданной, а искомой величиной. Это приводит к большим сложностям анализа замкнутых сетей по сравнению с разомкнутыми. Пример простейшей замкнутой сети: 0 v0  0 О1 ОА1 О2 S0 ОА2 Основные уравнения замкнутой сети будут выглядеть следующим образом: Задано ̅ ̅ ̅ ̅ ̅ ̅ ̅ ̅ ̅ , где . Отсюда получаем суще- ственно нелинейное уравнение относительно неизвестной ̅ ̅ ̅ ̅ ̅ . ̅ ̅ ( )( ) И так, даже для простейшей замкнутой сети приходится решать задачу численным методом. Возьмѐм сетевую модель ВС из предыдущего параграфа и сделаем еѐ замкнутой. Добавляем пользователя ВС, который моделируется СМО0 - S0. 66 Он получает ответы от СМО1 (процессор-оперативная память) и вводит в систему следующее задание. Пр-ОП 0 Р01 1 О1 v1 ОА1 Р10 1 S0 v2 МК 2 Р51 5 О2 ОА21 Р21 2 ОА22 v5 О5 ОА5 СК Р35 5 Р45 СК 2эт v2 ОА31 ОА4 Р12 v3 О3 v4 О4 Р13 3 Р14 4 СК 1эт Составим матрицу Р для нахождения  i. Матрица Р имеет вид: i\j 1 2 3 4 5 1 1 P10 P12 P13 P14 2 1 3 1 4 1 5 1 ; P ij  1 , i  0, n . Интенсивность можно определить по формуле: n  j   Pij i , j  0, n i 0 Так как матрица совладает с матрицей разомкнутой сети, то имеем туже систему уравнений: 0  P101        2 5  1  2  P121  3  P131  4  P141  5  3   4 Но в отличие от предыдущего случая, когда была задана, хотя в системе 6 уравнений и 6 неизвестных, но так как она линейно зависима, то имеет бесконечное множество решений. 67 Так как в замкнутой системе задано ̅ – среднее число заявок в СС, то перепирая различные варианты значения 0 с учѐтом обеспечения стационарного режима работы всех СМОi, находим все остальные интенсивности. После чего переходим к индивидуальному анализу каждой СМО. Находим все ̅ и затем ̅ как их сумму. Сравнивая это значение с ̅ продолжаем подбирать 0 до получения совпадения с необходимой погрешностью. 2.3 Методика моделирования сложных систем, представленных стохастическими сетями Рассмотрим методику на примере системы «Тестирование ITпродукта» Рисунок 1 – Схема процесса тестирования IT-продукта Данной системе соответствует стохастическая сеть из совокупности 3-х СМО. Рисунок 2 – Стохастическая сеть системы тестирования IT-продукта 68 Любое СМО стохастической сети может быть типа СМО М/G/K: процесс прихода заявок в систему является марковским, длительность обслуживания заявок случайная величина, распределѐнная по произвольному закону, K – число каналов. Для данного примера возьмѐм следующие исходные данные: Всѐ СМО одноканальные K1 = K2 = K3 = 1. Длительность обслуживания распределена по экспоненциальному закону. Интенсивность прихода заявок (обращений) λ0 = 10 обр./час. Вероятность решения проблемы p1,0 = 0,9. Вероятность требования экспертизы p1,2 = 0,06. Вероятность необходимости обращения к разработчику p1,3 = 0,04. Среднее время обслуживания: ̅ часа, ̅ часа, ̅ часа. Требуется найти характеристики каждой отдельной СМО ̅ ̅ ̅ ̅ , а главное характеристики стохастической сети в целом: ̅ ̅ и предельная достижимая производительность сети как max(λ0), при которой ̅ ̅ . Решение Расчѐт характеристик сети состоит из шести этапов: 1. Расчѐт интенсивностей потоков заявок в каждой СМОi; 2.· Проверка условий выполнения стационарного режима в сети; 3.· Расчѐт характеристик каждой СМОi; 4. Расчѐт коэффициентов передач a j в каждую СМОi (a j - доля заявок, попадающих в СМОi от входного потока λ0); 5.· Расчѐт сетевых характеристик в целом. 6. Оптимизация характеристик сети. Этап 1. Построим матрицу вероятностей движения { } ( ) ( ) заявок из одной СМО в другую. [ ] ̅̅̅̅̅. ∑ Найдѐм интенсивности переходов для отдельных СМО ∑ ̅̅̅̅ { Решаем СЛАУ 69 ( ) ( ( ) ( ) ). Этап 2. Необходимо проверить условия выполнения стационарного режима работы для всех СМО: . Для данной сети все , следовательно, все . Учитывая, что ̅ , получим: Коэффициент загрузки второй СМО превышает 1, следовательно требуется модификация. Заменим работника, проводящего экспертизу, более квалифицированным, который в среднем проводит экспертизу 1,4 часа. В общем случае, если условия выполнения стационарного режима работы не выполняются, то, их можно реализовать одним из следующих способов: - уменьшением интенсивности источника заявок до значения, при котором все условия будут выполняться; - увеличением числа обслуживающих каналов Ki в перегруженных СМО; - уменьшением длительностей обслуживания ̅ в перегруженных СМО. - уменьшением вероятностей передач заявок pji в перегруженные СМОi. Этап 3. Зная , рассчитаем ̅ ̅ ̅ ̅ для каждой из СМО в соответствии с их типом. Для типа СМО M/M/1 ̅ ̅ ̅ ̅ ̅ ̅ ̅ ̅ ̅ СМО1 ̅ (часа) ̅ (обращ.) ̅ (обращ.) ̅ =0,646+0,08=0,726(часа) СМО2 ̅ (часа) ̅ (обращ.) ̅ (обращ.) ̅ =21,89+1,4=23,29 23,3 (часа) СМО3 ̅ (часа) 70 ̅ (обращ.) ̅ (обращ.) ̅ =2,3+1,4=3,7(часа) Этап 4. Расчѐт коэффициента передачи в i-е СМО (доля заявок, попадающих в данное СМО от входного потока ) ; ; ; Этап 5. Расчѐт сетевых характеристик ̅ ̅ ̅ ( ). ̅ ∑ ̅ ∑ ̅ или ̅ ̅ . Производительность сети определяется как максимальное значение λ0,, которая ещѐ обеспечивает работу сети в стационарном режиме ( ) , ̅ - и при этом ̅ ̅ . Этап 6. Оптимизация характеристик сети заключается в поиске «узких мест». Ими являются те СМО, которые имеют максимальные коэффициенты загрузки каждого отдельного канала очень близкие к 1. Устра- нять «узкие места» следует способами, перечисленными на этапе 2. Устранение одного «узкого места» может привести к возникновению другого. Необходимо стремится к тому, чтобы для всех СМО должны быть одинаковыми. Ддя данного примера необходимо на первом шаге уменьшить значение до значения . Выводы: Аналитический расчѐт функционирования отдельных СМО и их сетей возможен только при наличии в системе определѐнных ограничений (например, большинство потоков заявок должны быть простейшими). Если эти ограничения не выполняются, то аналитические расчѐты могут привести к недопустимо большой погрешности результата. Поэтому, если удаѐтся получить достаточно адекватную аналитическую модель, то она всегда предпочтительна, если же нет, то необходимо использовать имитационное моделированию. 71 3 Имитационное моделирование 3.1 Логика работы GPSS Системе GPSS не содержтит алгоритмический язык подобный Паскалю или Си. Это язук продвижения транцактов (заявок на обслуживание) от оператора к оператору. Все транзакты находятся в одном из двух буферов: 1. Активном; 2. Пассивном. Пассивный буфер транзактов- это все потенциальные транзакты, которые модель может сгенерировать. При пуске модели все транзакты находятся в пассивном буфере. Перемещение транзакта при работе модели из пассивного в активный буфер осуществляется оператором GENERATE, обратное перемещение - оператор TERMINATE. Когда модель заканчивает работу транзакты могут находиться, как в пассивном, так и активном буфере. Работа модели в имитаторе GPSS заключается в перемещении транзакта от оператора к оператору, причем это осуществляется до тех пор, пока не возникнет одна из трех ситуаций: 1. транзакт входит в оператор, который его уничтожитTERMINATE; 2. транзакт входит в оператор задержки ADVANCE; 3. транзакт пытается войти в оператор, который его не пускает. В третьем случаетранзакт остается в предыдущем оператора и будет повторять попытки войти в данный оператор, который его не пускает. Причем в имитаторе GPSS все движения транзакта происходят без затрат моделируемого времени. В модели GPSSу любого транзакта имеются следующие параметры:  номер транзакта;  время движения – время, на которое транзакт запланировал вход в следующий оператор;  номер текущего оператора , где он находится;  приоритет транзакта;  номер следующего оператора. Все транзакты, которые находятся в активном буфере, могут находиться в нескольких цепях событий: 1. цепь текущих событий (ЦТС); 2. цепь будущих событий (ЦБС). В ЦБС находятся все транзакты, которые только появятся с помощью оператора GENERATE через какое-то время t , либо те транзакты, которые попали в оператор задержкиADVANCE. В текущий момент времени программа моделирования транзакты не рассматривает, так как время их движения еще не наступило. При работе модели двигаются транзакты, которые нужно обработать в текущий момент времени, поэтому в ЦТС транзакты 72 упорядочены только по приоритету, а в ЦБС они упорядочены по двум параметрам: 1. по приоритетам; 2. по времени дальнейшего движения. ЦТС просматривается логикой работы GPSS многократно, так как условие блокировки движения конкретноготранзакта может быть неоднозначным в данный момент времени и в связи с движениемдругих транзактов,оно может изменяться. Необходимость многократного просмотра связана с тем, что еще не все транзакты в ЦТС обработаны, то есть транзакты, блокирующие продвижение других транзактов, могут еще сами продвигаться, освобождая место. После обработки ЦТС, которая фиксируется под конец обработки, производится увеличение моделируемого времени до значения, которое имеется минимальное в ЦБС. Это минимальное значение времени в ЦБС становится текущим и все транзакты, имеющие в ЦБС это же время, переводятся в ЦТС. 3.2 Основы имитационного моделирования Объект моделирования в любой момент времени находится в определенном состоянии, которое определяется совокупностью параметров, описывающих систему. Изменение значений этих параметров рассматривается как изменение состояний системы. Сложная система может быть представлена в виде совокупности компонентов K i , связанных между собой. Причем над каждой компонентой существует надстройка, называемая множеством функциональных действий ФД ij . Пример:любую систему можно представить в виде совокупности функциональных действий ФД ij . ФД23 ФД12 ФД22 ФД11 ФД21 ФД31 К1 К2 К3 Совокупность взаимосвязанных ФД представляет собой описание сложной системы. Выполнение каждого функционального действия приводит к событию S j . Для каждой компоненты вводится понятие глобального времени ti . 73 В имитационных моделях сам характер ФД не уточняется. Отличитель- ной чертой ФД является длительность  ij . Для построения имитационной модели системы необходимо задать ФД ij . При построении имитационных моделей реальные ФД аппроксимируются в виде ФД i ' . Степень этой аппроксимации определяет уровень детализации модели. В имитационных моделях ФД ij производится при неизменном времени, т.е. сначала производится ФД ij при выполнении определенных условий, затем происходит модификация времени. Каждое ФД ij может быть представлено тройкой  АЛ ij , ti  ,  ij где АЛ ij - алгоритм соответствующих действий, запущенных в момент ti . Данная пара называется активностью или минимальным элементом, из которых строится имитационная модель. Активность – это наименьшая единица работы модели, работа происходит в результате выполнения активности. Активность относится к динамическим объектам имитационного моделирования. В сложных системах имеется большое число компонентов K i , следовательно, и большое количество ФД ij и активностей. Необходимо обеспечить имитацию параллельности событий и необходимую синхронизацию событий в дискретные моменты времени. Для обеспечения параллельности синхронизации используют глобальное время t0 . С помощью t0 организуется квази- параллельная работа отдельных компонент K i . Последовательно выполняются совпавшие ФД ij при некотором неизменном значении модельного времени t0  const . Когда выполнены все ФД ij , для каждого компонента системы вычисляется следующий момент времени: ti '  ti   ij , где ti ' - новое модельное время компоненты K i . Тогда глобальное время будет вычисляться как минимальное из новых ближайших моментов: t0  min(ti ') . i Наряду с сущностями – активностями в имитационном моделировании используется понятие процесс. Процесс – это логически связанный набор активностей. Процесс, в свою очередь, может служить активностью для более высокой иерархии моделей. 74 Процесс является динамическим объектом имитационной модели, в любой момент времени в реальной системе может протекать одновременно несколько процессов под действием различных ФД ij . Принято делить объекты на:  Активные или динамические;  Пассивные или статические. Примером статических пассивных объектом может быть функциональные средства системы; транзакты – пример активных объектов; очередь – пассивный объект. Событие - это мгновенное изменение состояния объекта, которое может распространяться на пассивные и активные объекты. Таким образом, конструктивными элементами построения имитационных моделей являются три сущности:  событие;  активность;  процесс. 3.3 Структура имитационной модели Имитационная модель состоит из двух частей: 1. выполнение активностей и условий их инициализации; 2. обеспечивает автоматизацию процедур моделирования. Вторая часть, это:  программа имитационного моделирования;  программа сбора статистики моделирования;  программа завершения моделирования и т.д. Таким образом, первая часть имитационной модели создается исследователем, а вторая часть есть технологическое средство для осуществления моделирования. 3.4 Способы формализации объектов моделирования Известны пять способов формализации объектов моделирования: 1. способ активности; 2. способ событий; 3. транзактный способ; 4. агрегатный способ; 5. процессный способ. Для каждого из этих способов разработан ряд языков программирования: 1. SMPL; 2. Симскрипт, Модис, CMPL, GASP 75 3. GPSS, ИМСС, АСИМ; 4. АИС, САПАС; 5. Сленг, Симула, MPL, PLSIM, SQL, DISLIMи др. Каждому способу формализации соответствует способ квазипараллелизма: 1. просмотр активности; 2. просмотр событий и составление расписания событий; 3. транзакты или управление обслуживанием транзактов; 4. управление агрегатами; 5. синхронизация процессов. 1) Просмотр активности наиболее эффективно используется, если ФД ij различны. При этом для выполнения каждого ФД ij требуются свои условия выполнения. Кроме того, их выполнение происходит независимодруг от друга. Имитационная модель для исследователя представляется в виде двух частей:  в виде множества активностей;  в виде множества условийинициации активности. Так как выполнение одних активностей может привести к инициализации других, то УПМ может содержать повторяющиеся циклы выполнения условий инициализации. При этом события не регламентированы, а лишь указываются условия, при которых они могут произойти. Проверка всех условий инициализации при работе УПМ может оказаться безуспешной, следовательно, возможно зацикливание. Поэтому при использовании данного способа квази параллелизма желательно использовать простые алгоритмы проверки условий инициализации. Это требование - недостаток этого способа. 2) Просмотр событий. Предыдущий недостаток устраняется, так как условия инициализации проводятся не по активности, а по событиям, то есть в данном способе в роли активности выступает событие. Этот способ целесообразно использовать, когда различные компоненты Кi могут выполнить одни и те же ФД ij , которые в свою очередь приводятся к одним и тем же событиям: Ki  ФДij  Cij , то есть когда некоторая группа ФД ij могут приводиться к одному событию, которое будет являться активностью. Имитационная модель для исследователя состоит из двух частей:  набор проверок появления событий;  инициализация соответствующих активностей, то есть событий. Объединение активностей в группы сокращает размеры циклов работы УПМ. Этот способ считается более экономичным, чем первый, но появляется свой недостаток: необходимо объединять активности различных компонент в составе процедур обслуживания событий. Такое объединение может привести к созданию модели, имеющей плохую адекватность к созданию модели. 76 Транзактный способ. Эффективен, когда ФД ij для различных компонент Кi имеют одинаковый смысл, то есть каждое ФД ij можно представить как набор простейших операций, которые можно аппроксимировать с помощью активностей. При этом способе возможен учет взаимосвязи между активностями. Взаимосвязь можно показать в виде СМО, однотипные активности объединяются в виде приборов СМО. Инициаторами появления событий Cij в приборах являются транзакты, которые в результате своего обслуживания создают весь алгоритм работы модели. Связь между приборами осуществляется с помощью очередей, дисциплины подачи, способов удаления транзактов. Модель создается в два этапа: 1. Отражаются источники заявки и их поглотители, 2. Отражается пространство их продвижений. Для описания используются стандартные блоки описания транзактов. С их помощьюмоделируются действия по образованию и исключению транзактов из системы. Недостаток: возникают дополнительные расходы машинного времени из-за большого списка транзактов и блоков, которые необходимо неоднократно просматривать при анализе ЦТС. 3) 4) Агрегативный способ. Эффективен, когда между компонентами системы Кi существует тесная взаимосвязь, когда выходной сигнал одних компонентов являются входными для других, то есть математически можно описать систему базируясь на модульном принципе. В общем случае каждый модуль имеет уникальную структуру. Моделирование поведения агрегата представляется как последовательная цепь переходов из одного состояния в другое. При этом выдается пять основных шагов работы агрегативных систем: 1. начальная установка состояний агрегата; 2. определение момента времени, в котором произойдет следующее событие в агрегатах; 3. определение нового состояния агрегата и формирование выходного вектора Y; 4. проверка множества выходных сигналов Y и, если необходимо в соответствии с матрицей коммутации агрегатов, определение номера канала, по которому передается выходной сигнал и номер канала, по которому поступают входные сигналы; 5. определение нового состояния агрегата. Целесообразно использовать этот метод при моделировании особо сложных объектов. Однако создание матрицы коммутации агрегатов может потребоваться значительное машинное время. 77 5) Процессный способ может быть использован при следующих условиях:  Все ФД ij компоненты различны;  Условия появлений событийиндивидуальны, но каждая компонента Кi осуществляет определенную последовательность выполнения ФД ij . Эта последовательность и формирует некоторые процесс. При этом способе сочетаются преимущества первого и второго способа: 1. краткость описания активности; 2. эффективность событийного представления имитации. Считается, что этот способ наиболее полезен, когда требуется выполнить высокий уровень детализации ФД ij . При этом модель имеет большое сходство с оригиналом, как по функционированию, так и по структуре. Принципиально для любого реального объекта моделирования можно применять любой способ имитационного моделирования, несмотря на ограничения. 78