События и условия (как элементы исходного анализа систем)

События – это действия, которые могут быть выполнены в системе.

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

Условия – это некоторый предикат или логическое условие, которое может принимать значение t и f.

Условие, определяющие выполнение событий, называются предусловием события.

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

Пример:

Задача моделирования логического управления технологическим участком, на котором детали проходят путь обработки.

Условия:

А. деталь ожидает обработки

Б. Технологический робот свободен

В. Деталь обрабатывается

Г. Деталь ожидает транспортного робота

Д. транспортный робот свободен

События:

1. Деталь поступает на входную очередь

2. Деталь начинает обрабатываться

3. Деталь обработана

4. Передача детали в накопитель

Составим таблицу, связывающую события и условия (в том числе выделенные предусловия и постусловия)

События	Условия
Предусловия	Постусловия
	Нет А, Б В Г, Д	А В Г, Б Нет

Здесь можно перейти к моделированию системы с помощью сети Петри. Условия будут представлены позициями переходов. Входами перехода будут являться предусловия. Выходами – постусловия.

Предварительно сопоставим с условиями либо математические переменные, что бы построить математическую модель (к сети Петри это не имеет отношения) и события ставятся в соответствии с переходами.

Условия	Математические переменные	События	Математические функции
А Б В Г Д

Построим упрощенную математическую модель, описывающую поведение системы. Модель связывает возникновение событий с условиями.

СМОТР И

Свяжем элементы сети Петри с элементами математической модели.

Позиции сети Петри	Математические переменные

Внимание!

Если в математической модели присутствуют оба состояния (два) (прямое и инверсное:
и ), то это эквивалентно двум разным позициям.

Поставим соответствие переходам математические функции:

переходы сети Петри	Математические функции

Эта сеть C для проведения моделирования должна иметь некоторую начальную маркировку М().

Некоторые виды процессов, моделируемые сетью Петри

Рассмотрим примеры, иллюстрирующие некоторые особенности сетей Петри и самих систем, процессов, моделируемых с их помощью.

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

Вообще говоря, существует ряд процессов, для моделирования которых необходим некий интервал выполнения. Вообще в сетях Петри механизмов такого рода нет, однако такие временные процессы, называемые «непримитивные события» могут в некоторой степени моделироваться так:

Моделирование конфликта

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

Синхронизация

Важным свойством систем является распределение в них различных ресурсов между компонентами систем.

Задача о взаимном исключении.

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

Пусть происходит в процессе следующая последовательность:

Процесс П1 считывает значение х разделяемой переменной.

Процесс П2 считывает х

П1 вычисляет новое значение

П2 вычисляет

П1 записывает на старое место

П2 записывает на старое место

Пусть рассматривается некой банковский счёт, на котором лежит $1000.

Пусть

g(x) – означает, снять со счёта $1000 (магазин)

f(x) – означает положить на счёт $1000 (его работа)

В этом случае: оба процесса П1 и П2 успели прочитать в свои буфера $1000. П1 -> положить $1000, то есть на счету у него $2000; П2 -> $0 = $1000 - $1000.

Такая ситуация называется взаимным исключением (это в некотором смысле конфликт).

Понятие взаимного исключения – часто используемый механизм в ВС. Здесь рассматривается две подсети Петри для каждого процесса соответственно. В каждом процессе рассматривается так называемая критическая секция. Идея состоит в том, что когда любой из процессов готов выполнить свою критическую секцию, он сначала ждёт, пока другой процесс не завершит свою критическую секцию. Выполнившийся процесс освобождает доступ к разделяемому ресурсу, а выполняющийся – блокирует.

В данном случае мы можем запускать любой процесс.

Глава 1.1.

Задача о производителя и потребителях или

Ох уж эти буфера.

Здесь так же присутствует разделяемый объект, понимаемый как буфер. Процесс – производитель создаёт некоторые объекты, которые помещает в буфер. Потребитель ждёт, пока объект не будет помещён в буфер, и изымает его и использует.

Сначала запустится П1, затем П2.

Задача о производителе и потребителе с ограниченным буфером.

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

В данном случае имеется буфер размерности n, причём позиция В означает занятые ячейки этого буфера, а В' означает свободные.

Пусть первоначальное состояние показано маркировкой, где n – количество фишек, соответствующее размеру буфера. Тогда при срабатывании перехода t2 происходит освобождение очередной ячейки буфера. Тогда переход t3.

Задача об обедающих мудрецах.

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

Анализ сети Петровича или как продать паленый самогон.

Приведенный ранее материал показывал моделирующую мощность сети Петри. Наиболее полезны сети Петри для анализа тех систем (процессов), которые они моделируют. Цель анализа заключается в выявлении ряда характеристик объекта или процесса. Однако учитывая что для моделирования используются сети Петри, то иногда говорят о характеристиках самих сетей, т. е. характеристики модели показывают характеристики сетей. Например понятие безопасности, при этом рассматриваются отдельно простые сети Петри (в простых кратные дуги не разрешены). Простая сеть безопасна, если безопасна каждая ее позиция, а позиция является безопасной в простой сети, если число фишек в ней не превышает единицы. Вообще для сетей Петри (всех) это условие (безопасности) означает, что количество фишек в каждой позиции должно быть меньше либо равно некоторого установленного значения k (k-безопасная сеть Петри).

Пример небезопасной сети Петри.

Что означает, при появлении фишек (условия) в P₁ разрешен t₃ .

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

P_i Є I (t_j) & P_i O (t_j)

То бывает полезным добавить еще одну позицию P’_i где P’_i к O (t_j). Если переход P_i Є O (t_j) связан с выходными функциями I (t_j), то вводится добавочная позиция P’_i к множеству комплекта входов I (t_j).

Понятие сохранения

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

Самый простой способ сделать это – потребовать что-то, что бы общее число фишек в сети оставалось постоянным. Формально это можно изобразить таким образом:

- новая маркировка

Разрешены (исходно) два перехода t₁ и t₂. Запустим t₁

P₁ P₂ P₃ P₄ P₅

t₁ 1 1 0 0 1

0 1 1 0 0 C₁

Самое простое очевидное требование покоя. Число входов в каждый переход должно равняться числу выходов.

Построим другую сеть, в которой выполнено такое требование.

(Исходная сеть была не строго сохраняющая)

P₁ P₂ P₃ P₄ P₅

t₁ 1 1 0 0 1

0 1 2 0 0 C₂

Физический смысл модифицированной схемы – появление кратного числа дуг.

Тууупики

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

Рассмотрим систему, включающую два различных ресурса q и r; и два процесса a и b.

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

Пусть процесс a сначала запрашивает q, затем r, а потом освобождает q и r.

Процесс b работает аналогично, но сначала запрашивает r, а затем q. Такая система может регулярно работать.

Для устойчивости сети является последовательность переходов (запусков)

t₁, t₂, t₃, t₄, t₅, t₆ или:

t₄, t₅, t₆, t₁, t₂, t₃

однако рассмотрим последовательность, которая начинается t₁, потом t₄. Процесс a обладает ресурсом q и хочет получить r, но процесс b уже обладает ресурсом r, а хочет получить q. В этом случае система заблокирована, процесс продолжаться не может.

Итак тупики в сети Петри – это множества (ил один) переходов, которые не могут быть запущены. Т.е. здесь (на схеме)тупик возникает из-за невозможности запуска t₂ и t₅.

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

Достижимость. Дерево достижимости.

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

Для предыдущей задачи тупик в термине достижимости может возникнуть если, достижимым является состояние:

P₁ P₂ P₃ P₄ P₅ P₆ P₇ P₈

0 1 0 0 0 0 1 0