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==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
Les méthodes de synchronisation

Barrière de synchronisation - Futex - Moniteur

Mutex - Sémaphore - Spinlock

Problèmes classiques des
méthodes de synchronisation

Couplage fort - Famine

Interblocage - Inversion de priorité


  • Portail de l’informatique Portail de l’informatique
Ce document provient de « Algorithme de Peterson ».

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

  • Barrière de synchronisation — Une barrière de synchronisation permet de garantir qu un certain nombre de tâches ait passé un point spécifique. Ainsi, chaque tâche qui arrivera sur cette barrière devra attendre jusqu à ce que le nombre spécifié de tâches soient arrivées à… …   Wikipédia en Français

  • Allocation de ressources — v · d · m Synchronisation en …   Wikipédia en Français

  • Inversion de priorité — L inversion de priorité est un phénomène qui peut se produire en programmation concurrente. Il s agit d une situation dans laquelle un processus de haute priorité ne peut pas avoir accès au processeur car il est utilisé par un processus de plus… …   Wikipédia en Français

  • Conditions de concurrence — Les conditions de concurrence correspondent aux situations dans lesquelles se retrouvent plusieurs processus tentant d accéder au même moment à une même ressource partagée (Fichier, Imprimante, etc... ). Le résultat de telles situations dépend de …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”