IX Международная студенческая научная конференция Студенческий научный форум - 2017

Е-сеть (оценочная сеть) является одним из самых мощных расширений аппарата сетей Петри (evaluation - «вычисления», «оценка») - «оценочные сети». Поэтому, чтобы разобраться в значимости Е-сетей, нужно вникнуть в смысл сетей Петри, провести сравнительную характеристику.

Сети Петри – математический аппарат для моделирования динамических дискретных систем. Сеть Петри представляет собой ориентированный мультиграф, так как он допускает существование кратных дуг от одной вершины графа к другой, а дуги являются направленными. Одно из основных достоинств аппарата сетей Петри заключается в том, что они могут быть представлены как в графической форме (что обеспечивает наглядность), так и в аналитической (что позволяет автоматизировать процесс их анализа). Вершины-позиции обозначаются кружками, вершины-переходы - черточками. С содержательной точки зрения, переходы соответствуют событиям, присущим исследуемой системе, а позиции - условиям их возникновения. Таким образом, совокупность переходов, позиций и дуг позволяет описать причинно-следствен­ные связи, присущие системе, но в статике. Чтобы сеть Петри «ожила», вводят еще один вид объектов сети - так называемые фишки, или метки позиций. Пе­реход считается активным (событие может произойти), если в каждой его вход­ной позиции есть хотя бы одна фишка. Расположение фишек в позициях сети называется разметкой сети(Рис.1).

Рис.1. Пример изменения разметки сети Петри при срабатывании переходов

Е-сеть также представляет собой граф, состоящий из двух типов вершин: позиций и переходов, соединённых друг с другом ориентированными дугами. Структура Е-сети формально, как и сеть Петри, представляется пятью параметрами: СЕ=(P, T, I, O, M). В Е-сетях реализуются шесть типов основных базовых переходов: обозначаемые буквами Т, J, F, X, Y, I. Динамика Е-сети определяется срабатываниями переходов и перемещениями меток из входных позиций переходов в выходные позиции в результате срабатывания. Формально срабатывание перехода имеет вид:

X-переход содержит дополнительную управляющую (разрешающую) позицию R (Рис.2).

Рис.2. Х-переход

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

У-переход отражает приоритетность одних потоков информации перед другими(Рис.3).

Рис.3. Y-переход

Логика работы У-перехода:

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

Рис. 4. Пример Е-сети

На рисунке переходы, соответствующие определенным событиям в системе (tj), имеют сле- дующие обозначения: t1 — постановка задания в очередь; t2 — выполнение задания в течение од- ного кванта времени; t3— анализ степени завершенности задания. Разрешающие позиции R1 и R2 служат для задания закона формирования случайных интервалов времени между поступающими заданиями и интервалов времени, необходимых для полного обслуживания каждого из них.

В отличие от сетей Петри в Е-сетях:

1) имеются несколько типов вершин-позиций: простые позиции, позиции-оче­реди, разрешающие позиции;

2) фишки (метки) могут снабжаться набором признаков (атрибутов);

3) с каждым переходом может быть связана ненулевая задержка и функция пре­образования атрибутов фишек.

4) введены дополнительные виды вершин-переходов.

5) в любую позицию может входить не более одной дуги и выходить также не более одной.

Применение управляющих оценочных сетей Петри к задаче об обедающих философах. Сформулируем постановку задачи: «каждый философ может сесть на любое свободное место (один из пяти стульев)». На рис. 5 представлена управляющая оценочная сеть Петри (BPN). В ней любой из пяти философов гуляет в саду (метка в p7i и t3i) и когда он проголодался – активизируется управляющий вектор Хi, который направляет метку к i-ому месту (метка в p5i) – идёт в столовую. Там он ожидает, когда будут доступны две вилки возле i-ой тарелки (наличие двух меток в вершине p3), к которой он подошел, начать кушать. При этом срабатывает соответствующий переход t1i (срабатывание соответствует совокупности действий а1i «сел на i–е место и начал кушать из i- ой тарелки»). При срабатывании t1i из вершины p3 две метки отнимаются, отнимается метка из вершины p5i. Наличие метки в вершине p6i моделирует окончание приема пищи на i-ом месте одним из пяти философов. Срабатывание перехода t2i моделирует действие: «философ освобождает место приёма пищи, две освободившиеся вилки моют для их дальнейшего использования», а передача двух меток по дуге t2i - p3 говорит о возврате чистых вилок к тарелкам. Переход метки в вершину p7i моделирует возвращение философа в сад. Переход t3i моделирует прогулку не проголодавшегося философа по саду, а когда он проголодается, то активизируется управляющий вектор Хi (Хi =1), и метка переместится в вершину места p5i. Данное решение позволяет также избегнуть критического свойства конфликтности [1-2], которое возникает, когда из одной вершины места исходят две и более дуги. Управляющий вектор позволяет руководить приоритетами при выборе активной исходящей дуги.

Рис.5. Модель задачи об обедающих философах, представленная оценочной сетью Петри

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

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

Список литературы

1. Кузьмук, В.В. ОЦЕНОЧНЫЕ УПРАВЛЯЮЩИЕ СЕТИ ПЕТРИ (SBPN) / В.В.Кузьмук, О.О.Супруненко, А.В.Кузьмук. – Киев, 2011. – 3 с.

2. Банников, А. А. ПРЕДСТАВЛЕНИЕ Е-СЕТЕЙ С ПОМО- ЩЬЮ СЕТЕЙ ПЕТРИ ДЛЯ ОБЕСПЕЧЕ- НИЯ ВОЗМОЖНОСТИ МАТРИЧНОГО АНАЛИЗА / А. А. Банников, Д. В. Фатхи. – Ростов-Дон, 2016. – 7с.

Код для цитирования: Скопировать