Mavzu: parallel dasturlashda kelishuv. Petri tarmog‘i magistrant: A

Model tavfsifi
Petri tarmog'i - bu ikki tomonlama yo'naltirilgan grafik bo'lib, ikki turdagi cho'qqilari (joylashuvlar va o'tishlar, mos ravishda doiralar va javonlar bilan ifodalanadi), pozitsiyalarni bog'laydigan yoylar.
o'tishlar va pozitsiyalar bilan o'tishlar va dastlabki belgilar bilan,
vektor bilan ifodalanadi.
Bunday ikki tomonlama yo'naltirilgan grafik misoli shaklda ko'rsatilgan. 2.1


2.1 rasm Petri tarmog‘iga misol

Bu rasmda pozitsiyalar pi belgilari bilan, o'tishlar esa belgilar bilan belgilanadi

tj
. Yo'naltirilgan yoylar faqat pozitsiyalarni o'tishlarga va faqat pozitsiyalarga o'tishlari mumkin, shuning uchun har qanday pozitsiya kirish yoki bo'lishi mumkin.
(i) bir yoki bir nechta o'tishning chiqish pozitsiyasi. Ba'zi pozitsiyalar markerlar yoki chiplar bilan belgilanadi, ular sifatida tasvirlangan
pozitsiya ichiga joylashtirilgan qalin nuqtalar. Umuman olganda, pozitsiya bir nechta fikrlarni o'z ichiga olishi mumkin. Lavozimlarning bunday etiketlanishi tarmoqning dastlabki yorlig'i deb ataladi.

Dastlabki markalash vektorining tarkibiy qismlari soni pozitsiyalar soniga teng va

har bir komponentning qiymati, agar tegishli pozitsiyada marker bo'lmasa, nol bilan yoki manfiy bo'lmagan butun sonlar bilan ifodalanadi.
markerlar soniga teng bo'lgan raqam - pozitsiya ichiga joylashtirilgan qalin nuqta

Petri tarmog'idagi dinamika markerlar bo'ylab harakatlanishi bilan tavsiflanadi

mahalliy xususiyatga ega bo'lgan o'tishning ishlash qoidasi to'g'risidagi konventsiyaga muvofiq tarmoq. Har bir kirish pozitsiyasi kamida bo'lsa, o'tish ishga tushiriladi
kamida bitta marker. Bir muncha vaqt o'tgach (oldindan belgilanmagan), hayajonlangan o'tish yong'inga tushadi. O'tishni ishga tushirish bo'linmas operatsiya hisoblanadi, buning natijasida har bir kirishdan bir vaqtning o'zida bitta token olib tashlanadi.
o'tish pozitsiyalari va uning har bir chiqish pozitsiyasiga bitta marker qo'shish.

Petri tarmog'i hayajonlangan o'tishlarni ishga tushirish orqali bir yorliqdan ikkinchisiga o'tish orqali ishlaydi. Shuning uchun uning xatti-harakati etiketkalash diagrammasi bilan tavsiflanadi - digraf, uning uchlari teglar, yoylari esa nomlar bilan belgilanadi.

o'tishlarni keltirib chiqardi

Rasmiy ravishda Petri tarmog'i (PT) shaklning to'rt barobari sifatida aniqlanadi

Bu erda: P - pozitsiyalarning cheklangan to'plami (boshqacha aytganda, joylar yoki shartlar);
T - o'tishlarning (yoki hodisalarning) cheklangan to'plami; E - chekli yoylar to'plami, E ⊆ P×T ∪ T×P; µ 0 - boshlang‘ich yorliqlash (yorliqlash vektori), µ 0 : P → N, bu yerda N = {0,1,2,…} - salbiy bo‘lmaganlar to‘plami
butun sonlar

tj ∈ T o'tishning kirish va chiqish pozitsiyalari to'plamlari belgilanadi

I(tj) va O(tj) mos ravishda. Xuddi shunday, I(pj) va O(pj) yozuvlari mos ravishda kirish va chiqish boʻlgan oʻtishlar toʻplamining belgisidir.
pozitsiyalari pj ∈ P.

Agar I(tj) va O(tj) larning barcha o‘tishlar ustidagi birikmalarini I va O bilan belgilasak.

tj
∈ T, ya'ni, (j)
T
I = U I t, ( j )
T
O = UO t, P = I UO, keyin Petri tarmog'i bo'lishi mumkin
shaklida ham berilgan

Petri tarmog'ining ikki tomonlama grafik ko'rinishida ko'rinishi o'rnatish imkonini beradi
Petri tarmog'ining tuzilishi statik. Yuqorida aytib o'tilganidek, dinamika modelga pozitsiyalarni belgilash (belgilash) ni o'zgartirish mexanizmi va o'tishlarni boshlash (amalga oshirish) qoidalari to'g'risidagi kelishuvdan foydalangan holda kiritiladi.
Yuqorida ta'riflanganidek, dastlabki yorliqlash Petri tarmog'ining pozitsiyalariga ba'zi bir butun sonlarni (shu jumladan, nol) belgilaydi. Grafikda belgilash quyidagicha o'rnatiladi: tegishli doiralarda ma'lum
markerlar (chiplar) nomini olgan nuqtalar soni (qalin).

Yana bir bor Petri tarmoqlarining ishlash printsipi haqida batafsil to'xtalib o'tamiz:

Petri tarmog'i bo'ylab markerlarning harakati uning o'tishlarini ishga tushirish orqali amalga oshiriladi
Faqat hayajonlangan (mumkin) ishlashi mumkin
o'tish, ya'ni. bunday o'tish tk ∈ T , barcha kirish pozitsiyalari I(tk) kamida bitta markerni o'z ichiga oladi (har bir bunday o'tish uchun va
har bir ps ∈ I(tk) pozitsiyasi uchun bizda µs ≥ 1 bor, bu erda µs = µ( ps ) ps pozitsiyasidagi markerlar sonini bildiradi).
O'tish otilishi o'tishdan keyin har qanday cheklangan vaqt oralig'idan keyin sodir bo'lishi mumkin. Triggerlash natijasi tetiklangan o'tishning barcha kirish pozitsiyalaridan bitta markerni olib tashlash va uning barcha chiqish pozitsiyalariga bitta markerni qo'shishdir.
O'tishni tetiklash bo'linmas akt deb hisoblanadi, ya'ni. barcha kirishlardan markerlarni olib tashlash nazarda tutiladi
pozitsiyalar va ularning barcha chiqish pozitsiyalariga harakati bir zumda, nol kechikish bilan. Biroq, ba'zi ilovalarda, konventsiya
bo'linmaslik to'g'risida buzilishi mumkin.
O'tish davridagi otishma qoidasi konventsiyasi kontseptsiyani aks ettiradi
sabab (sabab) munosabati: bizga ma'lum bo'lgandan keyin
hodisaning ob'ektiv sabablari (shartlari) pishgan, bu hodisa yuz berishi mumkin.
Biroq, uning paydo bo'lish vaqti oldindan ma'lum emas, chunki bizga noma'lum yoki biz uchun ahamiyatsiz bo'lgan boshqa sabablar ham bo'lishi mumkin, ular yakuniy tahlilda muhim sabablar bilan birgalikda qiziqarli voqealar boshlanishini muqarrar ravishda aniqlaydi bizdagi voqealar.

Voqea sodir bo'lgandan so'ng, yangi sharoitlar paydo bo'ladi - oqibatlar, o'z navbatida, keyingi voqealarning sabablari bo'lishi mumkin. Bunday holda, asl sabablar yo'qolishi yoki davom etishi mumkin. Ikkinchisi markerlar resursi to'liq tugamaganligi sababli ham, markerlarning qayta tiklanishi tufayli ham mumkin (pozitsiyalar kirish va chiqish bo'lganda)

Shaklda. 2.2 Petri'ning har bir pozitsiyasi uchun o'rnatilgan qoidalarni aks ettiruvchi to'rtta bo'lakni ko'rsatish (yana shuni eslaymizki
bu shaxsiy korxona)

Yorliqlarni o'zgartirish qoidalari

Shaklda. 2.2a pozitsiyasi pj - hayajonlangan o'tishning chiqish holati *

ti (hayajonlangan o'tish yulduzcha bilan belgilanadi), ya'ni. pj ∈ O(ti)

Unda
holatda, pj pozitsiyasining joriy belgisi µ( p j ) (ya'ni,

o'tishning qo'zg'alishidan oldin joy ti) qo'zg'atilgan o'tishning ishga tushirilishi natijasida ti* belgisi µ' ( p j ) bilan almashtiriladi va
µ' ( p j ) = µ( p j ) + 1 (ya'ni, aynan bitta marker qo'shilgan)
Shaklda. 2.2b
pozitsiyasi pj - hayajonlangan o'tish ti* ning kirish pozitsiyasi, ya'ni.
pj ∈ I(ti). Ti* µ' ( p j ) = µ( p j ) −1 ni ishga tushirish natijasida (pj dan bitta marker olib tashlanadi)
Shaklda. 2.2c pozitsiyasi pj - hayajonlangan o'tish ti* ning ham kirish, ham chiqish pozitsiyasi, ya'ni. p j ∈O(ti ) I I(ti ) , va undan keyin
µ' ( p j ) = µ( p j ) −1 + 1 = µ( p j ) ni ishga tushirish (joylashuvning oldingi belgisi saqlanib qoladi). Nihoyat, rasmda. 2.2d, pj pozitsiyasi o'tish uchun hodisa emas (o'tish bilan bog'liq emas) ti, ya'ni. p j ∉O(ti ) U I(ti ) .
O'tish ti quvvatlanmaydi, otash mumkin emas va markalash
ham saqlanadi: µ'( p j ) = µ( p j ) .
Shaklda ko'rsatilgan parchada. 2.3,



Guruch. 2.3. O'tish otish natijasi