книги / Моделирование систем

с абсолютным и относительным приоритетами. Заявки с абсолют­ ным приоритетом при выборе из очереди в накопитель вытесняют из канала заявки с более низким классом приоритета, которые при этом снова поступают в накопитель (в начало или конец очереди) или считаются потерянными, а заявки с относительным приорите­ том дожидаются окончания обслуживания каналом предыдущей заявки. Эти особенности учитываются в моделирующих алгорит­ мах приоритетных Q-схем, при определении времени освобождения канала и выборе претендентов на его занятие. Если наличие аб­ солютных приоритетов приводит к потере заявок, то необходимо организовать фиксацию потерянных заявок.

4. Ограничение по времени пребывания заявок в системе. В этом случае возможно ограничение как по времени ожидания заявок в накопителях, так и по времени обслуживания заявок каналами, а также ограничение по сумме этих времен, т. е. по времени пребы­ вания заявок в обслуживающем приборе. Причем эти ограничения могут рассматриваться как применительно к каждой фазе, так и к Q-схеме в целом. При этом необходимо в качестве особых состояний Q-схемы рассматривать не только моменты поступления новых заявок и моменты окончания обслуживания заявок, но и мо­ менты окончания допустимого времени пребывания (ожидания, об­ служивания) заявок в Q-схеме.

5. Выход элементов системы из строя и их дальнейшее вос­ становление. Такие события могут бьггь рассмотрены в Q-схеме, как потоки событий с абсолютными приоритетами, приводящими к потере заявок, находящихся в обслуживании в канапе или ожида­ ющих начала обслуживания в накопителе в момент выхода соответ­ ствующего элемента из строя. В этом случае в моделирующем алгоритме Q-схемы должны быть предусмотрены датчики (генера­ торы) отказов и восстановлений, а также должны присутствовать операторы для фиксации и обработки необходимой статистики.

Рассмотренные моделирующие алгоритмы и способы их моди­ фикации могут быть использованы для моделирования широкого класса систем. Однако эти алгоритмы будут отличаться по сложно­ сти реализации, затратам машинного времени и необходимого объема памяти ЭВМ.

Дадим краткую сравнительную оценку сложности различ­ ных моделирующих алгоритмов Q-схем, в основу построения ко­ торых положены перечисленные принципы. Детерминированный и асинхронный циклический алгоритмы наиболее просты с точ­ ки зрения логики их построения, так как при'этом использует­ ся перебор всех элементов Q-схемы на каждом шаге. Трудности возникают с машинной реализацией этих алгоритмов вследствие увеличения затрат машинного времени на моделирование, так как просматриваются все состояния элементов Q-схемы (по «при­ нципу А/» или по «принципу <5z»). Затраты машинного времени на моделирование существенно увеличиваются при построении

281

Рис. 8.14. Блок-диаграмма моделирующего алгоритма в символике языка GPSS

детерминированных моделирующих алгоритмов Q-схем, элементы которых функционируют в различных масштабах времени, напри­ мер когда длительности обслуживания заявок каналами многока­ нальной Q-схемы значительно отличаются друг от друга.

В стохастическом синхронном алгоритме рассматриваются про­ шлые изменения состояний элементов Q-схемы, которые произош­ ли с момента предыдущего просмотра состояний, что несколько усложняет логику этих алгоритмов.

Асинхронный спорадический алгоритм позволяет просматри­ вать при моделировании только те элементы Q-схемы, изменения состояний которых могли иметь место на данном интервале систем­ ного времени, что приводит к некоторому упрощению этих модели­ рующих алгоритмов по сравнению с синхронными алгоритмами и существенному уменьшению затрат машинного времени по срав­ нению с детерминированными и циклическими алгоритмами.

Затраты необходимой оперативной памяти ЭВМ на проведение имитации могут быть значительно уменьшены при построении блочных моделей, когда отдельные блоки (модули) Q-схемы ре­ ализуются в виде процедур (подпрограмм).

К настоящему времени накоплен значительный опыт модели­ рования Q-схем (при их классическом рассмотрении или в раз­ личных приложениях). Рассмотренные моделирующие алгоритмы

Рис. 8.15. Программа реализации моделирующего алгоритма на языке GPSS

283

позволяют практически отразить всевозможные варианты много­ фазных и многоканальных Q-схем, а также провести исследование всего спектра их вероятностно-временных характеристик, различ­ ных выходных характеристик, интересующих исследователя или разработчика системы S.

Рассмотрим особенности моделирования систем, формализуе­ мых в виде Q-схем, с использованием языка имитационного моде­ лирования GPSS. В этом случае отпадает необходимость выбора принципа построения моделирующего алгоритма, так как механизм системного времени и просмотра состояний уже заложен в систему имитации дискретных систем, т. е. в язык GPSS [33, 47].

Пример 85. Использование языка GPSS рассмотрим при моделировании Q- схемы, схема которой приведена на рис. 8.6. Блок-диаграмма моделирующего ал­ горитма в символике языка GPSS представлена на рис. 8.14. Условные обозначения отдельных блоков были приведены в табл. 5.2. Как ухе отмечалось, блок-диаграмма

пи и GPSS позволяет генерировать адекватные программы имитации. Пример

программы на языке GPSSпоказан на рис. 8.15. Действия операторов блок-диаграм­ мы (и программы) GPSS для данного примера приведены в табл. 8.1. При этом приняты следующие обозначения: NAKIsHi, KANKJ=К * , j.

284

Из приведенных примеров моделирования системы S, форм­ ализуемой в виде Q-схемы, видно, что при использовании для реализации как универсального алгоритмического языка, так и язы­ ка имитационного моделирования GPSS возможности по оценке в процессе имитации вероятностно-временных характеристик ис­ следуемых систем существенно расширяются по сравнению с приме­ нением аналитического подхода, когда получение оценок в явном виде ограничено результатами, полученными в теории массового обслуживания.

8.3. МОДЕЛИРОВАНИЕ ПРОЦЕССОВ ФУНКЦИОНИРОВАНИЯ СИСТЕМ НА БАЗЕ N-CXEM

Особенности использования при моделировании систем сетевого подхода, реализуемого в виде N-схем, и основные понятия сетей Петри и их модификаций были даны в § 2.6. Рассмотрим возмож­ ности применения N-схем для формального описания процесса функционирования некоторой моделируемой системы S. Характер­ ной особенностью N-схем является то, что с их помощью можно моделировать процессы в системах S, в которых происходит после­ довательная смена дискретных состояний, в том числе если эта смена происходит при выполнении разнообразных условий. Таким образом, с использованием N-схем могут быть описаны системы 5, относящиеся к разным классам: аппаратные, физические, про­ граммные, экономические и т. д.

Структурный подход на базе N-схем. Применение аппарата N- схем позволяет осуществить структурный подход к построению имитационной модели системы S , при котором обеспечиваются наглядность модели, модульный принцип ее разработки (сборки), возможность перехода к автоматизированной интерактивной про-

285

Пример 8.6. Пусть процесс функционирования не­ которой реальной системы S (процессор ЭВМ, мультиплексный канал, станок в тех­ нологической цепочке и т. п.), являющийся по своей природе процессом обслужива­ ния, представлен в виде двухфазной одноканальной Q-схемы (рис. 8.16). Тогда этот процесс можно представить //-схемой, структура которой показана на рис. 8.17.

Чтобы маркировать эту структуру, нужно задать состояние системы. Пусть в накопителе H j находятся две заявки, в Н2 — заявок нет, канал обслуживания Kj свободен. Такому состоянию соответствует маркировка, показанная на рис. 8.18. Процесс выполнения этой N-схемы моделирует процесс функционирования системы S, представленной в виде Q-схемы.

Через переход dx эта N-схема может быть сведена с другой N-схемой, моделиру­ ющей процесс порождения заявок на обслуживание, аналогично — по переходу dA— с системой потребления заявок.

Пример 8.7. Пусть имеется некоторая система 5, например производственно­ технологическая, процесс функционирования которой представлен в виде Q-схемы (рис. 8.19). По технологическому циклу для выполнения заказа необходимо выпол­ нить две фазы обслуживания; сначала обслуживание в канале К 1з затем либо в К 2, либо в К». Операторы Fx и F2 обслуживают (поддерживают в работоспособном состоянии) каналы, причем Fx обслуживает К2 и К2, a F2 — К 2 и К3.

Тогда в этой системе могут быть следующие состояния: а — заказ пришел и ждет в накопителе Н^;

б— заказ обработан К х и ждет в накопителе Н2;

в— заказ выполнен и находится в накопителе Н3;

г— канал К 2 не занят;

д — канал К2 не занят; е — канал К 3 не занят;

ж — оператор Fx не занят; з — оператор F2 не занят;

и— канал К2 выполняет заказ под управлением Fx;

к— канал К! выполняет заказ под управлением F2;

286

стемы, при котором каналы свободны, операторы не заняты, в системе нет заказов (рис. 8.20).

Синхронизация событии в N-схемах. Из приведенных примеров видно, что для в ы п о л н е н и я каждого события (перехода) необходи­ мо выполнение определенных условий. Эти условия в N-схемах (сетях Петри) называются предусловиями. Выполнение события мо­ жет вызвать нарушение предусловий и привести к выполнению условий для совершения других событий — постусловий.

Для примера 8.7 построена таблица предусловий и постусловий (табл. 8.2). Эта таблица является описанием структуры N-схемы, удобным для ввода в ЭВМ. Кроме таблицы для выполнения процес­ са моделирования должна быть задана начальная маркировка в ви­ де ц-мерного вектора. Для примера 8.7;

М = (О, О, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0).

287

Процесс моделирования заключается в последовательном вычи­ слении маркировок, получающихся в результате выполнения собы­ тий (переходов). События, по которым нет предусловий, являются входами N-схемы. Каждый вход должен быть присоединен к моде­ ли, генерирующей запуск события в соответствии с условиями, определяемыми моделируемой реальностью. В частности, это мо­ жет быть другая N-схема, моделирующая процесс появления этих событий.

В N-схемах два или несколько разрушенных невзаимодейству­ ющих событий могут происходить независимо друг от друга, т. е. N-схемам и их моделям свойствен параллелизм, или одновремен­ ность. Синхронизировать события, пока этого не требует моделиру­ емая система, нет нужды. Таким образом, N-схемы удобны для моделирования системы с распределенным управлением, в которых несколько процессов выполняются одновременно.

Другая важная особенность N-схем — это их асинхронная при­ рода. Внутри N-схемы отсутствует измерение времени. Для просто­ ты обычно вводят следующее ограничение. Запуск перехода (и соответствующего события) рассматривается как мгновенное собы­ тие, занимающее нулевое время, а возникновение двух событий одновременно невозможно. Моделируемое таким образом событие называется примитивным (примитивные события мгновенны и не­ одновременны).

Непримитивными называются такие события, длительность ко­ торых отлична от нуля. Любое непримитивное событие может быть представлено в виде двух примитивных событий: «н&чало неприми­ тивного события», «конец непримитивного события» — и состоя­ ния (условия) «непримитивное событие происходит».

Задание

ожидает

выбода

Выдача

задания

Рис. 8.21. Структура N-схемы с непримитивными (а) и примитивными (б) событиями

288

Пример 8.8. Рассмотрим особенности использования по* нятий примитивных и непримитивных событий на примере обработки заданий процессором ЭВМ. На рис. 8.21 пред­ ставлены N -схемы (эквивалентные сети Петри) для модели­ рования обработки задания в процессоре с применением перехода, соответствующего непримитивному событию (рис. 8.21, а), и с применением только переходов — прими­ тивных событий (рис. 8.21, б).

невозможно одновременное выполнение двух разрешенных перехо­ дов, изображена на рис. 8.22, где два разрешенных перехода djB.dk находятся в конфликте. Может быть запущен только один из

них, так как при запуске он удаляет метку из общего входа и запре­ щает другой переход.

Моделирование параллельных процессов. Возможность модели­ рования параллелизма и довольно простые процедуры объединения подсистем, представленных N-схемами, делают их весьма полезным инструментом моделирования сложных аппаратно-программных информационно-вычислительных комплексов и сетей, состоящих из большого количества одинаковых компонент. Поясним это следу­ ющим примером.

Првмер 8.9. Рассмотрим процесс функционирования ЭВМ с конвейерной об­ работкой. При построении высокопроизводительных асинхронных ЭВМ широко применяют метод конвейерной обработки чисел. Этот метод обработки подобен функционированию сборочного конвейера и особенно удобен для работы с век­ торами и массивами. Конвейер состоит из набора операций, которые могут выпол­ няться одновременно в разных блоках ЭВМ. Когда операция в Аг-м блоке завершает­ ся, ее результат передается в (£+ 1)-й блок, а к-й блок принимает результат операции из (к—1)-го блока. Если каждая операция запускается по завершении предыдущей, то имеем дело с асинхронным способом управления конвейером. Для управления к-м блоком такого конвейера необходима информация о выполнении следующих усло­ вий:

—входной регистр заполнен;

—входной регистр пуст;

—выходной регистр заполнен;

—выходной регистр пуст;

—блок к занят;

—блок к свободен;

—пересылка осуществляется.

На рис. 8.23, а показано, как строится N -схема для моделирования асинхронного конвейера такого типа, причем эта модель позволяет анализировать взаимодействия между блоками, игнорируя конкретные детали процессов, которые происходят внут­ ри блоков. Эти процессы в свою очередь могут быть промоделированы N -схемами и соединены между собой в соответствии со схемой, показанной на рис. 8.23, б. Такая возможность построения иерархических моделей может быть весьма полезной при моделировании сложных систем S .

Рис. 8.23. Блок-схема (а) и модель (б) устройства управле­ ния асинхронной ЭВМ с конвейерной обработкой

Особенности программирования N-схем. Как уже отмечалось, N-схема представляет собой формализованное описание процесса функционирования системы 5, причем структура N-схем отражает причинно-следственные связи в системе 5, а совместно с начальной маркировкой — процессы, которые в этой системе происходят. Та­ ким образом, переход от N-схем к моделирующей программе мо­ жет производиться формальным путем, т. е. автоматически, с ис­ пользованием специального языка и транслятора. Такие языки и трансляторы созданы за рубежом и в нашей стране [4, 24, 28, 29, 30, 50, 54].

Рассмотрим особенности программирования N-схем, моделиру­ ющих процессы в системе 5, на конкретных примерах.

Пример 8.10. Рассмотрим принципы программирования N-схем в языке MODAL, который предназначен для моделирования и реализации вычислительных алгорит­ мов на базе N-схем (сетей Петри). Он содержит семь операторов:

START — описание начальной маркировки; STOP — описание конечной маркировки; T(MOD) — описание структуры сети Петри;

TYPE — оператор промежуточного вывода на печать; SOMMENT

COMPLEKXITY

END — конец.

Операторы START и STOP представляют собой списки позиций, в которых устанавливаются метки в начале и должны оказаться в конце моделирования.

290