Problème des
philosophes avec les
sémaphores et
moniteurs
1
Dîner des Philosophes
Cinq philosophes se trouvent autour d'une table ; Chacun des
philosophes a devant lui un plat de spaghetti ; A gauche de
chaque assiette se trouve une fourchette
Un philosophe n'a que trois états possibles :
1. penser pendant un temps indéterminé ;
2. A faim (pendant un temps déterminé et fini sinon il y a
famine) ;
3. manger pendant un temps déterminé et fini.
Des contraintes extérieures s'imposent à cette situation :
• Quand un philosophe a faim, il va se mettre dans l'état « a faim» et attendre que les
fourchettes soient libres ;
• Pour manger, un philosophe a besoin de deux fourchettes : celle qui se trouve à sa
droite, et celle qui se trouve à sa gauche ;
• Si un philosophe n'arrive pas à s'emparer d'une fourchette, il reste affamé pendant un
temps déterminé, en attendant de renouveler sa tentative.
Le problème consiste à trouver un ordonnancement des philosophes tel qu'ils puissent tous
manger, chacun à leur tour, sans provoquer d’interblocage!
3
Il s'agit donc d'écrire les procédures prendre_fourchette et poser_fourchette.
4
Première solution :
5
Première solution :
6
Première solution :
On prend un sémaphore par fourchette
Chaque sémaphore est initialisé à 1
sem fourch[ N ] = {1,........1}
Cette implémentation pose un problème d'interblocage dans le cas où les N
philosophes décident de manger donc d'appliquer la procédure prendre fourchette.
En effet, tous les philosophes détiennent la fourchette qui est à leur droite et
attendent que celle qui est a leur gauche se libère.
7
Deuxième solution :
On se centre ici sur les philosophes. Un sémaphore est attribué à chaque philosophe.
Etat = { PENSE , MANGE , A_FAIM}
Un philosophe qui veut prendre les fourchettes (donc manger) déclare qu'il a faim. Si
l'un de ses deux voisins est en train de manger, il ne peut donc pas prendre les deux
fourchettes pour l'instant et donc se met en attente.
Si les deus philosophes a coté ne mangent pas alors il peut prendre les deux
fourchettes et déclarer qu'il mange. Quand le philosophe a fini de manger, il déclare
donc qu’il pense et regarde si ses deux voisins qui forcément ne pouvaient pas manger,
en ont dès lors l'opportunité. Si c'est le cas il les réveille.
sem philo_prive [ N ]
Etat Etat_Philo[ N ] = { PENSE, …......., PENSE}
sem mutex = 1 //mutex.c = 1 pour que l'écriture dans le tableau Etat_Philo se
//fasse en exclusion mutuelle
8
9 En utilisant les moniteurs
Déclarons les variables suivantes :
• Etat : Tableau[0..4] de (Faim, Pense, Mange)
• Self : Tableau[0..4] de Condition
La solution à proposer doit garantir les règles suivantes :
• Le philosophe i ne peut fixer la variable etat[i] à mange que si ses deux voisins
(i-1 mod N) et (i+1 mod N) ne sont pas en train de manger.
• Le philosophe i peut se retarder quand il a faim mais il est incapable d’obtenir
les baguettes dont il a besoin.
En utilisant une instance dp du moniteur Diner_Philosophe, le code d’un
processus philosophe devient :
Processus Philosophe(i)
Début
Repeat
Penser() ;
Dp.prendre_Baguette(i)
Manger() ;
Dp.Poser_Baguette(i) ;
Until False;
Fin.
10
Type Diner_Philosophe= Monitor
Const N=….;
Var Etat : Array[0..N-1] of (Pense, Faim, Mange) ;
Self : Array(0..N-] of Condition ;
Procedure Prendre_Baguette(i : 0..N-1)
Begin
Etat[i] :=Faim ;
Test(i) ;
If Etat[i]<>Mange Then Self[i].attendre() ;
End ;
Procedure Poser_Baguette(i : 0..N-1)
Begin
Etat[i] :=Pense ;
Test(i-1 mod N) ;
Test(i+1 mod N)
End ;
Procedure Test(i : 0..N-1)
Begin
If Etat[i-1 mod N]<>mange and Etat[i]=Faim and Etat[i+1 mod N]<>Mange
Then Begin
Etat[i] :=Mange ;
Self[i] .signaler();
End
End ;
Begin
For i=0 to N-1 do Etat[i] :=Pense
End.
PROBLÈME
DES LECTEURS
ET
DES RÉDACTEURS
1
PROBLÈME DES LECTEURSET DES RÉDACTEURS
Dans le problème des lecteurs et des rédacteurs nous considérons deux classes de
processus: les processus lecteurs et les processus rédacteurs. Les processus lecteurs
désirent lire des données (par exemple un fichier): les processus rédacteurs désirent
modifier ces données. Une solution correcte de ce problème devra assurer l'exclusion
mutuelle entre les rédacteurs (pas d'écriture simultanée pour éviter un risque
d'incohérence des données) et l'exclusion mutuelle entre les lecteurs et les rédacteurs (pas
de lecture pendant une écriture, pour éviter de lire des données dans un état incohérent).
Les lecteurs, en l'absence des rédacteurs, doivent toutefois pouvoir accéder
simultanément aux données.
Présenté ainsi, le problème n'est pas encore entièrement spécifié. Plaçons-nous par
exemple à un moment ou une lecture est en cours (par un processus I1). Arrive à cet
instant un rédacteur r1 puis un peu plus tard un deuxième lecteur l2. Si nous voulons
donner la priorité aux lecteurs, il faut autoriser l2 à lire: si nous voulons donner la priorité
aux rédacteurs, l2 attendra et ne pourra accéder aux données qu'après le rédacteur r1. En
fait il y a trois cas à distinguer:
1)- priorité aux lecteurs
2)- priorité aux rédacteurs
2)- même priorité aux lecteurs et aux rédacteurs (c'est-à-dire accès aux données selon 2
l'ordre d'arrivée des processus).
Considérons par exemple, durant une écriture, l'ordre d'arrivée suivant (li désigne un lecteur, ri
un rédacteur) : Il, l2, r1 l3, r2. Lorsque l'écriture se termine, l'accès aux données se fait selon
l'ordre suivant:
1)- priorité aux lecteurs: I1, l2, l3; puis r1; puis r2;
2)- priorité aux rédacteurs: r1; puis r2; puis I1, l2, l2;
3)- priorité égale: I1, l2; puis r1; puis l3; puis r2.
Considérons une procédure p et introduisons la notation suivante:
#act(p) : pour désigner le nombre de processus en cours d'exécution de la procédure p; #att(p)
: pour désigner le nombre de processus en attente de pouvoir exécuter la procédure p.
Dans notre problème, la procédure p sera soit une procédure écrire, soit une procédure lire.
La formulation la plus simple du problème des lecteurs et des rédacteurs est alors la suivante:
a)- lecture possible lorsque #act( écrire)= 0
b)- écriture possible lorsque #act( écrire)= 0 et #act(lire) = 0
1
3
La priorité aux lecteurs s'exprime ainsi:
a)- lecture possible lorsque #act( écrire)= 0
b)- écriture possible lorsque #act( écrire)= 0 et #act(lire) = 0 et #att(lire) = 0
La priorité aux rédacteurs s'exprime de la manière suivante:
a)- lecture possible lorsque #act( écrire)= 0 et #att(écrire) = 0
b)- écriture possible lorsque #act( écrire)= 0 et #act(lire) = 0
Le formalisme, tel qu'il est présenté, ne fait pas intervenir l'ordre d'arrivée des processus et ne
permet donc pas d'exprimer la variante où l'on donne même priorité aux lecteurs et aux rédacteurs.
1
4
Les Sémaphores : Priorité égale entre lecteurs et rédacteurs
Essayons maintenant d'utiliser les sémaphores pour résoudre le problème dans le cas d'une
priorité égale entre lecteurs et rédacteurs (la solution avec priorité aux lecteurs n'est pas plus
compliquée à exprimer; la solution avec priorité aux rédacteurs constitue quant à elle un petit
casse-tête). Voici une première esquisse de la solution dans le cas de priorités égales:
Le sémaphore lr est utilisé par les lecteurs et les rédacteurs. Comme la liste d'attente
d'un sémaphore est gérée en queue, l'ordre d'arrivée des processus sera l'ordre dans
lequel processus accéderont aux données: lecteurs et rédacteurs ont donc même
priorité. Cette première esquisse ne réalise toutefois que les conditions:
a)- lecture lorsque #act( écrire)= 0 5
b)- écriture lorsque #act( écrire)= 0
Il faut encore empêcher aux rédacteurs d'écrire lorsqu'une lecture est en cours. Nous
ajoutons donc un sémaphore r devant lequel les rédacteurs attendront si une lecture
est en cours, Il faut remarquer sur la figure ci-dessous l'exécution conditionnelle de P(r)
avant la lecture (ligne 9) et l'exécution conditionnelle de V(r) après la lecture (ligne 13):
c'est au premier lecteur débutant la lecture d'empêcher l'accès aux rédacteurs et c'est
au dernier lecteur finissant de lire d'autoriser l'accès aux rédacteurs.
16
Cette version est toutefois encore imparfaite: la variable nb_lecteurs est une ressource
critique! Il faut en protéger l'accès par un sémaphore mutex. La version finale de la
solution est donnée sur la figure ci-dessous.
Le sémaphore lr bloque tous les
lecteurs nouveaux dès qu'un
rédacteur est arrivé.
Le sémaphore r bloque toute écriture
tant que les lectures ne sont pas
finies ; il y a au plus un rédacteur
bloqué dans la file associée à r. Dès
qu'un lecteur passe ou est réveillé, il
incrémente le compteur des lecteurs,
bloque éventuellement la ressource
et réveille le processus suivant de la
file associée à r. L'ordre P(lr) P(r) évite
l'étreinte fatale ; on peut aussi faire
V(lr) puis V(r). L'ordre FIFO est assuré
si les files associées aux sémaphores
sont gérées suivant ce principe.
17
Les Sémaphores : Priorité aux lecteurs
Le seul cas d'attente d'un lecteur se produit quand un rédacteur écrit dans le fichier ;
un rédacteur ne peut accéder au fichier que si aucun lecteur n'est en attente ou en
cours de lecture.
r est un sémaphore d'exclusion mutuelle pour tous les rédacteurs. Il sert également au
premier lecteur qui occupe le fichier et au dernier qui le libère. mutex1 est un
sémaphore d'exclusion mutuelle pour les lecteurs uniquement, il protège la variable nl.
Si un lecteur est bloqué par r, tous les autres le seront par mutex1. mutex2 est un
sémaphore d'exclusion mutuelle pour les rédacteurs uniquement. Il assure la priorité
des lecteurs sur les rédacteurs car il empêche plusieurs rédacteurs de se bloquer sur r.
18
Les Sémaphores : Priorité aux rédacteurs
Un algorithme basé sur une priorité aux rédacteurs doit résoudre l’accès à la ressource,
en respectant les règles suivantes :
1)- Un lecteur peut accéder à la ressource si :
le nombre de rédacteurs en cours d’écriture vaut 0
ET
le nombre de rédacteurs en attente d’écriture vaut également 0
2)- Un rédacteur peut accéder à la ressource si :
le nombre de rédacteurs en cours d’écriture vaut 0
ET
le nombre de lecteurs en cours de lecture vaut également 0
Dans ce cas, à l’instar des lecteurs dans le cas d’une priorité les avantageant, les
rédacteurs pourront se coaliser pour empêcher les lecteurs d’accéder à la ressource.
19
Pour cet algorithme, nous aurons besoin d’une variable comptant le nombre de lectures
en cours, nl, ainsi qu’une comptant le nombre de rédacteurs en attente d’écriture ou en
cours d’écriture, nr.
Pour garantir l’accès concurrent correct, nous devons également exploiter 5 sémaphores :
a)- mutexL : qui permet de bloquer les lecteurs pendant que des écritures sont en cours.
b)- mutexR: qui permet de bloquer les rédacteurs pendant que des écritures ou des
lectures sont en cours.
c)- r : qui permet au premier lecteur qui accède la ressource de bloquer les potentiels
rédacteurs.
d)- l : qui permet au premier rédacteur arrivé de bloquer les potentiels futurs lecteurs.
e)- mutex : qui est en charge de protéger l’accès à la variable nl.
L’algorithme suivant présente une solution avec priorité aux rédacteurs, basée sur ces
cinq sémaphores.
20
21
Moniteur
Soit fich un moniteur chargé d’assurer le respect de ces contraintes. Nous imposons la
forme suivante aux accès au fichier :
Lecteur rédacteur
fich.début_lire() ; fich.début_écrire() ;
<accès en lecture> <accès en ecriture>
fich.fin_lire() ; fich.fin_écrire() ;
les procédure début_lire,…. ;fin_écrire doivent assurer le respect des contraintes
exprimées ci-dessus.
22
Moniteur : priorité aux lecteurs
Nous définissons les variables d’état suivantes :
ecr : une écriture est en cours (booléen)
nl : nombre de lecteurs en attente ou en cours de lecture.
Les conditions de franchissement s’expriment alors ainsi :
aut(lecture) : non(ecr) : pas d’écriture en cours
aut(écriture) : non(ecr) et non(lecr) et nl=0 (ni écriture ni lecture en cours, pas
de lecture en attente)
23
24
25
26
Moniteur : priorité aux rédacteurs
27
Moniteur : priorité aux rédacteurs
28
Moniteur :
priorité aux
rédacteurs
29
Exercice 14 :
Dans une ville tranquille, un coiffeur possède un petit salon ayant une porte d’entrée, une porte de
sortie, un fauteuil de coiffure et quelques chaises. Les clients arrivent par la porte d’entrée et
sortent par la porte de sortie après avoir eu leur coupe de cheveux. Comme le salon est petit,
uniquement le client sur le fauteuil de coiffure peut être servi à un moment donné par le coiffeur. Le
coiffeur passe sa vie entre dormir et servir ses clients. Quand il n’a aucun client, le coiffeur dort dans
le fauteuil. Quand un client arrive et trouve le coiffeur endormi, il le réveille, s’assoit dans le fauteuil
et s’endort pendant que le coiffeur lui coupe les cheveux. Si un client arrive et le coiffeur est occupé,
le client s’endort dans une chaise libre. Après avoir fini une coupe, le coiffeur ouvre la porte de
sortie et attend que le client coiffé quitte le salon. Ensuite, s’il y a des clients en attente, le coiffeur
réveille un et attend qu’il occupe le fauteuil de coiffure. S’il n’y a aucun client, le coiffeur s’endort.
30
INITIALISATION
C = sem(0) /* clients dans la salle d'attente */ Semaphore
B = sem(0) /* barbiers prêts a couper */
mutex = sem(1) /* pour l'exclusion mutuelle */
int n = Nbre de CHAISES
BARBIER CLIENT
Debut
Debut
P(mutex);
repeat
si (n<N) alors
P(B);
debut
<coupe cheveux>;
n= n +1;
Until false;
si n>1 alors debut
Fin
V(mutex);
P(C);
fin
sinon V(mutex);
V(B);
<se faire couper les cheveux>;
P(mutex);
n=n-1;
Si n>0 alors V(C);
V(mutex);
Fin 17
sinon V(mutex);
Fin
Salon_coiffure : moniteur
Const N=5; moniteur
Var nb_client : 0..N;
Coiffeur, Client : Condition;
Procedure Suiv() BARBIER
Debut Debut
si Nb_client=0 alors [Link]()
Salon_coiffure.Suiv();
sinon [Link]();
<coupe cheveux>;
Fin
Procedure terminer()
Salon_coiffure.terminer();
Debut Fin
Nb_client = nb_client – 1;
Fin;
Procedure Entree(var plein : booleen)
Debut
si nb_client = N alors plein = true CLIENT
sinon Var plein : booleen;
Debut Debut
plein = false; Salon_coiffure.Entrer(plein);
Nb_client = nb_client +1; Si not(plein) alors
Si not(vide(coiffeur)) alors [Link]() <se faire couper les cheveux>;
sinon [Link](); Fin
Fin;
18
Debut
nb_client = 0;
Fin.
Exercice13
Deux villes A et B sont reliés 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. Mais, 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). Ces processus se
décrivent 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 classe (producteur/consommateur, lecteur/rédacteur,
les philosophes), ce problème correspond à quel modèle ?
2)Ecrire sous forme de commentaires en utilisant les sémaphores, les opérations P et V,
les codes de demandes d’accès et de sorties, de façon à ce que les processus respectent
les règles de circulation sur la voie unique.
33
1) Modèle des lecteurs et des rédacteurs (la voie joue le rôle de la base de données).
2) Sémaphore autorisation =1 ;
// Le sémaphore autorisation est partagé par tous les trains
Sémaphore mutex =1 ;
//Le sémaphore mutex est partagé par tous les trains allant dans le même sens.
// Il y a donc deux sémaphores mutex un pour chaque sens.
Demande d’accès par un train AversB Demande d’accès par un train BversA
P(mutex) P(mutex)
Si NbAB ==0 alors P(autorisation) ; Si NbBA ==0 alors P(autorisation) ;
NbAB=NbAB+1 ; NbBA=NbBA+1 ;
V(mutex) ; V(mutex) ;
Sortie de la voie par B Sortie de la voie par A
P(mutex) P(mutex)
Si NbAB ==1 alors V(autorisation) ; Si NbBA ==1 alors V(autorisation) ;
NbAB=NbAB-1 ; NbBA=NbBA-1 ;
V(mutex) ; V(mutex) ;
34
Interblocage
Exercice 1 :
Considérons l’attribution des ressources suivante :
A détient R et demande S ;
B demandes T ;
C demandes S ;
D détient U et demande S et T ;
E détient T et demande V ;
F détient W et demande S ;
G détient V et demande U.
Construire le graphe d’allocation des ressources. Y a-t-il un interblocage? Si oui, quels
sont les processus concernés?
35
Exercice 1 :
Considérons l’attribution des ressources suivante :
A détient R et demande S ;
B demandes T ;
C demandes S ;
D détient U et demande S et T ;
E détient T et demande V ;
F détient W et demande S ;
G détient V et demande U.
Construire le graphe d’allocation des ressources. Y a-t-il un interblocage? Si oui, quels sont les processus
concernés?
Graphe d’allocation de ressources
36
Comme il y une instance unique par type de ressource, on utilise le graphe d’attente :
Dans ce graphe d’attente il y a un cycle D→ E→ G→ D donc les processus {D,E,G} sont
en inter-blocage
37
Exercice 2 :
Le graphe d’allocation de ressources pour un système à un moment donné est le suivant:
Y a-t-il risque d’interblocage en ce moment? Si oui, justifier. Si non, modifier ce graphe
en ajoutant une flèche pour que le risque d’interblocage existe.
38
Exercice 3 :
Dans un système, on a numéroté tous les types de ressources en donnant un numéro
unique à chacun d’eux. On oblige tout processus à ne demander un type de ressource
de numéro n, que s’il a déjà obtenu toutes les ressources dont il a besoin et dont le
numéro de type i est inférieur à n.
1. Peut-on avoir un cas d’interblocage avec cette méthode ? Justifiez.
2. Quel est l’inconvénient de cette méthode ?
39
Exercice 3 :
Dans un système, on a numéroté tous les types de ressources en donnant un numéro
unique à chacun d’eux. On oblige tout processus à ne demander un type de ressource
de numéro n, que s’il a déjà obtenu toutes les ressources dont il a besoin et dont le
numéro de type i est inférieur à n.
1. Peut-on avoir un cas d’interblocage avec cette méthode ? Justifiez.
1. On ne peut pas avoir d'interblocage avec ce protocole, car l'une des conditions
nécessaires et suffisantes pour l'apparition d'interblocage serait non vérifiée : la
condition de "l'attente circulaire". Justification : On fait un raisonnement par l'absurde.
Supposons qu'il y'a un interblocage entre n Processus P0, P1, … Pn-1, qui sont liés par une
chaine d'attente circulaire. Le processus P0 possédant une ressource R0 est en attente
d'au moins une ressource R1 de P1 (avec n° R0 > n° R1 pour respecter la méthode), le
processus P1 est au moins en attente d'une ressource R2 de P2 (avec n° R1> n° R2) , et ainsi
de suite … jusqu'au processus Pn-1 possédant une ressource Rn-1 et attendant une
ressource R0 détenue par le processus P0 (avec n° R0 > n° Rn-1). D'où une contradiction.
L'hypothèse de départ étant fausse, on n'a pas donc d'interblocage
40
Exercice 3 :
Dans un système, on a numéroté tous les types de ressources en donnant un numéro
unique à chacun d’eux. On oblige tout processus à ne demander un type de ressource
de numéro n, que s’il a déjà obtenu toutes les ressources dont il a besoin et dont le
numéro de type i est inférieur à n.
1. Peut-on avoir un cas d’interblocage avec cette méthode ? Justifiez.
2. Quel est l’inconvénient de cette méthode ?
Cette méthode peut conduire à une immobilisation inutile des ressources. Reprenons
l'exemple de l'énoncé (bande magnétique =1, processeur =2, imprimante=3, …).
Supposons qu'un processus P a besoin d'abord du processeur pendant X unité de
temps, ensuite du lecteur de bande magnétique pendant Y unités de temps et enfin de
l'imprimante . Pour respecter la méthode, P doit d'abord demander le lecteur de bande
magnétique qu'il immobilisera inutilement pendant X temps, et le processeur. Après
l'utilisation effective du processeur , du lecteur de bande magnétique et de
l'imprimante, le processeur termine.
C’est à dire un processus peut monopoliser pendant longtemps une ressource alors
qu’il n’en a pas besoin immédiatement.
41
Exercice 4
Imaginez l’instantané suivant d’un système :
Allocation Max Disponible
A B C A B C A B C
P0 0 1 0 7 5 3 3 3 2
P1 2 0 0 3 2 2
P2 3 0 2 9 0 2
P3 2 1 1 2 2 2
P4 0 0 2 3 3 3
Déterminer le nombre de ressources du système par type de ressource -)1
? Quel est le contenu de la matrice Need -)2
? Est-ce que le système est dans un état sain -)3
Si le processus Pi réalise une requête de la forme Requêtei , est-ce quelle peut être )3
: accordée immédiatement ? pour
a)- i = 1 et Requête1 = (3,3,3)
b)- i = 4 et Requête4 = (3,0,0)
a)- i = 1 et Requête1 = (1,0,2)
c)- i = 2 et Requête2 = (1,2,2)
42
Exercice 5 :
5 processus se partagent 11 ressources d'une classe de ressources qu'ils demandent une
à une. Chaque processus demande au total au plus 3 ressources. Peut-on avoir un cas
d’interblocage ? Justifiez.
Comment pouvez-vous généraliser le résultat précédent ?.
43
Exercice 5 :
5 processus se partagent 11 ressources d'une classe de ressources qu'ils demandent une
à une. Chaque processus demande au total au plus 3 ressources. Peut-on avoir un cas
d’interblocage ? Justifiez.
Comment pouvez-vous généraliser le résultat précédent ?.
Au pire, chaque processus a obtenu déjà 2 ressources, ce qui a mobilisé 10 ressources.
Le premier qui demandera sa troisième ressource pourra terminer et rendre une
ressource au moins; cette ressource pourra permettre à un autre processus de terminer,
...et ainsi de suite.
Nous avons donc une séquence saine, et par conséquent l’état du système est sain et il
n’y a aucun risque d’interblocage.
Généralisation : On peut généraliser le résultat précédent. Soient N, T, M
respectivement le nombre de processus, le nombre de ressources au maximum
demandées par chaque processus et le nombre total de ressources. Pour que le système
ne risque pas d’interblocage, il faudrait que : M soit égal au minimum à :
M = N(T - 1) + 1.
44
Exercice 6 :
Pour traiter une image de taille T unités, un système composé de N processeurs à
mémoire partagée, crée N processus. Chaque processus s’exécute sur un processeur et se
charge de traiter une partie de l’image. Pour faire son traitement, un processus a besoin
d’une unité de mémoire par unité d’image qu’il a à traiter, mais demande de la mémoire
unité par unité au fur et à mesure de ses besoins. Si une demande ne peut être
satisfaite, le processus demandeur est mis en attente (attente active). La libération des
unités de mémoire allouées à un processus aura lieu lorsqu’il aura fini le traitement de
toute sa partie. La mémoire disponible pour répondre aux demandes d’allocation des
différents processus est de taille M unités.
Question 1: Algorithme du banquier
Pour éviter les interblocages, le système utilise l’algorithme du banquier. Supposez que
N =4, T = 16, M = 8 et qu’à l’état courant les processus P1, P2, P3 et P4 ont
respectivement traité 1 sur 3 unités, 1 sur 4 unités, 1 sur 4 unités et 3 sur 5 unités (par
exemple, P1 : 1 sur 3 unités signifie que le processus P1 est chargé de traiter 3 unités de
l’image et a seulement traité 1 unité).
1)Est-il possible d’atteindre une situation d’interblocage, si T≤M ? Si T>M ? Justifiez votre
réponse.
2) Vérifiez, en utilisant l’algorithme du banquier, si l’état courant est certain (sûr ou sauf).
3)Le processus P3 demande une unité de mémoire. Doit-on la lui accorder ? Attention, 31
vous devez répondre à cette question en utilisant l’algorithme du banquier.
• Question 1 :
1) Si T ≤ M, il ne peut pas y avoir d’interblocage car il y a suffisamment d’espace mémoire
pour satisfaire toutes les demandes d’allocation des processus.
Par contre, si T>M, on peut atteindre une situation d’interblocage : il n’a plus d’espace
mémoire disponible et tous les processus ont encore besoin d’allouer de l’espace
mémoire.
2) Disponible= 8 – (1+1+1+3) = 2.
Allocation = ( 1, 1, 1,3) et Need = (2 3 3 2)
L’état est sain car l’ordonnancement suivant permet de terminer tous les processus :
P1 ; Disp = 3 ; P4 ; Disp = 6 ; P2 ; Disp=7 ; P3 ; Disp = 8.
3) Disp = 1 ; Allocation = ( 1, 1, 2, 3) et Need = ( 2 3 2 2)
L’état n’est pas sain car on ne peut satisfaire aucune requête. La demande est donc
refusée (le processus P3 doit être bloqué : attendre).
46
47
