Gestion des pannes Algorithmes de reconfiguration danneaux virtuels Alexis CLERC

Gestion des pannes

Algorithmes de reconfigurationd’anneaux virtuels

Alexis CLERC

Plan

Généralités sur les anneaux virtuelsProblématiquesAlgorithmes communsModélisation par réseaux de Pétri

Anneaux virtuels : généralités

Contexte : système réparti DéfinitionsJeton

Contexte : système réparti

Tolérance aux pannes Anneau virtuel

Définitions

Connexion logiqueSitePanne

Jeton

Message de contrôle uniqueDroits d’émissionDurée limitée

A

C B

TRT

THT(A) THT(B) THT(C)

d(A,B) d(B,C) d(C,A)

Jeton

Message de contrôle uniqueDroits d’émissionDurée limitée

Target TRT

En avance

En retard

TRT

TRT THT (A)

THT (A)

AA A

Problématiques

InitialisationInsertionFermeture de l’anneau après rupture de

liaison logique ou une panne de siteDétection et traitement d’un

partitionnement

Initialisation

Un site isolé pose sa candidatureNégociation

I J K L

Insertion

Si le consensus aboutit à un accordLes anciennes liaisons sont ferméesDe nouvelles liaisons avec le site candidat

sont ouvertes

I J K L

Oui, mais …..

… des problèmes

Un inconvénientUne anomalieAutre propositionRaison fondamentale : l’asynchronisme

Fermeture de l’anneau après rupture de liaison logique ou une panne de site

Anneau briséDétectionProcédure de fermeture

Fermeture de l’anneau après rupture de liaison logique ou une panne de site

Anneau briséDétectionProcédure de fermetureUn exemple :

I J K L

Etat initial

Fermeture de l’anneau après rupture de liaison logique ou une panne de site

Anneau briséDétectionProcédure de fermetureUn exemple :

Rupture de J-K détectée par K

I J K L

Fermeture de l’anneau après rupture de liaison logique ou une panne de site

Anneau briséDétectionProcédure de fermetureUn exemple :

Rupture de K-L détectée par L

I J K L

Fermeture de l’anneau après rupture de liaison logique ou une panne de site

Anneau briséDétectionProcédure de fermetureUn exemple :

Rupture de J-K détectée par J

I J K L

Fermeture de l’anneau après rupture de liaison logique ou une panne de site

Anneau briséDétectionProcédure de fermetureUn exemple :

J et L sont disponibles → J-L établie

I J K L

Fermeture de l’anneau après rupture de liaison logique ou une panne de site

Anneau briséDétectionProcédure de fermetureUn exemple :

Rupture de I-J détectée par I

I J K L

Fermeture de l’anneau après rupture de liaison logique ou une panne de site

Anneau briséDétectionProcédure de fermetureUn exemple :

I et K sont disponibles → I-K établie

I J K L

Fermeture de l’anneau après rupture de liaison logique ou une panne de site

Anneau briséDétectionProcédure de fermetureUn exemple :

Etat final : Anneau partitionné

I J K L

Détection et traitement d’un partitionnement.

Réévaluation des liaisonsVoisins les plus prochesSuppression de l’initialisation

Algorithmes communs

Pré-requisExclusion mutuelle par estampilles Election Terminaison Contrôle des accès concurrents et

traitements des interblocages

Pré-requis

Précédence causale Ordonnancement par estampille Ordonnancement par horloges vectorielles

Précédence causale

Précédence directe a précède b

a < b et site(a) = site(b) ou

a=site i .send(m) et b=site j .receive(m)

Précédence a -> b fermeture transitive de a précède b

Concurrence a // b non (a -> b) et non (b -> a).

Ordonnancement par estampille

Horloge logique Hi de Si Quand e sur Si, Hi ++Quand Si.send(m), Em estampille(m) = HiQuand Sj.receive(m),Hj = max(Hj, E(m))+1Ordre total =>

Soit a sur Si et b sur Sj a => b Hi(a) < Hj(b) ou (Hi(a) = Hj(b) et i<j).

e(numéro de site, estampille)

Ordonnancement par horloges vectorielles

Problème de => : a => b a -> b ou a et b causalement

indépendants

Soit un anneau à n sites Chaque Si a un Vi[1…n] Quand e sur Si, Vi[i] ++ Quand Si.send(m), Vm Estampille(m) = Vi Quand Sj.receive(m), Vj[k] := max (Vj[k], Vm[k])

pour k = 1, …, n

Ordonnancement par horloges vectorielles (suite)

Soit événement a daté par Va Passé(a) = {a, {e/e->a}} Va[i] = # {e / (e->a, et e sur Si) } +1 Ordre partiel

V <= W V[k] <= W[k] pour k = 1, …, n V < W V <= W et V <> W V // W non (V <= W) et non (V <= W)

Précédence causale a -> b Va < Vb a et b causalement indépendants Va // Vb

Exclusion mutuelle par estampilles

Application directe de l’ordonnancement des événements par estampilles

File d’attente répartie, ordonnée Un seul processus en section critique Pi demande l’autorisation, Pj la reçoit

Pj n’est en SC, et n’a pas fait de demande => accord Pj a fait un demande => accord ou accord différé Pj est en SC => accord différé

2(n-1) messages

Election

Exemple : perte du jetonUn seul doit le régénérerChoix de l’élu arbitraire : Si / i max(1 …n)Algorithme de filtrage

Chaque Pi candidat transmet m(i) Quand Pj recoit m(i)

Si i < j, m(i) détruit et Pj candidat Sinon, Pj retransmet m(i)

Terminaison

Détection de la fin d’un calcul répartiComparaison avec l’interblocage

Similitude : absence d’évolution Différence : non connu a priori

Détection en 2 tours de jeton Marquage des sites suivant leur activité Terminaison quand tous les sites sont marqués

inactifs

Contrôle des accès concurrents et traitements des interblocages

Exécution séquentielle de processus concurrents

Conflit : actions incompatibles sur un objetRelation de dépendance << sur un grapheCycle sur le graphe = interblocageContrôle de dépendance

Contrôle continu Contrôle de terminaison

Contrôle des accès concurrents et traitements des interblocages (suite)

Respect de l’ordre de verrouillage et méthode de détection-guérison des interblocages Graphe de dépendance = graphe d’attente Lors d’une détection de cycle p1-p2-…-pn

Un pi en jeu doit être annulé puis repris Choix du pi :

• Auteur de l’interblocage• Celui qui a verrouillé le moins de ressources• Le plus récent

Contrôle des accès concurrents et traitements des interblocages (suite et fin)

Ordonnancement par estampille et méthodes de prévention des interblocages. Ordre établi par estampillage En cas de conflit :

si ordre respecté, action acceptée sinon, action annulée, puis reprise

Résultat : pas de cycles dans le graphe des attentes

Modélisation par réseaux de Pétri

Analyse descendante Messages typiques Principe de suspicion Qualités de services des couches inférieures

Routage Transport

Pertes de messages détectées Messages non dupliqués Messages contrôlés, et donc supposés corrects Liaisons logiques surveillés par émission/acquittement de

messages de contrôle, avec un mécanisme de time-out

Niveau 0 : Etat d’un site

Etats Inactif Actif

Transitions Traitement de reprise Défaillance

IN

AC

df tr

[ IN ( tr > AC ; AC ( df > IN ] *

Niveau 1 : Etat d’un site / système

Etats Déconnecté

Transitions Traitement de défaillance Traitement de connexion

IN

AC

dfD

td

tcIN (tr > AC devient

IN (td > D ; D ( tc > AC

[IN (td > D ; D ( tc > AC ; AC ( df > IN ] *

Niveau 2 : Etat d’un site / anneau

Etats Inactif coté successeur Inactif coté prédécesseur Actif coté successeur Actif coté prédécesseur

Transitions Défaillance coté successeur Défaillance coté prédécesseur

PI

AC devient SA et PA

IN devient SI et PIdf devient sdf et pdf

D

SI

PA SA

pdf sdf

td

tc

[ PI et SI ( td > D ; D ( tc > PA et SA ; [ PA ( pdf > PI // SA ( sdf > SI ] ]*

Niveau 3 : Etat d’un site / voisins

Etats Liaisons ouvertes (PO, SO) Liaisons fermées (PF, SF)

Transitions Déconnexion quand liaison ouverte (ppo, spo) Déconnexion quand liaison fermée (ppf, spf) Ouverture de liaison (plo, slo) Fermeture de liaison (plf, slf) Rupture de liaison (plr, slr)

PI

PA devient PF ou PO

SA devient SF ou SO

sdf devient spo et spf

sdf devient spo et spf

D

SI

PF SF

ppf spf

td

tc

[ PF ( plo > PO ; PO ( plf ou plr > PF] // [ SF ( slo > SO ; SO ( slf ou slr > SF]

[ PF ( ppf > PI ou PO (ppo > PI ] // [ SF ( spf > SI ou SO (spo > SI ]

PO SO

ppo spo

plf slfplr plo slr slo

Et plus encore !!

Messages de synchronisationIdentité des sites émetteurs et destinataires-> Réseaux de Pétri à prédicats

Bibliographie

Modeling of a virtual ring protocol by means of Petri netsPascal Estraillier – Article présenté au 1er colloque de Génie logiciel

The Totem Single-Ring ordering and membership

protocolAmir, Moser, Melliar-Smith, Agarwal, Ciarfella – University of California

Depth first traversal and virtual ring construction in distribued systems

Helary, Raynal – Unité de recherche INRIA Rennes

Eléments fondamentaux des systèmes répartisMichel RIVEILL - Projet IMAG-INRIA Sirac

Remerciements

INRIA pour m’avoir envoyé ses articlesMr Terrat pour m’avoir prêté l’article sur

les réseaux de Petri en françaisVous, pour votre attention !