Taqsimlangan algoritmlar va tizimlar” fanidan mustaqil ish 2 Mavzu

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 xabarlar sonini hisoblash 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 ni yuboring
;
while counter < card (Out(this)) do
begin qabul ; hisoblagich: = hisoblagich + 1;
agar yuborilmasa,
start is_sent: = true;
forall q in Out(bu) q oxirigacha
ni yuboring
;
(* 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 xabarlarini jo'natadi va har bir sayt har bir qo'shnidan xabarini olgandan so'ng daraxt uchun algoritmni bajarishni 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 xabari va ikkita xabar yuboriladi, shuning uchun xabarning murakkabligi 4N–4 ni tashkil qiladi . Birinchi jarayon algoritm boshlanganidan keyin D vaqt birliklari ichida har bir jarayon xabarlarini yubordi, shuning uchun D+1 vaqt birliklarida har bir 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 xabarini olishdan oldin 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₀ bo'lsin. Barcha jarayonlar tashabbuskor bo'lmagan yoki identifikatorlari p₀ dan kichik bo'lgan tashabbuskorlardir, shuning uchun barcha jarayonlar p₀ tomonidan yuborilgan tokenga (token, p₀) o'tadi. Shuning uchun, p₀ o'zining tokenini qaytarib oladi va tanlangan bo'ladi.
Tashabbuschi bo'lmaganlarni tanlab bo'lmaydi, chunki ularning barchasi p₀ tokeni o'tgandan so'ng eng kech yutqazuvchi holatga kirishadi. est(p) < est(p0 ₎ ballga ega bo'lgan tashabbuskorni tanlab bo'lmaydi; p₀ tokenga (token, p) o'tmaydi , shuning uchun p hech qachon o'z tokenini olmaydi. Bunday inisiator p eng ko'p token (token, p₀) 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.