Picture Omitted
Projet de Programmation Système:
Sémaphores et synchronisation de threads.

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.

Nicolas Sayer

19980719 - Version 1.Nat


Picture Omitted

1  Introduction.

Désolé, ce n'est pas une habitude de ma part de transgresser les règles annoncées (contrairement à ce que pense mon père), mais je me voyais assez difficilement développer ce projet sous MS-Windows, n'ayant pas ce système chez moi. De plus je dois avouer que je ne suis pas trop fana du monde de Bill. J'ai donc écris et testé le programme sous UNIX en respect des normes POSIX sur les threads. Le programme compile et fonctionne sous Linux et Solaris 2.5.

2  Description détaillée du problème.

Nous tenterons de rédiger un programme simulant l'activité d'un salon de coiffure dans lequel on rase les barbes. Un seul barbier y travaille. Le salon est décomposé en une salle d'attente possédant un nombre fixe de chaises et une table avec des bandes dessinées, ainsi qu'une salle de travail où le barbier rase un client. Accessoirement cette salle de travail lui sert de chambre à coucher quand il n'a pas de client, car notre barbier a la méchante habitude de faire la fête toute la nuit, il rattrape donc ses heures de sommeil perdues lorsque le salon est calme.

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.

3  Analyse.

3.1  Organisation des threads.

Notre programme devra être décomposé en deux types de threads. D'un côté il y aura le barbier, représenté par un thread unique bouclant sans cesse pour voir si un client attend, s'occuper de lui si nécessaire ou alors aller se coucher. De l'autre côté il y aura un thread par client, qui simulera le client ``physique''. Il essayera de rentrer dans la boutique, ira s'asseoir s'il le peut, se fera raser, et disparaîtra.

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.

3.2  Que fait le barbier ?

Le thread symbolisant la barbier sera donc unique. Il sera démarr\'s au lancement du programme, avant tout client, et bouclera sur lui-même pour l'éternité.
Voici ce que notre barbier passera sa vie à faire :

Évidement, quand on arrive à la fin on re-boucle.

3.3  Que fait le client ?

Voici les actions que réalisera le thread symbolisant chaque client. S'il y a plusieurs clients, des threads identiques seront en concurrence :

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.

4  Les ressources.

Lors de la mise au point du programme je me suis trouvé devant deux façons de gérer les ressources. Soit j'optimise au maximum et j'ai un sémaphore et un lock en moins2, soit j'essaye de faire ``propre''. J'ai préféré la seconde solution car elle est beaucoup plus claire. Les primitives des sémaphores et des locks sous UNIX étant implantés au niveau du noyau, la différence en temps processeur est quasi-nulle.

4.1  Les nécessités.

Tout d'abord il est clair qu'il va falloir un sémaphore sur le nombre de places de libre dans la salle d'attente. Il limitera le nombre client pouvant se trouver dans la salle simultanément. Quand un client surnuméraire se présentera le thread se mettra en attente de la libération de la ressource (la chaise).

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.

4.2  Description détaillé.

Voici la façon dont seront utilisés les quatre sémaphores de notre barbier virtuel:

places
Nombre de places disponible dans la salle d'attente du salon. Lors de l'arrivée d'un client, celui-ci réalise un wait sur ce sémaphore. Si le nombre de place libres est nul à son arrivée, il attendra qu'un client libère une chaise. Le client réalise un post quand il réussit à rentrer dans la pièce du barbier (donc qu'il se lève de la chaise).

salle_vide
Le sémaphore salle_vide correspond à une valeur égale au nombre de clients se trouvant dans la salle d'attente. elle vaut 0 quand cette dernière ne compte aucun client. Le barbier réalise un wait sur ce sémaphore et se bloque (va se coucher) quand la salle est vide.

piece
Ce sémaphore est initialisé à 0. Tout client arrivant dans la salle d'attente se met en attente de la libération de cette ressource. Il est libéré par le barbier quand celui-ci est prêt à recevoir un client dans sa pièce de travail.

dehors
Le but de ce sémaphore est très proche de celui du précédent. Le client effectue un wait dessus et c'est le barbier qui libérera cette ressource par un post quand il a fini de raser le client. Alors que le sémaphore précédant synchronisait le début du rasage, celui-ci synchronise la fin.

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) 0c:wait(piece)
accueil du client 7 0 +(0) 0b: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é.

5  Organisation du programme.

Notre programme: ``le barbier virtuel'' possède trois groupes de variables globales:

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

6  Code source et exemple d'utilisation.

6.1  Le fichier: Makefile

Ce fichier contient les directives de compilation et de linkage pour créér le fichier exécutable.

OBJ = barber.o
LIB = -lpthread

cc = gcc

barber: $(OBJ)
  $(cc) -o barber $(OBJ) $(LIB)

barber.o:


clean:
  rm -f $(OBJ) barber core *~

6.2  Le fichier: barber.c

Voici le code source du simulateur de barbier. Il est écrit en C ANSI en respectant la norme POSIX actuelle sur les threads et les sémaphores.

/* 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");
}

6.3  Exemple.

Voici les messages sortie à l'écran lors de l'execution du barbier et la création de quelques clients:
[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.

7  Conclusion.

J'ai du passer sûrement quelques dizaines d'heures sur les threads et les sémaphores pendant cette dernière session, mais j'avoue que c'était bien plus pour m'amuser que pour réaliser ce rapport. Il est en effet très intéressant de voir les différents choix qu'on pu faire Sun, Microsoft, ou Linux pour gérer les threads. J'ai ainsi pu apprécier la très grande différence en temps d'exécution entre une machine mono-processeur et une machine multi-processeur.
Il y aurait évidemment beaucoup d'extentions possible à faire à ce programme. Il serait intéressant que les clients soient traiter dans leur ordre d'arrivée, ou que le salon soit animé par plusieurs barbiers.

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)...


Footnotes:

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à.


File translated from TEX by TTH, version 1.96.
On 4 Jan 1999, 02:05.