Макеты страниц 8.2. МОДЕЛИРОВАНИЕ ПРОЦЕССОВ ФУНКЦИОНИРОВАНИЯ СИСТЕМ НА БАЗЕ Q-CXEMОсобенности использования при моделировании систем непрерывно-стохастического подхода, реализуемого в виде Q-схем, и основные понятия массового обслуживания были даны в § 2.5. Рассмотрим возможности использования Q-схем для формального описания процесса функционирования некоторой системы S. Характерная ситуация в работе таких систем — появление заявок (требований) на обслуживание и завершение обслуживания в случайные моменты времени, т. е. стохастический характер процесса их функционирования. В общем случае моменты поступления заявок в систему S из внешней среды Е образуют входящий поток, а моменты окончания обслуживания образуют выходящий поток обслуженных заявок [6, 13, 39, 51, 53]. Формализация на базе Q-схем. Формализуя какую-либо реальную систему с помощью Q-схемы, необходимо построить структуру такой системы. В качестве элементов структуры Q-схем будем рассматривать элементы трех типов: И — источники; Н — накопители; К — каналы обслуживания заявок. Пример структуры системы S, представленной в виде Q-схемы, приведен на рис. 8.4. Кроме связей, отражающих движение заявок в Q-схеме (сплошные линии), можно говорить о различных управляющих связях. Примером таких связей являются различные блокировки обслуживающих каналов (но входу и по выходу): «клапаны» изображены в виде треугольников, а управляющие связи — пунктирными линиями. Блокировка канала по входу означает, что этот канал отключается от входящего потока заявок, а блокировка канала по выходу указывает, что заявка, уже обслуженная блокированным каналом, остается в этом канале до момента снятия блокировки (открытия «клапана»). В этом случае, если перед накопителем нет «клапана», при его переполнении будут иметь место потери заявок. Помимо выходящего потока обслуженных заявок можно говорить о потоке потерянных заявок.
Рис. 8.4. Структура системы, представленной в виде Q-схемы Как отмечалось выше, Q-схему можно считать заданной, если определены: потоки событий (входящие потоки заявок и потоки обслуживаний для каждого Н и К); структура системы S (число фаз Рассмотрим возможности формализации воздействий внешней среды Е, представляемых в Q-схемах в виде источников
сводится к рассмотренным ранее методам машинной имитации Так, для ординарных потоков с ограниченным последействием интервалы между моментами поступления заявок являются независимыми и совместная плотность распределения может быть представлена в виде произведения частных законов распределения: Если поток с ограниченным последействием удовлетворяет условию стационарности, т. Плотность распределения первого интервала
где Порядок моделирования моментов появления заявок в стационарном потоке с ограниченным последействием следующий. Из последовательности случайных чисел, равномерно распределенных на интервале
где Пример 8.2. Пусть при моделировании некоторой системы необходимо сформировать на ЭВМ простейший поток заявок. Распределение длин интервалов между заявками является экспоненциальным, т. е. Используем формулу Пальма для определения первого интервала у, т. е.
Из этого выражения следует, что Пример 8.3. Пусть при моделировании некоторой системы требуется сформировать на ЭВМ поток событий, равномерно распределенных на интервале Распределение первого интервала между началом отсчета и первым событием
Интенсивность потока
Заметим, что математическое ожидание первого интервала
Длины интервалов между событиями будут
Так, например, при
где Пример 8.4. Рассмотрим формирование на ЭВМ потока Эрланга, в котором между последовательными событиями закон распределения интервалов
Пусть
Для определения
При Тогда
Если реализация моделируемого случайного процесса оказывается достаточно длинной, то можно положить Проведем анализ принципов формирования потока событий, описываемого нестационарным распределением Пуассона с мгновенной плотностью потока С учетом выражения
где На основании соотношения
Из (8.3) аналитически или любым приближенным способом определяется
где Уравнение для нахождения очередного значения интервала имеет вид Чтобы описать неординарные потоки событий, для которых Вопросы построения и машинной реализации программных генераторов, имитирующих потоки событий, были рассмотрены в гл. 4, поэтому более подробно остановимся на особенностях построения моделирующих алгоритмов процесса функционирования таких элементов Q-схем, как накопители Способы построения моделирующих алгоритмов Q-схем. Моделирующий алгоритм должен адекватно отражать процесс функционирования системы S и в то же время не создавать трудностей при машинной реализации модели Мы. При этом моделирующий алгоритм должен отвечать следующим основным требованиям: обладать универсальностью относительно структуры, алгоритмов функционирования и параметров системы При этом необходимо иметь в виду, что появление одной заявки входящего потока в некоторый момент времени Известно, что существует два основных принципа построения моделирующих алгоритмов: «принцип построения адекватной модели Классификация возможных способов построения моделирующих алгоритмов Q-схем приведена на рис. 8.5.
Рис. 8.5. Классификация способов построения моделирующих алгоритмов Q-схем Более подробно особенности построения и реализации перечисленных разновидностей моделирующих алгоритмов будут рассмотрены при моделировании конкретных вариантов систем. Особенности моделирования на базе Q-схем. Математическое обеспечение и ресурсные возможности современных ЭВМ позволяют достаточно эффективно провести моделирование различных систем, формализуемых в виде Q-схем, используя либо пакеты прикладных программ, созданные на базе алгоритмических языков общего назначения, либо специализированные языки имитационного моделирования. Но прежде чем применять эти средства автоматизации моделирования, необходимо глубже вникнуть в суть процесса построения и реализации моделирующих алгоритмов [4, 7, 17, 23, 32, 46]. Пример 8.5. Для более детального ознакомления с технологией машинной имитации остановимся на рассмотрении Q-схемы достаточно обшего вида, показанной на рис 8.6. В частности, разберем на данном примере, какое влияние оказывает на особенности построения схемы моделирующего алгоритма принцип, положенный в основу его машинной реализации.
Рис. 8.6. Пример Q-схемы общего вида На рисунке представлена трехфазная Q-схема Для имитационной модели рассматриваемой Q-схемы можно записать следующие переменные и уравнения: эндогенная переменная Р — вероятность потери заявок; экзогенные переменные: При имитации процесса функционирования Q-схемы на ЭВМ требуется организовать массив состояний. В этом массиве должны быть выделены: подмассив К для запоминания текущих значений Процедура моделирования процесса обслуживания каждым элементарным каналом К., сводится к следующему. Путем обращения к генератору случайных чисел с законом распределения, соответствующим обслуживанию данных К получается длительность времени обслуживания и вычисляется время окончания обслуживания Детерминированный моделирующий алгоритм. Укрупненная схема детерминированного моделирующего алгоритма Q-схемы, т. е. алгоритма, построенного по принципу условий (блок 3). Работа вспомогательных блоков — ввода исходных данных 1, установки начальных условий 2, обработки 11 и вывода результатов моделирования 12 — не отличается по своей сути от аналогичных блоков, используемых в алгоритмах вычислений на ЭВМ. Поэтому остановимся более детально на рассмотрении работы той части моделирующего алгоритма, которая отражает специфику детерминированного подхода (блоки 4 - 9). Детализированные схемы алгоритмов этих блоков приведены на рис. 8.8, а — е. На этих и последующих схемах моделирующих алгоритмов Q-схем приняты следующие обозначения: Рис. 8.7. Укрупненная схема детерминированного моделирующего алгоритма Q-схемы (см. скан) Процедура обслуживания заявок каналами Окончание обслуживания заявки в некотором канале начиная с обслуживающего канала последней фазы по направлению к накопителю 1-й фазы (см. рис. 8.6).
Рис. 8.8. Схемы алгоритмов блока
Продолжение рис. 8.8 После пуска, ввода исходных данных и установки начальных условий (блоки 1 и 2 на рис. 8.7) проверяется условие окончания моделирования системы (блок 3). Затем переходят к имитации обслуживания заявок каналом Далее реализуется переход к моделированию работы каналов 2-й фазы Q-cxeмы (рис. 8.8, б). При этом проводится последовательный просмотр каналов, этой фазы (операторы 5.1, 5.9 и Затем имитируется взаимодействие в процессе обслуживания заявок в накопителе и каналов 2-й фазы последовательно для каждого из каналов (операторы 6.1, 6.7 и 6.8 на рис. 8.8, а). Далее, если в накопителе Потом имитируется взаимодействие конкретного канала 1-й фазы и накопителя 2-й фазы Продолжение рис. 8.8. (см. скан) (оператор 7.12). Затем операторы 7.3 и 7.4 повторяются, так как одновременно из 1-й фазы во 2-ю могут переместиться две заявки. При третьем выполнении операторов 7.13 и 7.14 управление будет передано по условию «Да» следующему блоку 8 (см. рис. 8.7). Продолжение рис. 8.8 (см. скан) Затем имитируется взаимодействие в процессе обслуживания заявок в накопителе и каналов 1-й фазы (операторы 8.1, 8.7 и 8.8 на рис. 8.8, д). Проверяется необходимость и возможность обслуживания каналами Далее имитируется взаимодействие источника Затем управление снова передается блоку 3 (рис. 8.7), который при наборе необходимой статистики проводит обработку и выдачу результатов моделирования, а затем остановку моделирования (блоки 77 и 12). Синхронный моделирующий алгоритм. Рассмотрим особенности построения моделирующих алгоритмов той же Q-схемы, структура которой приведена на рис. 8.6, по «принципу Продолжение рис. 8.8 (см. скан) Каналом имеющим минимальное время окончания обслуживания, является тот, для которого
Укрупненная схема синхронного моделирующего алгоритма представлена на рис. 8.9. Работа большинства блоков этой схемы аналогична детально рассмотренной схеме детерминированного моделирующего алгоритма (см. рис. 8.7). Поэтому остановимся более подробно только на взаимодействии синхронизирующего элемента, т. е. источника Рис. 8.9. Укрупненная схема синхронного моделирующего алгоритма Q-схемы (см. скан) входного потока в накопитель На этой схеме вспомогательными являются операторы 6.1, 6.5 — 6.8. Проверяется наличие свободных каналов 1-й фазы (оператор 6.2). Если среди каналов 1-й фазы Асинхронный моделирующий алгоритм. Рассмотрим особенности построения асинхронного моделирующего алгоритма, который Рис. 8.10. Схема алгоритма блока 6 (рис. 8. 10) (см. скан) отличается от синхронного отсутствием ведущего (синхронизирующего) элемента, причем очередному шагу моделирования соответствует особое состояние, т. е. момент окончания обслуживания одной из заявок любым каналом или момент поступления заявки из источника. При использовании такого принципа построения моделирующего алгоритма целесообразно процесс изменения состояний элементов Q-схемы рассматривать в направлении, противоположном направлению движения заявок в системе. Это можно сделать, циклически просматривая на каждом шаге моделирования все элементы Q-схемы и определяя, какие переходы заявок из одного элемента в другой могут иметь место в данный момент системного времени. Такой асинхронный циклический моделирующий алгоритм в плане просмотра состояний элементов Q-схемы тождествен детерминированному моделирующему алгоритму, который приведен на рис. 8.7. Отличие заключается лишь в том, что отсчет системного времени проводится следующим образом:
т. е. время очередного шага определяется как минимум из минимальных времен окончания начатого обслуживания всеми каналами всех фаз Q-схемы и минимального времени поступления очередных заявок из источника. В силу указанных причин не будем подробно останавливаться на рассмотрении асинхронного циклического моделирующего алгоритма Q-схемы, а рассмотрим только укрупненную схему, приведенную на рис. 8.11. Рис. 8.11. Укрупненная схема асинхронного циклического моделирующего алгоритма Q-схемы (см. скан) В асинхронных спорадических моделирующих алгоритмах в отличие от циклических для каждого момента системного времени Укрупненная схема асинхронного спорадического моделирующего алгоритма, реализующего «принцип
Рис. 8.12. Укрупненная схема асинхронного спорадического моделирующего алгоритма Q-схемы (см. скан) — это минимальное время освобождения канала Рассмотренные алгоритмы моделирования многофазовой многоканальной Q-схемы, конечно, по своей общности не охватывают всех тех разновидностей Q-схем, которые применяют в практике анализа и синтеза систем. Однако эти конкретные примеры моделирования позволяют детально ознакомиться с основными принципами построения моделирующих алгоритмов таких систем, причем эти принципы инвариантны к виду и сложности моделируемой системы S. Рис. 8.13. Схема алгоритма блока 3 (рис 8. 12) (см. скан) Возможности модификации моделирующих алгоритмов Q-схемы. В плане усложнения машинных моделей Мы при исследовании вариантов системы S можно - рассмотреть следующие модификации: 1. Наличие потоков заявок нескольких типов. В этом случае необходимо иметь несколько источников (генераторов) заявок и фиксировать признак принадлежности заявки к тому или иному потоку тогда, когда накопители и каналы рассматриваемой Q-схемы критичны к этому признаку или требуется определить характеристики обслуживания заявок каждого из потоков в отдельности. 2. Наличие приоритетов при постановке заявок в очередь в накопитель. В зависимости от класса приоритета заявок может быть рассмотрен случай, когда заявки одного класса имеют приоритет по записи в накопитель (при отсутствии свободных мест вытесняют из накопителя заявки с более низким классом приоритета, которые при этом считаются потерянными). Этот фактор может быть учтен в моделирующем алгоритме соответствующей Q-схемы путем фиксации для каждого накопителя признаков заявок, которые в нем находятся (путем организации соответствующего массива признаков). 3. Наличие приоритетов при выборе заявок на обслуживание каналов. По отношению к каналу могут быть рассмотрены заявки с абсолютным и относительным приоритетами. Заявки с абсолютным приоритетом при выборе из очереди в накопитель вытесняют из канала заявки с более низким классом приоритета, которые при этом снова поступают в накопитель (в начало или конец очереди) или считаются потерянными, а заявки с относительным приоритетом дожидаются окончания обслуживания каналом предыдущей заявки. Эти особенности учитываются в моделирующих алгоритмах приоритетных Q-схем, при определении времени освобождения канала и выборе претендентов на его занятие. Если наличие абсолютных приоритетов приводит к потере заявок, то необходимо организовать фиксацию потерянных заявок. 4. Ограничение по времени пребывания заявок в системе. В этом случае возможно ограничение как по времени ожидания заявок в накопителях, так и по времени обслуживания заявок каналами, а также ограничение по сумме этих времен, т. е. по времени пребывания заявок в обслуживающем приборе. Причем эти ограничения могут рассматриваться как применительно к каждой фазе, так и к Q-схеме в целом. При этом необходимо в качестве особых состояний Q-схемы рассматривать не только моменты поступления новых заявок и моменты окончания обслуживания заявок, но и моменты окончания допустимого времени пребывания (ожидания, обслуживания) заявок в Q-схеме. 5. Выход элементов системы из строя и их дальнейшее восстановление. Такие события могут быть рассмотрены в Q-схеме, как потоки событий с абсолютными приоритетами, приводящими к потере заявок, находящихся в обслуживании в канале или ожидающих начала обслуживания в накопителе в момент выхода соответствующего элемента из строя. В этом случае в моделирующем алгоритме Q-схемы должны быть предусмотрены датчики (генераторы) отказов и восстановлений, а также должны присутствовать операторы для фиксации и обработки необходимой статистики. Рассмотренные моделирующие алгоритмы и способы их модификации могут быть использованы для моделирования широкого класса систем. Однако эти алгоритмы будут отличаться по сложности реализации, затратам машинного времени и необходимого объема памяти ЭВМ. Дадим краткую сравнительную оценку сложности различных моделирующих алгоритмов Q-схем, в основу построения которых положены перечисленные принципы. Детерминированный и асинхронный циклический алгоритмы наиболее просты с точки зрения логики их построения, так как при этом используется перебор всех элементов Q-схемы на каждом шаге. Трудности возникают с машинной реализацией этих алгоритмов вследствие увеличения затрат машинного времени на моделирование, так как просматриваются все состояния элементов Q-схемы (по «принципу (кликните для просмотра скана) детерминированных моделирующих алгоритмов Q-схем, элементы которых функционируют в различных масштабах времени, например когда длительности обслуживания заявок каналами многоканальной Q-схемы значительно отличаются друг от друга. В стохастическом синхронном алгоритме рассматриваются прошлые изменения состояний элементов Q-схемы, которые произошли с момента предыдущего просмотра состояний, что несколько усложняет логику этих алгоритмов. Асинхронный спорадический алгоритм позволяет просматривать при моделировании только те элементы Q-схемы, изменения состояний которых могли иметь место на данном интервале системного времени, что приводит к некоторому упрощению этих моделирующих алгоритмов по сравнению с синхронными алгоритмами и существенному уменьшению затрат машинного времени по сравнению с детерминированными и циклическими алгоритмами. Затраты необходимой оперативной памяти ЭВМ на проведение имитации могут быть значительно уменьшены при построении блочных моделей, когда отдельные блоки (модули) Q-схемы реализуются в виде процедур (подпрограмм). К настоящему времени накоплен значительный опыт моделирования Q-схем (при их классическом рассмотрении или в различных приложениях). Рассмотренные моделирующие алгоритмы Рис. 8.15. Программа реализации моделирующего алгоритма на языке GPSS (см. скан) позволяют практически отразить всевозможные варианты многофазных и многоканальных Q-схем, а также провести исследование всего спектра их вероятнскггно-временных характеристик, различных выходных характеристик, интересующих исследователя или разработчика системы S. Рассмотрим особенности моделирования систем, формализуемых в виде Q-схем, с использованием языка имитационного моделирования GPSS. В этом случае отпадает необходимость выбора принципа построения моделирующего алгоритма, так как механизм системного времени и просмотра состояний уже заложен в систему имитации дискретных систем, т. е. в язык GPSS [33, 47]. Пример 8.5. Использование языка GPSS рассмотрим при моделировании Q-схемы, схема которой приведена на рис. 8.6. Блок-диаграмма моделирующего алгоритма в символике языка GPSS представлена на рис. 8.14. Условные обозначения отдельных блоков были приведены в табл. 5.2. Как ухе отмечалось, блок-диаграмма языка GPSS позволяет генерировать адекватные программы имитации. Пример программы на языке GPSS показан на рис. 8.15. Действия операторов блок-диаграммы (и программы) GPSS для данного примера приведены в табл. 8.1. При этом приняты следующие обозначения: Таблица 8.1 (см. скан) Продолжение табл. 8.1 (см. скан) Из приведенных примеров моделирования системы S, формализуемой в виде Q-схемы, видно, что при использовании для реализации как универсального алгоритмического языка, так и языка имитационного моделирования GPSS возможности по оценке в процессе имитации вероятностно-временных характеристик исследуемых систем существенно расширяются по сравнению с применением аналитического подхода, когда получение оценок в явном виде ограничено результатами, полученными в теории массового обслуживания.
|
Оглавление
|