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.
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'À États(NumeroTache % 2 + 1)==VEUXPAS OU Autre==NumeroTache
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
Voir aussi
- Luigi Zaffalon et Pierre Breguet, Programmation concurrente et temps réel avec ADA 95, Presses polytechniques et universitaires romandes, Lausanne, 1999
Wikimedia Foundation.
2010.
Contenu soumis à la licence CC-BY-SA. Source : Article Algorithme de Peterson de Wikipédia en français (auteurs)
Regardez d'autres dictionnaires:
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… … Wikipédia en Français
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… … Wikipédia en Français
Algorithme de la boulangerie — L algorithme de la boulangerie (Lamport s bakery algorithm en anglais) est un algorithme d exclusion mutuelle découvert par Leslie Lamport[1], dans le cadre général de machines multi processeurs à mémoire partagée ne fournissant aucune opération… … Wikipédia en Français
Algorithme de Dekker — L algorithme de Dekker est un algorithme d exclusion mutuelle. Il est basé sur une approche par attente active et est divisé en deux parties, à savoir le protocole d entrée dans la section critique et le protocole de sortie. L algorithme présenté … Wikipédia en Français
Algorithme du banquier — L algorithme du banquier est un algorithme qui a été mis au point par Edsger Dijkstra en 1965 pour éviter les problèmes interblocages et gérer l allocation des ressources. Cet algorithme est nommé ainsi car il reproduit le modèle du prêt à des… … Wikipédia en Français
Peterson — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Cet article possède des paronymes, voir : Patterson et Petersen. Peterson est un nom de famille et un nom de li … Wikipédia en Français
Parallélisme (informatique) — Pour les articles homonymes, voir parallèle. Blue Gene L cabinet., un des ordinateurs massivement parallèle les plus rapides des années 2000 En informatiqu … Wikipédia en Français
Famine (informatique) — Pour les articles homonymes, voir Famine. La famine est un problème que peut avoir un algorithme d exclusion mutuelle. Il se produit lorsqu un algorithme n est pas équitable, c est à dire qu il ne garantit pas à tous les threads souhaitant… … Wikipédia en Français
Exclusion mutuelle — Un Mutex (anglais : Mutual exclusion, Exclusion mutuelle) est une primitive de synchronisation utilisée en programmation informatique pour éviter que des ressources partagées d un système ne soient utilisées en même temps. Son implémentation … Wikipédia en Français
Liste Des Algorithmes — Sommaire 1 Liste par catégories 1.1 Compression de données 1.2 Tri 1.2.1 Algorithmes en temps quadratique … Wikipédia en Français
