Algorithme de Peterson

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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[modifier | modifier le code]

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[modifier | modifier le code]

bool flag[0]   = false;
bool flag[1]   = false;
int turn;
P0: flag[0] = true;
    turn = 1;
    while (flag[1] && turn == 1)
    {
        // attente
    }
    // Début de la section critique
    ...
    // fin de la section critique
    flag[0] = false;
P1: flag[1] = true;
    turn = 0;
    while (flag[0] && turn == 0)
    {
        // attente
    }
    // Début de la section critique
    ...
    // fin de la section critique
    flag[1] = false;

Algorithme pour n processus[modifier | modifier le code]

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[modifier | modifier le code]

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[modifier | modifier le code]

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')[modifier | modifier le code]

#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 flag[2];
    int turn;
    int shared_value;
} Peterson_two_thread_struct;



void thread_num_zero(Peterson_two_thread_struct *ptt)
{
    ptt->flag[0] = TRUE;
    ptt->turn = 1;
    
    while (ptt->flag[1] && ptt->turn == 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->flag[0] = FALSE;
}

void thread_num_one(Peterson_two_thread_struct *ptt)
{
    ptt->flag[1] = TRUE;
    ptt->turn = 0;
    
    while (ptt->flag[0] && ptt->turn == 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->flag[1] = FALSE;
}


int main(int argc, const char * argv[]) {
    
    pthread_t pthread_0, pthread_1;

    Peterson_two_thread_struct ptt_struct;
    ptt_struct.flag[0] = FALSE;
    ptt_struct.flag[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 system can 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[modifier | modifier le code]