Algorithme de Maekawa

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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[1].

Terminologie[modifier | modifier le code]

  • 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[modifier | modifier le code]

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[modifier | modifier le code]

Site demandeur[modifier | modifier le code]

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

Site receveur[modifier | modifier le code]

  • 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[modifier | modifier le code]

  • 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[modifier | modifier le code]

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

  1. \forall i \,\forall j\, [R_i \bigcap R_j \ne \empty ]
  2. \forall i\, [ P_i \in R_i ]
  3. \forall i\, [ |R_i| = K ]
  4. Le site P_i est contenu dans exactement K ensembles de requêtes
Ce qui implique:
    • |R_i| \geq \sqrt{N-1}

Performance[modifier | modifier le code]

  • 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

Notes et références[modifier | modifier le code]

  1. Oldehoeft,1987

Bibliographie[modifier | modifier le code]

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

Voir aussi[modifier | modifier le code]

Lien externe[modifier | modifier le code]