Студентам > Курсовые > Синтез комбинацонных схем и конечных автоматов
Синтез комбинацонных схем и конечных автоматовСтраница: 8/10
t1 t4
‘Новая’ ‘Новая’
(01001100)
(10010010)
t2
t4 t1 t5
(00100100)
(01000010) (01000010) (10000001)
‘Новая’ ‘Тупик’
‘Тупик’ ‘Новая’
t3
t6
(10011100)
‘Старая’ (10011100)
‘Старая’
Рисунок 3.3.1 – Дерево покрываемости маркировок
Дерево покрываемости удобно оформить в виде графа.
При этом более наглядно видны зацикливающиеся переходы, тупиковые маркировки
никакими дополнительными пояснениями снабжать не требуется – отсутствие дуг,
исходящих из данной маркировки, говорит само за себя. При достижении старой
маркировки её не нужно заново наносить на граф – достаточно соединить дугой
предыдущую маркировку и уже существующую “старую”.
Граф покрываемости сети выглядит
следующим образом:
μ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.
 (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);
| 
Главная
Документация
Файлы
Информация
