Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Моделирование дискретных асинхронных процессов и сети Петри

Читайте также:
  1. ERP - типизация производственных процессов и продуктов. Нормативно-справочная информация о продукте
  2. АКТИВАЦИЯ СВОБОДНОРАДИКАЛЬНЫХ ПРОЦЕССОВ В КЛЕТКЕ
  3. Анализ базовых технологических процессов
  4. Анализ случайных процессов изменения ОП объектов
  5. Базовые концепты и типы политических процессов
  6. Валидация процессов
  7. ВВЕДЕНИЕ В КОРПУСКУЛЯРНУЮ ТЕОРИЮ ФАЗОВОГО ПРОСТРАНСТВА. ТЕРМОДИНАМИЧЕСКИЕ ВЕРОЯТНОСТИ И ПРОСТЕЙШЕЕ МОДЕЛИРОВАНИЕ МИКРОКАНОНИЧЕСКИХ АНСАМБЛЕЙ.

 

Сети Петри [13] предназначены для моделирования дискретных асинхронных процессов. Их основные отличия от автоматной модели – возможность отображать параллелизм, асинхронность и иерархичность моделируемых объектов.

Сети Петри можно описать формально в виде

N=(P,T,F,H,m0 )

Где P – конечное непустое множество позиций (состояний);

Т - конечное непустое множество переходов (событий);

 

F:PхT®{0,1,2..} – функция входных инциденций

H:TхP®{0,1,2..} - функция выходных инциденций

m0 :P®{0,1,2..} – начальная маркировка (разметка) сети.

Сети Петри удобно представлять графически в виде двудольного ориентированного графа с двумя типами вершин, соответствующими

 

 

0001 0011 0010

а) S1 S2 б) S1 S2

1001

0101 1010

0110


S3 S4 S3 1100 S4

0100 1000

 

00 01 000 001

в) S1 S2 г) S1 S2

101

011

 


S3 S4 S3 110 S4

10? 100 010

Рис.43

 

 

позициям pÎP и переходам tÎT (рис.44) Позиции изображаются кружками. Внутри кружка могут находиться маркеры (фишки), изображаемые точками. Переходы изображаются черточками (барьерами).

Функции входных и выходных инциденций могут быть представлены матрицами. Для сети на рис. 44 имеем:

t1 t2 t3 t4 p1 p 2 p3 p4 p5

p1 1 0 0 0 t1 0 0 1 2 0

p2 1 0 0 0 t2 1 0 0 0 1

F= p3 0 1 0 0 H= t3 1 1 0 0 0

p4 0 0 1 0 t4 0 0 0 1 0

p5 0 0 0 1

 

Если можность множества P равна n, то маркировка представляется n-мерным вектором, значения координат которого равны числу маркеров в соответствующих позициях.

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

" pÎP:m1(p) – F(p,t)³0

В результате срабатывания перехода t маркировка М заменяется маркировкой М1

VPÎP:M1(P)= M(P) – F(p,t)+H(t,p).

Это означает, что в результате срабатывания из всех входных позиций перехода t удаляются F(p,t) маркеров, а в каждую входную позицию добавляется H(t,p) маркеров. В рассматриваемом случае маркировка M1 непосредственно достижима из маркировки М, что обозначается М→ M1 функционирование сети Петри – это последовательная система маркировок в результате срабатывания возбужденных переходов. Состояние сети Петри – в каждый момент времени определяется ее текущей маркировкой.

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

Возможные варианты функционирования сети описываются графом достижимости. Вершинами графа достижимости являются маркировки, а

дуги представляют отношение непосредственной достижимости на множестве маркировок.

Маркировка М называется тупиковой, если при этой маркировке ни один переход не может сработать.

Маркировка М1 достижима из маркировки М, если на графе достижимости существует такой путь ΐ=(t1,t2,…,tk), что

t1 t2 tk

m→m1→…→m1

Множество всех маркировок, достижимых из начальной маркировки m0, называется множеством достижимости сети Петри и обозначается R(N). На рис.45 показано построение графа достижимости.

 

Виды сетей Петри

 

Множества входных и выходных позиций перехода t обозначают соответственно (0p), (p0)

 

Сеть Петри называется:

- автономной сетью, если для каждого t € T имеется не более одной входной позиции и не более одной выходной позиции, т.е. |0t|=|t0|=1;

- маркированым графом, если для каждого p€P имеется только один входной и один выходной переходы, т.е. |0P|=|P0|=1;

- сетью свободного выбора, если для каждого ti€T и для каждого pj€*ti позиция Pj является либо единственной входной позицией перехода ti, т.е. |Pj *|=1, либо этот переход имеет единственную входную позицию, т.е. |0tj|=1;

- простой сетью, если любая пара переходов ti,tj€T имеет не более одной общей выходной позиции, т.е. |*tintj0|≤1;

- бесконфликтной сетью, если для каждой позиции p€P существует не более одной исходящей дуги |P0|≤1 либо для всех t€T выполняется условие t€0p.

 


Дата добавления: 2015-10-23; просмотров: 115 | Нарушение авторских прав


Читайте в этой же книге: Минимизация числа состояний абстрактного автомата | Тестирование абстрактных автоматов | Язык Граф-Схем Алгоритмов | ФОРМАЛЬНЫЕ ГРАММАТИКИ И ЯЗЫКИ | ПРЕДСТАВЛение СИМВОЛЬНОЙ ИНФОРМАЦИИ | Машинное изображение чисел | Выполнение арифметических и логических операций | Микропрограммирование | Элементная база построения комбинационных автоматов | Переключательные функции (логика высказываний) |
<== предыдущая страница | следующая страница ==>
Канонический метод структурного синтеза автоматов| Безопасность и ограниченность.

mybiblioteka.su - 2015-2024 год. (0.008 сек.)