Contrôle final 20016-2017
La pile (14 points)
On souhaite programmer une pile contenant des entiers de quatre façons différentes :
sans se préoccuper des problèmes de synchronisations,
en utilisant des verrous,
en utilisant un mémoire transactionnelle,
et en utilisant un algorithme sans verrou.
Pour vous guider, on vous propose de partir du squelette suivant :
struct node {
struct node* next;
int value;
};
struct node* head = 0;
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
4 points
Nous commençons par une version initiale dans laquelle on ne soucie pas des problèmes de
synchronisation. Donnez le code des fonctions void push_unsafe(int value)
et int pop_unsafe() permettant d'ajouter et de retirer un élément de la pile.
Si la pile est vide, la fonction int pop_unsafe() doit retourner la valeur -1.
void push_unsafe(int value) {
struct node* node = malloc(sizeof(struct node));
node->next = head;
node->value = value;
head = node;
}
int pop_unsafe() {
struct node* node = head;
if(node) {
int res = node->value;
head = node->next;
free(node);
return res;
} else
return -1;
}
2 points
Nous programmons maintenant la version protégée par un verrou.
Donnez le code des fonctions push_lock(int value) et
int pop_lock() utilisant un verrou.
Pensez à réutiliser les fonctions que vous avez précédemment programmées.
void push_lock(int value) {
pthread_mutex_lock(&mutex);
push_unsafe(value);
pthread_mutex_unlock(&mutex);
}
int pop_lock() {
pthread_mutex_lock(&mutex);
int res = pop_unsafe();
pthread_mutex_unlock(&mutex);
return res;
}
2 points
On suppose maintenant que votre langage dispose des mots clés atomic
et retry. Donnez le code des fonctions
void push_tm(int value) et int pop_tm() utilisant
une mémoire transactionnelle.
void push_tm(int value) {
atomic {
push_unsafe(value);
}
}
int pop_tm() {
atomic {
return pop_unsafe();
}
}
2 points
On souhaite maintenant écrire une fonction int pop_tm_wait() qui attend
qu'il existe au moins un élément dans la pile avant de le retourner.
La fonction int pop_tm_wait() doit utiliser la fonction int pop_tm()
pour retirer un élément de la pile.
int pop_tm_wait() {
atomic {
int res = pop_unsafe();
if(res == -1)
retry;
return res;
}
}
4 points
On souhaite maintenant écrire une version sans verrou permettant d'accéder à la pile.
Donnez le code des fonctions void push_lock_free(int value)
et int pop_lock_free().
void push_lock_free(int value) {
struct node* node = malloc(sizeof(struct node));
node->value = value;
do {
node->next = head;
} while(__sync_val_compare_and_swap(&head, node->next, node) != node->next);
}
int pop_lock_free() {
struct node* node;
do {
node = head;
} while(__sync_val_compare_and_swap(&head, node, node->next) != node);
return node->value;
}
Questions de cours (6 points)
2 points
Dans un modèle mémoire TSO, pour quelle raison le code suivant, dans
lequel il existe un unique thread sender et un unique thread
receiver, est-il correct ?
char* msg = 0;
int go = 0;
void sender() {
msg = "coucou";
go = 1;
}
void receiver() {
while(!go);
printf("%s\n", msg);
}
4 points
On suppose une architecture à mémoire non uniforme. Chaque cœur possède un cache L1 unifié.
Les cœurs d'un nœud NUMA partagent un cache L2 unifié.
En partant de l'adresse virtuelle @v d'une variable x,
décrivez étape par étape comment le matériel exécute un accès en écriture à la variable.
Pensez à expliquer ce qui se passe dans les différents caches.
On suppose que votre machine possède quatre nœuds NUMA.
On suppose aussi que l'accès est effectué par le cœur 5 du nœud 0,
que la variable est gérée par le nœud 1 et qu'elle
est se trouve dans le cache L1 du cœur 3 du nœud 2 à l'état Modified.
Transforme @v en @p via la table des pages
Demande à L1 un accès exclusif à @p
Demande à L2 un accès exclusif
Demande à Noeud 1 un accès exclusif
Noeud 1 enregistre @p sur noeud 0/coeur 5
Noeud 1 forward la requête à noeud 2/coeur 3
Noeud 2/coeur 3 invalide @p et envoie @p à noeud 0/coeur 5
L2 ajoute @p à son cache en exclusif
L1 ajoute @p à son cache en exclusif
Processeur effectue l'accès
