Synchronisation de processus légers

Exercice 6 (À la recherche du signal perdu...) Soit l’extrait de code producteur/consommateur suivant :

/* Consommateur */

pthread_mutex_lock(&lock);
while (!expression)
  pthread_cond_wait(&cond, &lock);

do_thing(); 
pthread_mutex_unlock(&lock);

/* Producteur, Signaleur */ 

expression = TRUE; 
pthread_cond_signal(&cond);

Question 1 Montrer que le consommateur peut ne pas être réveillé alors qu’il le devrait : des pthread_cond_signal() pouvant être perdus.

Question 2 Quelle(s) correction(s) apporter à cet extrait de code pour éviter ce comportement ?

On reprend l’exemple du producteur/consommateur vu en cours :

fonction put_cb_data() du producteur
fonction get_cb_data() du consommateur

Question 3 Est-ce que le producteur peut échanger l’ordre des deux instructions pthread_cond_signal() et pthread_mutex_unlock() ?

Exercice 7 (Synchronisation de l’arbre de calcul) On propose encore d’améliorer la solution des exercices 1 et 4 de calcul du n^e nombre de Fibonacci de la manière suivante : on modifie la dernière solution de mémorisation des calculs précédents pour marquer qu’un processus léger est en train de calculer une valeur. Les éléments du tableau fibtab sont soit une valeur positive, soit une des deux valeurs INCONNUE et ENCOURS

#define INCONNUE       -1
#define ENCOURS        -2
static int fibtab [];

Identifiez la synchronisation nécessaire entre un processus léger en cours de calcul d’une valeur et un processus légers ayant besoin de cette valeur. Proposez une implémentation de cette synchronisation.

Exercice 8 (Barrières de synchronisation) On désire implanter une bibliothèque de barrières de synchronisation à l’aide des constructions fournies par la bibliothèque POSIX.

L’interface de cette bibliothèque sera la suivante :

typedef struct barrier_s barrier_t; 

barrier_t *barrier_init(unsigned n_clients); 
void barrier_destroy(barrier_t *barrier); 
void barrier_wait(barrier_t *barrier);

La fonction barrier_init() alloue et initialise une barrière qui sera utilisée par n_clients.

La fonction barrier_destroy() demande la destruction de la barrière. Aucun thread ne doit attendre sur la barrière lors de la destruction.

La fonction barrier_wait() est appelée par un thread pour rentrer dans la barrière. Quand n_clients threads ont atteint la barrière, ils sont tous libérés.

Question 1 Quelle structure est nécessaire à l’implantation des barrières ?

Question 2 Donner le code des fonctions de la bibliothèque.

On considère maintenant l’utilisation suivante de la bibliothèque :

#define N      ...
barrier_t b; 

static void *
foo(void *dummy) 
{
    do_thing1(); 
    barrier_wait(&b); 
  
    do_thing2(); 
    barrier_wait(&b); 
  
    pthread_exit(0); 
}

int 
main(void) 
{
    int i; 
    pthread_t dummy_tid; 
    b = barrier_init(N); 
  
    for (i=1; i<N; i++) 
        pthread_create(&dummy_tid, NULL, 
                       foo, NULL); 
    foo(); 
}

Question 3 Considérez les différents ordonnancements des threads pouvant intervenir entre la première et la seconde utilisation de la barrière. Mettez en évidence un fonctionnement erroné possible.

Question 4 Corrigez la première implantation de la bibliothèque pour que l’utilisation multiple des barrières ne pose aucun problème.

Exercice 9 (Barrières cumulatives) On change l’interface de la bibliothèque de l’exercice précédent. Le prototype de la fonction barrier_wait() devient

int barrier_wait(barrier_t *barrier, int increment);

Elle est appelée par un thread qui atteint la barrière. Quand n_clients threads ont atteint la barrière, ils sont tous libérés. Le résultat retourné est la somme de tous les increment passés par les threads lors de leur appel à barrier_wait.

Exercice 10 (Barrières asymétriques) On change encore l’interface de la bibliothèque. La fonction barrier_wait() est remplacée par trois nouvelles fonctions. L’utilisation des deux fonctions barrier_init() et barrier_destroy() change légèrement :

barrier_t *barrier_init(unsigned n_slaves); 
void barrier_destroy(barrier_t *barrier); 
int barrier_master(barrier_t *barrier); 
int barrier_release(barrier_t *barrier); 
int barrier_slave(barrier_t *barrier, int increment);

La fonction barrier_init() est appelée par le thread maître pour allouer et initialiser une barrière qui sera utilisée avec n_slaves threads esclaves.

La fonction barrer_destroy() est appelée par le thread maître pour détruire la barrière.

La fonction barrier_master() est appelée par le thread maître pour attendre que les n_slaves threads esclaves aient atteint la barrière. Quand c’est le cas, barrier_master() retourne la somme des incréments donnés par l’ensemble des esclaves.

La fonction barrier_release() est appelée par le maître pour libérer l’ensemble des esclaves qui attendent sur la barrière.

La fonction barrier_slave() est appelée par un thread esclave qui atteint la barrière. La valeur increment est accumulée pour être retournée (barrier_master()) au maître. barrier_slave() retourne après que le maître ait appelé barrier_release(). La valeur retournée est la somme des increment de l’ensemble des esclaves (i.e. la même valeur que celle retournée au maître par barrier_master()).

Question 1 Quelle utilité voyez-vous à l’utilisation d’une telle structure de synchronisation ?

Question 2 Donnez une implantation de la bibliothèque barrier initiale à l’aide de cette version asymétrique.

Question 3 Donnez une implantation de cette version asymétrique à l’aide de la version initiale de la bibliothèque.

Question 4 Donnez une implantation native de cette version de la bibliothèque.

Exercice 11 (Verrous récursifs) On désire implanter une extension des verrous mutex de la bibliothèque pthread de base. Un de nos rec_mutex peut à nouveau être rec_mutex_lock() par le thread propriétaire du verrou sans qu’il se bloque. Le propriétaire d’un verrou le relâche par un nombre d’appels à rec_mutex_unlock() égal au nombre d’appels à rec_mutex_lock() réalisés.

Question 1 Définir un type et écrire les fonctions suivantes :

typedef struct _rec_mutex_s rec_mutex_t; 

struct _rec_mutex_s { ... }; 

#define REC_MUTEX_INITIALIZER ...

int rec_mutex_init(rec_mutex_t *rm);
int rec_mutex_destroy(rec_mutex_t *rm);

int rec_mutex_lock(rec_mutex_t *rm);
int rec_mutex_unlock(rec_mutex_t *rm);

Question 2 Définir la fonction :

int rec_mutex_trylock(rec_mutex_t *rm);

3 Synchronisation de processus légers