Главная > Разное > Моделирование систем
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

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

НА БАЗЕ N-CXEM

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

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

процедуре проектирования [30, 33, 54]. Рассмотрим особенности такого подхода, используя для общности и простоты понятия, введенные в § 8.2 для Q-схем, на следующих примерах.

Рис. 8.16. Моделируемый процесс обслуживания реальной системы

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

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

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

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

а — заказ пришел и ждет в накопителе Н

б - заказ обработан и ждет в накопителе

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

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

д — канал не занят;

е — канал не занят;

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

з — оператор не занят;

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

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

Рис. 8.17. Структура N-схемы

Рис. 8.18 Маркировка структуры

л - канал выполняет заказ под управлением ;

м — канал выполняет заказ под управлением и могут происходить следующие события-переходы:

1 поступление заказа;

2 - начинает выполнение заказа на ;

3 - закончил выполнение заказа на

4 - начинает выполнение заказа на ;

5 - закончил выполнение заказа на

6 - начинает выполнение заказа на ;

7 - закончил выполнение заказа на ;

8 - начинает выполнение заказа на ;

9 - закончил выполнение заказа на

10 — заказ отправляется на доставку.

Рис. 8.19. Моделируемый процесс обслуживания

Рис. 8.20. Структура N-схемы

После этого построение N-схемы происходит формально: состояниям системы соответствуют позиции N-схемы, событиям — переходы. Нанесем маркировку, соответствующую такому состоянию системы, при котором каналы свободны, операторы не заняты, в системе нет заказов (рис. 8.20).

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

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

Таблица 8.2 (см. скан)

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

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

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

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

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

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

Рис. 8.22. Конфликт двух переходов в N-схеме

Ранее упоминалось, что в N-схемах все разрешенные переходы срабатывают одновременно и независимо. Однако с помощью N-схем можно моделировать и такие системы S, в которых порядок запуска в разрешенных переходах имеет существенное значение. Ситуация, в которой невозможно одновременное выполнение двух разрешенных переходов, изображена на рис. 8.22, где два разрешенных перехода находятся в конфликте. Может быть запущен только один из них, так как при запуске он удаляет метку из общего входа и запрещает другой переход.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рис. 8.24. Структура N-схемы с начальной маркировкой (а) и ее описание на языке MODAL

Оператор T(MOD) представляет собой таблицу пред- и постусловий для каждого перехода N-схем.

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

Кроме описания структуры должны быть составлены программные модули — описания переходов (событий) причем все модули должны содержать единую для данного набора COMMON-область, которая служит для передачи данных между модулями.

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

Расширение N-схем. Возможные расширения N-схем, заданных в виде сетей Петри, о которых говорилось в § 2.6, рассмотрим с точки зрения их прикладного использования, т. е. с ориентацией на увеличение моделирующих возможностей данного аппарата. Для моделирования процессов в информационных системах наибольший интерес представляют N-схемы в виде временных сетей и Е-сетей, являющихся наиболее мощным расширением сетей Петри [28].

Задание временной сети, т. е. включает семь множеств

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

Фактор времени учитывается в -схемах путем введения пассивного состояния метки в позиции. При поступлении метки в позицию она остается в пассивном состоянии (не может участвовать в возбуждении переходов) на время и только после этого переходит в активное состояние.

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

Пример 8.11. Построим в виде -схемы модель микропроцессорного абонентского пункта информационно-вычислительной сети [30, 54,]. Структура этого показана на рте. 8.25, где обозначено: — микропроцессор; ОЗУ — оперативное запоминающее устройство; — периферийный адаптер; — электрифицированная пишущая машинка; и — входной и выходной каналы связи.

Задание -схемы в виде временной сети включает в себя задание структуры , вектора разметок и вектора задержек

Структуру -схемы графически, та» как именно графическое представление обладает наибольшей наглядностью и простотой соотношения со структурой объекта, т. е. в данном примере со структурой На рис. 8.26 для наглядности пунктиром выделены элементы -схемы, относящиеся к конкретным элементам структуры (рис. 8.25).

Вектор разметок имеет вид

а вектор задержек

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

Еще большие возможности для моделирования сложных систем дают такие расширения N-схем, как Е-сети, которые обозначим как N-схемы. В отличие от временных сетей в Е-сетях определено дополнительно четыре типа переходов: разветвление, объединение, управляемое разветвление и приоритетное объединение. Важной особенностью N-схем является также детализация представления метки. С каждой меткой в N-cxeмe

Рис. 8.25. Структура АП

Рис. 8.26. Структура N-схемы (см. скан)

связавы описателей. Каждый из описателей метки несет в себе определенную количественную информацию о моделируемом объекте, т. е. системе S.

Структурное задание модели элементов системы S в форме -схемы позволяет использовать модульный принцип разработки имитационной модели с применением библиотеки -сетевых модулей и их параметрической настройки. В этом случае -сетевая модель является основой для сборки имитационной программы из модулей, реализованных на некотором языке программирования [30, 54].

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

Пример 8.12. Поступление метки во входную позицию перехода (рис. 8.27) инициирует процедуру проверки готовности перехода к срабатыванию (рис. 8.28). Проверяемые при этом условия включают в себя анализ разметки решающей позиции где а также проверку разметки выходных позиций и сопряженных позиций . В том случае, когда на данной фазе производится также вычисление решающей процедуры перехода

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

Процедура перехода выполняется в два этапа: сначала вычисляются предикаты а затем реализуется требуемое подмножество операций над описателями меток Далее переход вступает в фазу завершения, содержанием которой

Рис. 8.27. Обобщенная структура Е-сетевого перехода

является смена разметки входных и выходных позиций перехода Разметка позиции , меняется на нулевую: При разметка решающей позиции становится неопределенной: Затем выполняется перемещение меток в ряд выходных позиций в соответствии с типом данного перехода. Эта операция завершает работу перехода по обработке поступившей метки

Рис. 8.28. Алгоритм работы Е-сетевого перехода. (см. скан)

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

Использование ЯИМ. Программная реализация моделей систем S на базе расширенных N-схем более сложна по сравнению с программированием моделей на основе обычных сетей Петри. Для упрощения перехода к моделирующей программе рационально использовать языки имитационного моделирования Рассмотрим особенности использования ЯИМ для имитации на базе N-схем на примере применения системы моделирования GPSS, которая детально была рассмотрена ранее.

Пример 8.13. Проведем анализ соответствия между элементами и объектами языка моделирования GPSS (см. § 5.3). В результате сравнительного анализа можно сформулировать следующее 37.

1. Метка -схемы может быть представлена динамическим объектом GPSS, т. е. транзактом.

2. Описатели меток аналогичны параметрам транзактов GPSS.

3. Позиция -схемы идентична объекту, принадлежащему к аппаратной категории GPSS типа накопителя единичной емкости.

4. Решающие позиции -схемы в зависимости от принадлежности к множеству реализуются двумя способами: а) если А то А эквивалентна набору объектов типа булевых переменных вычислительной категории если то А может быть представлена накопителем единичной емкости аппаратной категории GPSS.

5. Временные параметры переходов реализуются объектом ADVANCE операционной категории

6. Операции вычисления предикатов для соответствует применение блока изменяющего маршруты транзактов, в сочетании с булевыми переменными вычислительной категории GPSS.

7. Операции для выполняются с помощью блоков динамической категории GPSS в сочетании с арифметическими переменными.

8. Хранение значений описателей меток можно имитировать путем записи значений параметров транзактов в ячейки хранимых значений с помощью блока SAVEVALVE запоминающей категории GPSS.

9. Процессы синхронизации движения меток через переход и удаления меток из решающей позиции могут быть обеспечены с помощью логических переключателей и аппаратной категории GPSS.

10. Макропоэиция генератора аналогична блоку GENERATE динамической категории GPSS.

И. Макропоэиция поглощения функционально идентичена блоку TERMINATE динамической категории GPSS.

12. Макропозиция очереди может интерпретироваться в GPSS записью транзак-та в цепь пользователя.

Таким образом, рассмотренное представление моделей элементов информационных систем в виде позволяет упростить этап определения их базовой структуры. Задание модели в виде -схем допускает достаточно простую программную реализацию имитационной модели на ЯОН или ЯИМ.

<< Предыдущий параграф Следующий параграф >>
Оглавление