Algorithme de Peterson

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

L'algorithme de Peterson est un algorithme d'exclusion mutuelle. Cet algorithme est basé sur une approche par attente active. Il est constitué de deux parties : le protocole d'entrée dans la section critique et le protocole de sortie. L'algorithme présenté est une version pouvant fonctionner avec deux threads. Il a été publié par Gary Peterson en 1981.

Description de l'algorithme[modifier | modifier le code]

L'algorithme de Peterson nécessite que chaque processus dispose d'un identifiant unique. Dans notre cas, on considérera deux processus d'identifiants 0 et 1.

Algorithme initial pour 2 processus[modifier | modifier le code]

bool flag[0]   = false;
bool flag[1]   = false;
int turn;
P0: flag[0] = true;
    turn = 1;
    while (flag[1] && turn == 1)
    {
        // attente
    }
    // Début de la section critique
    ...
    // fin de la section critique
    flag[0] = false;
P1: flag[1] = true;
    turn = 0;
    while (flag[0] && turn == 0)
    {
        // attente
    }
    // Début de la section critique
    ...
    // fin de la section critique
    flag[1] = false;

Algorithme pour n processus[modifier | modifier le code]

Il faut disposer d'un tableau (dont chaque case correspond à un thread grâce à l'utilisation des numéros précités) et d'une variable. Le tableau pourra contenir deux valeurs, à savoir une valeur indiquant qu'un thread souhaite entrer en section critique ou y est et qu'un thread ne souhaite pas entrer en section critique. Par défaut aucun thread ne souhaite entrer dans la section critique.

Pour la suite de la discussion, États désignera le tableau et Autre désignera la variable précitée. Les constantes VEUX et VEUXPAS définiront les deux états précités.


Protocole d'entrée[modifier | modifier le code]

Le protocole d'entrée est défini par l'algorithme suivant (le paramètre de l'algorithme est le numéro du thread) :

Entree(NumeroTache) :
 États(NumeroTache) = VEUX
 Autre = NumeroTache % 2 + 1
 REPETER
    Ne rien faire
 JUSQU'À États(NumeroTache % 2 + 1)==VEUXPAS OU Autre==NumeroTache

Protocole de sortie[modifier | modifier le code]

Le protocole de sortie est défini par l'algorithme suivant (le paramètre de l'algorithme est le numéro du thread) :

Sortie(NumeroTache) :
   États(NumeroTache)=VEUXPAS

Voir aussi[modifier | modifier le code]