Portail informatique Année 2018 – 2019

PAAM – Programmation avancée des architectures multicoeurs

Durée: 1h30, tout document autorisé
On suppose que, initialement, x et y valent 0. Pour quelle raison le code suivant affiche forcément 42 avec un modèle mémoire TSO ?
Thread 1 1.a x = 42; 1.b y = 1; Thread 2 2.a while(y == 0); 2.b printf("%d\n", x);
  • On ne peut que passer 2.a après l'exécution de 1.b.
  • 2.b s'exécute forcément après 2.a (TSO : lecture après lecture).
  • 1.a précède 1.b (TSO : écriture après écriture).
  • Donc 1.a précède 2.b.
Pour quelle raison, si on considère un modèle mémoire plus relaché, le programme précédent pourrait afficher la valeur 0 ? Si les lectures peuvent être réordonnancée, la lecture 2.b pourrait être exécutée avant 2.a, donc aussi avant 1.a et pour afficher 0. On suppose que, initialement, x, y, t1 et t2 valent 0. On suppose aussi qu'on dispose d'un modèle de cohérence séquentiel, c'est-à-dire que les lectures et écritures se propagent aux autres threads exactement dans le sens où elles sont exécutées. Après l'exécution des trois threads, quelles sont les valeurs que les 4 variables peuvent avoir ?
Thread 1 1.a x = 2; 1.b t1 = y; Thread 2 2.a y = 1; 2.b x = 1; Thread 3 3.a t2 = x;
Dans tous les cas, y=1 à la fin. On n'en parle donc plus. Ensuite, x peut être égal à 2 ou 1 à la fin, donc on explore ces deux cas :
  • Si x=2 à la fin, forcément, 2.b précède 1.a. Comme 2.a précède 2.b et 1.a précède 1.b, on a forcément 2.a précède 1.b, donc t1=1. Ensuite t2 peut valoir 0, 1 ou 2 car on peut exécuter 3.a avant 2.b (x vaut encore 0), juste après 2.b (x vaut 1) ou après 1.a (x vaut 2).
  • Si x=1 à la fin, forcément 1.a précède 2.b. Entre 1.a et 2.b, on peut exécuter 1.b et 2.a dans n'importe quel ordre, donc t1 peut valoir 0 (1.b puis 2.a) ou 1 (2.a puis 1.b). Enfin, comme dans le cas précédent, t2 peut valoir 0, 1 ou 2 car on peut exécuter 3.a quand on veut.

En version courte :
  • Si x=2 => t1=1, y=1 et t2=0, 1 ou 2,
  • Si x=1 => t1=0 ou 1, y=1 et t2=0, 1 ou 2.
Si on suppose maintenant un modèle mémoire TSO, quelles sont les valeurs que les 4 variables peuvent avoir ? On fait sauter la contrainte 1.a avant 1.b car TSO autorise une lecture par anticipation avant une écriture. Donc, dans les cas où x=2, on peut remonter la lecture 1.b au début lorsque y vaut 0. On ajoute donc les cas x=2, t1=0, y=1 et t2=0, 1 ou 2.
On souhaite mettre en œuvre une file (FIFO). Vous disposez du canevas de code suivant. Mettez en œuvre addFirst et removeLast en utilisant la variable mutex pour synchroniser les threads. Modifiez vos fonctions de façon à utiliser une mémoire transactionnelle pour synchroniser les threads. En ré-utilisant removeLast et à l'aide d'une mémoire transactionnelle, écrivez une fonction int removeAsync() retirant le dernier élément si le FIFO n'est pas vide et renvoyant -1 sinon. On souhaite mettre en œuvre un algorithme de verrouillage reposant sur un ticket. Le verrou est modélisé par deux entiers : un numéro de ticket et un numéro de guichet. Pour acquérir un verrou, un thread tire un ticket et l'incrémente. Le thread attend ensuite que la variable guichet atteigne la valeur du ticket qu'il a retiré. Pour libérer le verrou, le thread incrémente le guichet. Donnez la définition de la structure de données modélisant un ticket et le code fonction init initialisant cette structure. Donnez le code de la méthode lock permettant d'acquérir un verrou. Donnez le code de la méthode unlock permettant de libérer un verrou.