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.
- 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.
