Вопрос достижимости какой- либо маркировки легче всего решается, глядя на граф покрываемости. Действительно, возьмём для примера две маркировки: μ1 = (01000010) и μ2 = (00100010). Первая из них достижима, и возможны два пути прихода к ней: t1 , t4 или t4 , t1 . Однако они не единственны, перед вторым запуском перехода возможно бесконечное число раз запустить для первого случая последовательность t2 , t3 , для второго случая – t5 , t6 . Вторая маркировка явно недостижима, так как её нет на графе.

С помощью матриц этот вопрос решается следующим образом. Составляем уравнение вида (3.2.19), в котором вместо σ ставим неизвестный вектор x той же размерности, а вместо μ – интересующую нас маркировку μ1. В итоге получаем систему из 8 уравнений относительно 6 неизвестных компонент вектора x.

(3.3.5)

Проанализировав данную систему, видим, что пятое уравнение является следствием из третьего и шестого, шестое – из седьмого и восьмого, первое – из второго и третьего. Из (1) и (4) следует, что x5 = 0, x6 = 0, из (7) следует, что x4 = 1. Первые три уравнения в (3.3.5) являются линейно зависимыми, поэтому за свободное неизвестное примем x1. Тогда получаем решение в виде x1 = {y y-1 y-1 1 0 0}, где y – любое целое число. Полученное решение говорит о достижимости маркировки μ1 и указывает, какие из переходов и сколько раз должны быть для этого запущены.

Сравнив оба способа решения, сразу можно увидеть недостатки второго. Во- первых, решение (3.3.5) не указывает, в какой именно последовательности должны быть запущены указанные переходы. Во- вторых, глядя на матрицу изменений, мы не можем судить о наличии в сети петель. Кроме того, полученное матричное решение не даёт, вообще говоря, гарантий своей реализуемости – оно является лишь необходимым условием достижимости. Однако, не получив решения, можно говорить о недостижимости маркировки.

Действительно, записав (3.2.19) для μ2, получаем систему:

(3.3.6)

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

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

Данная сеть является активной – в ней каждый переход может сработать хотя бы один раз. Проанализируем уровни активности отдельных переходов. Переходы t1 и t4 являются L1- активными, так как они в худшем случае (то есть при получения тупиковой маркировки) могут сработать хотя бы один раз. Переходы t2, t3, t5 и t6 являются L2- активными, так как они могут сработать любое наперёд заданное число раз и даже больше.

Отсюда можно сделать вывод о том, что данная сеть не является бесконфликтной – у неё есть тупиковое состояние.

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

x·D = 0 (3.3.7)

Получаем систему

(3.3.8)

Данная система имеет 2 решения: {y y y 0 0 0} и {0 0 0 y y y}, где y – любое. Действительно, запуская любое число раз последовательности t1 t2 t3 или t4 t5 t6 , каждый раз мы возвращаемся к исходной маркировке.

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

Можно сказать, что данная сеть не является устойчивой. У неё есть тупик, и, кроме того, непосредственно перед переходом в тупиковое состояние всегда существуют два разрешённых перехода. Запуская ‘неправильный’ переход, мы запрещаем оба – и оказываемся в тупике. Такое свойство сети говорит о наличии потенциально возможных конфликтов.

Па основании графа (3.3.2) можно выписать множество достижимых из μ0 маркировок:

(3.3.9)

Для моделирования сети была написана программа на языке Turbo Pascal. Она отображает состояние сети и разрешённые в каждый момент переходы. Для выбора запускаемого перехода используется мышь.

3.4 Выводы по разделу

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

ЗАКЛЮЧЕНИЕ

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

ЛИТЕРАТУРА

1 Сигорский В.П. Математический аппарат инженера.– Киев:Техника, 1975. –538 с.

2 Г.Корн, Т.Корн Справочник по математике для научных работников и инженеров.– М.: Наука, 1984. –831 с.

3 В.Брауэр Введение в теорию конечных автоматов.– М.: Радио и связь, 1987. –392 с.

4 Фаронов В.В. Турбо Паскаль 7.0: практика программирования. – М.: Нолидж, 1997. –432 с.

Приложение А

Программа моделирования сети Петри

Program Farewell_Pascal_Please_Forgive_Me;

Uses graph,crt;

Const m_0=$9C;

r_0=$90;

path='cursor.dat';

mask:array[0 5] of byte = ($90,$48,$20,$0C,$12,$01);

jump:array[0 5] of word = ($406F,$20B7,$98DF,$02F3,$01ED,$1CFE);

Var

i,j,counter,number:integer;

flag_of_exit:boolean;

ok:word;

bm:integer;

ScrMask:array[1 64] of byte;

r,m,old_m,old_r:byte;

f:file of byte;

procedure Init_Graph_Mode;

var

Driver,

Mode,

ErrCode: Integer;

begin

Driver := Detect;

InitGraph(Driver, Mode, '');

ErrCode := GraphResult;

if ErrCode <> grOk then

begin

Writeln('Ошибка графического режима:',

GraphErrorMSG(ErrCode));

Halt(1);

end;

SetTextStyle(DefaultFont, HorizDir, 1);

SetColor(15);

SetLineStyle(0,0,1);

SetFillStyle(1,0)