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 critiqueOldehoeft,1987.
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
Liens externes
Catégorie:Algorithme d'exclusion mutuelle