- Algorithme de peterson
-
Algorithme de Peterson
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
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.
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==NumeroTacheProtocole 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
Voir aussi
- Luigi Zaffalon et Pierre Breguet, Programmation concurrente et temps réel avec ADA 95, Presses polytechniques et universitaires romandes, Lausanne, 1999
Les méthodes de synchronisation Problèmes classiques des
méthodes de synchronisation
Portail de l’informatique
Catégories : Algorithme d'exclusion mutuelle | Attente active
Wikimedia Foundation. 2010.
