Событийный подход

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

Для этого используются средства языка системы моделирования. Естественно, эти средства должны быть достаточно представительными для того, чтобы описывать широкий круг процессов. В частности, для процессного подхода необходимыми являются средства явного (или неявного) определения участков модели, на которых необходимо представление квазипараллельных процессов.

Оба подхода имеют как достоинства, так и недостатки. К достоинствам процессно-ориентированного представления моделей следует отнести компактность и наглядность (рис. 6). Здесь стрелками показано направление развития процессов. Событийные модели обладают большей гибкостью, но они уступают процессно-ориентированным системам в простоте и наглядности составления моделей.

Графическое представление примера процесса продвижения транзактов

Моделирование работы с материальными ресурсами.

Материальные ресурсы подразделяются на две разновидности: неперемещаемые и перемещаемые. Неперемещаемый ресурс выделяется в определенном месте (как в реальности, так и в модели). Например, мастер в парикмахерской - это один элемент ресурса, выделяемый клиенту для обслуживания (стрижки и бритья). Этот элемент не может перемещаться вместе с клиентом (транзактом). После обслуживания одного клиента он либо приступит к обслуживанию следующего, если есть очередь, либо будет отдыхать.

Перемещаемый ресурс выделяется клиенту, после чего клиент использует его в других местах и возвращает только при отсутствии необходимости дальнейшего использования. Например, ресурс - это гараж; клиенту можно выделить три грузовика для использования в работах, проводимых в других местах (естественно, не в гараже).

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

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

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

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

Перемещаемый ресурс представляет собой "склад" единиц ресурса, количество которых известно. Число таких складов не регламентировано. Транзакт попадает в очередь к складу и требует выделения определенного числа единиц ресурса. Склад ресурсов может описываться в имитационной модели различными способами.

Обслуживание транзакта заключается в выделении ему требуемого числа единиц ресурса. Транзакт "путешествует" с захваченными единицами по графу модели до тех пор, пока в соответствии с определенными условиями он не вернет все (или часть) единицы ресурса. Транзакт может несколько раз становиться в очередь к одному и тому же ресурсу, получая дополнительные единицы.

Существует интересная особенность при работе с перемещаемыми ресурсами: транзакт может отдать какие-либо единицы ресурса не только на тот склад, на котором он их получил, но и на другой. При таком перераспределении (или "похищении") на этих двух складах произойдет изменение мощностей: на одном она уменьшится, а на другом - увеличится. Например, в GPSS перемещаемый ресурс может быть описан ячейками памяти, значения которых изменяются оператором SAVEVALUE: при захвате ресурса транзактом значение захваченного объема ресурса присваивается соответствующему параметру транзакта, а значение ячейки соответственно уменьшается на данную величину захваченного ресурса; при возврате ресурса параметр транзакта обнуляется, а значение ячейки памяти, определяющее общий объем свободного ресурса увеличивается на величину возвращенного ресурса.

Имитация информационных ресурсов.

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

- стартовый информационный ресурс, без которого нельзя начинать выполнение функции (например, права или разрешение на ее выполнение, инструкция по сборке принципиально нового устройства);

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

Стартовый информационный ресурс дает возможность отправить заявку на выполнение какой-либо функции, т.е. поместить транзакт в очередь на обслуживание. В языках имитационного моделирования может быть реализован различными способами, например, логическими переключателями (LOGIC R, LOGIC S, GATE LS).

Оперативный информационный ресурс может описываться также разными способами - одним из них является использование операторов захвата и освобождения прибора (В GPSS - PREEMPT, RETURN).

Общие понятия сетей Петри

Сетевые модели (сети Петри) используется для анализа причинно-следственных связей в сложных системах. Аппарат теории сетей Петри позволяет описывать структуру и взаимодействие параллельных систем и процессов. Сеть Петри (N-схема) задается четырьмя элементами:

N = <B,D,I,O>,

где B - конечное множество позиций; D - конечное множество переходов; I - входная функция (прямая функция инцидентности), I:BXD®{0,1}; O - выходная функция (обратная функция инцидентности), O:DXB®{0,1}.

I отображает переход d_j в множество входных позиций , а выходная функция О отображает переход d_j в множество выходных позиций . Для каждого можно определить множество входных позиций перехода и выходных позиций перехода как

Аналогично, для каждого можно определить множество входных переходов позиции и выходных переходов позиции :

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

заявка ждет обслуживания

Канал обслуживания заявка обрабатывается

свободен (канал занят)

конец обслуживания

заявка ждет вывода

выход заявки

Структура N (схема)

Для представления динамических свойств объекта вводится функция маркировки (разметки) . Маркировка - присвоение абстрактных объектов, называемых метками (фишками), позициям:

N_M = <B,D,I,O,M>.

Функционирование сети Петри отражается путем перехода от разметки к разметке. M₀ - начальная разметка. Смена разметок - срабатывание одного из переходов сети. Необходимое условие срабатывания перехода :

,

где - разметка позиции .

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

,

т.е. переход изымает по одной метке из каждой своей входной позиции и добавляет по одной метке в каждую из выходных позиций. Для отражения временных параметров процесса функционирования моделируемой системы на базе N-схем используется расширение аппарата сетей Петри - временные сети.

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

2. Анализ сетей Петри

Само моделирование малополезно. Необходимо провести анализ моделируемой системы. Существует два подхода к анализу свойств сетей Петри - это статистическое моделирование на компьютере и аналитические методы. Большое практическое значение имеет изучение следующих свойств сетей Петри: ограниченность, сохранение, активность, достижимость и покрываемость. Необходимо отметить, что задачи нахождения этих свойств разрешимы для классических сетей Петри и неразрешимы для расширений сетей Петри (например, Е-сетей).

Рассмотрим свойство ограниченности. Позиция является к-ограниченной, если количество фишек в ней не может превышать целое число k: M(b_i)£k, для всех MÎR(N,M) (множество достижимости). 1-ограниченная позиция называется безопасной. Сеть Петри ограниченна, если все ее позиции ограничены. Изучение данного свойства может иметь важное практическое значение при проектировании технических систем, в которых должно быть ограниченно присутствие одновременное присутствие активных процессов, например моделирование транспортных потоков или систем управления трафиком в глобальных вычислительных сетях. Такие системы должны быть обеспечены механизмами автоматической разгрузки или распределения.

Важным свойством для сетей Петри является сохранение. Сеть Петри является с начальной маркировкой М называется сохраняющей по отношению к вектору взвешивания W=(w₁, w₂,..., w_n), n=|B|, w_i >0, если для всех возможных маркировок выполняется следующее условие: å w_i × M'(b_i)= å w_i × M(b_i).

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

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

Очевидными являются задачи достижимости и покрываемости. Задача достижимости: можно ли из данной маркировки М достичь маркировки М'?. Задача покрываемости: для данной маркировки М существует ли достижимая маркировка М', такая что M'>=M.

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