SE205: Travaux Pratiques sur la Programmation Concurrente en POSIX

$Id: index.texi,v 1.22 2010/09/29 13:18:22 pautet Exp $

Laurent Pautet (pautet@telecom-paristech.fr)

Index

1 TP de Concurrence en POSIX

Ce TP ne présente pas tous les outils proposés par POSIX pour gérer la concurrence. Il illustre le fonctionnement de quelques uns d’entre eux. Le support de cours sur les threads se trouve ici. Vous trouverez une documentation complète des fonctions POSIX concernant les threads en suivant le lien http://pubs.opengroup.org/onlinepubs/007908799/xsh/pthread.h.html

Vous trouverez dans cette archive compressée l’intégralité des sources.

Pour décompresser, utiliser GNU tar:

/usr/local/bin/tar zxf src.tar.gz

1.1 Création de processus et terminaison par ordre de création

On considère le fichier main_join.c. Complèter cette application pour créer autant de threads que demandé sur la ligne de commande.

Chaque thread devra s’endormir pendant une certaine durée. Cette durée sera déterminée au hasard par le thread principal et passée en argument lors la création du thread. Le thread retrouvera cette durée dans les paramètres d’appel de son main.

Par ailleurs, complètez le code pour que le thread principal attende la fin de l’execution de ses threads. Dans un premier temps, on attendra la terminaison dans l’ordre de création des threads. Lors de la terminaison, le thread principal obtiendra le temps que le thread ayant terminé devait rester en sommeil. Celui-ci sera d’ailleurs indiqué entre parenthèses lors de l’affichage.

thread (0x10544d000) join after 5 s (3 s)

1.2 Tampon circulaire protégé contre les accès concurrents

Nous allons implanter un tampon circulaire protégé dans le fichier protected_buffer.c. Pour ce faire, on pourra utiliser l’implantation d’un tampon circulaire non-protégé qui est fourni dans les fichiers circular_buffer.c et circular_buffer.h. Consulter les fonctionnalités disponibles dans circular_buffer.h.

Complètez la structure protected_buffer_t. Elle ne contient qu’un tampon circulaire non-protégé actuellement. Il vous faudra rajouter un mutex et une variable conditionnelle.

Complètez les procédures protected_buffer_init, protected_buffer_get et protected_buffer_put afin qu’il offre les services suivants :

protected_buffer_init : initialise le tampon circulaire protégé contre les accès concurrents et dispose d’un nombre de cases fourni en paramètre de la procédure.
protected_buffer_get : retire du tampon circulaire protégé l’élément le plus anciennement ajouté (donc en politique FIFO). Si le tampon est vide, l’appel sera bloquant jusqu’à ce qu’une case se remplisse. L’opération doit se faire en interdisant les accès concurrents.
protected_buffer_put : ajoute au tampon circulaire protégé un élément. Si le tampon est plein, l’appel sera bloquant jusqu’à ce qu’une case se libère. L’opération doit se faire en interdisant les accès concurrents.

Testez le bon fonctionnement du tampon circulaire protégé grace au programme principal du fichier main_protected_buffer.c. On notera les moments où les consommateurs et les producteurs sont supposés bloquer.

1.3 Création de processus et terminaison par ordre d’arrivée

On s’intéresse de nouveau au fichier main_join.c. Comme précédemment, on crée autant de threads que demandés sur la ligne de commande et le thread principal attend la fin de l’execution de ses threads. Par contre, on souhaite que celui-ci reçoive les notifications de terminaison des threads dans l’ordre où elles surviennent et non plus dans l’ordre de création. Typiquement, on souhaite que la terminaison des threads s’effectue comme elle le fait pour la fonction wait des processus lourds. Utiliser le tampon circulaire protégé (implanté dans la question précédente) pour obtenir un tel comportement.

1.4 Exclusion mutuelle entre lecteurs et rédacteurs (3 mutexes)

On cherche à implanter un mécanisme d’exclusion mutuelle sur une donnée v qui permette de respecter les contraintes suivantes en présence de plusieurs lecteurs et rédacteurs:

plusieurs lecteurs doivent pouvoir lire la donnée v en même temps
si un rédacteur est en train de modifier la donnée v, aucun autre utilisateur (ni rédacteur, ni même lecteur) ne doit pouvoir y accéder.

Par ailleurs, on veillera à ce qu’il n’y ait pas de famine pour les rédacteurs, notamment lorsque survient un flot continu de lecteurs. Pour ce faire, vous pouvez vous rappeler de vos cours de première année par exemple. Une solution relativement simple consiste à utiliser 3 verrous :

un verrou mutex sert à effectivement protéger la donnée v
un verrou r_mutex sert à protéger les accès à la donnée n_readers qui indique le nombre de lecteurs en cours de consultation de la donnée v
un verrou w_mutex sert à prévenir un flot continu de lecteurs en cas d’arrivée d’un rédacteur

A l’aide des fichiers main_readers_writers.c, readers_writers_mutexes.c et readers_writers_mutexes.h, implanter ce mécanisme et vérifier le bon fonctionnement. On pourra notamment vérifier l’absence de famine sur les scenarios suivants :

./main_readers_writers 2 2

./main_readers_writers 5 2

1.5 Exclusion mutuelle entre lecteurs et rédacteurs (1 mutex et 1 cond)

Pour cet exercice, on utilisera les fichiers alternatifs main_readers_writers_2.c, readers_writers_mutexes_2.c et readers_writers_mutexes_2.h. On propose de concevoir une autre implantation de l’exclusion mutuelle entre redacteurs et lecteurs qui satisfait les conditions précédentes.

Cette nouvelle implantation ne devra utiliser qu’un mutex et une variable conditionnelle. Pour contrôler le flux de lecteurs et de rédacteurs, on utilisera la structure rw_mutex_t décrite dans readers_writers_2.h. Elle comporte les éléments suivants :

un attribut owner qui indique la nature du thread courant utilisant le verrou (READER, WRITER, UNUSED - voir readers_writers_mutexes_2.c)
une file d’attente queue qui indique la nature des threads bloqués en attente de l’accès au verrou. Cette file d’attente sera implantée en utilisant un tampon circulaire (non protégé) déjà fourni
une variable conditionnelle guard pour bloquer les threads en attente d’accès et un mutex mutexx pour éviter les accès concurrents aux variables partagées
le compteur n_readers qui détermine le nombre de lecteurs accèdant actuellement au verrou en lecture

En quelque sorte, on peut considérer que cette implantation se rapproche de celle d’un ordonnanceur de noyau.