Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Algorithme de Peterson
Résumé
En informatique, l'algorithme de Peterson est un algorithme d'exclusion mutuelle pour la programmation concurrente. Cet algorithme est basé sur une approche par attente active et est garanti d'être sans famine et sans interblocage. 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 a été publié par Gary Peterson en 1981.
Le principe de base de l'algorithme de Peterson est que chaque thread aura accès à son tour à la section critique, et qu'un thread ne peut entrer dans la section critique que lorsque celle-ci est libre.
Chaque thread dispose d'un identifiant unique. Par convention, nous considérons que les deux threads utilisés porteront les identifiants 0 et 1. Dans son implémentation de base avec 2 processus, l'algorithme utilise un tableau de deux valeurs booléennes pour indiquer si l'un des threads est actuellement intéressé d'entrer dans la section critique. Il utilise également une autre variable pour indiquer quel thread a actuellement accès à la zone critique.
La particularité importante de cet algorithme est qu'il utilise deux variables différentes pour contrôler l'accès à la zone critique.
Ci-dessous veut_entrer est un tableau de deux booléens, indiquant pour chaque processus (0 et 1) s'il veut entrer en section critique. La variable tour indique à qui est le tour d'exécuter la section critique.
Voici le pseudo-code de l'algorithme écrit en Java. Les deux threads possèdent comme identifiant 0 et 1, ils peuvent obtenir leur identifiant en appelant ThreadID.get().
class Peterson implements Lock {
// index du thread local, vaut 0 ou 1
private boolean[] drapeau = new boolean[2];
private int victime;
public void lock() {
int i = ThreadID.get();
int j = 1 - i;
drapeau[i] = true; // je suis intéressé
victime = i; // il va en premier
while (drapeau[j] && victime == i) {} // j'attends
}
public void unlock() {
int i = ThreadID.get();
drapeau[i] = false; // je ne suis plus intéressé
}
}
#include
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.