Петри желісі СЖ

Петри желісі

Петри желісі - динамикалық дискретті жүйені модельдеуге арналған математикалық құрылғы. Ең бірінші рет 1962 жылы Карл Петри іске асырды.

1-сурет. Петри желісінің мысалы. Ақ дөңгелек – орны, сызық – орын ауыстыру, қара дөңгелек – таңбалар.

Петри желісі – екі жақты бағытталған мультиграф, ол екі типті шыңнан тұрады: бір-бірімен доға арқылы байланысқан орны мен орын ауыстырулар. Бір типтің шыңы тікелей байланысқа түсе алмайды, орындарда таңбалар(маркерлар) болады, олар желі бойынша қозғалысты еркін жасайды.

Таңба кіріс орнынан шығыс орынға бағытталған кезде, орын ауыстыру үрдісі жүреді, оны оқиға деп атайды. Оқиға тез немесе әртүрлі уақытқа байланысты орындалады, ол шарттардың орындалуына байланысты.

Сонымен Петри желесі дегеніміз мультиграф, себебі ол графтың бір шыңынан екінші шыңына дейін еселі доғаның болуына жол береді. Доғаның белгілі бір бағыты болғандықтан, ол бағытталған мультиграф. Граф шыңдарын екі көпмүшеге(орны мен орын ауыстыру) бөлуге болады, осылайша бір көпмүше элементінен әр доға екінші көпмүше элементіне бағытталады. Оны екі жақты бағытталған мультиграф(двудольный ориентированный мультиграф) деп атайды.

Петри желісі параллель өзара байланысқан компоненттері бар жүйе үшін жобаланған еді, оны Карл Адам Петри өзінің «Связь автоматов» атты еңбегінде жариялап, есептеуіш жүйедегі асинхронды компоненттерінің байланысы жайлы негізгі түсініктерін енгізді.

Петри желісінің динамикасы

Петри желісінің қызмет ету үрдісін жеткілікті маркирлеу графында көруге болады. Маркирлеу – маркерлерді(таңбаларды) орны бойынша орналастыру. Желінің жағдайы оның таңбалануы арқылы анықталады – орын бойынша фишкаларды орналастыру.Граф шыңы - Петри желісінің жеткілікті маркирленуі, доға – іске асатын орын ауыстыру белігісімен белгіленіп тұр. Доға әр қимылға түсетін орын ауыстыру үшін құрылады. Қимылға түспейтін орын ауыстыру немесе графта бар таңбалар пайда болса, оны құрастыру тоқтайды. Жеткілікті маркирлеу графы автомат болып табылады.

Петри желісінің кейбір түрлері:

• Уақытша Петри желісі – іске асу(тоқтату) ұзақтығымен анықталатын орын ауыстыру.

• Стохастикалық Петри желісі – тоқтатулар кездейсоқ өлшем ретінде болады.

• Функционалды Петри желісі - тоқтатулар кейбір аргументтердің функциясы ретінде анықталады, мысалы, қайсыбір орындағы таңба саны, кейбір орын ауыстырулардың жағдайы.

• Түрлі-түсті Петри желісі – түс арқылы белгіленген таңбалар әртүрлі типті болуы мүмкін. Таңба типі аргумент ретінде қолданылуы мүмкін.

• Ингибиторлы Петри желісі - ингибиторлы доғаның орын ауыстыруымен байланысқан кіріс орында таңба болса, орын ауыстырудың іске асуына тыйым салатын ингибиторлы доға.

• Иерархиялық желі – мүмкін осындай иерархиялық желілер енгізілген тез әрекет етпейтін орын ауыстырулардан тұрады. Мұндай орын ауыстырудың іске асуы толық өмірлік циклдың іске асқанын сипаттайды.

• WF-желі. WF-желі – жұмыс ағымының желісі. Оны құрастырған Вил ван дер Аальст(Work –жұмыс, Flow- ағым). PN = (P,T,F) Петри желісі жұмыс ағымының желісі деп аталады, егер: 1) і-ға кіретін орын ауыстырулары жоқ тек бір і орны бар; 2) 0-ға кіретін орын ауыстырулары жоқ тек бір соңғы орны бар; 3) берілген желінің әр түйіні і-дан 0-ге дейінгі жолда орналасқан. WF-желілер жұмыс ағымындағы графтардың ақауларын тексеру үшін пайдаланады.

Ақаудың жоқ болуы немесе дұрыс аяқталу келесі талаптарға сай болуы керек:

1. 0 соңғы орны і орнынан кез-келген орын ауыстырудың реттілігі кезінде қол жетімді;

2. WF-желілер үрдіске қатыспайтын артық орыннан тұрмайды.

3. Соңғы орынға жеткен кезде аралық орындарда фишкалар қалмауы тиіс.

Ақаудың болмауы Петри желісінің екі жақсы қасиетіне сәйкес келеді: жандылығы және шектеулілігі.

Петри желісінің сараптамасы

2-сурет. Петри желісіндегі орын ауыстыру мысалы.

Петри желісінің негізгі қасиеттері:

• шектеулілік – кез-келген желі орнында таңба саны белгілі К мәнінен артық бола алмайды;

• қауіпсіздік – шектеуліліктің жеке жағдайы, K=1;

• сақтандылық – қорды жүктеу тұрақтылығы –тұрақты . Мұндағы і орындағы таңба саны, салмақты коэффициент;

• қол жетімділік – желінің берліген жағдайдан басқаға орын ауыстыру мүмкіндігі;

• жандылығы – жобаланатын нысан қызмет еткен кезде кез-келген орын ауыстырудың іске асу мүмкіндігі.

Аталған қасиеттерді зерттеу негізіне жетімділік сараптамасы кіреді. Петри желісінің қасиетін сараптау әдісі жетімділік графын пайдалану, желі жағдайының теңдеуін шешу, орын мен орын ауыстырулардың сызықты инварианттылығын есептеу болып табылады. Сонымен қатар, қосымша әдістер де пайдаланылады: редукция – Петри желісін қасиеттерін сақтай отырып көлемін кішірейту және декомпозиция – бастапқы желіні желі астына бөлшектеу.

1974 жылы Тилак Аджервала Петридің ингибиторлы желісі әмбебап алгоритмдік жүйе екенін көрсетті. Петридің шексіз желісі есептеуіш торды верификациялау үшін енгізілді және Петри желісінің қасиетін күнделікті құрылым(сызықты, ағаш типті, шаршы, үшбұрышты, алты бұрышты, гиперкуб) үшін анықтауға мүмкіндік берді.

Петри желісін анықтау мысалдары

Петри желісі төрттігімен анықталады, мұндағы Р және Т – орын мен орын ауыстырулардың қорытынды көпмүшесі. І және О – кіріс және шығыс функциялардың көпмүшесі. Орын дөңгелек арқылы белгіленсе, ал орын ауыстыру қалың сызықпен белгіленеді; І функциясына орыннан орын ауыстыруға , ал О функциясына орын ауыстырудан орынға бағытталған доғалар сәйкес келеді.

Петри желісінде екі типті нысан болады: динамикалық – орынның ішінде таңбамен белгіленеді және статикалық – Петри желісінің шыңдары сәйкес келеді.

3-сурет. Петри желісінің мысалы

шарты әр кіріс орнында орындалса, орын ауыстыру іске асады, мұндағы - і кіріс орнындағы маркер саны, - і орнынан орын ауыстыруға баратын доға саны; орын ауыстыру кезінде і кіріс орнындағы маркер саны -ға азайса, ал j шығыс орнында -ға артады, мұндағы - j шығыс орнымен орын ауыстыруды байланыстыратын доға саны. 3-суретте әлі жүзеге аспаған кездегі маркерлерді орны байынша орналастыру мысалы көрсетілген. Бұл маркирлеу (2,2,3,1) түрінде жазылады, ал орын ауыстыру болғаннан кейін маркерлеу (1,0,1,4) түріне ие болады.

Жобалау алгоритміне көптеген шарттар мен ережелер енгізу арқылы Петри желісінің түрлерін алуға болады. Осылайша, оқиға реттілігімен қатар, жобалау уақытын енгізу арқылы оны уақытқа байланыстырады. Орын ауыстыруға іске асу ұзақтығын беру арқылы, берілген алгоритммен өзгерту енгізуге де болады. Алынған жоба уақытша Петри желісі деп аталады.

Мысал.

Петри желісі арқылы, сұраулар ағымындағы берілген сипаттамалармен, жалғыз WS жұмыс станциясындағы пайдаланушылар тобының WS-ті пайдалануды және тапсырмалар сипаттамаларын сипаттау қажет.

4-сурет. Петри желісінің мысалға сәйкес суреті

Орын ауыстырулар келесі оқиғалармен байланысқан: - WS пайдалануға байланысты сұраудың түсуі, - станция іс –әрекеті, - станцияны босату, - қызмет етілген өтініштің шығысы; орны WS жағдайын бейнелеуге пайдаланылады: егер -те таңба болса, WS тәуелсіз және берілген сұрау орын ауыстыруының іске асуына әкеледі; бұл сұрауға жауап болмағанға дейін, -те таңба болмайды, сәйкесінше орнына келген сұраулар орын ауыстыруының іске асқанын күтеді.