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

Petri tarmoqlarining tasnifi

Har bir inson, hatto informatika bilan shug'ullanishi shart bo'lmasa ham, uni yaxshi biladi

texnik topshiriq va spetsifikatsiya kabi tushunchalar bilan
Agar kimdir tushuntirishga muhtoj bo'lsa, Vikipediyaga murojaat qilishingizni tavsiya qilamiz. Bu yerda
tushunishni kutgan holda faqat ba'zi fikrlarga to'xtalamiz
Petri tarmoqlarini tasniflash zarurati
Agar kimdir tushuntirishga muhtoj bo'lsa, Vikipediyaga murojaat qilishingizni tavsiya qilamiz. Bu yerda
tushunishni kutgan holda faqat ba'zi fikrlarga to'xtalamiz
Petri tarmoqlarini tasniflash zarurati
Texnik topshiriq (TK) har qanday murakkab ob'ektni, tabiatidan qat'i nazar, loyihalash uchun dastlabki hujjatdir.
TK buyurtmachi va pudratchi o'rtasidagi munosabatlarni boshqaradi va mohiyatan tomonlarning javobgarligini belgilaydigan huquqiy hujjatdir.
Vakolatli TK sizga loyiha uchun vaqt va xarajatlarni sezilarli darajada kamaytirishga, har ikki tomonda ham jiddiy xatolarga yo'l qo'ymaslik imkonini beradi. TK ning etishmasligi voqealarga olib keladi
Anekdot voqeasi ma'lum bir kompaniya taniqli ixtirochi Edisonni elektr generatorini tuzatish iltimosi bilan taklif qilganida ma'lum. U bolg'a bilan qurollanib, o'rashni almashtirish kerak bo'lgan joyni ko'rsatmaguncha, butun perimetri bo'ylab generatorni urdi. Mashinani almashtirgandan so'ng ishlay boshladi,
va firmaning baxtli egasi Edisonga chek berib, undan so'ralgan summani o'zi yozishini so'radi. O'sha paytda 100 dollar deyarli edi
bir boylik va mijoz pudratchidan uning nima uchun ekanligini tushuntirishni so'radi
xizmatlar juda qimmat. Edison bu savolga oddiygina javob berdi: protseduraning o'zi 1 dollar turadi va men jihozni qanday tuzatishni bilishim 99 dollarni tashkil qiladi.
Kompyuter fanida TK emas, balki rasmiy deb ataladigan narsa ko'proq qo'llaniladi
spetsifikatsiya - dasturiy ta'minot yoki apparatning matematik tavsifi
ushbu tavsifga muvofiq amalga oshirilishi mumkin bo'lgan tizim
va tizim modelidir. Asl modelni tekshirish va tasdiqlashning (haqiqiyligini) (rasmiy) usullaridan foydalanish uning spetsifikatsiya talablariga javob beradimi yoki yo'qligini aniqlash imkonini beradi.

Ushbu kontekstda biz Petri to'rlari haqida gapirayotganimiz sababli, tabiiy ravishda savol tug'iladi: ushbu Petri tarmog'ining dastlabki vazifasini qanday tekshirish kerak.

amalga oshirilgan tizim xatti-harakatlarining undan oldin istalmagan ta'sirining yo'qligi
amalga oshirish yoki ular mavjud emasligiga ishonch hosil qiling? Ehtimol, eng samarali
Bu savolga javob Petri to'rlarini tasniflashga urinishdir. Nega? G'oya oddiy: modelning egaligini aniqlang (spetsifikatsiya)
Petri to'rlarining ma'lum sinflari. Bundan tashqari, ushbu bobdan boshlab
Petri to'rlari nazariyasi haqida bo'lsa, unda bunday bo'lishi mumkinmi (har qanday
boshqa) tasnifsiz nazariya? Bundan tashqari, tarix ko'rsatganidek
Fanlar, to'g'ri tasniflash ko'pincha yangi nazariyalarni keltirib chiqaradi.
Xo'sh, biz qaysi sinflar haqida gapirayapmiz? Ilovalarda, agar barcha kirish pozitsiyalari bo'lsa
Ushbu o'tishning kamida bitta belgisi mavjud, keyin bu
fakt bu o'tishning qo'zg'alishi uchun ma'lum bir shartga rioya qilish va uni hodisa sifatida tetiklash deb talqin qilinadi. Shuning uchun, har bir
Petri tarmog'ining bir bo'lagi ba'zi sabablarga mos keladi
spetsifikatsiyadagi havolalar.
Qo'shma korxona shaklida modelning o'ziga xos xususiyatlarining mavjudligi har xil turdagi xatti-harakatlarni (ko'p turli diagrammalar) hosil qiladi. Matn yozish vazifasi
SP ularning xatti-harakatlarining quyidagi ta'siri bilan bog'liq. Tarmoqlarning ba'zi pozitsiyalarida cheksiz ko'p belgilarni to'plash mumkin bo'lganligi sababli
ruxsat etilgan holatlar (belgilar) to'plami chekli bo'lmasligi mumkin.
Petri tarmog'ida o'lik nuqtalar bo'lmasligi mumkin (masalan
tarmoqlar tsiklik yoki avtonom jarayonlarni modellashtiradi). Nihoyat,
tsikl faqat ruxsat etilgan holatlarning ayrim kichik to'plamidagi shtatlarni o'z ichiga olishi mumkin. Bu xususiyatlar Petri tarmoqlarini tasniflashni ham talab qiladi.
Turli xil SPlar bir-biridan nafaqat grafik tuzilmalarida, balki o'zgarishlar diagrammalarini etiketlashda ham farq qilishi mumkin (shtatlar, shuningdek, ruxsat etilgan holatlar to'plami. SP bo'lgan modelni o'rganish uning statik va statik xususiyatlarini o'rganish bilan bog'liq. dinamik xususiyatlar
Tasniflash
SP ruxsat etilgan konfiguratsiyalarga (statik cheklovlar) va mumkin bo'lgan belgilar turlariga (dinamik cheklovlar) qo'yilgan sifat va miqdoriy cheklovlarga asoslanadi.

Keling, alohida qiziqish uyg'otadigan ba'zi sinflarning ta'riflarini beraylik

Dinamik cheklovlar bilan hosil qilingan Petri tarmoqlari
Petri tarmog'i deyiladi: k-chegaralangan (k ≥ 1 - butun son), agar uning erishish mumkin bo'lgan holatlar to'plamida pi ∈ P pozitsiyasi bo'lmasa.
µ( pi ) > k (bunda Petri tarmog‘ining ishlashi
k dan ortiq belgilar);
agar u 1-chegaralangan bo'lsa, xavfsiz (uning hech bir pozitsiyasida
bir nechta marker paydo bo'ladi);
chegaralangan, agar u k bilan chegaralangan bo'lsa;
1- konservativ, agar Petri tarmog'ining ishlash jarayonida bo'lsa
undagi belgilarning um umiy soni doimiy bo'lib qoladi, ya'ni. har kim uchun



t Tr ∈ yuzaga keladi

Keling, ta'riflaringizning amaliy ma'nosini sharhlaylik.

SP ning cheklangan xususiyati saqlangan ma'lumotlarning cheklanganligini aks ettiradi
qo'shma korxonaning "xotirasida"
Haqiqatan ham, agar SP ba'zi parametrlar bilan cheklangan bo'lsa
k bo'lsa, bundan kelib chiqadiki, mumkin bo'lgan butun sonni belgilash vektorlari soni cheklangan va shuning uchun PN tomonidan modellashtirilgan tizimdagi holatlar soni ham cheklangan. Bunday holda, har doim mavjud bo'lgan barcha SP belgilarini ifodalash uchun xotira miqdori bo'yicha yuqori chegarani topish mumkin.
SP ning xavfsizligi to'g'ridan-to'g'ri moslikni topish imkoniyatiga mos keladi
Petri tarmog'i va ba'zi bir mantiqiy sxema o'rtasida, ularning holatlari ikkilik vektorlar sifatida ifodalanishi mumkin, ularning maksimal soni 2n soni bilan cheklangan, bu erda n - PNdagi pozitsiyalar soni. SP ning konservatizmi, masalan, modellashtirilgan tizim cheklangan miqdordagi resurslarga ega ekanligini ko'rsatishi mumkin. Zamonaviy muammoli bayonotlarda ko'pincha iste'mol qilinadigan energiya oqimlarini simulyatsiya qilish kerak (batareya quvvati cheklangan mobil tizimlardagi eng muhim manba)
Petri to'rlarining jonliligining pragmatikligini tushunish oson - agar biz hamma narsani xohlasak
Simulyatsiya qilingan tizimdagi organlar o'z ishining butun tsikli davomida faol bo'lib qoldi, tegishli Petri tarmog'i tirik bo'lishi kerak.
Keling, ilovalarda muhim bo'lgan va PN ga qo'yilgan statik cheklovlar tomonidan yaratilgan Petri tarmoqlarining ba'zi sinflarini sanab o'tamiz. (Bu yerda,
|A| orqali A) to‘plamning kardinalligini belgilaymiz.
Avvalo, bunday tarmoqlarning ma'nosi vakillik qilish imkoniyati bilan bog'liq
ma'lum bir parallel hisoblash jarayonlarining xatti-harakatlarida
"xususiyatlar", masalan, tanlov tufayli shoxlanish va turli manbalarda mustaqil harakatlar bilan bog'liq parallel "iplar". Bu nuqtai nazardan, masalan, belgilangan grafiklar shartlar bo'yicha tanlash mumkin bo'lmagan PNlar sinfidir. Ular faqat parallelizmga ega bo'lishi mumkin, bu barqaror boshqaruv tuzilmalarini modellashtirish uchun foydalidir
va operatsiyalarning o'zgarmas (ma'lumotlardan) ketma-ketligi, masalan, konveyer konstruktsiyalarida. Avtomatik qo'shma korxonada, aksincha, bu mumkin emas
parallel bo'ling, lekin tanlov bo'lishi mumkin. Ushbu sinflar asosan ikki tomonlama bo'lib, bir-birini to'ldiradi, bu erkin tanlov tarmoqlarida aks etadi,
bu ikkala sinfni o'z imkoniyatlari bo'yicha qamrab oladi.
Asosiysi, resursning o'ziga xosligi (masalan, protsessor bloki) tufayli ikkala harakatni bir vaqtning o'zida bajarish mumkin emas.
yoki aloqa avtobusi).