TD 1 : Généralités sur la programmation concurrente
Exercice 1
Objectif : Appréhender la notion de programmation concurrente
On suppose que deux processus utilisent une zone de mémoire partagée comportant 10 cases,
numérotées de 0 à 9, contenant initialement 10 '$'. Le premier écrit dans la zone de mémoire
partagée et le second lit le contenu de la zone mémoire de la façon suivante :
Code processus 1 Code processus 2
for (char c='a';c<= 'z';c++){ for (int i=0 ; i<10 ;i++){
for(int i=0 ; i<10 ;i++){ /*affiche le contenu de la i-ème
/*-- la i-ème case de la zone de mémoire case de la zone de mémoire
partagée reçoit le caractère contenu dans c */ partagée */
T[i]=c ; fprintf(stdout,"%c",T[i]);
}end loop; }
}end loop;
Le système fonctionne en mode multi processus et est ordonnancé par un tourniquet dont on ne
connaît pas la valeur du quantum. On ne connaît pas non plus les durées d'exécution de chacune
des instructions effectuées ni les surcharges liées à l'exécution de primitives SE, par exemple
pour gérer la mémoire.
Le second processus peut-il afficher la séquence bbbaaaaaaa ? la séquence aaaaaaabbb ? la
séquence abcdefghij ? la séquence cccaaabbbb ? Si oui, décrivez le déroulement de l'exécution
qui permet d'aboutir à l'affichage désiré, et si non, expliquez pourquoi ça n'est pas possible.
Exercice 2
Objectif : Modéliser l’utilisation des ressources et détecter un interblocage
On considère un système constitué de 9 processus A, … I et comportant 7 ressources R, … X.
L'attribution des ressources est la suivante :
Le processus A détient R et demande S.
Le processus B ne détient pas de ressource et demande T.
Le processus C ne détient pas de ressource et demande S.
Le processus D détient U et demande S et T.
Le processus E détient T et demande V.
Le processus F détient W et demande S.
Le processus G détient V et demande U.
Le processus H détient X et demande U.
Le processus I ne détient pas de ressource et demande X.
Construisez le graphe d'allocation de ressources correspondant. Y a-t-il interblocage, et si oui,
quels sont les processus directement concernés ? Cela a-t-il une incidence sur les autres ?
Exercice 3
Objectif : Modéliser les ressources multi-instances
On considère un système de 4 processus P1, P2, P3 et P4, possédant deux ressources multi-
instances R1 et R2.
Les besoins des processus sont les suivants :
P1 : 2 instances de R1 et 1 de R2
P2 : 2 instances de R1 et 2 de R2
P3 : 3 instances de R1 et 3 de R2
P4 : 3 instances de R1 et 1 de R2
Existe-t-il des situations d'interblocage :
a – S'il y a 7 instances de R1 et 5 de R2 ?
b – S'il y a 9 instances de R1 et 6 de R2 ?
Exercice 4
Objectif : Analyse le code pour déterminer si un programme concurrent est correct
Soient trois processus concurrents P1, P2 et P3 qui partagent les variables n et out. Pour
contrôler les accès aux variables partagées, un programmeur propose les codes suivants :
1) Cette proposition est-elle correcte ? Si non, pourquoi ?
2) Proposer une solution correcte.
Semaphore m1=1
Semaphore m2=1
Code processus P1 Code processus P2 Code processus P3
P(m1) P(m2) P(m1)
P(m2) out=out-1 n=n+1
out=out+1 V(m2) V(m1)
n=n-1
V(m2)
V(m1)
Exercice 5
Objectif : Utiliser les sémaphores
On considère 6 blocs d'instructions, S1 à S6. Un graphe de préséance présente les contraintes
sur l'ordre d'exécution des instructions. Par exemple, la flèche allant de S1 vers S2 indique que
l'instruction S2 doit nécessairement être exécutée après S1. On place chaque bloc d'instruction
dans un processus distinct P1 à P6. Utilisez des sémaphores pour synchroniser les processus de
manière à respecter les contraintes du graphe de préséance ci-dessous :
Exercice 6
Objectif : Utiliser les sémaphores
Deux villes A et B sont reliées par une seule voie de chemin de fer. Les trains peuvent circuler
dans le même sens de A vers B ou de B vers A. Cependant, ils ne peuvent pas circuler dans les
sens opposés.
On considère deux classes de processus : les trains allant de A vers B (Train AversB) et les trains
allant de B vers A (Train BversA). Leur comportement se définit comme suit :
Train AversB Train BversA
Demande d’accès à la voie par A Demande d’accès à la voie par B
Circulation sur la voie de A vers B Circulation sur la voie de B vers A
Sortie de la voie par B Sortie de la voie par A
1) Parmi les modèles étudiés en cours (producteur/consommateur, lecteur/rédacteur, rendez-
vous, …), à quel modèle ce problème correspond-il ?
2) En utilisant les sémaphores (opérations P et V), traduire les demandes d’accès et de sorties,
de façon à ce que les processus respectent les règles de circulation sur la voie unique.
Exercice 7
Objectif : Analyse le code pour déterminer si un programme concurrent est correct
Considérez le programme suivant.
1- Listez les paires de sémaphores que chaque processus cherche à obtenir et montrez qu’il peut
avoir interblocage.
2- On cherche à éviter les interblocages en ordonnant les réservations selon l’ordre a < b < c.
Discutez les réservations de chaque processus selon ce critère.
3- Proposez une modification pour éviter l’interblocage.
Conditions initiales Processus 1 Processus 2 Processus 3
Semaphore a=1 P(a) P(c) P(c)
Semaphore b=1 P(b) P(b) V(c)
Semaphore c=1 V(b) V(b) P(b)
P(c) V(c) P(a)
V(c) P(a) V(a)
V(a) V(a) V(b)
Exercice 8
Objectif : Analyse le code pour déterminer si un programme concurrent est correct
Considérez le programme suivant. Est-ce que les processus peuvent entrer en interblocage ?
Pourquoi ?
Conditions initiales Processus 1 Processus 2
Semaphore a=1 P(a) P(c)
Semaphore b=1 P(b) P(b)
Semaphore c=1 V(b) V(b)
P(c) V(c)
V(c)
V(a)
Exercice 9
Objectif : Utiliser les sémaphores
Problème du barbier. La boutique du barbier est composée d’une salle d’attente contenant n
chaises et du salon où se trouve la chaise du barbier. Lorsque le barbier a fini de raser un client, il
fait entrer le client suivant dans le salon. Si la salle d’attente est vide, le barbier s’y installe pour
dormir. Si un client trouve le barbier endormi, il le réveille. Si non, il s’installe dans la salle
d’attente s’il reste de la place (et rentre chez lui sinon).
1- Ecrivez le code du client et du barbier sans vous préoccuper de synchronisation, mais
simplement des opérations que veulent réaliser les processus. En particulier, ignorez pour l’instant
que le barbier dort parfois.
2- Il s’agit maintenant d’ajouter les synchronisations nécessaires au programme écrit à la question
précédente. Le premier problème `a résoudre est une condition de compétition entre les clients
lorsqu’ils rentrent dans la salle d’attente. Corrigez ce problème.
3- Assurez-vous ensuite que le barbier ne commence pas à couper les cheveux tant que le client
n’est pas prêt.
4- Enfin, assurez-vous ensuite que le client ne s’assoit pas sur le siège tant que le barbier n’est
pas prêt.
Exercice 10
Problème des philosophes. Cinq philosophes, réunis pour philosopher, ont au moment du repas
un problème pratique à résoudre. En effet, le repas est composé de spaghetti qui, selon la
coutume de ces philosophes, se mangent avec deux fourchettes. Or, la table n’est dressée
qu’avec une seule fourchette par couvert. Les philosophes décident d’adopter le rituel suivant :
— Chaque philosophe prend une place à table.
— Chaque philosophe qui mange utilise la fourchette à sa droite et celle à sa gauche (pas celle
d’en face).
— A tout instant, chaque philosophe est dans l’un des états suivants :
— il mange avec deux fourchettes ;
— il a faim, et attend la fourchette de droite, celle de gauche ou les deux ;
— il pense, et n’utilise pas de fourchette.
— Initialement, tous les philosophes pensent.
— Un philosophe qui mange s’arrête en un temps borné.
. Question 1: Proposez une solution à ce problème. Vous pourrez utiliser l’une des méthodes vues
plus haut pour éviter l’interblocage.
. Question 2: On ajoute maintenant l’hypothèse suivante au problème :
— Les philosophes sont droitiers : ils ne prennent pas de fourchette à gauche sans avoir d’abord
celle de droite. Proposez une nouvelle solution tenant compte de cette nouvelle hypothèse. Vous
serez amené à utiliser l’autre méthode d’évitement des interblocages vue en cours.
