• Document: 1 Exclusion Mutuelle. 1.1 Algorithmes basés sur les permissions. Master Info - Info
  • Size: 138 KB
  • Uploaded: 2019-03-14 14:33:30
  • Status: Successfully converted


Some snippets from your converted document:

Master Info - Info 0701 1 1 Exclusion Mutuelle 1.1 Algorithmes basés sur les permissions Algorithme 1 Alorithme de Ricart Agrawal, local au site i etat ←− S E, SC, S éttat du site i h ←− 0 entier date des demandes last ←− 0 entier date de la derniere demande attendu ←− φ ensemble de sites qui attendent la permission dif f ere ←− φ ensemble de sites qui retardent l’envoi d’une perm priorit ←− f aux booleen si i prioritaire ou non demande d’entree en section critique etat ←− E last ←− last + 1 attendu ←− R for all j ∈ attendu do Envoi msg(dem, (lasti, i)) à j end for while attendu 6= φ do reception msg(perm(j)) de j attendu ←− attendu j end while etati ←− SC Sortie de section critique etat ←− S for all j ∈ dif f ere do Envoi msg(perm(i)) à j end for dif f erei ←− φ Réception de msg(dem, (h0 , j)) de j h ←− max(h, h0 ) priorit ←− (etat 6= sortie) ∧ (last, i) < (h0 , j) if priorit = vrai then dif f ere ←− dif f ere ∪ j else Envoi msg(perm(i)) à j end if Liste d’Algorithmes 2014-2015/ Thibault BERNARD Master Info - Info 0701 2 Algorithme 2 Algorithme de Carvalho Roucairol, local au site i R ←− {j ∈ V tel que i ne possedes pas perm(i, j)} etat ←− S E, SC, S etat du site i h ←− 0 entier date des demandes last ←− 0 entier date de la derniere demande dif f ere ←− φ ensemble de sites qui retardent l’envoi d’une permission priorit ←− f aux booleen si i prioritaire ou non Demande d’entree en section critique etat ←− E last ←− h + 1 for all j ∈ R do Envoi msg(dem(last, i) à j end for while R 6= φ do Reception msg(perm(i, j)) de j R ←− R\{j} end while etat ←− SC Sortie etat ←− S for all j ∈ dif f ere do Envoi msg(perm(i, j)) à j end for R ←− dif f ere dif f ere ←− ∅ Reception de msg(dem, (h0 , j)) de j h ←− max(hi, h0 ) priorit ←− (etat = SC) ∨ [(etat = E) ∧ (last, i) < (h0 , j)] if priorit = V RAI then dif f ere ←− dif f ere ∪ {j} else Envoi msg(perm(i, j)) à j R ←− R ∪ {j} if etat = E then Envoi msg(dem, (last, i)) à j end if end if Liste d’Algorithmes 2014-2015/ Thibault BERNARD Master Info - Info 0701 3 1.2 Algorithmes basés sur un jeton Algorithme 3 Algorithme de Lelann, local au site i etat ←− S E, SC, S suivant ←− le site voisin dans l’anneau Reception du jeton if etat = E then etat ←− SC else Envoi (jeton) à suivant end if sortie etat ←− S Envoi (jeton) à suivant Algorithme 4 Algorithme de Ricart Agrawal, local au site i Etat ←− S E, SC, S N bdem ←− 0 tableau de N entiers jetonpresent ←− f aux booleen (si le site a le jeton) sauf pour un site Demande d’entree en section critique Etat ←− E if ¬jetonpresent then N Bdem[i] ←− N bdem[i] + 1 for all j 6= i do Envoi dem à j end for Réception de jeton jetonpresent ←− V RAI end if Etat ←− SC Sortie de SC Etat ←− S jeton[i] ←− N bdem[i] if COND ATT then Envoi jeton à j jetonpresent ←− F AU X end if Reception de dem de j N bdem[j] ←− N bdem[j] + 1 if jetonpresent ∧ (Etat = S) ∧ CON D AT T then Envoi jeton à j jetonpresent ←− F AU X end if COND ATT (site i) jeton[j] < N bdem[j] Liste d’Algorithmes 2014-2015/ Thibault BERNARD Master Info - Info 0701 4 2 Election Algorithme 5 Algorithme de Lelann, local au site i Variables List ensemble de d’identifiants, init. à ∅ etat ∈ {elu, battu, init, noninit} init. à init pour les initiateurs et noninit pour les autres if etat = noninit then while f alse do Reception msg Envoi msg if etat = noninit then etat ←− battu end if end while else list ←− list ∪ {i} Envoi msg(i) Recoit msg(j) while i 6= j do list ←− list ∪ {j} Envoi msg(j) Reception msg(j) end while if i = min list then etat ←− elu else etat ←− battu end if end if Liste d’Algorithmes 2014-2015/ Thibault BERNARD Master Info - Info 0701 5 Algorithme 6 Algorithme de Chang Roberts, local au site i Variables etat ∈ {elu, battu, init, noninit} init. à init pour les initiateurs et noninit pour les autres if etat = noninit then while f alse do Reception msg Envoi msg if etat = noninit then etat ←− battu end if e

Recently converted files (publicly available):