Taqsimlangan algoritmlar va tizimlar
Daraxt algoritmini tanlash
Download 245.82 Kb. Pdf ko'rish
|
Mustaqil ish 2 23 02 23
- Bu sahifa navigatsiya:
- 3.Algortm matniga qo’yilgan mantiqiy qiymatlar.
|
Daraxt algoritmini tanlash
Agar taqsimlangan tizim topologiyasi daraxt yoki mavjud bo'lsa "Axborotni tarqatish uchun to'lqin algoritmlari" bo'limida keltirilgan algoritm yordamida tanlov qilish mumkin. Bu algoritm barcha so'nggi tugunlar algoritm tashabbuskori bo'lishini talab qiladi. Algoritmni ba'zi saytlar ham tashabbuskor bo'lgan holatga aylantirish uchun uyg'onish bosqichi qo'shiladi. Saylovni boshlamoqchi bo'lgan saytlar boshqa barcha saytlarga Sayt har bir kanal orqali sayt identifikatorini hisoblash va har bir sayt qaytish (OK) protsedurasini bajarish uchun kengaytirilgan Axborotni tarqatish to'lqini algoritmlaridan algoritmni bajarishni boshlaydi. Sayt ushbu protsedurani amalga oshirganda, u identifikatorni biladikoordinator; agar bu identifikator mos kelsajarayon identifikatori, u koordinatorga aylanadi, agar bo'lmasa, yutqazuvchi. 3.Algortm matniga qo’yilgan mantiqiy qiymatlar. Algoritm matnida jo'natilgan mantiqiy qiymati har bir saytga xabarlarini ko'pi bilan bir marta yuborish uchun ishlatiladi va hisoblagich o'zgaruvchisi sayt tomonidan qabul qilingan uchun ishlatiladi. var is_sent: mantiqiy init false; hisoblagich: integer init 0; rec p[q] : boolean dlya vseh q prinadlejashchix Out(this) init false; m: integer this; davlat: (uyqu, koordinator, yo'qolgan) init uyqu; start if this - inisiator then begin is_sent: = true; forall q in Out(this) q end ga ; while counter < card (Out(this)) do begin qabul agar yuborilmasa, start is_sent: = true; forall q in Out(bu) q oxirigacha ; (* Nachalo algoritma iz lektsii 12 *) while card {q: not rec p[q] } > 1 do q dan qabul qilishni (token, r) boshlaydi; recp[q]: = true; agar est(r) > est(m) bo'lsa, m: = r end; not rec p[q0] bilan q0 ga (token, m) yuborish; q0 dan qabul qilish (token, r); agar est(r) > est(m) bo‘lsa, m := r; (* return(OK) s otvetom m *) agar m = bu holda holat: = koordinator boshqa holat: = yo'qolgan; forall q in Out(this), q not equils q0 do send (token, m) to q end Hech bo'lmaganda bitta sayt algoritmning bajarilishini boshlaganida, barcha saytlar barcha qo'shnilariga qo'shnidan boshlaydi. Barcha jarayonlar daraxt uchun algoritmni bir xil ball qiymati, ya'ni saytning eng yuqori balli bilan yakunlaydi. Bu ballga ega yagona sayt shtatda tugaydikoordinator, va boshqa barcha saytlar yutqazgan holatda. Har bir kanal orqali ikkita yuboriladi, shuning uchun xabarning murakkabligi 4N–4 ni tashkil qiladi . Birinchi jarayon algoritm boshlanganidan keyin D vaqt birliklari ichida har bir jarayon jarayon to'lqinni boshladi. Birinchi qaror to'lqin boshlanganidan keyin D vaqt birligidan kechiktirmay, oxirgi qaror esa birinchidan keyin D vaqt birligidan kechiktirmay qabul qilinishini ko'rish oson, buning uchun umumiy vaqt 3D+1 ni tashkil qiladi. Agar kanaldagi xabarlar tartibini o'zgartirish mumkin bo'lsa (ya'ni, kanal FIFO bo'lmasa), jarayon o'sha qo'shnidan qo'shnisidan xabar (token, r) olishi mumkin. Bunday holda, xabar (token, r) vaqtincha saqlanishi yoki keyinroq keladigan xabarlar (token, r) sifatida qayta ishlanishi mumkin. Lelanning halqali (yo'naltirilgan tsikl) arxitekturali taqsimlangan tizim algoritmida har bir tashabbuskor barcha tashabbuskorlarning identifikatorlari ro'yxatini hisoblab chiqadi, shundan so'ng eng yuqori est() ballga ega bo'lgan tashabbuskor tanlanadi . Har bir tashabbuskor o'z identifikatorini o'z ichiga olgan tokenni halqa atrofida yuboradi va bu token barcha saytlar tomonidan uzatiladi. Kanallar FIFO intizomiga ega, deb taxmin qilinadi va tashabbuskor boshqa tashabbuskorning tokenini olishdan oldin o'z tokenini yaratishi kerak (sayt tokenni olganida, u algoritmni keyinchalik ishga tushirmaydi). Boshlovchi p o'z tokenini olganida, barcha tashabbuskorlarning tokenlari p dan o'tgan va p tashabbuskorlar orasida eng yuqori ballga ega bo'lgan taqdirdagina p tanlanadi. Sizga shuni eslatib o'tamizki, siz tashqi va ichki sayt belgilarini farqlashingiz kerak. Bu erda p va q tashqi belgilar. Ular boshqa saytlarda ishlaydigan jarayonlar tomonidan kerak bo'lganda foydalaniladi. O'z jarayonida p o'z sayti this identifikatori bilan belgilanadi. Bu holda, albatta, p va bu bir xil qiymatga ega (masalan, raqamli yoki kod). Quyidagi algoritmda davlat o'zgaruvchisi sayt holatini belgilaydi. Lelan algoritmi: var Listp: integer to'plami {est(this)}; davlat: (uyqu, koordinator, yo'qolgan); boshlash agar bu - keyin tashabbuskor start holati: = cand; (token, bu) Keyingi p ga yuboring; qabul qilish (belgi, q); q not esa buni amalga oshirishga tengdir start Ro'yxat p : = Ro'yxat p qo'shilish {q}; yuborish (token, q) Next_p ga; qabul qilish (belgi, q); oxiri; agar bu = max ( p ro'yxati) bo'lsa, u holda: = koordinatorini bildiring boshqa holat: = yo'qolgan oxiri Aks holda takroriy qabul qilish (token, q); yuborish (token, q) Keyingi p ga; agar davlat = uyqu, keyin holat: = yo'qolgan yolg'onga qadar oxiri Ringdagi tokenlar tartibi saqlanib qolganligi sababli (FIFO kanali taxminidan) va tashabbuskor q qabul qilishdan oldin (token, q) yuboradi (token, p), keyin inisiator p qaytib kelishdan oldin (token, q) oladi (token, p). Bundan kelib chiqadiki, har bir tashabbuskor p barcha tashabbuskorlar to'plami bilan bir xil bo'lgan p ro'yxati bilan tugaydi va eng yuqori ball to'plagan yagona sayt tanlangan bo'ladi. Barcha tashabbuskor bo'lmaganlar yutqazgan holatga kiradilar, lekin (token, r) xabarlarni abadiy kutishadi. Rahbar saylov tugaganini e'lon qilish uchun ring atrofida maxsus marker yuborsa, kutish to'xtatilishi mumkin. Quyidagi Chung-Roberts algoritmi saylovda yutqazishi aniq bo'lgan saytlarning markerlarini ringdan olib tashlaydi. Shu ma'noda, u Lelanning algoritmini yaxshilaydi. Bular. inisiator p agar est(q) < est(p) bo'lsa, tokenni (token, q) halqadan olib tashlaydi. Boshlovchi p id q bo‘lgan est(q) > est(p) tokenini olganida mag‘lub bo‘ladi yoki p idli tokenni olganida koordinatorga aylanadi . var holati: (uyqu, koordinator, yo'qolgan); boshlash agar bu - keyin tashabbuskor start holati: = cand; (token, bu) Keyingi p ga yuboring ; takroriy qabul qilish (token, q); agar q = bu holda: = koordinatorini bildiring else if est(this) < est(q) keyin start if state = cand then state: = lost; yuboring (token, q) Keyingi p oxiri davlat = koordinatorgacha oxiri Aks holda takroriy qabul qilish (token, q); yuborish (token, q) Keyingi p ga; agar davlat = uyqu, keyin holat: = yo'qolgan yolg'onga qadar end (* Faqat koordinator dasturni tugatishi mumkin. U barcha saytlarga o'z identifikatorini aytish uchun xabar yuboradi. *) Eng katta identifikatorga ega bo'lgan inisiator p 0 bo'lsin. Barcha jarayonlar tashabbuskor bo'lmagan yoki identifikatorlari p 0 dan kichik bo'lgan tashabbuskorlardir, shuning uchun barcha jarayonlar p 0 tomonidan yuborilgan tokenga (token, p 0 ) o'tadi. Shuning uchun, p 0 o'zining tokenini qaytarib oladi va tanlangan bo'ladi. Tashabbuschi bo'lmaganlarni tanlab bo'lmaydi, chunki ularning barchasi p 0 tokeni o'tgandan so'ng eng kech yutqazuvchi holatga kirishadi. est(p) < est(p0 ) ballga ega bo'lgan tashabbuskorni tanlab bo'lmaydi; p 0 tokenga (token, p) o'tmaydi , shuning uchun p hech qachon o'z tokenini olmaydi. Bunday inisiator p eng ko'p token (token, p 0 ) u orqali o'tkazilganda yutqazuvchi holatga kiradi. 1 rasm Chung-Roberts algoritmi uchun rasm Shaklda . 18.2 Chung-Roberts algoritmining ba'zi bir momentini ko'rsatadi. Saytlar halqada joylashgan. Ringning tashqi tomonida ularning identifikatorlari ko'rsatilgan, ichki qismida - tanlov qilingan baholarning qiymatlari.koordinatori. 2 raqami bo'lgan doira - bu reyting "31" bo'lgan sayt raqamini ko'rsatadigan marker (token, 2), o'q marker harakati yo'nalishini ko'rsatadi. Algoritm bajarilganda boshlang'ich sayt yulduzcha bilan ko'rsatilgan - bu est(1) = 24 ball bilan 1-sayt . Xulosa Men ushbu Taqsimlangan algoritmlar va tizimlar fanidan berilgan “ Saytlarni tanlash algoritmlari” mavzusi bo’yicha olgan o’zimga xulosalarim avvalo, Saytlar orasidagi tanlov markazlashtirilganda ham amalga oshirilishi kerak algoritm va algoritm tashabbuskori roli uchun ilgari ma'lum bo'lgan nomzod yo'q. Misol uchun, tizimni ishga tushirish jarayoni boshida yoki tizim xatosidan keyin bajarilishi kerak. Ko'pgina dasturchilar marshrutizatorlar, ma'lumotlar bazasi ulanishlari, xatolarni qayta ishlash bilan saytlarni ishlab chiqishni boshlaydilar, bu esa kelajakda o'z kodlarini qayta yozish yoki ular oldindan ko'ra olmagan narsaga qoqilishlari bilan kodga mo'l-ko'l tayoqchalarni kiritish zarurligiga olib keladi. Hamma narsani oldindan ko'rish mumkin emas, buning uchun siz yuqoridan pastgacha tizimni ishlab chiqishingiz kerak. Ishlaydigan yuqori darajadagi sinflarning mavjudligi deyarli avtomatik ravishda xizmatchilar uchun barcha kerakli talablarni aniqlaydi. Ushbu mavzu bo’yicha olgan xulosalarim qisqacha shulardan iborat. |
