Содержание
- 2. Основная задача начального этапа проектирования УА – выбор формализованного языка. Основные понятия – базис сетей Петри:
- 3. Пример: A = {a0, a1, a2, a3, a4} T = {t0, t1, t2, t3, t4} I(t0)
- 4. f-вектор маркировки сети Петри. N = (A, T, I, O, M0), где M0 – вектор начальной
- 5. Безопасная сеть Петри. запрещено наличие кратных дуг между позициями и переходами; вектор маркировки может содержать лишь
- 6. Тайм-аутные сети Петри. 0 q (q+a) (q+b) Помеченные сети Петри. метка – цвет 1 позиция –
- 7. Управляющие процессы и их формализованное описание.
- 8. Простейший линейный последовательный процесс – оригинальная сеть Петри. Ai – процедуры (i = 0 – k)
- 9. Если выполнение процедуры – неделимое событие, то: фрагмент с tHi, tKi, ∆i и zi, ai,ωi –
- 10. Пример: Если для Ai – {Cвi}=C1, {Cзi}=C3, C4 и {Cоi}=C1, C4, то Ai({C1}, {C3, C4}, {C1,
- 13. Скачать презентацию
Основная задача начального этапа проектирования УА – выбор формализованного языка.
Основные понятия
Основная задача начального этапа проектирования УА – выбор формализованного языка.
Основные понятия
событие;
условие.
Сеть Петри – структура УП
↓
это последовательность
процедур
Условия → событие
Состояние системы – это множество условий
Событие → новые условия →
→ изменение состояния системы
События – множество переходов
T={t0, t1, …, tr}
Условия – множество позиций
A={a0, a1, …, af}
I – входная функция
связь T и A
O – выходная функция
I – отображает tv(v=0 r) в мн-во позиций I(tv) – входные позиции перехода
O – отображает tv в мн-во позиций O(tv) – выходные позиции перехода
aµ - входная позиция tv, если aµ ϵ I(tv)
aµ - выходная позиция tv, если aµϵO(tv)
Сеть Петри – N = (A, T, I, O)
Пример:
A = {a0, a1, a2, a3, a4}
T = {t0, t1, t2,
Пример:
A = {a0, a1, a2, a3, a4}
T = {t0, t1, t2,
I(t0) = a0 I(t1) = a1
I(t2) = a2 I(t3) = a3
I(t4) = a4
O(t0) = a1 O(t1) = a2
O(t2) = a3 O(t3) = a4
I – матрица следования
O – матрица предшествования
Графическое представление
сети Петри
Типы вершин:
позиции – «O»
переходы – «|»
if (aµ - вход для tv), then (дуга aµ→ tv)
if (aµ - выход для tv), then (дуга tv→ aµ)
↓
G = (V, W) – ориентированный двудольный мультиграф, где
V – множество вершин
W – множество направленных дуг
V = A U T A ∩ T = Ø
позиция – условие
↓
Выполнение условия – маркировка позиции
(метка – «точка» в позиции)
↓
ʘ
↓
Если несколько точек –
то «емкость условия»
f-вектор маркировки сети Петри.
N = (A, T, I, O, M0), где
M0
f-вектор маркировки сети Петри.
N = (A, T, I, O, M0), где
M0
Пример:
M0 = (1, 0, 0, 0, 0)
Разрешающие метки
реализация активного перехода
↓
замена маркировки сети
M
на
M’ (непосредственно достижимая из M)
Достоинства языка сети Петри:
позволяет описывать параллельные процессы;
имеет средства для задания конфликтных состояний.
q
ω > q
Выполнение сети → связанные последовательности:
реализуемых переходов
маркировок M0, M1, M2, …
распределение меток в позициях
↓
порядок выполнения сети
↑ - зависит от
последовательности реализации
переходов
___________________________________________________________________________
переход реализуется если он активен,
т.е.
число меток во вх. позиц. => числу дуг,
соединяющих ее с эти переходом
Безопасная сеть Петри.
запрещено наличие кратных дуг между позициями и переходами;
вектор маркировки
Безопасная сеть Петри.
запрещено наличие кратных дуг между позициями и переходами;
вектор маркировки
реализация активного перехода возможна, если ни 1 из его выходных позиций не содержит меток – число меток в любой позиции не больше 1;
конечное число состояний – 2f при f позициях.
Ограниченная сеть Петри.
k → k-безопасная позиция или k-ограниченная
k’ >= k – k’-безопасной
kmax
Ограничение оригинальной сети Петри – моделирование примитивных событий.
________________________________
это сеть позиция-переход
↓
автоматная сеть
↓
маркированный граф
________________________________
сети с предикатами на переходах
↓
расширение ее описательных возможностей
________________________________
Введение позиции времени в сети Петри.
Временные сети: переход – t;
Тайм-аутные сети: переход – a и b.
Тайм-аутные сети Петри.
0<=a<=b
q
(q+a) (q+b)
Помеченные сети Петри.
метка – цвет
1 позиция – несколько цветов
Численные
Тайм-аутные сети Петри.
0<=a<=b
q
(q+a) (q+b)
Помеченные сети Петри.
метка – цвет
1 позиция – несколько цветов
Численные
метки любой природы и величины;
условия активизация и результата реализации независимы;
при реализации переходов изменяется маркировка входных и выходных позиций и содержимое памяти данных
Использование дуг разных типов в сети Петри.
Существуют:
Простые дуги:
1.1. активизирующая;
1.2. сдерживающая;
1.3. входная;
1.4. выходная;
Составные дуги:
2.1. активизирующая входная;
2.2. сдерживающая выходная.
Управляющие процессы и их формализованное описание.
Управляющие процессы и их формализованное описание.
Простейший линейный последовательный процесс – оригинальная сеть Петри.
Ai – процедуры (i
Простейший линейный последовательный процесс – оригинальная сеть Петри.
Ai – процедуры (i
операторные функциональные блоки – ОФБ
Процедура – переход сети Петри – ti (i = 0 – k)
aj (j = 0 – f) – позиции
Фазы выполнения процедуры:
начало;
выполнение;
окончание.
Подсеть Петри для процедуры Ai.
где:
tHi и tKi – переходы
zi и ωi - внешние позиции
tHi – начало процедуры Ai
метки в zi – включение ОФБi
метки в ai – выполнение Ai
метки в ωi – окончание ОФБi
↓
срабатывание перехода tKi
↓
метки в ai+1 – завершение Ai
∆i – непримитивный переход этой же сети Петри
Если выполнение процедуры – неделимое событие, то:
фрагмент с tHi, tKi, ∆i
Если выполнение процедуры – неделимое событие, то:
фрагмент с tHi, tKi, ∆i
Ci (i = 0 – l) – разделяемые ресурсы
q – число экземпляров i-го ФР
↓
q – кратность ресурса Ci – Ciq
↓
его могут использовать α <= q процедур
при q=1 - у ресурса 2 состояния
q+1
внутренние или собственные ресурсы
Процедуры Ai линейного процесса:
{Cвi} – множество ФР – уже владеет;
{Cзi} – множество ФР – запрашивает;
{Cоi} – множество ФР – освобождает.
Это длительный переход.
У него есть время выполнения.
Функциональные ресурсы (ФР)
Собственный ФР
Разделяемый ФР
Пример:
Процесс из 5-и последовательно
выполняемых процедур Ai при
следующем распределении 3-х ФР Cj:
A1({C2}, {-}, {-});
A2({C2}, {C1}, {C2});
A3({C1}, {C3}, {C1, C3});
A4({-}, {C2, C3}, {C3}).
Сj – ресурсные внутренние позиции
Tдi- длительные переходы
aµ - основные внутренние позиции
Пример:
Если для Ai – {Cвi}=C1, {Cзi}=C3, C4 и {Cоi}=C1, C4,
то Ai({C1},
Пример:
Если для Ai – {Cвi}=C1, {Cзi}=C3, C4 и {Cоi}=C1, C4,
то Ai({C1},
{Cзi}∩{Cвi}=Ø
Иногда: {Cвi}=Ø и {Cзi}={Cоi}
Особенности описания параллельного линейного процесса в сети Петри.
длительные переходы – процедуры;
tR – переходы распараллеливания;
tS – переходы соединения;
наличие элементарных подпроцессов;
cобственные ФР подпроцесса
Пример: