|
9-ma’ruza. Saytlarni aylanish va tanlash algoritmlari. Reja
|
| bet | 4/11 | | Sana | 10.08.2024 | | Hajmi | 172,01 Kb. | | #269345 |
Bog'liq 9а-mavzu (1)out(token, 1) through n – 1 kanal
(token, k) marker qabul qilingandagi har bir jarayon uchun:
begin if k=2n then return(OK)
else begin faraz qilaylik l - 2l|k bo’lgan eng katta nomer ;
out(token, k+1) through kanal l
end
end
Algoritmdan ko`rinib turibdiki, 2n marker jo`natmasidan so`ng qaror qabul qilinadi. p0- initsiator, pk- (token, k) markerini qabul qiladigan jarayon bo`lsin. Har bir k < 2n uchun pk va pk+1 qiymatlari 1 bitga farq qiladi, bunda quyidagi shartlarni qoniqtiradigan l(k) indeksini belgilaymiz:
Har bir i <n uchun mos bo`lgan k {0, ..., 2n} сl(k) = i, тоp0 = p2n sonlar mavjud va qaror initsiatorda qabul qilinadi. Bunda pa = pb dan 2n|(b – a) bo`ladi, bunda barcha p0, ..., p2n-1 turli xil bo`ladi.
Tarri algoritmi
Mustaqil aloqadagi graflar uchun aylanish algoritmi sifatida quyidagi ikki qoidaga asoslangan Tarri algoritmi berilgan.
Jarayon hech qachon bitta kanal orqali ikki marta marker yubormaydi.
Noinitsiator qoidaga asoslangan holda boshqa kanallar orqali markerni yuborolmasa, o`zidan oldingisiga (u dasylab marker qabul qilgan qo`shnisiga ) markerni yuboradi.
Quyidagi matnda saytning local o`zgaruvchilaridan foydalaniladi.
pre – jarayon bajarilayotgan saytdan oldingi sayt, ya`ni marker kelgan sayt.
used[q] - u saytgamarker yuborilganligining belgisi.
|
| |
