TD 6 : Synchronisation entre Processus

Introduction      FAQ   TD 1   TD 2   TD 3   TD 4   TD 5   TD 6   TD 7   TD 8

1.  Exclusion mutuelle: l'algorithme de la Boulangerie (Lamport)

Voici l'algorithme dit de la Boulangerie (Bakery en anglais) inventé par L. Lamport pour implanter une section critique entre plusieurs threads. Le thread numéro i exécute le code suivante:

 1 var choosing: shared array[0..n-1] of boolean; (* false at the beginning *)
 2     number: shared array[0..n-1] of integer; (* 0 at the beginning *)

 3 repeat
 4     choosing[i] := true;
 5     number[i] := max(number[0],number[1],...,number[n-1]) + 1;
 6     choosing[i] := false;
 7     for j := 0 to n-1 do begin
 8         while choosing[j] do (* nothing *);
 9         while number[j] <> 0 and
10                    (number[j], j) < (number[i],i) do
11              (* nothing *);
12    end;
13    (* BEGIN critical section *)
      ...
14    number[i] := 0; (* END critical section *)
15    ...
16    until false;

1.1.  Analyse

Essayez de répondre aux questions suivantes sur cet algorithme:

1.1.1.  Question 1

Quel est le rôle de la variable number[i] ? Quelle est sa valeur:

1.1.2.  Question 2

Supposons que deux threads t1 et t2 seulement veulent entrer dans la section critique: lequel entrera le premier dans la section critique:

1.1.3.  Question 3

Supposez que l'on supprime le tableau partagé choosing: pouvez-vous trouver un exemple d'exécution (avec deux threads) où les deux threads exécutent la section critique en même temps ?

1.2.  Implantation

Implantez cet algorithme dans le cadre suivant: cinq threads doivent incrémenter (ajouter 1) chacun 1000 fois une variable partagée. Affichez la valeur de la variable partagée à la fin. Répondez d'abord aux questions suivantes:

Vous pouvez utiliser le squelette suivant.

1.2.1.  Question 1

Pourquoi ce programme nécessite t'il l'utilisation d'un algorithme d'exclusion mutuelle ? Quel pourrait être le résultat sans section critique ?

1.2.2.  Question 2

Quel attribut faut-il donner aux variables pour qu'elles soient vraiment partagées ? Que se passe t'il sans cet attribut ?

1.2.3.  Question 3

Commencez par écrire un programme qui crée cinq threads, chacun affichant juste son numéro, puis attend leur terminaison.

1.2.4.  Question 4

Implantez le programme avec un sémaphore pour créer la section critique.

1.2.5.  Question 5

Implantez maintenant l'algorithme de la Boulangerie. Fonctionne t'il correctement ? Tentez d'expliquer, à partir de vos connaissances sur les ordinateurs actuels, pourquoi vous n'obtenez pas le résultat espéré.

Solution: bakery.c , à compiler avec gcc -o bakery bakery.c -lrt.

2.  Mise à jour du projet

N'oubliez pas de mettre à jour votre archive en téléchargeant l'archive forum.tar.gz et en y insérant vos fichiers (préalablement copiés) client.c, server.c et common.c.

3.  Sémaphores

Pour se synchroniser, le client et le serveur utilisent actuellement des sémaphores partagés: le serveur crée au démarrage deux sémaphores /forum_[login]_sem1 et /forum_[login]_sem2, où [login] est le login de l'utilisateur, obtenu par getlogin, LOGNAME ou USER. Le premier est bloqué tandis que le second est ouvert au démarrage. Le serveur commence alors à attendre sur le premier.

Lorsqu'un client veut transmettre un message au serveur, il commence par prendre le second sémaphore. Lorsque celui-ci est pris, il sait alors qu'il est le seul à pouvoir écrire dans la mémoire partagée. L'écriture du message effectuée (fonction client_shm_write du TD précédent), le client relache le premier sémaphore: la mémoire reste protégée en écriture, mais cette action a pour effet de libérer le serveur. Celui-ci lit dans la mémoire le contenu du message (fonction server_shm_read du TD précédent), puis relache le second sémaphore, ce qui va permettre à un autre client d'écrire un nouveau message dans la mémoire partagée.

3.1.  Dans le client (fonction client_sem)

Le client effectue ce travail au moyen d'une fonction client_sem(action):

extern void client_sem(int action);

qui manipule les deux sémaphores partagés: l'argument action peut prendre les valeurs suivantes (déinies dans client.h):

Définissez votre propre fonction client_sem pour votre client. Vous pouvez utiliser l'option -v du client et du serveur pour les forcer à afficher des messages d'information, qui pourront être utiles pour trouver de potentielles erreurs. En particulier, comment forcer l'appel client_sem(CLIENT_END) à la fin de votre programme ?

Appels systèmes nouveaux: sem_open, sem_close, sem_wait et sem_post.

3.2.  Dans le serveur (fonction server_sem)

Le serveur effectue le travail réciproque au moyen d'une fonction server_sem(action):

extern int server_sem(int action);

qui manipule les deux sémaphores partagés: l'argument action peut prendre les valeurs suivantes (déinies dans server.h):

Définissez votre propre fonction server_sem pour votre server. Vous pouvez utiliser l'option -v du server et du serveur pour les forcer à afficher des messages d'information, qui pourront être utiles pour trouver de potentielles erreurs. En particulier, comment forcer l'appel server_sem(SERVER_END) à la fin de votre programme ?