4-ma’ruza. Taqsimlangan imitasion modellashtirish va modellashtirishda vaqtni sinxronizasiyalash. Reja

5. Konservativ vaqtni boshqarish

Birinchi sinxronizatsiya algoritmlari konservativ usuldan foydalanilgan. Konservativ protokolning asosiy vazifasi keyingi hodisaning ishlov berilmagan hodisalar ro'yxatidan o'tkazilishi "xavfsiz" bo'lgan vaqtni aniqlashdir. Boshqacha qilib aytganda, agar jarayon boshqa jarayonlardan pastroq vaqt tamg'asi bilan hodisa sodir bo'lmaganda, voqea xavfsiz bo'lishi mumkin. Konservativ yondashuv, xavfsiz bo'lish kafolati bo'lmagunga qadar, voqea sodir bo'lishiga yo'l qo'ymaydi.

Ko'p konservativ algoritmlar mantiqiy jarayon orqali olinadigan kelajakdagi xabarlarning LBTS (Time Stamp ustida pastki bog'lanish) hisobiga asoslangan. Ushbu mexanizm ishlov berilmagan hodisalar ro'yxatidan muntazam hodisalarning xavfsizligini tekshirish imkonini beradi. Haqiqatan ham, agar konservativ algoritm LBTS = 11 ni aniqlasa, unda ishlamaydigan hodisalar ro'yxatidan 11dan kam vaqt belgisi bo'lgan barcha voqealar xavfsizdir va bajarilishi mumkin. Shunga ko'ra, 11 dan katta timestamp bo'lgan voqealar xavfsiz emas va amalga oshirilmaydi. 12 ta (LBTS = 12) vaqt tamg'asi bo'lgan voqealarga kelsak, ularni qayta ishlash ma'lum konservativ algoritmni va bir xil vaqt nuqtasiga (bir vaqtning o'zida sodir bo'lgan voqealar - bir vaqtning o'zida sodir bo'lgan) .
Biz mantiqiy jarayonlarda bir xil model vaqt uchun rejalashtirilgan hodisalarni hisoblamaymiz.

4.3-rasm "Bank" jarayoni va har bir aloqa liniyasining FIFO navbatchilari.

Nolli xabarlar bilan algoritm.
Birinchi konservativ algoritmlar Bryant, Chandy, Misra tomonidan ishlab chiqilgan algoritmlardir.
Algoritm quyidagini ta'kidlaydi:
• Xabarlarni bir-biriga yuboradigan jarayonlarning topologiyasi ma'lum va aniqlangan.
• Har bir mantiqiy jarayon xabarlarni kamaytirmayotgan vaqt belgilari bilan yuboradi.
• Aloqa muhiti xabarlarni jo'natish tartibida etkazib berishni ta'minlaydi.
Ushbu taxminlarga asoslanib, quyidagi xulosani keltiramiz:
• Aloqa liniyasida qabul qilingan xabarning vaqt belgilari ushbu aloqa liniyasi orqali uzatiladigan kelajakdagi barcha xabarlarning vaqt belgilari (LBTS) pastki chegarasidir.
• Mantiqiy jarayonning pastki vaqt tamg'asi (LBTS) barcha kirish liniyalari bo'yicha jarayon tomonidan olingan barcha pastroq vaqt belgilari sifatida tavsiflanadi.
Har bir bog'ning xabarlari navbatda, bu FIFO intizomi tomonidan qayta ishlanadi. Navbat shuningdek, vaqt belgilari bo'yicha buyurtma qilinadi. Har bir bog'da navbatdagi birinchi xabarning vaqtinchalik damgasi (agar mavjud bo'lsa) yoki so'nggi qabul qilingan xabarning vaqt tamg'asi bilan teng bo'lgan o'z mahalliy vaqti bor (4.3-rasm). Jarayonning o'zi o'zi uchun rejalashtirgan barcha hodisalar boshqa navbatda. Algoritm vaqti-vaqti bilan ulanishni eng qisqa vaqt bilan tanlaydi va hodisalar bo'lsa, bu hodisani qayta ishlaydi. Navbat bo'sh bo'lsa, jarayon bloklanadi. O'zingiz uchun rejalashtirgan xabarlar navbatining holatini tekshirsangiz jarayon hech qachon bloklanmaydi. Shunday qilib, ushbu algoritm har bir mantiqiy jarayonni voqealarni xronologik tartibda qayta ishlashga imkon beradi.
Maqsad: tadbirlar xronologik tartibda amalga oshirilishi kerak:
(imitatsiya oxirigacha emas) boshlang
Har bir navbatda kamida bitta xabar mavjud bo'lguncha kutib turing
Har bir navbatni ko'rib, xabarni eng kichik yorliq bilan o'chirib tashlang.
Ushbu hodisani ko'rib chiqing
Misolga qaytib boraylik: navbatda, t1 = 10, t2 = 11 vaqt uchun rejalashtirilgan tadbirlar navbati bilan qayta ishlangan. Bu jarayon xaridordan xabarning ko'rinishini kutmoqda. Aks holda, u ishni davom ettira olmaydi.
Jarayon bloklanadi (4.4 rasm).

4.4- Rasm Jarayon bloklanadi, chunki xaridor jarayoni bilan aloqa liniyasida xabar yo'q.

Algoritm lokal nedensellikka erishishiga qaramasdan, u o'limga olib kelishi mumkin. Haqiqatan ham, barcha aloqa liniyalaridagi vaqt markalarining pastki chegarasi ishlov berilmagan hodisalardan kamroq bo'lsa, bu boshqa davrni kutishga olib keladi.
Misol: Shunday qilib, bizda LP₁, LP₂, LP₃ jarayonlari mavjud. Jarayon LP₁ bloklangan, chunki Xabarni LP₃ dan kelishi uchun kutadi va xabarni LP₂ jarayoniga yubora olmaydi. LP2 jarayoni ham bloklanadi, u LP1 dan xabarlarni kutadi. LP₃ jarayoni o'z navbatida qulflangan bo'ladi, chunki uning birinchi navbatida birinchi LP₁ jarayonidan xabar yo'q. Keling, jarayonlarning davriy kutish jarayoni (qulflashga) borligini ko'ramiz. Masalan, bir misol, shakl, Chandy va Misraning halokatlarining oldini olish uchun nol xabarlarni ishlatishni taklif qildi. LP_a jarayoni Tnull vaqt tamg'asi bilan LPb jarayoniga xabar yuboradi. Ushbu jarayon LP_a LP_b jarayoniga Tnullga qaraganda kamroq vaqt oralig'ida xabar yubormasligini bildiradi. Nolli xabarlar modellashtirilgan ob'ektning jismoniy hodisalariga mos kelmaydi.

4.5- rasm. Jarayonlarni vaqtincha kutish.

Jarayonlar keyingi hodisani ko'rib chiqqandan keyin barcha chiqish kamarlariga nolli xabarlar yuboradi. Nolinchi xabar keyingi xavfsiz voqeani aniqlash uchun qo'shimcha ma'lumot sifatida xizmat qiladi.

Nolli xabar oddiy xabar sifatida ko'rib chiqiladi, ammo jarayon o'zgaruvchisi va hech qanday voqea rejalashtirilmasligi kerak. Mantiqiy jarayonning mahalliy vaqti nolinchi xabarning vaqt tamg'asini bosadi.

4.6- rasm. Null xabarlarni chiqish kamarlariga yuboring.

Jarayon yuboradigan nolinchi xabarning vaqt tamg'asini qanday aniqlaydi?

Har bir ulanishning soat qiymati ushbu havolaning tamponidan chiqariladigan navbatdagi hodisaning vaqt belgilari pastki chegarasini belgilaydi. Ushbu pastki chegara operatsiyani bajarish haqidagi ma'lumot bilan birgalikda, chiqish kamarlaridan yuborilgan barcha xabarlar uchun vaqt belgilari pastki chegarasini belgilash uchun dastlabki ma'lumotdir. Fujimoto quyidagi misolni keltiradi: agar ba'zi bir xizmat ko'rsatuvchi qurilmada T modelidagi model vaqtidagi dasturni qayta ishlasa, keyin yuborilgan xabarning vaqt tamg'asi kelajakda paydo bo'lishi mumkin bo'lgan har qanday xabarning vaqt tamg'asidan katta bo'lgan T modeli vaqt birliklari bo'ladi (4.5-rasm).
Jarayon nol yoki nolga teng bo'lmagan xabarni qayta ishlashni tugatgandan so'ng, u yana chiqadigan kamonlarga bo'sh xabar yuboradi. Nolli xabar olgan jarayon timestampning pastki chegarasini hisoblashi va bu ma'lumotni qo'shnilariga yuborish kerak va hokazo.
Nolinchi xabarlar bilan algoritm (har bir mantiqiy LP jarayonida bajarilgan)
Maqsad: Voqealar xronologik tartibda amalga oshirilishi va halokatga olib kelishini ta'minlash
(imitatsiya oxirigacha emas) boshlang
Shart shart bajarilgunga qadar kuting: har bir FIFO navbat
kamida bitta xabar mavjud.
Voqeani FIFO dan eng kichik vaqt belgilari bilan o'chirib tashlang.
Ushbu hodisani ko'rib chiqing.
Qo'shnilaringizga vaqt tamg'asi bilan nol-xabar yuboring,
ushbu LPga yuborilgan kelgusi tadbirlarning pastki chegarasini bildiradi
(joriy vaqt + lookahead) tugatish
Shunday qilib, yuqoridagi algoritm nolli xabarlarni ishlatib, o'lik uchidan qutilish imkonini beradi.