8.3. Моделирование процессов функционирования систем

НА БАЗЕ N-CXEM

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

Структурный подход на базе N-схем. Применение аппарата N-схем позволяет осуществить структурный подход к построению имитационной модели системы S, при котором обеспечиваются наглядность модели, модульный принцип ее разработки (сборки), возможность перехода к автоматизированной интерактивной процедуре проектирования [30, 33, 54]. Рассмо­трим особенности такого подхода, используя для общности и простоты понятия, вве­денные в § 8.2 для Q-схем, на следующих примерах.

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

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

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

Пример 8.7. Пусть имеется некоторая система S, например производственно-технологическая, процесс функционирования которой представлен в виде Q-схемы (рис. 8.19). По технологическому циклу для выполнения заказа необходимо выпол­нить две фазы обслуживания: сначала обслуживание в канале К_1; затем либо в К₂, либо в К,. Операторы F₁ и F₂ обслуживают (поддерживают в работоспособном состоянии) каналы, причем .F, обслуживает К₁ и К₂, z.F₂ — K_1и К₃.

Тогда в этой системе могут быть следующие состояния:

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

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

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

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

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

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

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

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

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

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

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

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

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

2 — F₁ начинает выполнение заказа на К₁;

3 — F₁ закончил выполнение заказа на К₁;

4 —F₁ начинает выполнение заказа на К₁

5 — F₂ закончил выполнение заказа на K₁;

6 — F₁ начинает выполнение заказа на К₂;

7 — F₁ закончил выполнение заказа на К₂;

8 — F₂ начинает выполнение заказа на К₃;

9 — F₂ закончил выполнение заказа на К₃;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

START — описание начальной маркировки;

STOP — описание конечной маркировки;

T(MOD) — описание структуры сети Петри;

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

SOMMENT -вспомогательные операторы

COMPLEKXITY

END — конец.

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

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

перехода N-схем.

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

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

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

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

[28].

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

где В, D, I, О, М имеют тот же смысл, что и ранее (см. § 2.6); v=(t₁, ... ..., ti...) — возрастающая последовательность действительных чи­сел, называемая временной базой; v:Bx v=>v — функция времен­ных задержек.

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

Подклассом временной сети является сеть Мерлина, где время пассивного состояния метки определяется как случайная величина, находящаяся в диапазоне между t* и t**(t*≤t_s ≤t**), которые зада­ются в описании N_s-cxeмы.

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

Задание N _S-схемы в виде временной сети включает в себя задание структуры <В, D, I, О>, вектора разметок М_о и вектора задержек Z.

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

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

М_о ==(010100001110000001Nb₀)

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

Z = (z_вх, 0, z_кс1,. 0, 0, z_мп1,. 0, z_лм1, 0, 0, 0, z_bx , z_пм2,. 0, z_кс, 0, 0).

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

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

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

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

[30, 54].

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

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

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

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