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