Faculté des Sciences de Tunis
Département des Sciences de l'Informatique
Systèmes d’exploitation
TD - Interblocage
Exercice 1 :
Soient trois ressources R1, R2, R3 et les trois processus suivants :
• P1 : demande (R1); demande (R2); travaille; libère (R1); libère (R2)
• P2 : demande (R2); demande (R3); travaille; libère (R2); libère (R3)
• P3 : demande (R3); demande (R1); travaille; libère (R3); libère (R1)
Est-ce qu'il y a un risque d'interblocage ? Si oui, comment le corriger.
Exercice 2 :
Soient trois processus concurrents qui utilisent en exclusion mutuelle 6 ressources différentes
(de A à F). Ces trois processus exécutent respectivement les codes suivants :
Processus_1() Processus_2() Processus_3()
{ { {
while(1) while(1) while(1)
{ { {
Prendre (&D); Prendre (&C); Prendre (&A);
Prendre (&E); Prendre (&B); Prendre (&B);
Prendre (&C); Prendre (&F); Prendre (&E);
// Utilisation des // Utilisation des // Utilisation des
ressources; ressources; ressources;
Liberer (&D); Liberer (&F); Liberer (&E);
Liberer (&E); Liberer (&B); Liberer (&B);
Liberer (&C); Liberer (&C); Liberer (&A);
} } }
} } }
Ces processus concurrents peuvent-ils entrer en interblocage ? Expliquez à l’aide d’un
graphe. Si oui, peut-on l’éviter ? Justifiez brièvement.
Exercice 3
Dans un système électronique de transfert de fonds, il existe des centaines de processus
identiques qui fonctionnent comme suit : Chaque processus lit une ligne de données qui
spécifie la quantité d’argent, le numéro de compte à créditer et le numéro de compte à débiter.
Il verrouille ensuite l’un après l’autre les deux comptes, transfère l’argent puis libère les
verrous.
1) Peut-on avoir des situations d’interblocage ? Justifiez votre réponse
2) Si vous répondez oui à la question précédente, proposez une solution qui permet de les
éviter. Attention : ne pas libérer l’enregistrement d’un compte avant que le transfert ne soit
terminé.
1
Exercice 4 :
Soient 5 processus et 3 ressources (resp. 10, 5 et 7 ressources disponibles). Les demandes max
des processus sont définies comme suit :
• P0 (7 5 3), P1 (3 2 2), P2 (9 0 2), P3 (2 2 2), P4 (4 3 3)
A l'instant t, les processus ont les ressources suivantes :
• P0 (0 1 0), P1 (2 0 0), P2 (3 0 2), P3 (2 1 1), P4 (0 0 2)
1. L'état est-il fiable ?
2. P0 demande (0 1 0) puis (1 0 0) ; faut-il le servir ?
Exercice 5
On considère les 5 tâches T0, T1, T2, T3 et T4 et 4 ressources A, B, C et D. On considère les
structures de données suivantes : Disponible désigne le nombre de ressources disponible de
chaque type. Le Max indique le maximum de demandes de chaque tâche. Et L’Allocation
détermine le nombre de ressources de chaque type allouées à chaque tâche.
Dans ce système, lorsqu’une tâche entre, elle doit déclarer le nombre maximum d’instances de
chaque type de ressources qu’elle doit utiliser. Lorsqu’une requête utilisateur demande un
ensemble de ressources, le système doit assurer si cette allocation laisse le système dans un
état sain.
Considérez l’image suivante à un instant donné t0 du système :
Allocation Max Disponible
t0 A B C D A B C D A B C D
T0 0 0 1 2 0 0 1 2 1 5 2 0
T1 1 0 0 0 1 7 5 0
T2 1 3 5 4 2 3 5 6
T3 0 6 3 2 0 6 5 2
T4 0 0 1 4 0 6 5 6
1) En utilisant l’algorithme du banquier donner le contenu de la matrice Besoin indiquant le
besoin restant en ressource pour chaque tâche.
2) Le système est-il dans un état sain ?
3) Si la tâche T1 émet la requête (0,4,2,0), peut-elle être honorée immédiatement ?
Exercice 6
Considérez un ensemble de processus composés de plusieurs producteurs et d’un seul
consommateur dont les codes sont les suivants :
2
Semaphore plein =0, vide=N, mutex=1,mutex1=1;
char T[N] ;
int ip=0 ;
Producteur ( ) Consommateur ( )
{ {
int i, M ; int ic =0 ;
char ch[N]; char c ;
Repeter Repeter
{ {
M =Lire (ch, N); P(plein) ;
M = min (N, M); P(mutex) ;
c= T[ic] ;
Pour i=1 à M pas 1 faire V(mutex) ;
P (vide) ; V(vide) ;
Traiter(c) ;
P (mutex) ; ic++ ;
Déposer (ch, M, ip) ; } tant que vrai ;
//insérer ch dans T }
ip = (ip+M)%N ;
V (mutex) ;
Pour i=1 à M pas 1 faire
V (plein) ;
} tant que vrai ;
}
1. Peut-on avoir une situation d’interblocage ? (si oui, expliquez en décrivant clairement
une situation d’interblocage).
2. Complétez le code précédent de manière à éviter les situations d’interblocage.
Exercice 7
On considère 5 processus (P0, P1, P2, P3, P4) et 5 catégories de ressources désignées
respectivement par R0, R1, R2 , R3, et R4. Ces ressources sont disponibles en un seul
exemplaire [Link] le tableau Tab_Max ci-dessous on représente les ressources
maximales demandées par les processus.
Tableau Processus R0 R1 R2 R3 R4
Tab_Max P0 1 1 0 0 0
P1 0 1 1 0 0
P2 0 0 1 1 0
P3 0 0 0 1 1
P4 1 0 0 0 1
3
On suppose qu’à un instant t donné P0 à obtenu R0, P2 a obtenu R2 et P3 a obtenu R3.
Questions :
1. Donner la représentation matricielle des données du problème à savoir les matrices
d’allocation et des besoins à la date t.
2. Calculer le vecteur de disponibilité à cette date t.
3. Montrer qu’à cet instant t le système est fiable.
4. Supposons qu’à l’instant t1 le processus p4emet une demande de ressource R4. Selon
l'algorithme du banquier, est ce que la requête peut être immédiatement accordée/
5. A l’instant t2, une requête de P2 correspondant à demander R2. Est-ce que la requête
peut être satisfaite selon le même algorithme.
6. Comment peut-on prouver ce résultat par une méthode basée sur les graphes.
7. Cette description correspond à un problème classique de synchronisation lequel ?
8. Est-il possible de prévenir ce problème d’interblocage sans passer par l’algorithme
du banquier ? Expliquez !
Exercice 8
On considère un système optimiste dans lequel on autorise la l'arrivée des interblocages. Soit
le graphe d’assignation de ressources de la figure ci-dessous
R1
P1 .
R2
P3
R6
P2
R3 P4
P6 R4
R5 P5
1. Sur ce graphe il existe des cycles lesquels?
2. Que signifie l'existence d'un cycle dans ce cas?
3. Donner en se basant sur les données du graphe la matrice d'allocation des ressources, la
matrice des demandes (requêtes) et le vecteur de disponibilité des ressources.
4. Existe-il un interblocage dans ce cas de figure? Justifier votre réponse.
