CSC5101 – Advanced Programming of Multicore Architectures

Parallel and Distributed Systems track

PAAM – Contrôle final 2017-2018

Durée: 1h30, tout document autorisé

Modèles mémoires (6 points)

1 points

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.

1 point

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.

2 point

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.

2 point

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.

La FIFO (8 points)

On souhaite mettre en œuvre une file (FIFO). Vous disposez du canevas de code suivant.

3 points

Mettez en œuvre addFirst et removeLast en utilisant la variable mutex pour synchroniser les threads.

3 points

Modifiez vos fonctions de façon à utiliser une mémoire transactionnelle pour synchroniser les threads.

2 points

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.

Algorithmique lock-free (6 points)

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.

1 point

Donnez la définition de la structure de données modélisant un ticket et le code fonction init initialisant cette structure.

3 points

Donnez le code de la méthode lock permettant d'acquérir un verrou.

2 points

Donnez le code de la méthode unlock permettant de libérer un verrou.