EXAMEN de RATTRAPAGE
EXAMEN de RATTRAPAGE
Informatique, Gestion d'interblocage, Algorithmes · exam
Fiche de révisionCorrigé
Rédigée à partir de ce document, puis vérifiée avant publication.
La sûreté (safety) dans les systèmes répartis garantit que "rien de mauvais n'arrive". Pour les algorithmes de gestion d'interblocage (spécifiquement la détection), la sûreté se traduit par le fait que l'algorithme ne doit jamais détecter de faux interblocages. Si l'algorithme annonce qu'un interblocage est présent, alors cet interblocage doit exister réellement dans le système. Dans le cas de la prévention ou de l'évitement, la sûreté signifie que le système ne doit jamais entrer dans un état d'interblocage.
La vivacité (liveness) garantit que "quelque chose de bon finit toujours par arriver". Dans le contexte de la gestion d'interblocage, cela signifie que si un véritable interblocage se produit dans le système, l'algorithme finira obligatoirement par le détecter et par le résoudre dans un délai fini. Cela implique également qu'aucun processus ne subisse de famine infinie à cause de l'algorithme de résolution.
La différence réside dans le moment et la manière dont on traite le risque d'interblocage :
Le principe fondamental de tous les algorithmes de détection d'interblocage est la construction, la mise à jour et l'analyse d'un graphe d'attente (ou graphe d'allocation de ressources). L'algorithme cherche à identifier la présence de cycles (ou de nœuds terminaux spécifiques, selon le modèle de requêtes) dans ce graphe, car l'existence d'un cycle fermé dans le graphe d'attente est la preuve matérielle d'un interblocage.
Lorsqu'un algorithme détecte à tort un interblocage (faux interblocage), le système déclenche inutilement une procédure de recouvrement. Cette procédure consiste généralement à avorter (tuer) un ou plusieurs processus victimes et à annuler (roll-back) leurs transactions pour briser le cycle supposé. L'impact est une perte de travail utile, un gaspillage des ressources de calcul, et une dégradation injustifiée des performances globales du système.
L'anneau est constitué des sites dans l'ordre suivant : 2 -> 1 -> 4 -> 3 -> 2.
Le processus 2 initie l'élection. Initialement, pour tous les sites i, la variable M = 0.
M = 0. Il exécute M := 2 (son propre numéro) et envoie le message <2> à son voisin, le site 1.j = 2. Sur le site 1, M = 0. La condition M < j (0 < 2) est vérifiée. Le site 1 exécute M := 2 et transmet <2> au suivant, le site 4.j = 2. Sur le site 4, M = 0. La condition M < j (0 < 2) est vérifiée. Le site 4 exécute M := 2 et transmet <2> au suivant, le site 3.j = 2. Sur le site 3, M = 0. La condition M < j (0 < 2) est vérifiée. Le site 3 exécute M := 2 et transmet <2> au suivant, le site 2.<2>. L'identifiant reçu j est 2. Puisque j = i (2 = 2), la condition finale est remplie. Le processus 2 déclare "Je suis le leader".(Note : Lors de l'étape 5, M sur le site 2 vaut déjà 2, donc la condition M < j qui correspond à 2 < 2 est fausse, le message n'est donc pas retransmis plus loin, ce qui termine correctement l'algorithme.)
Dans l'algorithme de Chang et Roberts, l'identifiant maximum l'emporte et les identifiants plus petits sont purgés de l'anneau. Comparons les comportements :
i met M := i et envoie <i>. La variable M conserve toujours la valeur du plus grand identifiant vu par le site. Lorsqu'un message <j> arrive, il n'est transmis que si j > M. Par conséquent, exactement comme chez Chang et Roberts, les messages portant des identifiants faibles seront bloqués par les sites ayant déjà vu (ou possédant) un identifiant plus grand. Le plus grand identifiant fera le tour complet.M = 0. Lorsqu'il reçoit le premier message de l'élection contenant un identifiant j > 0, la condition 0 < j est toujours vraie. Le site passif met à jour M := j et fait suivre le message. Il se comporte donc comme un routeur passif parfait, ce qui équivaut au comportement d'un site non initiateur chez Chang et Roberts.(Note : Cette question est numérotée 2 dans le document source extrait).
Si l'on élimine la composante site (l'identifiant i utilisé pour départager les ex-aequo), la propriété qui est perdue est l'ordre total des événements. Il devient possible que deux événements concurrents se produisant sur deux sites différents possèdent exactement la même estampille temporelle scalaire H. Nous n'obtenons plus qu'un ordre partiel.
Cependant, l'horloge ainsi modifiée respecte toujours la condition de validité faible des observations. Cette condition stipule que pour deux événements e et e', si e -> e' (e précède e' causalement), alors H(e) < H(e'). Puisque l'horloge scalaire s'incrémente sur chaque événement local et prend max(H_local, H_recu) + 1 lors d'une réception, l'estampille d'un événement qui en cause un autre sera toujours strictement inférieure. La condition faible est donc préservée.
Non, cette modification ne garde pas la propriété fondamentale des horloges de Mattern.
La propriété fondamentale est : e -> e' <=> Ve < Ve'. L'inégalité vectorielle stricte implique qu'au moins une composante est strictement inférieure.
Exemple illustratif :
Considérons deux sites, P1 et P2, avec les vecteurs initiaux V1 = [0, 0] et V2 = [0, 0].
P1 exécute un événement d'émission e1 vers P2.
P1 incrémente sa composante : V1 = [1, 0].e1 est daté de [1, 0]. Le message part avec l'estampille [1, 0].P2 réceptionne ce message lors de l'événement e2.
P2 fait uniquement la mise à jour : V2 = max([0, 0], [1, 0]) = [1, 0].e2 est daté de [1, 0].Nous savons par définition causale que l'émission précède la réception : donc e1 -> e2.
Selon la propriété fondamentale, nous devrions avoir V(e1) < V(e2).
Or, ici nous avons [1, 0] et [1, 0], ce qui signifie que V(e1) = V(e2). L'équivalence est donc rompue, la propriété est perdue.
Attention : Le diagramme d'exécution mentionné ("le diagramme suivant") n'est pas présent dans l'énoncé source extrait. Il est physiquement impossible de déterminer l'ordre d'entrée en section critique ou le contenu des files d'attente sans les messages et leurs estampilles temporelles de départ. Si ce diagramme vous est fourni en annexe, l'ordre d'entrée sera dicté par la plus petite estampille Hi de la requête (en utilisant l'identifiant du site pour départager les ex-aequo), à condition que le processus ait reçu un acquittement de tous les autres processus.
Les communications doivent être de type FIFO (First-In, First-Out) car l'algorithme de Lamport repose de manière critique sur l'ordre de réception des estampilles temporelles.
Si les canaux n'étaient pas FIFO, un message de libération (Liberation, H2) ou d'acquittement envoyé par un processus Pi pourrait arriver sur un site distant avant une requête (Demande, H1) envoyée précédemment par ce même processus Pi (avec H1 < H2).
Cela fausserait totalement la cohérence de la file d'attente locale du récepteur : il pourrait traiter une libération pour une requête qu'il n'a pas encore mise en file, puis ajouter ensuite la requête qui resterait bloquée indéfiniment. Le canal FIFO garantit que si un site reçoit un message estampillé t d'un processus P, il a la certitude qu'il ne recevra plus aucun message de P avec une estampille inférieure à t, ce qui est indispensable pour prendre la décision sécurisée d'entrer en section critique.
Pour aborder ce type de sujet d'Informatique Répartie :
e -> e' <=> Ve < Ve').M, état du nœud) pour chaque site, à chaque réception de message. Cela évite les erreurs d'inattention, particulièrement sur la condition de fin.Si M < j), même si elles diffèrent légèrement des versions canoniques vues en cours. L'examinateur teste votre capacité d'analyse logique, pas seulement votre mémoire.