CSC5101 – Advanced Programming of Multicore Architectures

PAAM – Contrôle final 2018-2019

Durée: 2h, tout document autorisé

Questions de cours (5 points)

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

1 point – facile

Dans une machine NUMA, qu'est-ce qui ralentit le plus l'application : quand le réseau d'interconnexion sature parce que tous les cœurs accèdent de façon aléatoire à tous les bancs mémoires, ou quand un contrôleur mémoire sature parce que tous les cœurs y accèdent ? Justifiez.

Le contrôleur mémoire. En effet, si tous les cœurs accèdent de façon aléatoire à la mémoire, la charge s'équirépartie sur les différents liens entre les nœuds NUMA, alors que si tous les cœurs accèdent au même banc mémoire, toute la charge arrive sur un unique contrôleur mémoire.

1 point – facile

On suppose un modèle mémoire TSO. On suppose qu'un thread 1 exécute la fonction t1 et qu'un thread 2 exécute la fonction t2. Pour quelle raison le thread 2 peut ne jamais effectuer son affichage ? Quelle modification faut-il apporter au code pour corriger le problème ?

int s = 0;
char* msg = NULL;

void t1() {
  msg = "coucou";
  s = 1;
}

void t2() {
  while(s == 0) { 
  }
  printf("Coucou !\n");
}

Le compilateur peut optimiser le code et s'apercevoir que, comme s n'est pas modifié dans t2, il n'y a aucune raison de relire la variable après une lecture initiale. Dans ce cas, le compilateur va remplacer le code de la boucle par un code équivalent à celui-ci :

if(s == 0)
  while(true) { }

et t2 n'atteindra donc jamais le printf. Pour corriger le problème, il suffit de marquer la variable s comme volatile.

1 point – facile

Pour quelle raison le code (corrigé) de la question suivante affiche forcément "Coucou" avec un modèle mémoire TSO alors qu'il peut se terminer sur une faute de segmentation avec un modèle mémoire plus relâché ? Justifiez.

Avec un modèle mémoire relâché, il est possible que l'écriture dans s effectuée par t1 soit propagée aux autres cœurs avant l'écriture dans msg Dans ce cas, t2 peut observer un s != 0 et un msg == NULL, ce qui conduit à une faute de segmentation. De la même façon, il est possible que la lecture de msg soit effectuée avant la lecture de s par t2, ce qui conduit exactement au même problème. Ces deux cas sont impossibles en TSO car TSO empêche le réordonnancement des lectures après les lectures (read after read) et celles des écritures après les écritures (write after write).

1 point – facile

Dans un hyperviseur, pourquoi peut-on exécuter nativement un processus alors que ce n'est pas possible pour le système d'exploitation ? Justifiez.

Un processus n'exécute pas d'instructions privilégiées et interagit avec le système via un appel système. On peut donc l'exécuter nativement pourvu que l'hyperviseur redirige les appels systèmes vers le code du système invité. Ce n'est pas possible pour le système invité car il utilise des instructions privilégiées qui peuvent entrer en conflit avec les actions effectuées par l'hyperviseur.

1 point – facile

Expliquez pourquoi, avec une mémoire transactionnelle matérielle, une transaction peut avorter alors que le thread s'exécute seul ?

Une TM matérielle peut avorter lorsque le cache est plein. Il suffit donc d'exécuter une transaction qui accède à une grande quantité de mémoire pour la faire systématiquement avortée, même si le thread s'exécute seul.

Le verrou lecteur-écrivain (15 points)

Cet exercice a pour but de concevoir un verrou lecteur-écrivain. Ce verrou synchronise l'accès à une section critique. Ce verrou définit deux façon d'accéder à la section critique :

[accès en lecture] si un thread accède à la section critique en lecture (on dit que c'est un lecteur), le thread a la garantie qu'il n'existe pas d'écrivain. En revanche, il peut y avoir d'autres lecteurs s'exécutant en parallèle.
[accès en écriture] si un thread accède à la section critique en écriture (on dit que c'est un écrivain), le thread a la garantie qu'il n'existe ni lecteurs ni écrivains.

L'avantage d'un verrou lecteur-écrivain par rapport à un verrou classique est que le verrou lecteur-écrivain augmente le parallélisme pour les lecteurs.

D'un point de vu technique, le verrou lecteur-écrivain offre quatre fonctions :

void pread(struct rwlock* lock) : appelée par à un thread avant d'entrer en section critique en temps que lecteur.
void vread(struct rwlock* lock)nbsp;: appelée par à un thread pour quitter une section critique en temps que lecteur.
void pwrite(struct rwlock* lock) : appelée par à un thread avant d'entrer en section critique en temps qu'écrivain.
void vwrite(struct rwlock* lock) : appelée par à un thread pour quitter une section critique en temps qu'écrivain.

Approche pessimiste à base de mutex POSIX

Dans un premier temps, nous utilisons une approche pessimiste reposant sur des mutex POSIX. Dans cette configuration, pread doit bloquer tant qu'il existe un écrivain alors que pwrite doit bloquer tant qu'il existe soit un écrivain, soit des lecteurs.

Vous pouvez définir la structure rwlock de la façon qui vous convient le mieux, mais nous vous conseillons d'utiliser la structure rwlock suivante :

struct rwlock {
  pthread_mutex_t wlock;      /* verrou bloquant les écrivains */
  pthread_mutex_t rlock;      /* verrou pour synchroniser les lecteurs */
  int             nb_readers; /* donne le nombre de lecteurs dans la section critique */
};

Initialement, les deux mutex wlock et rlock sont libres, et nb_readers vaut 0.

4 points – moyen

Mettez en œuvre les quatre fonctions pread, vread, pwrite et vwrite. Pour vous guider, les écrivains se synchronisent uniquement en utilisant wlock, et seul le premier lecteur a besoin de prendre ce verrou pour empêcher les écrivains d'entrer en section critique.

Répondre à cette question devrait nécessiter une quinzaine de lignes de code.

void pwrite(struct rwlock* rwlock) {
  pthread_mutex_lock(&rwlock->wlock);
}

void vwrite(struct rwlock* rwlock) {
  pthread_mutex_unlock(&rwlock->wlock);
}

void pread(struct rwlock* rwlock) {
  pthread_mutex_lock(&rwlock->rlock);
  if(!rwlock->nb_readers)
    pthread_mutex_lock(&rwlock->wlock);
  rwlock->nb_readers++;
  pthread_mutex_unlock(&rwlock->rlock);
}

void vread(struct rwlock) {
  pthread_mutex_lock(&rwlock->rlock);
  if(!--rwlock->nb_readers)
    pthread_mutex_unlock(&rwlock->wlock);
  pthread_mutex_unlock(&rwlock->rlock);
}

2 points – difficile

L'algorithme simple que vous avez mis en œuvre peut entraîner des famines. En effet, une fois qu'il existe des lecteurs, un écrivain qui souhaite prendre le verrou wlock verra les nouveaux lecteurs passer devant lui. Modifiez votre algorithme pour empêcher les lecteurs d'entrer en section critique si il existe un écrivain qui souhaite entrer en section critique.

Le code nécessaire pour empêcher les lecteurs d'entrer en section critique lorsqu'il existe des écrivains nécessite de modifier une unique fonction et ne devrait pas nécessiter plus de deux lignes de code.

Il est possible qu'avec votre mise en œuvre, la problème de famine n'existe pas. Si c'est le cas, au lieu de répondre à la question, expliquez pourquoi.

Avec la solution naïve proposée à la question précédente, tant qu'il existe des lecteurs, les écrivains sont mis en attente. Il suffit donc d'imaginer des arrivées et départs de lecteurs en continue pour empêcher les écrivains de progresser. Une solution simple à ce problème consiste en empêcher les lecteurs d'entrer en section critique si il existe des lecteurs. Pour cela, il suffit de bloquer le verrou lecteur si il existe un écrivain :

void pwrite(struct rwlock* rwlock) {
  pthread_mutex_lock(&rwlock->rlock);
  pthread_mutex_unlock(&rwlock->rlock);
  pthread_mutex_lock(&rwlock->wlock);
}

Approche pessimiste versus optimiste

On souhaite maintenant mettre en œuvre une pile offrant trois opérations :

void push(int n) : ajoute un élément en haut de la pile,
int pop() : retire l'élément se trouvant en haut de la pile.
int size() : compte le nombre d'éléments se trouvant dans la pile.

3 points – facile

Donnez le code des structures de données et des trois fonctions sachant qu'on vous demande de mettre en œuvre la pile à l'aide d'une liste chaînée (si vous construisez votre pile comme un tableau, la réponse sera considérée comme fausse). Plutôt que d'utiliser des verrous classiques, on vous demande d'utiliser un verrou lecteur-écrivain pour synchroniser l'accès à la pile.

struct node {
  struct node* next;
  int          value;
};

struct node* stack = 0;
struct rwlock lock;

void push(int n) {
  struct node* new = malloc(sizeof(*new));
  new->value = n;

  pwrite(&lock);
  new->next = stack;
  stack = new;
  vwrite(&lock);
}

int pop() {
  pwrite(&lock);
  int res = stack->value;    // null case management not requested
  struct node* node = stack;
  stack = stack->next;
  free(node);
  vwrite(&lock);

  return res;
}

int size() {
  int n = 0;
  pread(&lock);
  for(struct node* cur=stack; cur; cur=cur->next)
    n++;
  vread(&lock);
  return n;
}

2 point – facile

Donnez les modifications que vous devez apporter à votre code pour utiliser une mémoire transactionnelle ? Pour cela, vous supposerez que vous disposez d'une construction atomic { ... } permettant de définir un bloc atomique.

Il suffit de remplacer les sections critiques (les couples pwrite/vwrite et pread/vread) par des blocs atomiques.

2 points – moyen

Si il existe beaucoup de lecteurs et peu d'écrivains, quelle solution vous semble la plus efficace sachant qu'on utilise une mémoire transactionnelle matérielle. Justifiez (de façon concise en cinq lignes maximum).

Toutes les réponses, pourvues qu'elles soient clairement justifiées, peuvent être admises. Une première réponse peut être la suivante. La solution avec une mémoire transactionnelle est probablement meilleure. En effet, le verrou est appliqué à toute la liste alors que la mémoire transactionnelle détecte les conflits à la granularité du nœud. Si on imagine une grande liste la probabilité de conflit écrivain/lecteur à l'échelle de toute la liste est beaucoup plus grande que celle à l'échelle d'un nœud. Moins de threads progressent avec les verrous, donc la mémoire transactionnelle est meilleure.

Une autre réponse possible peut être la suivante. La solution avec des verrous est probablement meilleure. Si le nombre d'écriture est très faible, les deux solutions vont passer à l'échelle (très rare d'être bloqué avec le verrou car peu de demande en écriture, très rare d'avoir un conflit avec une mémoire transactionnelle car peu de demande en écriture). Avec une mémoire transactionnelle, on payera en revanche un surcout pour chaque accès à une variable (instrumentation du code) alors que ce n'est pas le cas avec le verrou, donc le verrou devrait être plus efficace.

Remarquez que ces deux réponses ne sont pas en contradiction. Pour la première réponse, on considère qu'il y a suffisamment d'écritures pour que les conflits lecteurs/écrivains existent à l'échelle de la liste, alors qu'avec la seconde réponse, on considère que le nombre de ces conflits est négligeable.

Approche pessimiste sans verrou POSIX (partie difficile, à faire à la fin)

On souhaite maintenant mettre en œuvre le verrou lecteur-écrivain sans utiliser de mutex POSIX. Pour cela, nous vous proposons d'utiliser la structure suivante :

union rwlock {
  struct {
    uint64_t nb_readers : 63;
    uint64_t has_writer : 1;
  };
  uint64_t state;
};

Le mot clé union permet de placer la structure anonyme interne et la variable state au même endroit en mémoire. Les deux points suivi de nombres indiquent le nombre de bits utilisés par les champs. Dans notre cas, la structure anonyme fait donc 63 + 1 = 64 bits, c'est-à-dire la taille d'un entier 64 bits comme state.

Pour illustrer, voici comment on peut utiliser cette structure :

void f(struct rwlock* rwlock) {
  union rwlock old;
  old->state = rwlock->state; /* copie les 64 bits de rwlock dans old */
                              /* old->nb_readers et rwlock->nb_readers sont donc égaux */
                              /* et old->has_writer et rwlock->has_writer sont donc égaux */

  union rwlock new;
  new->state = old->state;    /* idem, on copie de nouveau les 64 octets */
  new->has_writer = 0; 
  /* on peut aussi remplacer les 64 bits de rwlock avec une opération atomique */
  __sync_val_compare_and_swap(&rwlock->state, old->state, new->state);

  /* ou décrémenter rwlock->nb_readers avec une opération atomique */
  __sync_fetch_and_add(&rwlock->nb_readers, -1);
}

2 points – très difficile

Donnez les codes des quatre fonctions d'accès aux verrous. L'ensemble du code fait entre 20 et 25 lignes.

union rwlock {
  struct {
    uint64_t nb_readers : 63;
    uint64_t has_writer : 1;
  };
  uint64_t state;
};

void pread(struct rwlock* rwlock) {
  union rwlock initial;
  union rwlock newstate;
  do {
    initial->has_writer = 0;
    initial->nb_readers = rwlock->nb_readers;
    newstate->nb_readers = initial->nb_readers + 1;
    newstate->has_writer = 0;
  } while(__sync_val_compare_and_swap(&rwlock->state, initial->state, newstate->state) != initial->state);
}

void vread(struct rwlock* rwlock) {
  __sync_fetch_and_add(&rwlock->nb_readers, -1);
}

void pwrite(struct rwlock* rwlock) {
  union rwlock initial;
  union rwlock newstate;
  do {
    initial->nb_readers = 0;
    initial->has_writer = 0;
    newstate->nb_readers = 0;
    newstate->has_writer = 1;
  } while(__sync_val_compare_and_swap(&rwlock->state, initial->state, newstate->state) != initial->state);
}

void vwrite(struct rwlock* rwlock) {
  rwlock->has_writer = 0;
}