CSC5101 – Advanced Programming of Multicore Architectures

Parallel and Distributed Systems track

PAAM – Contrôle final 2019-2020

Durée: 2h, tout document autorisé

La file (11 points)

On souhaite mettre en œuvre une pile (LIFO) à l'aide d'un tableau. Dans cette pile, le dernier élément ajouté est donc le premier élément retiré. Techniquement, un élément est un caractère. Vous disposez donc d'un tableau tab de MAX caractères et d'un index head. La fonction int push(char e) pose un élément et renvoie 0 lorsque la pile n'est pas pleine. Elle ajoute l'élément en tab[head] puis incrémente head. La fonction char pop() retire un élément. Elle décremente head puis renvoie l'élément en tab[head].

3 points (was 2)

Donnez le code de votre pile sans vous soucier des problèmes de synchronisations. Lorsque la pile est vide, la fonction pop doit attendre qu'un élément soit déposé, et lorsque la pile est pleine, la fonction push doit attendre qu'un élément soit retiré. Pour les attentes, à cette question, vous pouvez effectuer une attente active (c'est-à-dire une boucle qui attend respectivement qu'une place soit libre ou qu'il y ait un élément).
Pensez à donner les définitions des structures de données et des variables que vous utilisez.

4 point (was 3)

Donnez le code de votre pile en utilisant un verrou pour synchroniser les threads. Pour les attentes, on vous demande d'utiliser des variables conditions.

3 points

Donnez un code lock-free de la pile. Pour les attentes, effectuez une attente active.

2 points

On suppose que vous disposez d'une mémoire transactionnelle et des mots clés atomic et retry. Donnez le nouveau code de la pile. Pour les attentes, utilisez la construction naturelle correspondant aux mémoires transactionnelles.

2 points (was 1)

En réutilisant la fonction void push(int c) de la question précédente, donnez le code de la fonction void push_async(int c) qui, au lieu d'attendre lorsque la pile est pleine, renvoie -1.

Algorithme de verrouillage (5 points)

On souhaite mettre en œuvre un algorithme de verrouillage équitable reposant sur une liste chaînée. On suppose que vous disposez du code suivant :
struct node { int locked; struct node* next; }; struct node* queue; /* variable partagée */ __thread struct node* node; /* une variable par thread */

5 points

L'algorithme qu'on vous demande de mettre œuvre s'appelle MCS. Lorsqu'un thread veut prendre un verrou :
  • Il pré-initialise sa variable node->locked à faux,
  • Il échange node avec queue et stocke l'ancienne valeur de queue dans une variable nommée tmp,
  • Si tmp est null, c'est que le verrou n'est pas pris, le thread a donc acquis le verrou.
  • Sinon, c'est qu'il existe un thread qui possède le verrou. Dans ce cas, il suffit de positionner tmp->next à node et d'attendre que node->locked passe à vrai.
Lorsqu'un thread souhaite relâcher un verrou :
  • Si head vaut node, c'est qu'aucun thread n'attend le verrou. Il suffit donc de passer head à null.
  • Sinon, c'est qu'un thread attend le verrou. Si node->next est null, c'est que l'autre thread n'a pas encore eu le temps de s'ajouter à la chaîne, il faut donc l'attendre (avec une boucle active).
  • Une fois qu'on connaît le thread qui attend le verrou, il suffit de lui indiquer que le verrou est libre en modifiant le champs locked de son nœud.
Donnez le code des fonctions lock et unlock.

Questions de cours (4 points)

Dans cet exercice, lorsqu'on vous demande de justifier, il vous ait demandé de rédiger des réponses concises et synthétiques.

2 points

Pour quelle raison le code suivant, lorsqu'il est exécuté en multi-threads sur une machine quelconque, peut mener à une faute de segmentation ? Donnez le scénario exact menant à cette faute.
int inited = 0; pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER; struct { char* name; }* data; void f() { if(!inited) { pthread_mutex_lock(&mutex); if(!inited) { data = malloc(sizeof(*data)); data->name = "Igor le Zombie"; inited = true; } pthread_mutex_unlock(&mutex); } printf("%s\n", data->name); }

1 point

Pourquoi, avec un modèle mémoire TSO, le problème identifié à la question précédente ne peut pas se produire ?

1 points

Sur une architecture NUMA, pour quelle raison faut-il d'abord s'occuper d'équilibrer la charge sur les contrôleurs mémoires avant de s'occuper d'améliorer la localité ?