Algorithme de Peterson
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. 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.
Description de l'algorithme
L'algorithme de Peterson nécessite que chaque processus dispose d'un identifiant unique. Dans notre cas, on considérera deux processus d'identifiants 0 et 1.
Algorithme initial pour 2 processus
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.
bool veut_entrer[2];
veut_entrer[0] = false;
veut_entrer[1] = false;
int tour;
| |
P0: veut_entrer[0] = true;
tour = 1;
while (veut_entrer[1] && tour == 1)
{
// attente
}
// Début de la section critique
...
// fin de la section critique
veut_entrer[0] = false;
|
P1: veut_entrer[1] = true;
tour = 0;
while (veut_entrer[0] && tour == 0)
{
// attente
}
// Début de la section critique
...
// fin de la section critique
veut_entrer[1] = false;
|
Algorithme pour n processus
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 + 1) % NombreTaches REPETER Ne rien faire JUSQU'À États(Autre)==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
Exemple d'application en C (avec la librairie 'pthread')
#include <stdio.h>
#include <pthread.h>
#define PTHREAD_FUNCTION(fct) (void *(*)(void *))fct
#define FALSE 0
#define TRUE 1
// Use Peterson's algorithm, 1981
typedef struct {
// We need an array with same number of slots
// that we have thread to manage
int veut_entrer[2];
int tour;
int shared_value;
} Peterson_two_thread_struct;
void thread_num_zero(Peterson_two_thread_struct *ptt)
{
ptt->veut_entrer[0] = TRUE;
ptt->tour = 1;
while (ptt->veut_entrer[1] && ptt->tour == 1)
{
// Wait
}
// Critical section
for (int i = 0; i < 100; i++) {
ptt->shared_value++;
printf("[0] shared_value = %i\n", ptt->shared_value);
}
// End of critical section
ptt->veut_entrer[0] = FALSE;
}
void thread_num_one(Peterson_two_thread_struct *ptt)
{
ptt->veut_entrer[1] = TRUE;
ptt->tour = 0;
while (ptt->veut_entrer[0] && ptt->tour == 0)
{
// Wait
}
// Critical section
for (int i = 0; i < 100; i++) {
ptt->shared_value++;
printf("[1] shared_value = %i\n", ptt->shared_value);
}
// End of critical section
ptt->veut_entrer[1] = FALSE;
}
int main(int argc, const char * argv[]) {
pthread_t pthread_0, pthread_1;
Peterson_two_thread_struct ptt_struct;
ptt_struct.veut_entrer[0] = FALSE;
ptt_struct.veut_entrer[1] = FALSE;
ptt_struct.shared_value = 0;
printf("START : shared_value = %i\n", ptt_struct.shared_value);
int ret0 = pthread_create(&pthread_0, NULL, PTHREAD_FUNCTION(thread_num_zero), &ptt_struct);
int ret1 = pthread_create(&pthread_1, NULL, PTHREAD_FUNCTION(thread_num_one), &ptt_struct);
// If the system can't create thread (see manual)
if(ret0 != 0 || ret1 != 0)
{
printf("Error\n");
printf("Thread \"thread_num_zero\" error : %i \n", ret0);
printf("Thread \"thread_num_one\" error : %i \n", ret1);
return -1;
}
pthread_join(pthread_0, NULL);
pthread_join(pthread_1, NULL);
printf("END : shared_value = %i\n", ptt_struct.shared_value);
return 0;
}
Voir aussi
- Luigi Zaffalon et Pierre Breguet, Programmation concurrente et temps réel avec ADA 95, Presses polytechniques et universitaires romandes, Lausanne, 1999