?0 t3 t6
10011100
00100100 t1 t4 10000001
t2 t5
01001100 10010010
t4 t1
01000010
Рисунок 3.3.2 – Граф покрываемости маркировок сети Петри
Проанализируем сеть двумя методами – матричным и графическим и сравним полученные результаты.
Вопрос достижимости какой- либо маркировки легче всего решается, глядя на граф покрываемости. Действительно, возьмём для примера две маркировки: ?1 = (01000010) и ?2 = (00100010). Первая из них достижима, и возможны два пути прихода к ней: t1 , t4 или t4 , t1 . Однако они не единственны, перед вторым запуском перехода возможно бесконечное число раз запустить для первого случая последовательность t2 , t3 , для второго случая – t5 , t6 . Вторая маркировка явно недостижима, так как её нет на графе.
С помощью матриц этот вопрос решается следующим образом. Составляем уравнение вида (3.2.19), в котором вместо ? ставим неизвестный вектор x той же размерности, а вместо ? – интересующую нас маркировку ?1. В итоге получаем систему из 8 уравнений относительно 6 неизвестных компонент вектора x.
[pic]
(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) end; function Init_Mouse:word; begin asm push ax mov ax,00h int 33h mov @Result,ax pop ax end end; procedure Show_Mouse; begin asm push ax mov ax,01h int 33h pop ax end end; procedure Hide_Mouse; begin asm push ax mov ax,02h int 33h pop ax end end; procedure Set_Graph_Cursor(segm,ofst:word;x,y:integer); begin asm push ax push bx push cx push dx mov bx,x mov cx,y mov es,segm mov dx,ofst mov ax,09h int 33h pop dx pop cx pop bx pop ax end end; procedure Get_Mouse_State(var bt,x,y:integer); begin asm push ax push bx push cx push dx mov ax,03h int 33h lds di,bt mov [di],bx lds di,x mov [di],cx lds di,y mov [di],dx pop dx pop cx pop bx pop ax end end; procedure Get_Web_State; begin r := 0; for counter:= 0 to 5 do if (mask[counter] and m) = mask[counter] then r := r or ($80 shr counter) end; procedure Design_Kernel; begin
OutTextXY(190,20,'Распределение ресурсов для');
OutTextXY(207,27,'случая двух процессов'); for counter := 0 to 2 do
Circle(150,counter*150+50,15); for counter := 0 to 2 do
Circle(450,counter*150+50,15); for counter := 0 to 1 do
Circle(300,counter*150+120,15); for counter := 0 to 2 do begin
Line(140,counter*150+123,160,counter*150+123);
Line(140,counter*150+127,160,counter*150+127);
Line(140,counter*150+123,140,counter*150+127);
Line(160,counter*150+123,160,counter*150+127) end; for counter := 0 to 2 do begin
Line(440,counter*150+123,460,counter*150+123);
Line(440,counter*150+127,460,counter*150+127);
Line(440,counter*150+123,440,counter*150+127);
Line(460,counter*150+123,460,counter*150+127) end; for counter := 0 to 1 do begin
Line(counter*300+150,65,counter*300+150,123);
Line(counter*300+150,127,counter*300+150,185);
Line(counter*300+150,215,counter*300+150,273);
Line(counter*300+150,277,counter*300+150,335);
Line(counter*300+150,365,counter*300+150,423);
Line(counter*300+150,123,counter*300+148,114);
Line(counter*300+150,123,counter*300+152,114);
Line(counter*300+150,185,counter*300+148,176);
Line(counter*300+150,185,counter*300+152,176);
Line(counter*300+150,273,counter*300+148,264);
Line(counter*300+150,273,counter*300+152,264);
Line(counter*300+150,335,counter*300+148,326);
Line(counter*300+150,335,counter*300+152,326);
Line(counter*300+150,423,counter*300+148,414);
Line(counter*300+150,423,counter*300+152,414) end;
Arc(120,427,180,360,25);Arc(480,427,180,360,25);
Arc(122,35,0,180,27);Arc(478,35,0,180,27);
Line(95,35,95,425);Line(505,35,505,425);
Line(293,134,163,431);Arc(159,427,180,330,5);
Line(290,281,170,436);Arc(162,427,180,320,12);
Line(307,134,436,431);Arc(440,427,210,360,5);
Line(310,281,429,436);Arc(438,427,220,360,12);
Line(283,117,169,106);Arc(171,121,80,180,15);
Line(312,129,439,262);Arc(429,273,0,45,15);
Line(283,267,169,256);Arc(171,271,80,180,15);
Line(311,257,426,110);Arc(432,121,0,160,12);
Line(150,35,145,26);Line(150,35,150,26);
Line(450,35,455,26);Line(450,35,450,26);
Line(155,123,156,114);Line(155,123,159,115);
Line(155,273,156,264);Line(155,273,159,265);
Line(445,123,444,114);Line(445,123,440,115);
Line(445,123,444,114);Line(445,123,441,116);
Line(445,273,444,264);Line(445,273,440,265);
Line(293,135,287,142);Line(293,135,291,143);
Line(307,135,309,143);Line(307,135,312,142);
Line(290,282,282,288);Line(290,282,285,290);
Line(311,282,315,290);Line(311,282,317,288);
SetFillStyle(1,8); for counter := 0 to 1 do begin
Line(540,counter*70+150,600,counter*70+150);
Line(540,counter*70+170,600,counter*70+170);
Line(600,counter*70+150,600,counter*70+170);
Line(540,counter*70+150,540,counter*70+170);
FloodFill(570,counter*70+160,15) end;
SetFillStyle(1,15);
OutTextXY(543,159,'Restore');
OutTextXY(555,229,'Exit'); end; procedure Design_Mark_and_Jumps; begin
SetColor(15);
SetLineStyle(0,0,3);
Hide_Mouse; for counter := 0 to 2 do if ((m shr (7 - counter)) and 1) = 1 then begin
FillEllipse(150,counter*150+50,1,1) end else begin
SetColor(0);
SetFillStyle(1,0);
FillEllipse(150,counter*150+50,1,1) end; for counter := 3 to 4 do if ((m shr (7 - counter)) and 1) = 1 then begin
FillEllipse(300,(counter-3)*150+120,1,1) end else begin
FillEllipse(300,(counter-3)*150+120,1,1) end; for counter := 5 to 7 do if ((m shr (7 - counter)) and 1) = 1 then begin
FillEllipse(450,(counter-5)*150+50,1,1) end else begin
FillEllipse(450,(counter-5)*150+50,1,1) end; for counter := 0 to 2 do if ((r shr (7 - counter)) and 1) = 1 then begin
SetFillStyle(1,10);
FloodFill(150,counter*150+125,15) end else begin
SetFillStyle(1,12);
FloodFill(150,counter*150+125,15) end; for counter := 3 to 5 do if ((r shr (7 - counter)) and 1) = 1 then begin
FloodFill(450,(counter-3)*150+125,15) end else begin
FloodFill(450,(counter-3)*150+125,15) end;
Show_Mouse end; Begin
Init_Graph_Mode; ok := Init_Mouse; flag_of_exit := false; m := m_0; r := r_0; old_m := 0; old_r := 0; if ok = $FFFF then begin {$I-} assign(f,path); reset(f); ok := filesize(f); {$I+} if (IOResult = 0) and (ok = 64) then begin for i := 0 to 63 do read(f,ScrMask[i]);
Set_Graph_Cursor(seg(ScrMask),ofs(ScrMask),2,2) end;
Design_Kernel;
Show_Mouse; repeat
Get_Mouse_State(bm,i,j); if (m old_m) or (r old_r) then begin
Get_Web_State;
Design_Mark_and_Jumps; old_m := m; old_r := r end; if bm = 1 then begin number := 6; for counter := 0 to 2 do if (i < 165) and (i > 135) and
(j < counter*150+130) and (j > counter*150+120) then number := counter; for counter := 3 to 5 do if (i < 465) and (i > 435) and
(j < (counter-3)*150+130) and (j > (counter-3)*150+120) then number := counter; if (number < 6) and (((1 shl (7-number)) and r) 0) then begin m := m and (jump[number] and $FF); m := m or (jump[number] shr 8) end; if (i < 600) and (i > 540) and (j < 170) and (j > 150) then m := m_0; if (i < 600) and (i > 540) and (j < 240) and (j > 220) then flag_of_exit := true end; until flag_of_exit;
Hide_Mouse;
CloseGraph end else begin
CloseGraph;
WriteLn('Ошибка мыши: Device or driver not found.') end End. ----------------------- [pic]
Страницы: 1, 2, 3, 4
