Пример 3.

⇐ ПредыдущаяСтр 10 из 11Следующая ⇒

Читайте также:

|T|=6, |P|=7, |V|=13, M₀ = <1,0,0,0,1,0,1>

t₂

M₀ ├── M₁=<0,0,1,0,1,0,1>

t₃

M₁ ├── M₂=<0,0,0,1,0,0,1>

t₄

M₂ ├── M₃=<0,0,0,0,1,0,1>

t₁

p₂ p₁ p₄

●

t₂ t₃ t₄

p₃

● p₅

t₅

p₆p₇

●

t₆

Функционирование сети Петри продолжается до тех пор, пока существует хотя ба один переход.

Примечания.

1. Моделирование систем с дискретными событиями, которые могут происходить одновременно и параллельно, отражает два аспекта: события и условия. Позиции сети (места) соответствуют условиям, переходы –событиям

2. Сеть Петри может рассматриваться как форма задания некоторого формального языка. Для этого вводится функция индексирования переходов в сети Петри

φ: T → ∑, где

∑ - алфавит формального языка,

φ – присваивает каждому переходу некоторый символ из ∑.

Последовательность срабатывания переходов определяется как слово α из множества Σ^* (α∈Σ^*)

τ = <t_1,t_j, …, t _k>

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

L (N_m)={α ∈ Σ^*:M, M₀ ├── M}

3. Языки сетей Петри могут служить средством формального представления протоколов обмена информацией.

4. Основные направления анализа сетей Петри:

- проблема достижимости.

τ M₀ ├── M

В заданной сети с начальной разметкой требуется решить вопрос: "достижима ли принципиально некоторая разметка ".

- свойства живучести перехода.

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

- ограниченность сети.

В заданной сети для любого места имеется число фишек, меньше или равное n (n N, n задано), для любой разметки в множестве всех достижимых разметок сети Петри.

- безопасность сети.

В заданной сети не при каких условиях не должно появиться более одной фишки в каждой позиции (n=1).

- свойства сохранения.

Σ M(p_i)=const p_i ∈ P

В заданной сети должно быть постоянным число фишек для любой разметки из множества всех достижимых разметок.

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

Анализ модели на сохранение важен тогда, когда под фишками (метками, динамическими объектами) понимают какие-либо неизменные ресурсы системы.

Пример. Сеть Петри, моделирующая специализируемую параллельную систему для реализации итерационных вычислительных процедур.

МПК

МПД 1

МПД 3

МПК – модуль памяти команд

МПД – модуль памяти данных

ПЭ - процессорный элемент

В этой схеме совокупность ПЭ и модулей памяти связаны в кольцо. ПЭ работает в двух режимах. Режим указывается командой, считанной из МПК:

- ПЭ захватывает оба смежных МПД, используя левый для извлечения исходных данных новой итерации, а правый – для выборки результатов предыдущей итерации. По завершении итерации ПЭ помещает результат в правый МПД и освобождает оба МПД.

- ПЭ работает с внутренними данными.

Решение.

q₁ – обработка внутренних данных

q₂ – захвачен левый МПД

q₃ – захвачен правый МПД

q₄ – захвачены оба МПД.

Можно убедиться, что дерево достижимости этой сети Петри (рис.1) содержит две маркировки:

τ₁ M₀ ├─→ M₁, M₁ = {q₂¹, q₂², q₂³} τ₂ M₀ ├─→ M₂, M₂ = {q₃¹, q₃², q₃³}

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

При другом варианте работы системы ПЭ (параллельная работа устройства управления ПЭ) осуществляется только одновременный захват смежных элементов памяти. В этом случае каждому ПЭ соответствует только состояние q₁ и q₄, а сеть Петри имеет вид (Рис.2).

Эта сеть безопасна и активна (живуча), так как дерево достижимости не содержит терминальных маркировок:

< 1,1,1,1,0,1,0,1,0 >