Un article de Wikipédia, l'encyclopédie libre.
L'algorithme de Peterson est un algorithme d'exclusion mutuelle. Cet algorithme est basé sur une approche par attente active. Cet algorithme est divisé en deux parties, à savoir 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 thread. Cet algorithme est dû à G.L. Peterson.
[modifier] Description de l'algorithme
L'algorithme de Peterson nécessite les éléments et les informations suivantes :
- Chaque thread dispose d'un numéro l'identifiant, à savoir dans le cas avec deux thread les numéros 1 et 2.
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 souhaitent 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.
[modifier] Protocole d'entrée
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'A États(NumeroTache % 2 + 1)==VEUXPAS OU Autre==NumeroTache
[modifier] Protocole de sortie
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
- Luigi Zaffalon et Pierre Breguet, Programmation concurrente et temps réel avec ADA 95, Presses polytechniques et universitaires romandes, Lausanne, 1999
