Algorithme de Peterson
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. 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 est dû à Gary Peterson.
Sommaire |
[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 threads 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 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.
[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
[modifier] Voir aussi
- Luigi Zaffalon et Pierre Breguet, Programmation concurrente et temps réel avec ADA 95, Presses polytechniques et universitaires romandes, Lausanne, 1999
|
|
|
|
