| Le problème du barbier: conception d'une application multi-threadée, synchronisée avec des sémaphores et des verrous (locks) à la norme POSIX 1003.1b. |
19980719 - Version 1.Nat
Quand un client arrive, celui-ci ouvre la porte du salon de coiffure. Si
aucune place n'est disponible il reste dehors (même en février). Sinon
il va s'asseoir dans une chaise libre. À l'ouverture de la porte un carillon
vénitien sonne pour réveiller notre barbier, si jamais il avait piqué un
somme. Quand le barbier se libère d'un client, celui-ci n'a pas le droit
de dormir si il reste du monde en salle. Il ouvre la porte et crie ``AU
PROCHAIN !''. À cet instant là un concours de vitesse a lieu entre chaque
client. Celui qui est le plus rapide à poser sa BD est le prochain à se
faire raser1.
Lorsque le barbier a fini de raser un client, ce dernier paye 10 francs (nous sommes toujours dans les années trente). Puis il quitte le salon. Le barbier prend le prochain client, à défaut il va se coucher... et ainsi de suite.
Alors que notre programme possédera un seul barbier, il pourra y avoir autant de clients que d'hommes sur la planète (ou du moins que de place en mémoire). Les threads clients s'empileront donc en attendant que de la place se libère dans la salle d'attente, puis que le barbier s'occupe d'eux.
| Est-ce-qu'il y a quelqu'un dans la salle d'attente ? Si oui je
m'occupe de son cas, sinon je vais me coucher;
| Quand un client est là je le fais entrer à l'abattoir;
| Je le rase;
| Je lui donne congé.
| |
Évidement, quand on arrive à la fin on re-boucle.
| Je regarde dans le salon de coiffure pour voir s'il y a de la place de
libre. Si oui je rentre, sinon j'attends;
| Quand je suis à l'intérieur je m'assieds sur une chaise (et je
prens ma BD);
| J'attends que le barbier soit libre;
| Je me lève de ma chaise (et libère donc une place) et je rentre
dans la pièce;
| Je me laisse tailler la barbe;
| Quand il a fini, je paye et je rentre chez moi.
| |
En regardant la différence de taille entre la liste d'actions du barbier et du client, on remarque que le client fait plus de choses. En fait le client doit gérer une ressource supplémentaire par rapport au barbier : la place libre dans la salle d'attente lorsqu'il se présente à l'entrée du salon.
Maintenant il faut gérer le sommeil du barbier. Il nous faut un sémaphore
bloquant le barbier quand aucun client n'est là. Il doit donc être
incrémenté à l'arrivée de chaque client et initialisé à
zéro.
Passons maintenant à la gestion du passage du client. Il faut que le
thread du barbier et celui du client aient un ``moment'' en commun quand le
rasage a lieu. Il existe une myriade de bitouilles possibles, mais
le plus simple est encore de posséder deux sémaphores : un pour
l'arrivée du client, le second pour son
départ.
Pour finir j'ai ajouté la gestion du paiement. Sans grand intérêt mais histoire de tripoter les mutex de POSIX.
Je vais présenter maintenant un tableau récapitulatif de l'évolution de chacun de ces
sémaphores pendant le passage d'un client dans ce salon de coiffure. Je suppose que le salon
est vide avant son arrivé et qu'aucun autre client n'arrive pendant qu'il est là.
Je ne décrierai pas le fonctionnement du lock, il est assez explicite.
| places | salle_vide | piece | dehors | action | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| état initial |
8 |
0 |
0 |
0 | exec(main)
|
barbier couché |
8 |
(0) |
0 |
0 | b:wait(salle_vide)
|
arrivée d'un client |
(8) |
(0) |
0 |
0 | c:wait(places)
|
le client s'asseoie |
7 |
+(0) |
0 |
0 | c:post(salle_vide)
|
le client attend |
7 |
0 |
(0) |
0 | c:wait(piece)
|
accueil du client |
7 |
0 |
+(0) |
0 | b:post(piece)
|
le client entre |
+7 |
0 |
0 |
0 | c:post(places)
|
client en rasage |
8 |
0 |
0 |
(0) | c:wait(dehors)
|
le barbier rase... |
8 |
0 |
0 |
(0) | b:sleep()
|
il libère son client |
8 |
0 |
0 |
+(0) | b:post(dehors)
| |
Les sémaphores encadrés par une paire de parenthèses signifient qu'un wait a été effectué sur cette ressource et qu'un thread est donc bloqué, en attente de la libération de cette ressource. Le + signifie qu'un post a été effectué.
| Les quatre sémaphores;
| Le lock pour la caisse;
| La valeur de cette caisse.
| |
Il possède en plus deux fonctions: proc_barbier et proc_client, respectivement les procédures du barbier et du client. Le programme principal (main) s'occupe tout d'abord d'initialiser les sémaphores et le lock. Puis il crée le thread correspondant au barbier. Celui-ci va directement se coucher vu qu'aucun client n'a encore été créé. Les threads simulant le client sont créés un par un, de façon dynamique quand l'utilisateur appuie sur la touche ``entrée''. S'il laisse son doigt enfoncé quelques secondes sur la touche il peut créér très rapidement un nombre important de clients. Les résultats de l'application sont envoyés sur la sortie standard (stdout).
Remarques d'utilisation: Sur une station rapide ce petit programme peut très rapidement faire des bêtises. Sous le système d'exploitation Linux la machine a recours à l'appel noyau clone() pour créer un nouveau thread, ce qui a pour effet de créer un nouveau processus. Lors de mes tests je me suis trouvé (après m'être endormi moi-même sur la touche ``entrée'') avec plus de 200 processus client qui attendaient mon pauvre barbier...
OBJ = barber.o LIB = -lpthread cc = gcc barber: $(OBJ) $(cc) -o barber $(OBJ) $(LIB) barber.o: clean: rm -f $(OBJ) barber core *~
/* NOM: barber.c *
* VERSION: 2 *
* AUTEUR: Nicolas Sayer *
* COMPIL: gcc *
* ARCH: POSIX 1003.1b */
#include <
stdio.h >
#include <
unistd.h >
#include <
pthread.h >
#include <
semaphore.h >
/* Taille de la salle d'attente */
#define NB_PLACES 8
/* Lock pour le porte monnaie */
pthread_mutexattr_t mutex_attr;
pthread_mutex_t money_lock;
/* Les quatres semaphores */
sem_t places;
sem_t salle_vide;
sem_t piece;
sem_t dehors;
/* Caisse du barbier */
int porte_monnaie=0;
void proc_barbier(void *ptr);
void proc_client(void *ptr);
void main(void)
{
/* Thread du barbier */
pthread_t barbier;
/* Ptr sur thread pour les clients */
pthread_t *ptr_sur_thread;
/* Init des semaphores */
sem_init(&places, 0, NB_PLACES);
sem_init(&salle_vide, 0, 0);
sem_init(&piece, 0, 0);
sem_init(&dehors, 0, 0);
/* Init du lock */
pthread_mutex_init(&money_lock, &mutex_attr);
/* On demarre le barbier */
pthread_create(&barbier, NULL, (void*)&proc_barbier, NULL);
/* Quand le user fait un retour de chariot, on lance un client */
while(1)
{
getchar();
printf("main: creation client.\n");
ptr_sur_thread=(void*)malloc(sizeof(pthread_t));
pthread_create((void*)&ptr_sur_thread, NULL, (void*)&proc_client, NULL);
}
/* Quand le barbier meurt, on exit */
pthread_join(barbier, NULL);
}
void proc_barbier(void *ptr)
{
int i;
printf("b: Ouverture du magazin.\n");
while(1)
{
sem_getvalue(&salle_vide, &i);
if(i==0)
{
pthread_mutex_lock(&money_lock);
i=porte_monnaie;
pthread_mutex_unlock(&money_lock);
printf("b: je vais me coucher, journee a %i francs... pour l'instant.\n",i );
}
sem_wait(&salle_vide);
sem_post(&piece);
printf("b: je mousse un client.\n", i);
sleep(2);
printf("b: fini.\n");
sem_post(&dehors);
}
}
void proc_client(void *ptr)
{
int i;
printf("c: J'arrive\n");
sem_getvalue(&places, &i);
printf("c: Il reste %i places de libre.\n", i);
sem_wait(&places);
printf("c: Je me pose sur une chaise (et je prend une BD).\n", i);
sem_post(&salle_vide);
sem_wait(&piece);
sem_post(&places);
printf("c: Je rentre dans la piece et me fait raser.\n");
pthread_mutex_lock(&money_lock);
porte_monnaie=porte_monnaie+10;
pthread_mutex_unlock(&money_lock);
sem_wait(&dehors);
printf("c: Je rentre chez moi, apres avoir payer.\n");
}
[sayer@hike source]$ ./barber b: Ouverture du magazin. b: je vais me coucher, journee a 0 francs... pour l'instant. main: creation client. c: J'arrive c: Il reste 8 places de libre. c: Je me pose sur une chaise (et je prend une BD). b: je mousse un client. c: Je rentre dans la piece et me fait raser. b: fini. b: je vais me coucher, journee a 10 francs... pour l'instant. c: Je rentre chez moi, apres avoir payer. main: creation client. c: J'arrive c: Il reste 8 places de libre. c: Je me pose sur une chaise (et je prend une BD). b: je mousse un client. c: Je rentre dans la piece et me fait raser. main: creation client. c: J'arrive c: Il reste 8 places de libre. c: Je me pose sur une chaise (et je prend une BD). main: creation client. c: J'arrive c: Il reste 7 places de libre. c: Je me pose sur une chaise (et je prend une BD). main: creation client. c: J'arrive c: Il reste 6 places de libre. c: Je me pose sur une chaise (et je prend une BD). main: creation client. c: J'arrive c: Il reste 5 places de libre. c: Je me pose sur une chaise (et je prend une BD). b: fini. b: je mousse un client. c: Je rentre chez moi, apres avoir payer. c: Je rentre dans la piece et me fait raser. b: fini. b: je mousse un client. c: Je rentre chez moi, apres avoir payer. c: Je rentre dans la piece et me fait raser. b: fini. b: je mousse un client. c: Je rentre chez moi, apres avoir payer. c: Je rentre dans la piece et me fait raser. b: fini. b: je mousse un client. c: Je rentre chez moi, apres avoir payer. c: Je rentre dans la piece et me fait raser. b: fini. b: je vais me coucher, journee a 60 francs... pour l'instant. c: Je rentre chez moi, apres avoir payer.
La raison pour laquelle j'ai apprécié tout particulièrement ce TP est que j'ai pu l'étudier et le réaliser dans mon environnement fétiche, avec mes outils préférés (gcc, gdb, LATEX)...
1 situation peu réelle, mais vous avez du remarquer que ce salon de coiffure des années trente n'est pas commun.
2 Le lock sur la caisse est inutile car le client paye en fin de rasage et le barbier est seul et ne ne s'occupe pas simultanément de plusieurs clients. Il ne consulte jamais le montant de ses recettes quand un client est là.