Lekciya 13. Saytlardı shetlep ótiw algoritmları Joba: Tolıq graftı shetlep ótiw algoritmi

var i: integer init 0 ; (* счетчик *)
iniciator ushın:
begin while i < n – 1 do
begin out token to u_i+1 ;
receive token; i := i + 1
end ;
return(OK)
end

ne -initiator sayt procesi:

begin receive júzimen from ol ; out júzimen tap ol end
Tordı shetlep ótiw algoritmı
" Tor" turining grafigi-tómengi qatardaǵı tóbeliklerge, sonıń menen birge, shep qatardan (" ústin") vertikalar menen oń qatardan vertikalar menen baylanıstıratuǵın qosımsha qabırǵalar menen tor. Sonday etip, qosımsha cikller bar. Tavrotning hár bir uchi (tordan ayrıqsha bolıp esaplanıw ) 4 dárejesine iye, yaǵnıy. Bunday grafikdıń standart suwreti menen hár bir tóbelikda" shep " qońsılas, " oń " qońsılas, " joqarı " qońsılas, " tómengi " qońsılas (súwret. 1 ). Thor, tor tiykarında qurılǵan m n, mn túyinleri hám 2 Mn qabırǵa óz ishine aladı. Qabırǵalar sanı tuwrıdan-tuwrı hám grafik teoriyasınıń málim teoremasiga tiykarlanǵan halda esaplanıwı múmkin: " túyinlerdiń dárejeleri jıyındısı eki ese kóp qabırǵa sanına teń".



Súwret . 1 Tor 3 x 5. Túrli baǵdardaǵı qabırǵalar.

Onıń úzliksiz qásiyetleri sebepli tar yamasa onıń modifikatsiyası kóbinese túrli arxitekturalarda qollanıladı. Mısal ushın, illiac-Iv kóp protsessorli kompyuterlerdiń birinshi arxitekturalarınan biri protsessorlarning operativ baylanısınan paydalanǵan.

Tar m n dıń barlıq túyinlerin shetlep ótiw kerek (lekin barlıq qabırǵalar emes). Initiator-dáslepki túyindi shetlep ótiw túyinlerden biri bolıwı múmkin. Algoritm Tavrotning tapologiyasiga qaratılǵan, biraq saytlarda tapologiya haqqında global maǵlıwmat joq, joqarıdaǵı suwretke muwapıq jónelislerdi anıqlaytuǵın qabırǵalar (L, R, Ol, D) atları bar. Olar tapologiya haqqında jergilikli bilim retinde qaralıwı múmkin.

Iniciator háreketler (bir ret ámelge asıriladı ):

out (token, 1) through U
Markerdi alıwda hár bir sayttıń procesi (júzimen, k) :
begin if k = m*n then return(OK)
else if (k mod n = 0) then out (token, k+1) through U
else out (token, k+1) through R
end
2 hám 3 Súwretlerde 3x4 hám 2x5 boyınsha. torlardı shetlep ótiw kórsetiledi. Juldızsha menen shetlep ótiw iniciatori saytı hám " OK" háripleri - shetlep ótiwning tawısıwı haqqında xabar beretuǵın sayt kórsetilgen. Qabırǵanıń janında nomer jazıladı -k ma`nisi, bul qabırǵadan bir sayttan ekinshisine uzatıladı.

Súwret. 2. 3x4 tártiptegi tordı shetlep ótiw

Súwret. 3. 2x5 tártiptegi tordı shetlep ótiw