Introduction FAQ TD 1 TD 2 TD 3 TD 4 TD 5 TD 6 TD 7 TD 8
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;
Essayez de répondre aux questions suivantes sur cet algorithme:
Quel est le rôle de la variable number[i]
? Quelle est sa valeur:
Supposons que deux threads t1
et t2
seulement veulent entrer dans la section critique: lequel entrera le
premier dans la section critique:
number[t1] < number[t2]
? number[t1] = number[t2]
? 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 ?
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.
Pourquoi ce programme nécessite t'il l'utilisation d'un algorithme d'exclusion mutuelle ? Quel pourrait être le résultat sans section critique ?
Quel attribut faut-il donner aux variables pour qu'elles soient vraiment partagées ? Que se passe t'il sans cet attribut ?
Commencez par écrire un programme qui crée cinq threads, chacun affichant juste son numéro, puis attend leur terminaison.
Implantez le programme avec un sémaphore pour créer la section critique.
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
.
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
.
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.
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
):
CLIENT_INIT
: la fonction est appelée une fois au
début de l'exécution avec cet argument pour ouvrir les sémaphores
(créés par le serveur). CLIENT_WAIT
: la fonction est appelée avant
d'écrire dans la mémoire partagée. Le client peut être bloqué si la
mémoire est en cours d'écriture par un autre client. CLIENT_DONE
: la fonction est appelée après
l'écriture dans la mémoire partagée. Le client doit libéré le
serveur de son attente pour qu'il puisse lire le message. CLIENT_END
: la fonction est appelée une fois à la
fin de l'exécution avec cet argument pour fermer les sémaphores. 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
.
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
):
SERVER_INIT
: la fonction est appelée une fois au
début de l'exécution avec cet argument pour créer les sémaphores et
leur donner une valeur initiale. SERVER_WAIT
: la fonction est appelée avant de lire
dans la mémoire partagée. Le server reste bloqué tant qu'aucun
client n'a écrit dans la mémoire. La fonction retourne 0 si
l'attente a été interrompue, ou 1 si le sémaphore a été débloqué. SERVER_DONE
: la fonction est appelée après la
lecture du message depuis la mémoire partagée. La mémoire doit alors
pouvoir être accédée en écriture par un client qui voudrait
transmettre un message. SERVER_END
: la fonction est appelée une fois à la
fin de l'exécution avec cet argument pour supprimer les sémaphores. 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 ?