29 0 431KB
Ecole Supérieur en Informatique de Sidi Bel Abbès 1ère année Cycle Secondaire Année universitaire: 2019-2020
Module: Système d’exploitation 2 Semestre : S2
Corrigé Type Interblocage 1 Exercice 1 1. Rappelez les quatre conditions qui peuvent conduire à un interblocage. Est-il nécessaire qu’elles soient toutes vérifiées pour qu’un interblocage puisse se produire ? Sont-elles indépendantes ? 2. Rappelez la définition du graphe ressource-allocation. 3. On suppose que dans un système, il n’existe qu’une seule instance de chaque ressource. Comment déterminer un interblocage à partir du graphe ressource-allocation. En déduire un mécanisme possible de détection.
Exercice 2 a) Quelle sont parmi les 5 processus ci-dessous ceux qui amènent à un interblocage. Les processus sont A, B, C, D et E. var S1,S2,S3,S4 : semaphore; init(S1,1);init(S2,1);init(S3,1);init(S4,0); A:debut P(S1);V(S1);P(S2);V(S2);fin B:debut P(S1);P(S2);V(S4);V(S2);V(S1);fin C:debut P(S2);P(S3);V(S2);V(S3);fin D:debut P(S4);P(S2);P(S1);V(S1);V(S2);fin E:debut P(S3);P(S2);V(S2);V(S3);fin b) Quels sont les processus additionnels qui peuvent être bloqués à cause du blocage précédent ? c) Pour les processus donnés le blocage est-il inévitable ou dépend-il de la façon dont est réalisée la succession des taches ?
Exercice 3 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 inter-blocage? Si oui, quels sont les processus concernés?
1
Corrigé 1. Les quatre conditions qui conduisent à un interblocage : - L’exclusion mutuelle - Pas de réquisition - Possession et attente - Attente circulaire Oui, les 4 conditions doivent êtres présentes pour qu’un interblocage se produis, car ce sont des conditions nécessaires (et suffisantes) pour l’interblocage. Les 4 conditions ne sont pas totalement indépendantes : - Attente circulaire possession et attente - Attente circulaire pas de réquisition 2. Un graphe d’allocation de ressources : Un ensemble de sommets V et d’arêtes E V est partitionné en 2 ensembles: P = {P1, P2, …, Pn}, l’ensemble qui consiste de tous les processus dans le système R = {R1, R2, …, Rm}, l’ensemble qui consiste de tous les types de ressources dans le système Arêtes requête : arêtes dirigées Pi Rj Arêtes affectation : arêtes dirigées Rk Pl 3. Dans un système avec un seul exemplaire par ressource, l’existence d’un cycle dans le graphe ressource-allocation veut dire l’existence d’un interblocage. Un mécanisme de détection : un algorithme de détection de cycles dans un graphe orienté.
Exercice 2 var S1,S2,S3,S4 : semaphore; init(S1,1);init(S2,1);init(S3,1);init(S4,0); A:debut P(S1);V(S1);P(S2);V(S2);fin B:debut P(S1);P(S2);V(S4);V(S2);V(S1);fin C:debut P(S2);P(S3);V(S2);V(S3);fin D:debut P(S4);P(S2);P(S1);V(S1);V(S2);fin E:debut P(S3);P(S2);V(S2);V(S3);fin
a) Les processus qui amènent à un interblocage sont les processus : C et E (tous les deux exécutent une opération P sur S2 et sur S3 mais dans un ordre différent). b) Les processus additionnels qui peuvent être bloqués à cause du blocage précédent : Tous les autres processus, car ils exécutent tous un P(S2). c) Pour les processus donnés le blocage est-il inévitable ou dépend-il de la façon dont est réalisée la succession des taches : Non, l’interblocage n’est pas inévitable, il dépond de l’ordre d’exécution des 2
tâches des processus. Exemple : Si les processus sont exécutés d’une façon séquentielle dans l’ordre {A, B, C, D, E}, l’un après l’autre, il n’y aura pas d’interblocage.
Exercice 3
-
Oui, il y a un interblocage car il y a un cycle dans le graphe d’allocation de ressources (E, V, G, U, D, T, E), et il y a un seul exemplaire par ressource. Les processus impliqués dans l’interblocage : E, G, et D. Cet interblocage va bloquer aussi le processus B.
3