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

Ko'rinishni ishlatish (Oldinga yugurish). Konservativ sinxronizatsiya algoritmlari uchun maxsus xususiyat - bu tashqi ko'rinishdan foydalanish ba'zi mantiqiy jarayon mahalliy vaqt tamg'asi T. jarayoni ularga yuborgan kelajakda xabarlari vaqt tamg'asi bo'ladi ta'minlash mumkin, deb taxmin, bir vaqt tamg'asi t + L. teng miqdorda, keyinchalik xabarlarni kelib ortib ketishi Bu holda biz jarayoni nol xabarlarni bir vaqt tamg'asi hisoblash uchun ishlatiladi L. oldindan teng ko'rib chiqish ahamiyatga ega, deb aytish. Ko'rib chiqish qiymati muayyan vaqt oralig'ida hech qanday chiquvchi xabar bo'lmasligini ko'rsatadi.
Muhokama algoritm masalan kabi ko'plab modifikatsiyadagi, individual xatti-mantiqiy jarayonlarda muhim kamaytirish natijasida turli chiquvchi yoylari uchun lookahead hisoblash sezgir bo'ladi. Bu algoritm salbiy ishlashi jarayonlari kuchli ulangan bo'lsa, u holda barcha mantiqiy jarayonlar juda kichik vaqt oralig'ida faqat targ'ib qilinadi, deb haqiqatni ulanishi mumkin. Shunday qilib, imitatsiya tabiiy ravishda izchil. algoritm bir kamchiligi shundaki, iloji lookahead deb bir necha tsiklik kutish LP kichik o'zgarishlar mahalliy soat kichik qiymatlari uchun. Ba'zi tizimlarda, may, va ko'pincha nol oldindan ko'rish (zerolookahead) foydalanishni talab qiladi, lekin algoritm nol oldindan yuqorida muhokama imkon bermaydi.
Keyingi voqeaning vaqt tamg'asi haqida qo'shimcha ma'lumotlardan foydalanish. Nolli xabarlar bilan algoritmlarning kamchiliklarini batafsil ko'rib chiqamiz. Shunday qilib, algoritmning kamchiliklaridan biri bu juda ko'p null xabarlarni ishlab chiqishi mumkin.
Misol uchun, biz ikkita mantiqiy LP jarayoniga egamiz. Ikkalasi ham qulflangan deb taxmin qiling. Ularning har biri 100 belgigacha (TlocLP1 = 100) va n qiymatiga ega. Bo'lsin, keyingi rejalangan tadbir 200. teng, bir vaqt tamg'asi bor davom etadi nol xabarlar bilan algoritm quyidagicha: Xabarlar 101, 102, 103, va hokazo teng vaqt jarayonlari yuboriladi Bu jarayonlar 200 belgigacha bo'lgan vaqtgacha davom etadi. Shundan so'ng, vaqt belgisi 200 (ei, 200) bilan tadbir amalga oshiriladi. Shunday qilib, nol bo'lmagan ishlanmagan voqea yuzaga kelgunga qadar 100 ta nolli xabarlar yuborilganini va ishlov berilishini ko'rayapmiz. Shaklning misolidan. Bu holatda nol-xabar algoritmining samarasizligi 4.6-rasm. Ko'p sonli jarayon bilan ishlayotgan bo'lsak, vaziyat yanada yomonlashadi.
Keling, misolni ko'rib chiqaylik. 4.7- rasm 3 mantiqiy jarayonning o'zaro ta'sirini ko'rsatadi. Nolli xabarlar 5.0, 5.5, 6.0, va hokazolarda rejalashtirilgan, ular har bir vaqtning 0,5 daqiqasida yuboriladi. Nolli xabarlar avvalgi misolga qaraganda ancha katta. Shunday qilib, agar tashqi ko'rinish kichkina bo'lsa, bu juda ko'p null xabarlarga olib keladi.
Muammo, kelajakdagi jarayon voqealari uchun minimal vaqt tamg'asini hisoblash uchun faqat joriy model vaqtini va ko'rinish qiymatini ishlatishdir. Algoritmni takomillashtirish - bu keyingi ishlanmaydigan hodisaning vaqt tamg'asi qiymati haqida ma'lumot. Imitatsiya jarayonida ishtirok etadigan barcha mantiqiy jarayonlar ushbu ma'lumotga tegishli bo'lsa, ular darhol mahalliy vaqtni 200 belgigacha (TlocLP1 = 200) aylantirishi mumkin. Shunday qilib, yuqorida aytib o'tilgan algoritm etishmasligidan nolli xabarlar bilan xalos bo'lishimiz mumkin.



4.7-rasm Ko'p null xabarlar (lookahead = 0.5).

Ko'p rivojlangan algoritmlar, yuqorida keltirilgan g'oyani qo'llaydi.

Yana bir muammo bu: har bir operatsiyani to'liq grafikning vertikasini aks ettiraylik (har bir jarayon boshqa jarayonlarning har biriga xabar yuborishi mumkin). Har bir nol voqea qayta ishlanganida, har bir jarayon barcha boshqa jarayonlarga xabarlarni eshittiradi. Bir so'z bilan aytganda, jarayonlar tomonidan yaratilgan nol voqealar soni juda katta bo'ladi.
Chandy va Misra ushbu muammoni quyidagicha hal qildilar: hisob-kitoblar chiqquncha davom etaveradi. Bundan tashqari, tashvish aniqlanmaydi va yo'q qilinadi. Tushuntirishni eng kam vaqt bilan yuborilgan xabarning xavfsizligi va shuning uchun qayta ishlanishi mumkinligi sababli yo'q qilinishi mumkin.
Ushbu echimning muqobilligi xavfsiz xabarlar sonini ko'paytirish uchun pastki chegarani hisoblashdir.

6.