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

Vaqtni optimistik boshqarish

Lokal nedensellik chegaralarini buzmagan konservativ algoritmlardan farqli o'laroq, optimistik usullar ushbu cheklovga amal qilmaydi. Biroq, ushbu yondashuv sababli buzilishlarni aniqlash va uni bartaraf etishni kafolatlaydi. Optimistik uslub konservativ davo bo'yicha ikkita muhim afzallikka ega. Birinchisi, parallelizmning yuqori darajasiga ega. Haqiqatan ham, agar ikkita voqea bir-biriga ta'sir qilishi mumkin bo'lsa, lekin algoritm shunday emaski, u holda optimistik dastur mexanizmi konservativ davolagandan farqli ravishda voqealarni parallel ravishda qayta ishlashga imkon beradi. Ushbu holatda konservativ usul bu ikki hodisaning izchil amalga oshirilishini talab qiladi. Ikkinchidan, konservativ mexanizm, odatda, qo'shimcha ma'lumotni talab qiladi, masalan, ob'ektlar orasidagi masofa. Bu xavfsiz jarayonning hodisasini aniqlash uchun zarur(4.8-rasm).

Ushbu ma'lumotdan foydalanadigan optimallash algoritmlar ham tezroq, lekin bu ma'lumotlarning to'g'riligi ta'siri juda kam. Shuning uchun optimistik algoritm konservativlarga qaraganda matematik dasturiy ta'minotni ishlab chiqishda shaffofroq bo'ladi, dasturiy ta'minot ishlab chiqish osonlashadi. Boshqa tomondan, optimistik yondashuv uchun qo'shimcha hisob-kitoblar talab qilinishi mumkin, bu esa uni qo'llash samaradorligini pasaytiradi.

4.8-rasm. Optimistik algoritmda t1 = 10, t2 = 11 va t3 = 12 ga tegilgan barcha hodisalar bajariladi.

Optimistik algoritmlar quyidagilar bilan tavsiflanadi:

• Mantiqiy jarayonlar xabarlarni vaqt belgilari bilan almashadi.
• jarayonlar topologiyasi o'zgarib turadi, ya'ni. yangi jarayonlarning paydo bo'lishi.
• Bir xil aloqa liniyasiga yuborilgan xabarlar vaqtida tartibga solinishi kerak emas.
• Tarmoq yetarlicha ishonchliligi bilan xabarlarni etkazishi kerak, lekin etkazish tartibi uchun javobgar emas.
Eng mashhur optimizm algoritm Jefferson tomonidan ishlab chiqilgan algoritmdir. Algoritm Time Warp deb nomlanadi. Agar mantiqiy jarayonlar qayta ishlangan voqealardan kichikroq vaqt tamg'asi bo'lgan hodisani qabul qilsa, u bu voqealarni ketma-ket ravishda xronologik tarzda tartibga keltiradi va qayta ishlaydi. Orqaga o'tkazish jarayoni jarayonni qayta ishlashdan oldin (tekshiruv punktlari ishlatiladi) holatni qayta tiklaydi va "yuborilgan" hodisalar orqali xabarlarni yuboradi. Ushbu xabarlarning oldini olish uchun zararli anti-xabarlashuv mexanizmi ishlab chiqilgan.
Antispam - ilgari yuborilgan xabarning nusxasi. Anti-xabar va unga tegishli xabar (ijobiy) bir xil navbatda saqlansa, ular o'zaro yo'q qilinadi. Xabarni o'chirish uchun jarayon mos keladigan xabarni jo'natishi kerak. Agar tegishli ijobiy xabar allaqachon qayta ishlangan bo'lsa, unda qabul qilish jarayoni qaytib ketadi. Bunday holatda, qo'shimcha ogohlantirishlar paydo bo'lishi mumkin. Ushbu takrorlovchi amaliyotni ishlatsangiz, barcha noto'g'ri xabarlar yo'q qilinadi.
Ishonchli algoritmning ishonchli sinxronizatsiya mexanizmi bo'lishiga erishish uchun ikkita muammo hal qilinishi kerak:
• U operatsiyalari kabi ba'zi bir xato jarayoni qaytarib olinmaydi.
• Muhokama qilinayotgan algoritm katta xotirani talab qiladi (qayta tiklash yoki yo'qotishdan qat'i nazar, yaratilgan nazorat nuqtalarida jarayonlarning holatini tiklash uchun), ushbu xotirani bo'shatish uchun maxsus mexanizm zarur.
Bu muammolarning hammasi global virtual vaqt (GVT) yordamida hal etiladi. GVT kelgusida qayta tiklanish vaqtining pastki chegarasi. GVT o'tmishda olingan xabarlar natijasida yuzaga keladigan keskinliklar hisobga olingan holda hisoblanadi. Shunday qilib, ishlov berilmagan va qisman qayta ishlanadi xabarlar orasida eng kichik TIMESTAMP GVT hisoblanadi. hisoblangan qiymati GVT so'ng, GVT cheksiz model vaqtida amalga sobit kiritish Ey, xotira (mantiqiy jarayonlar har biri uchun bir davlatning bundan mustasno) tiklanadi.
GVT hisoblash konservativ algoritmlarni LBTS hisoblash juda o'xshaydi. Buning sababi, mantiqiy jarayoning o'tmishdagi xabarlari yoki xabarlarga qarshi bo'lganligi sababli. Binobarin, GVT - keyinchalik olinishi mumkin kelajakda xabarlar (yoki antisoobscheny) vaqti muhri, quyi chegarasi hisoblanadi.
GVT (LBTS) hisoblash uchun bir necha algoritmlar mavjud. mos kelmaydigan, hisoblash algoritmlari yilda GVT imitatsion paytida fon rejimida ishlaydi. Bu holatda, jarayon turli vaqtlarda mahalliy minimal xabardor qilinishi kerak bo'lgan qiyinchilik tug'iladi. Ikkinchi muammo, yuborilgan, lekin hali olinmagan xabarlarni ko'rib chiqish bilan bog'liq. Ba'zi mualliflar (hedef (hedef)) samarali yuqorida bayon muammolarni hal, hisoblash va kommunikatsiya hisoblagichlarini keyingi segmentlar foydalanishni tavsiya qilamiz.
Sof Time Warp tizimlari uchun ba'zi bir jarayonlarning haddan tashqari "oldinga siljishi" bilan tavsiflanadi. Bu juda jiddiy xotirani va uzoq muddat qaytib ketishga olib keladi. Eng optimistik algoritmlar ushbu "ishlaydigan" narsani chegaralashga harakat qiladilar. Shu maqsadda, model vaqtida "ko'chib" bo'lgan oyna kiritiladi. Oyna [GVT, GVT + W] deb ta'riflanadi, bu erda V foydalanuvchi tomonidan belgilangan parametrdir. Jarayon faqat vaqt belgilari belgilangan vaqt oralig'ida bo'lgan voqealarni ishlaydi. Sinxronizatsiya algoritmining harakatlanuvchi oyna bilan murakkab modifikatsiyalari mavjud: V parametri uchun uni o'tkazish uchun algoritm belgilanadi.
Yana bir yondashuv shuki, xabarni jo'natish, kafolatni qaytarib olishdan keyin sodir bo'lmaydi deb gumon qilingan paytgacha qoldiriladi. Boshqacha aytganda, GVT tadbirni rejalashtirilgan model vaqtiga o'tadi. Shunday qilib, anti-xabarlarga bo'lgan ehtiyoj yo'q bo'lib ketadi va kaskad kikbakorlar (yangi qo'shimchalar keltirib chiqaruvchi zarbalar) chiqarib tashlanadi.
"Qayta ko'rib chiqish" dan foydalanadigan yondashuv mavjud. "Orqaga qarab" konservativ sinxronizatsiya protokollarida "oldindan ko'rish" ga o'xshash narsa. Bu sizga qarshi xabarlardan xalos bo'lishga imkon beradi.
Bundan tashqari, ba'zida noto'g'ri xabarlarni (Fujimoto) tezda bekor qilish uchun ishlatiladigan to'g'ridan-to'g'ri bekor qilish texnikasi mavjud.
Optimistik algoritmni amalga oshirish bilan bog'liq yana bir muammo - tarixiy ma'lumotlarni saqlash uchun katta xotira xarajatlari. Xotira muammosiga ba'zi yechimlarni batafsil ko'rib chiqamiz:
• Xotirani bo'shatish uchun orqaga buriling (Jefferson).
• Har bir voqea so'ng saqlashdan ko'ra, joriy holatni kamroq saqlang. Saqlash davri imitatsiya boshida yoki har bir saqlangan davlatdan keyin qayta hisoblab chiqilishi mumkin.
• Vaqt belgilari GVT dan katta bo'lsa ham, davlat vektorlari egallagan xotirani bajaring.
Optimallashtirish uchun Time Warp algoritmini boshqarishda erta usullar foydalanuvchi tomonidan belgilangan parametrlarga asoslangan. Keyinchalik algoritmni tatbiq etuvchi adaptiv yondashuvlar qo'llanildi va ushbu algoritmni bajarish tezligini oshirish uchun sozlandi.
Shunday qilib, modelni bilishdan foydalanadigan yondashuv ko'rib chiqildi.
Imitatsiya tajribasining bajarilish vaqtini an'anaviy ham, agentlik imitatsiyasi modelida tarqatish uchun qisqartirish. Ko'pincha, sinxronizatsiya algoritmlarini optimallashtirishda, ishlab chiquvchilar algoritmni universallashtirishga moyildirlar va yuqorida keltirilgan ishlarning natijalari muayyan model haqida ma'lumotni olishning ham foydali ekanligidan dalolat beradi. Shu bilan yondashuv taqsimlangan imitatsiya tajribasi o'tkaziladigan hisoblash nodlarini muvozanatlashda qo'llash maqsadga muvofiqdir.