Algorithme de Maekawa

L'algorithme de Maekawa est un algorithme d'exclusion mutuelle sur un système distribué.

Dans l'algorithme de Maekawa, chaque composant appelé « site » ne peut donner de permission d'entrée dans une section critique qu'à un seul autre composant à la fois. Chaque site a la charge d'arbitrer les éventuels conflits qui apparaîtront entre différents autres sites. Cela impose au participant à qui cette permission a été donnée de rendre la main sur la section critique spontanément une fois qu'il a fini son travail, c'est-à-dire lorsqu'il sort de sa section critique.

Terminologie

• Un « site » est l'endroit où est exécuté l'algorithme de Maekawa
• Pour toute demande d'entrée en section critique :
  • Le « site demandeur » est le site qui demande d'entrer en section critique.
  • Le « site de réception » est tout autre site qui reçoit la demande du site demandeur.
• Tout site ayant donné sa permission en réponse à une demande est dit « verrouillé »

Différents types de messages échangés

Les types de messages échangés lors de l'exécution de l'algorithme sont :

• DEMANDE : un message de demande d'entrée en section critique
• ACCORD : un message d'acceptation d'entrée en section critique
• ÉCHEC : un message de refus d'entrée en section critique
• SONDAGE : un message envoyé pour résoudre les problèmes d’interblocage
• RESTITUTION : une réponse à un message SONDAGE
• LIBÉRATION : un message de sortie de section critique

Algorithme

Site demandeur

• Un site $P_i$ demandant envoie un message de demande $(ts,i)$ à tous les sites dans son quorum Ri.

Site receveur

• Lors de la réception d'un message de demande $(ts,i)$, le site de réception $P_j$ :
  • Si le site $P_j$ n'a pas un accord en cours (c'est-à-dire un message d'accord qui n'a pas été relâché), alors le site $P_j$ envoie un message d'accord (j) sur le site $P_i$.
  • Si le site $P_j$ a un accord en cours pour un processus avec une priorité plus élevée que la demande, alors le site $P_j$ envoie un message d'échec (j) sur le site $P_i$ et $P_j$ ajoute à sa file d'attente la demande du site $P_i$.
  • Si le site $P_j$ a un accord en cours pour un processus avec une priorité inférieure à la demande, alors le site $P_j$ envoie un message de sondage (j) au processus qui est actuellement autorisé à accéder à la section critique par le site $P_j$ (c'est-à-dire le site avec le message d'accord en cours).
• Lors de la réception d'un message de sondage (j), le site $P_k$ :
  • Envoie un message de restitution (k) sur le site $P_j$ si et seulement si le site $P_k$ a reçu un message d'échec d'un autre site, ou si $P_k$ a envoyé un message de restitution à un autre site, mais n'a pas reçu un nouvel accord.
• Lors de la réception d'un message de restitution (k), le site $P_j$ :
  • Envoie un message d'accord à la première demande de sa file d'attente. Notez que les requêtes au sommet sont celles de plus haute priorité.
  • Place $P_k$ dans sa file d'attente.
• Lors de la réception d'un message de libération (i), le site $P_j$ :
  • Supprime $P_i$ de sa file d'attente.
  • Envoie un message d'accord à la première demande de sa file d'attente.

Section critique

• Un site $P_i$ entre dans la section critique lorsqu'il reçoit un message d'accord de tous les sites du quorum Ri.
• À la sortie de la section critique, $P_i$ envoie un message de libération (i) à tous les sites de Ri.

Quorum

Un quorum doit respecter les propriétés suivantes :

1. $\mathrm{\forall }i\mathrm{\forall }j[R_i\bigcap R_j\ne \mathrm{\varnothing }]$
2. $\mathrm{\forall }i[P_i\in R_i]$
3. $\mathrm{\forall }i[|R_i|=K]$
4. Le site $P_i$ est contenu dans exactement K ensembles de requêtes

Ce qui implique:

• • $|R_i|\ge \sqrt{N-1}$

Performance

• En nombre de messages sur le réseau : $3\sqrt{N}$ à $6\sqrt{N}$
• Délai de synchronisation : délai de 2 messages de propagation

Bibliographie

• Maekawa, M., Oldehoeft, A., Oldehoeft, R.(1987). Operating Systems: Advanced Concept.Benjamin/Cummings Publishing Company, Inc.

Voir aussi

• Algorithme de la boulangerie
• Algorithme de Ricart et Agrawala

Lien externe

• Modèle:Fr Modèle:Lien web