La coordination répartie

Le besoin de synchroniser et de faire communiquer des processus existe également dans un système réparti.

Les ordres sur les événements

Il est nécessaire, pour traiter un certain nombre de problèmes, d'avoir un ordre global sur les événements d'un système.

L'ordre physique

Peut être construit à partir de : adresse machine, numéro de processus, horloge locale.

Problème : pas cohérent (du fait des dérives) avec l'envoi et la réception de messages.

UTC : Temps Universel Coordonné suffit pour beaucoup de problèmes (dates des fichiers ...), mais insuffisant pour section critique, interblocages...car les délais de transmission ne sont pas connu exactement.

Un ordre logique : les horloges de Lamport

Une relation $R$ telle que :

1. Pour chaque processus $P$, si $a$ est antérieur à $b$, alors $R(a_P) < R(b_P)$
2. Pour chaque couple de processus $(P,Q)$, si $P$ envoie à $Q$ un message $m$, alors $R(envoi_P(m)) < R(reception_Q(m))$

L'algorithme de Lamport :

1. A chaque création de processus $P_i$, initialiser un compteur $c_i$ à 0.
2. A chaque événement significatif de $P_i$, incrémenter $c_i$.
3. Estampiller chaque envoi de message $m$ par $P_i$ du compteur $c_i$.
4. A chaque réception de message $(m,E)$ par un processus $P_i$, celui ci effectue l'opération $c_i = max(c_i,E)+1$.

Le problème de l'exclusion mutuelle

L'approche centralisée

Un coordinateur : 3 messages par entrée (éventuellement un acquittement de la demande).

Pb : si le coordinateur tombe en panne.

L'approche répartie

Une solution basée sur les horloges logiques avec $2 \times (N-1)$ messages par entrée en section critique.

L'approche par circulation d'un privilège

Un jeton matérialise l'accès à la section critique. Le jeton circule de processus en processus généralement sur un circuit.

Le problème de l'interblocage

Les politiques de prévention

Les solutions vues au chapitre sur l'interblocage sont plus ou moins adaptables :

Exclusion mutuelle :

on utilise un spool pour toutes les ressources qui le permettent.

Tenir et attendre :

un protocole à deux phases est souvent mis en place pour les transactions dans les SGBD.

Pas de réquisition :

la solution proposée (un processus déclare réquisitionnables ses variables) ne peut pas s'appliquer à toutes les ressources, et peut provoquer la famine.

Attente circulaire :

la solution de l'ordre sur les ressources du réseau est difficile à mettre en uvre.

L'algorithme suivant qui utilise des horloges logiques permet un contrôle des réquisitions qui ne provoque pas de famine. L'idée est la suivante :

1. A chaque processus $P_i$ est associée une estampille $E_i$ qui correspond à son instant de création.
2. L'estampille détermine la priorité du processus, afin qu'un processus retardé deviennent de plus en plus prioritaire.

Il existe deux schémas de mise en uvre :

wait-die (attendre-mourir)

n'utilise pas la réquisition. Dans ce schéma, si $P_i$ désire une ressource détenue par $P_j$ deux cas :

1. $P_i$ attend (un certain temps) si $E_i < E_j$.
2. $P_i$ meurt (il rend ses ressources un certain temps) si $E_i > E_j$.

wound-wait (blessé-attendre)

utilise la réquisition. Dans ce schéma, si $P_i$ désire une ressource détenue par $P_j$ deux cas :

1. $P_i$ attend (un certain temps) si $E_i > E_j$.
2. $P_i$ blesse $P_j$ (il le force à rendre ses ressources) si $E_i < E_j$.

Ces schémas sont sans famine si les processus blessés et morts recommencent avec la même estampille après un délai qu'il faut estimer, mais peuvent être très inefficaces.

Les politiques de détection

La détection consiste toujours à trouver un cycle dans le graphe d'allocation des ressources.

Le problème

Il est facile pour chaque site $S_k$ de maintenir un graphe d'attente local qui contient tous les arcs $P_i,P_j$ dès que $P_i$ (local ou non) désire une ressource $R$ du site $S_k$, tenue par $P_j$ (local ou non).

Ces graphes vérifient les propriétés :

1. si l'un deux possède un cycle, il y a un interblocage.
2. il n'y a pas d'interblocage si l'union de l'ensemble des graphes est sans cycle.

Il est donc nécessaire de construire le graphe d'attente global.

Un exemple

d'interblocage.

L'approche centralisée

Un processus coordonnateur est chargé de gérer le graphe global. Celui-ci peut être maintenu en permanence ou bien calculer périodiquement.

Le défaut majeur est qu'il est impossible d'avoir le graphe réel du fait du temps pris par les communications. Une des conséquences est la détection de faux interblocages (une libération est arrivée trop tard).

Un exemple :

Soit la situation suivante :

Supposons maintenant le scénario suivant :

1. $P_2$ libère la ressource du premier site.
2. $P_2$ demande une ressource du second site tenue par $P_3$

et enfin supposons que du fait du réseau le message de la demande arrive au coordinateur avant le message de libération. La situation est alors :

Il existe des solutions centralisées basées sur les horloges logiques.

L'approche répartie

Chaque site $S_k$ maintient un graphe composé de :

1. Les arcs $P_i,P_j$ dès que $P_i$ (local ou non) désire une ressource $R$ du site $S_k$, tenue par $P_j$ (local ou non).
2. Les arcs $P_i,P_{ex}$ dès que $P_i$ local désire une ressource d'un autre site, tenue par un processus quelconque non local.
3. Les arcs $P_{ex},P_i$ dès que $P_{ex}$ non local désire une ressource $R$ du site $S_k$, tenue par $P_i$ (local ou non).

Dans ce graphe une attente d'un processus $P_i$ non local sur une ressource locale détenue par $P_j$ apparaît deux fois : $P_i,P_j$ et $P_{ex},P_j$

Ce graphe possède les propriétés :

1. si l'un deux possède un cycle sans $P_{ex}$, il y a un interblocage.
2. si l'un deux possède un cycle avec $P_{ex}$, il y a risque d'interblocage.

Dans le second cas, notons $C_k = P_{ex},P_{k_1},...,P_{k_n},P_{ex}$ le cycle du site $S_k$. Il faut noter que le site $S_k$ connaît exactement la composition de $P_{ex}$ qui débute le cycle, mais pas celle de $P_{ex}$ qui termine le cycle. Le site déclenche l'algorithme suivant :

1. $S_k$ communique le cycle $C_k$ au site $S_q$ qui détient la ressource convoitée par le processus $P_{k_n}$;
2. le site $S_q$ met à jour son graphe. Trois cas :
   1. il n'existe pas de cycle, il n'y a pas d'interblocage.
   2. il existe un cycle sans $P_{ex}$, il y a un interblocage.
   3. il existe un cycle avec $P_{ex}$, le site $S_q$ continue l'algorithme de détection vers un nouveau site.
3. les $P_{ex}$ sont à chaque itération de moins en moins nombreux, il y a donc un site sur lequel l'algorithme s'arretera, et qui conclura par interblocage ou non.

En fait, s'il y a interblocage distribué, plusieurs sites vont posséder un cycle local avec $P_ex$, il est donc inutile que tous déclenchent l'algorithme. Une optimisation possible utilise un ordre sur les processus :

• le site $S_k$ observe le cycle $C_k = P_{ex},P_{k_1},...,P_{k_n},P_{ex}$,
• le site $S_k$ déclenche l'algorithme si et seulement si $k_n < k_1$.

Un exemple :

Considérons la situation du vrai interblocage initial. Supposons que :

• les processus $P_1, P_3, P_5$ sont du site $S_1$,
• les processus $P_2, P_4$ sont du site $S_2$,
• les arcs localisent les ressources.

Nous avons alors :

L'algorithme produit :

1. Les deux sites constatent un cycle :
   • $S_1$ voit le cycle $P_{ex}=P_2, P_3, P_{ex}$,
   • $S_2$ voit le cycle $P_{ex}=P_3, P_4, P_2, P_{ex}$,
2. le site $S_2$ envoie à $S_1$ le cycle $P_{ex}=P_3, P_4, P_2, P_{ex}$,
3. le site $S_1$ met à jour son graphe.
4. le site $S_1$ détecte l'interblocage.

Autres problèmes de coordination réparties

On peut citer :

L'Atomicité :

les transactions sont des suites d'actions qui n'en font qu'une. C'est à dire que soit toutes les actions terminent, soit aucune. Les actions peuvent concernées des ressources et des processus sur plusieurs sites. La solution la plus souvent mise en uvre est le protocole de validation à deux phases.

L'élection :

de nombreux algorithmes répartis utilisent un coordinateur. Celui-ci peut tomber en panne, il est alors nécessaire d'initialiser un nouveau coordinateur. Le problème est complexe car :

• il faut être certain que le coordinateur est en panne,
• il faut connaître tous les coordinateurs potentiels.

Une solution est basée sur :

• un processus qui pense que le coordinateur est en panne se proclame nouveau coordinateur, et diffuse l'information à ses voisins;
• un processus qui reçoit un message d'élection participe à l'élection, soit il sait que le coordinateur n'est pas en panne, soit il accepte le nouveau coordinateur, soit il se déclare nouveau coordinateur car il est prioritaire au processus qui lui à envoyer le message. Le processus diffuse cette nouvelle information;
• un processus est élu lorsqu'il à reçu un accord de tous ses voisins.