Algorithme de Maekawa

L'algorithme de Maekawa est un algorithme d'exclusion mutuelle sur un système distribué. Dans l'algorithme de Maekawa, chaque site ne peut donner sa permission d'entrée en section critique un seul à la fois : chaque site à la charge d'arbitrer un certain nombre de conflits qui apparaîtra entre différents sites. Donc cela impose au participant à qui cette permission a été donnée de la rendre la main sur la section critique spontanément une fois qu'il a finis son travail, c'est-à-dire lorsqu'il sort de sa section critique^[1]

Terminologie

• Un site est l'endroit où est exécuter l'algorithme de Maekawa
• Pour toute demande d'entrée en sections critiques:
  • Le site demandeur est le site qui est demande la 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 lors de l'exécution de l'algorithme

• DEMANDE: un message d'entrée en section critique
• ACCORD: un message d'acceptation d 'entrée en section critique
• ECHEC: un message de refus d entrée en section critique
• SONDAGE: un tel message est envoyé pour résoudre les problèmes d interbloquages
• RESTITUTION: réponse à un messages sondages
• LIBERATION: un message de sortie de section critique

Algorithme

Site demandeur

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

Site receveur

• Lors de la réception d'une demande (ts, i) un message, le site de réception sera Pj:
  • Si le site Pj n'a pas un message de permission exceptionnelle (c'est-à-dire, un message de permission qui n'a pas été publié), alors le site Pj envoie une subvention (j) message sur le site Pi.
  • Si le site Pj a un message de permission exceptionnelle d'un processus avec une priorité plus élevée que la demande, alors le site Pj envoie un échec (j) message sur le site Pi et Pj site files d'attente de la demande à partir du site Pi.
  • Si les sites Pj a un message de permission exceptionnelle d'un processus avec une priorité inférieure à la demande, alors le site Pj envoie un (j) message au processus qui a actuellement été autorisés à accéder à la section critique par site Pj. (Autrement dit, le site avec le message de subvention exceptionnelle.)
• Lors de la réception d'un savoir (j) message, le Pk site:
  • Envoyer un message sur le site Pj si et seulement si Pk site a reçu un message qui a échoué sur un autre site ou si Pk a envoyé un message à un autre site, mais n'ont pas reçu une nouvelle subvention.
• Lors de la réception d'un rendement (k) message, le site sera Pj:
  • Envoyer un message de permission à la demande sur le haut de sa file d'attente . Notez que les requêtes au sommet sont la plus haute priorité.
  • Placez Pk dans sa file d'attente demande.
• Lors de la réception d'un message, le site sera Pj:
  • Supprimer Pi de sa file d'attente demande.
  • Envoyer un message de permission à la demande sur le haut de sa file d'attente demande.

Notes et références

Bibliographie

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

Voir aussi

Lien externe

• (fr) Description de l'algorithme de Maekawa

• Portail de l’algorithmique