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^[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)$ $(ts,i)$ , le site de réception $P_{j}$ $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}$ $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}$ $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}$ $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 :

$\forall i\,\forall j\,[R_{i}\bigcap R_{j}\neq \emptyset ]$
$\forall i\,[P_{i}\in R_{i}]$
$\forall i\,[|R_{i}|=K]$
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]

↑ 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]

(fr) « Description de l'algorithme de Maekawa »

Portail de l'informatique théorique

[1] Oldehoeft,1987

[1]

v · m Synchronisation en programmation concurrente
Principes de base	Atomicité Section critique Communication inter-processus Thread Local Storage
Patrons de conception	Barrière de synchronisation Futex Futures Moniteur Mutex Sémaphore Spinlock Algorithme de Peterson Algorithme de Dekker Algorithme du banquier Algorithme de Maekawa
Problèmes classiques	Couplage fort Famine Interblocage Inversion de priorité Situation de compétition