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  demandant envoie un message de demande  à tous les sites dans son quorum Ri.

Site receveur 
 Lors de la réception d'un message de demande , le site de réception  :
 Si le site  n'a pas un accord en cours (c'est-à-dire un message d'accord qui n'a pas été relâché), alors le site  envoie un message d'accord (j) sur le site .
 Si le site  a un accord en cours pour un processus avec une priorité plus élevée que la demande, alors le site  envoie un message d'échec (j) sur le site  et  ajoute à sa file d'attente la demande du site .
 Si le site  a un accord en cours pour un processus avec une priorité inférieure à la demande, alors le site  envoie un message de sondage (j) au processus qui est actuellement autorisé à accéder à la section critique par le site  (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  :
 Envoie un message de restitution (k) sur le site  si et seulement si le site  a reçu un message d'échec d'un autre site, ou si  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  :
 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  dans sa file d'attente.
 Lors de la réception d'un message de libération (i), le site  :
 Supprime  de sa file d'attente.
 Envoie un message d'accord à la première demande de sa file d'attente.

Section critique 
 Un site  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,  envoie un message de libération (i) à tous les sites de Ri.

Quorum 
Un quorum doit respecter les propriétés suivantes :
 
 
 
 Le site  est contenu dans exactement K ensembles de requêtes

Ce qui implique:

Performance 

 En nombre de messages sur le réseau :   à 
 Délai de synchronisation : délai de 2 messages de propagation

Notes et références

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 
  

Algorithme d'exclusion mutuelle