Voici la présentation d’un problème basique d’exclusion mutuelle, de la solution trouvée par Peterson, et des particularités des architectures actuelles qui rendent sa solution originale invalide.

Un peu d'histoire - Motivation

Les utilisateurs des premières machines multi-coeurs ont été rapidement confrontés à des problèmes de synchronisation : ils souhaitaient que plusieurs unités de calcul puissent partager les même zones mémoires, tout en garantissant que certaines portions de code ne soient exécutées que par une et une seule unité de calcul à la fois. Ces portions de code s’appellent des sections critiques, et faire en sorte qu’une seule unité de calcul puisse y accèder est réaliser une exclusion mutuelle.

Au début des années 60 les machines multi-coeurs n’avaient pas une architecture à mémoire partagée compliquée : les différentes unités de calcul étaient branchées sur la même mémoire, qu’elles accédaient directement. Il n’y avait donc pas de mémoire virtuelle, ni les différents niveaux de caches ou les multiples bancs mémoire que l’on peut avoir sur nos machines aujourd’hui.

L’idée d’écrire cet article m’est venu en présentant le problème à mes étudiants : je voulais illustrer les solutions théoriques proposées en réalisant leurs implémentations (le support de cours fourni ne les y incitant pas), mais pour que celles-ci marchent j’ai du tenir compte des particularités des architectures récentes. Je me suis dis que ça pouvait être utile de faire un article récapitulant les modifications nécessaires et leurs raisons.
Je vais donc rapidement présenter un problème illustrant la nécessité de l’exclusion mutuelle ainsi que sa solution dans le contexte d’une architecture mémoire simple, puis expliquer pourquoi celle-ci ne marche pas sur nos machines “récentes”, et enfin détailler quels ajustement sont nécessaires pour la rendre fonctionnelle.

Le problème

Présentation

Disons que pour cet exemple deux processeurs souhaitent incrémenter une même variable i, le code pseudo-assembleur correspondant à l’instruction i++ est le suivant :

load r0, $i  --charge la valeur à l'adresse de i dans le registre 0
inc r0       --incrémente i
store $i, r0 --enregistre la valeur de r0 à l'adresse mémoire de i

Le problème se pose si les deux processeurs effectuent le load avant que l’un des deux n’ait fait le store : dans ce cas là les deux processeurs vont incrémenter la valeur originale de i, ce qui, au final, n’aura incrémenté i qu’une seule fois sur les deux attendues.

Ce problème a été résolu par Dekker en 1966, et Peterson a proposé une solution plus élégante en 1981.

En cours le “jeu” proposé aux étudiants est de réussir à retrouver la solution de Dekker en suggérant et étudiant différentes implémentations. Je ne vais pas passer sur toutes les implémentations suggérées, mais le code que j’utilise pour les démonstations est ici1, et je vais me contenter de commenter la solution “améliorée” de Peterson.

La solution de Peterson

On suppose ici que seul deux unités de calcul veulent accèder à la ressource partagée (dont l’accès est encadré par les appels à entreeSC et sortieSC), et que l’indice de l’unité demandeuse est proc.

int dernier;
bool demandeSC[2] = { false, false };
void entreeSC(int proc)
{
    demandeSC[proc] = true;
    dernier = proc;
entree:
    if (demandeSC[1 - proc] == true) {  //c1
        if (dernier == proc)            //c2
            goto entree;
    }
}

void sortieSC(int proc)
{
    demandeSC[proc] = false;
}

Le principe est simple : avant d’entrer en section critique, le processus indique son intention d’y rentrer, et qu’il est le dernier à avoir fait la demande. Si l’autre processus a fait sa demande alors le dernier processus à avoir demandé attend.

L’astuce ici est de remarquer que même si les deux processus font la demande en même temps (ie: c1 est vraie pour les deux au même moment), un et un seul attendra : celui qui a mis à jour la variable dernier en dernier (c2 ne peut être vraie que pour l’un des deux : les store correspondant aux deux affectations auront forcément un ordre, qui déterminera la valeur finale de dernier). L’autre pourra rentrer sans attendre.

Particularités des architectures x86

Si vous implémentez la solution de Dekker et/ou celle de Peterson, et que vous l’exécutez sur une machine multi-coeurs utilisant le jeu d’instructions x86 (votre ordinateur portable fait probablement partie de cette catégorie), alors vous constaterez qu’il n’y a pas d’exclusion mutuelle (!). Voici un exemple de l’exécution sur ma machine personnelle :

[16:30]:~/ensimag/sepc/dekker_examples$ ./peterson_1981
x: 0
(thread) : X incrémenté 1 000 000 fois.
(main) : X incrémenté 1 000 000 fois
x: 1991421

La valeur finale de x peut changer, l’important est qu’elle n’est pas égale à la valeur attendue que l’on devrait avoir si l’algorithme réalisait bien une exclusion mutuelle (2 000 000 pour ceux qui ne suivent pas) !
L’algorithme est pourtant bon, alors pourquoi ce comportement ?

Il y a deux raisons qui peuvent l’expliquer.

Instruction Reordering

La première chose à savoir, c’est que peu importe le code assembleur que votre compilateur va générer, le processeur a une certaine marge de manoeuvre avec les instructions qu’il doit exécuter.
Jetons un oeil au code peudo assembleur correspondant à la demande d’entrée en section critique :

-- "demandeSC[proc] = true" et "dernier = proc"
store $demandeSC[proc], 1
store $dernier, proc
-- loads pour c1 et c2 :
load r0, $demandeSC[1 - proc]
load r1, $dernier
--cmp et jmp

Voici ce qu’on peut lire dans la documentation d’Intel concernant le réordonnancement d’instruction2 : «Loads may be reordered with earlier stores to different locations».
En supposant que votre processeur utilise un jeu d’instruction x86 (supposition raisonable pour un ordinateur de bureau), voici donc ce que le cpu pourraient réellement exécuter :

load r0, $demandeSC[1 - proc]
store $demandeSC[proc], 1
store $dernier, proc
load r1, $dernier

En effet, l’adresse de demandeSC[1-proc] n’est concernée par aucun des deux store, le processeur peut donc effectuer le load avant !
Si les deux threads exécutent ce code, ils vont tous les deux voir la demande de l’autre comme étant à false, et vont donc tous les deux entrer en section critique, d’où le problème observé précédemment !

Load/Store Buffer

La deuxième source de problème est l’ensemble load/store buffer3, présent dans certaines architectures de processeurs comme les Sandy et Ivy Bridge, dont votre processeur fait sûrement partie.
Leur objectif est de stocker les opérations de load et store pendant la lecture ou l’écriture de la mémoire, afin que le processeur ne soit pas bloqué à ne rien faire pendant l’attente de la fin de l’opération.

Il est donc possible qu’un load passe avant un store à ce moment là, et que le schéma d’exécution décrit précédemment se reproduise.

La solution : la barrière mémoire

À ce moment là de l’article vous devriez avoir compris qu’utiliser le mot clé volatile (en C/C++) pour supprimer le réordonnancement d’instructions au niveau du compilateur n’est pas suffisant.
La solution à ces deux problèmes est donc d’utiliser une barrière mémoire physique, qui existe dans le jeu d’instruction x86 sous le nom de mfence (pour “Memory Fence”).
En C/C++ il y a plusieurs moyens de la traduire, dans mon code j’ai utilisé la fonction __sync_synchronize qui fait partie des builtins de gcc, et qui est également implémentée dans clang.

On obtient alors l’exécution attendue :

[16:31]:~/ensimag/sepc/dekker_examples$ ./peterson_1981
x: 0
(thread) : X incrémenté 1 000 000 fois.
(main) : X incrémenté 1 000 000 fois
x: 2000000

Voilà pour l’explication du problème “historique”. Actuellement de nombreuses primitives de synchronisation sont déjà implémentées et largement utilisées (opérations atomiques, moniteurs et sémaphore…), donc si vous n’essayez pas de réinventer la roue, vous ne devriez pas rencontrer ce problème en pratique (au moins, maintenant, vous savez qu’il peut exister…).


1 : Dépendances pour les sources : la librairie pthread et un compilateur pour c99 compatible avec les opérations atomiques de gcc.
2 : Un excellent article sur le réordonnancement d'instructions : ici.
3 : Un article général sur l'interaction entre le CPU et le cache sur les architectures Sandy Bridge : ici.