9-ma’ruza. Saytlarni aylanish va tanlash algoritmlari. Reja

var i: integer init 0 ; (* hisoblagich *)
Initsiator uchun.
begin while ido
beginouttoken to u_i+1;
receive token; i := i + 1
end ;
return(OK)
end
Noinitsiator – saytning jarayoni.
begin receive token from u ; outtoken to uend

2. 
   Torning aylanish algoritmi
   

Tor ko`rinishidagi graf panjaraning o`ng qatoridagi uchlari bilan chap qatordagi uchlarni birlashtiradigan qovurg`alardan, shuningdek panjaraning yuqori qatori bilan pastki qatordagi uchlarni birlashtiradigan qo`shimcha qovurg`alardan iborat bo`lgan panjara ko`rinishida bo`ladi. Bu bilan qo`shimcha tsikllar paydo bo`ladi. Graf tartibli bo`lib, torning har bir uchi (panjaradan tashqari) to`rtinchi darajaga ega. Bunday grafning standart ko`rinishida har bir uchning o`z “chap” , “o`ng” , “tepa” , “past” qo`shnilari mavjud (9.1-rasm). mn, panjarasi asosida qurilgan tor mn tugunlaridan va ikki mn qovurg`alaridan tashkil topgan. Qovurg`alar sonini mashhur graf teoriyalari teoremasiga ko`ra : “ tugunlar darajasining qiymati qovurg`alar sonining ikkilanganiga teng ” hisoblash mumkin.

9.1-rasm. 3 x 5 tor. Turli yo`nalishdagi qovurg`alar.
Torning tartibli xususiyatlari tufayli yoki modefikatsiyasi tufayli turli arxitekturalarda ko`p ishlatiladi. Masalan, EHMning dastlabki ko`p protsessorli arxitekturalardan biri ILLIAC-IV torga o`xshash protsessorlar ulanishidan foydalangan.
m x n torning barcha tugunlaridan o`tishga to`g`ri keladi (qovurg`alarming esa hammasidan emas). Boshlang`ich tugun – initsiator sifatida har qanday tugun bo`lishi mumkin. Algoritm tor topologiyasiga mo`ljallangan bo`lib, lekin saytlarda topologiya to`g`risida global ma`lumotlar mavjud emas, faqatgina yuqoridagi rasmda ko`rsatilganligi kabi belgilangan yo`nalishga ega bo`lgan qovurg`alar nomi berilgan ((L, R, U, D),) ularni topologiya to`g`risidagi local ma`lumotlar deb hisoblash mumkin.
Initsiator harakati (bir marta bajariladi):