Algorithme de Peterson

Un article de Wikipédia, l'encyclopédie libre.
Ceci est une version archivée de cette page, en date du 26 février 2019 à 23:56 et modifiée en dernier par SyntaxTerror (discuter | contributions). Elle peut contenir des erreurs, des inexactitudes ou des contenus vandalisés non présents dans la version actuelle.

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