Faculté des Sciences de GabesDépartement d’informatique
10/10/2016
Cours Système d'exploitation 1
10/10/2016 1Khaled Hassine
Par :
Khaled Hassine
CCHAPITREHAPITRE IIII ––L’L’INTERBLOCAGEINTERBLOCAGE
((DDEADLOOKSEADLOOKS))
10/10/2016 2Khaled Hassine
Esquive des interblocages
Prévention des interblocages
Généralités
Détection et guérison
PLAN
10/10/2016 3
Modélisation de l’interblocage
Khaled Hassine
Faculté des Sciences de GabesDépartement d’informatique
10/10/2016
Cours Système d'exploitation 2
Esquive des interblocages
Prévention des interblocages
Généralités
Détection et guérison
PLAN
10/10/2016 4
Modélisation de l’interblocage
Khaled Hassine
Interblocage : définition
Besoin au niveau d’un SE de partager l’accès àdes ressources (mémoire, UC, périphériques,…)
Un ensemble de processus est en interblocage sichaque processus attend un évènement que seulun autre processus de l'ensemble peut engendrer.
Le terme interblocage est quelquefois remplacépar les expressions poétiques "verrou mortel"(en anglais deadlock), "étreinte fatale", …
10/10/2016 Khaled Hassine 5
Exemple
Deux processus P1 et P2 utilisent deux ressources R1et R2 P1 possède R1 et demande R2
P2 possède R2 et demande R1
C’est une situation d’interblocage.
10/10/2016 Khaled Hassine 6
P1 P2
R1
R2
Faculté des Sciences de GabesDépartement d’informatique
10/10/2016
Cours Système d'exploitation 3
Ressources
En SE, lorsqu'un processus demande uneressource et que cette dernière n'est pasdisponible, des états sont définis (bloqué,suspendu bloqué, etc.).
En pratique : plusieurs processus peuvent être demandeurs de
la même ressource, chacun de ces processus peut demander plus
d'une ressource.
10/10/2016 Khaled Hassine 7
Ressources : définition
Dans le cas qui nous préoccupe (les deadlocks), nouspouvons définir une ressource comme tout ce qui nepeut être accédé que par un seul processus à la fois.
Ceci correspond aux : périphériques matériels (lecteur de disquette, imprimante,
etc.), informations (par exemple, un enregistrement dans une
base de donnée, une variable partagée, etc),
et dont l'OS peut avoir à gérer en plusieurs exemplaires(par exemple, plusieurs imprimantes).
10/10/2016 Khaled Hassine 8
Deux types de ressources
Ressource préemptive ou encoreréquisitionnable (préemptive ressource) : peut être retirée au processus qui la détient sans
risque. Exemple : la mémoire.
Ressource non-préemptive ou encore nonréquisitionnable (non préemptive ressource) : le fait de retirer cette ressource au processus qui la
détient provoque des problèmes. Exemple : l'imprimante.
10/10/2016 Khaled Hassine 9
Faculté des Sciences de GabesDépartement d’informatique
10/10/2016
Cours Système d'exploitation 4
Problématique
Les problèmes d’accès concurrent à ces ressourcespeuvent être résolus par des stratégies desynchronisation faisant appel par exemple à dessémaphores.
Autrement dit, il est possible d’empêcher que deuxprocessus accèdent en même temps à une ressource.
Même la meilleure technique de synchronisation nepeut toutefois garantir que chaque processus pourraaccéder aux ressources dont il a besoin et que desprocessus ne resteront pas éternellement bloqués enattente.
10/10/2016 Khaled Hassine 10
Exemple 1 : Rond pointavec priorité à droite
Les interblocages sont dessituations assez courantesdans la vie quotidienne.
Le meilleur exemple estcelui du rond point avecpriorité à droite.
Si 4 routes arrivent à ce rondpoint et s'il y a quatrevéhicules, aucun ne peuts'engager sur le rond pointpuisque chaque véhiculepossède à sa droite un voisin
10/10/2016 Khaled Hassine 11
Exemple 2 : le spooling massif
Un processus P veut imprimer des données.Comme le système utilise un spool (une filed’attente), le processus envoie ses données sur undisque (buffer) et le périphérique (imprimante)attend que toutes les données soient sur le disquepour imprimer.
Mais si le buffer est plein avant que le processusait envoyé toutes ses données, le processus vaattendre et l'imprimante, de son côté, attend aussi.
10/10/2016 Khaled Hassine 12
Faculté des Sciences de GabesDépartement d’informatique
10/10/2016
Cours Système d'exploitation 5
Exemple 2 : le spoolingmassif
10/10/2016 Khaled Hassine 13
Esquive des interblocages
Prévention des interblocages
Généralités
Détection et guérison
PLAN
10/10/2016 14
Modélisation de l’interblocage
Khaled Hassine
Outils de modélisation
L'étude de l'interblocage dans un systèmeimpose la représentation de l'état desprocessus et des ressources.
Ceci peut se faire en utilisant un graphe d'allocation des ressources ou
des matrices d'allocation des ressources.
10/10/2016 Khaled Hassine 15
Faculté des Sciences de GabesDépartement d’informatique
10/10/2016
Cours Système d'exploitation 6
Modélisation del’interblocage
Graphe d’allocation des ressourcesMatrice d’allocation des ressourcesConditions de Coffman
10/10/2016 Khaled Hassine 16
Graphe d'allocation des ressources
Les graphes d'allocation de ressources permettent demodéliser simplement les problèmes d'interblocage par ungraphe : G = (N, T) N = P U RAvec : P : ensemble des processus R : ensemble des ressources T RxP U PxR
Soit (x, y) T. si (x, y) RxP la ressource x est utilisée par le processus y si (x, y) PxR le processus x demande la ressource y.
10/10/2016 Khaled Hassine 17
Conventions de représentation
Un processus est représenté par un cercle Une ressource est représentée par un
rectangle Un arc d’une instance de R vers un processus
P l’instance est détenue par le processus P. Un arc d’un processus P vers une ressource R P est bloqué en attente d’une instance de laressource R.
10/10/2016 Khaled Hassine 18
Faculté des Sciences de GabesDépartement d’informatique
10/10/2016
Cours Système d'exploitation 7
Instances indifférentiables
S’il existe plusieurs instances indifférentiableson les représente dans la même boite. Indifférentiables : lorsqu’un processus n’a pas à
choisir une instance particulière de cette ressourceplutôt qu’une autre, il prend la première disponible.
Toutes les instances sont alors équivalentes. Dés lors qu’un processus doit choisir une instance
plutôt qu’une autre, elles sont différentiables eton les modélise alors comme des instances deressources différentes.
10/10/2016 Khaled Hassine 19
Exemple
10/10/2016 Khaled Hassine 20
P1
P2
P3
Rb
RaRc
P1 détient une ressource de classe RbP1 demande une ressource de classe Ra
Pas d’interblocage
Exemple
10/10/2016 Khaled Hassine 21
P1
P2
P3
Rb
RaRc
Interblocage
Faculté des Sciences de GabesDépartement d’informatique
10/10/2016
Cours Système d'exploitation 8
Modélisation del’interblocage
Graphe d’allocation des ressourcesMatrice d’allocation des ressourcesConditions de Coffman
10/10/2016 Khaled Hassine 22
Etat du système
Soit un système disposant d’instances de différentes ressources. A tout instant donné, l’état de chaque processus présent dans le
système va être partiellement décrit par : Nb_Max : le nombre maximum d’instances des ressources dont il a besoin pour
terminer son exécution (donnée sur les processus) Nb_Détenue : le nombre d’instances de chaque type de ressource qu’il détient
(montre l’évolution du système) Nb_Requis : le nombre d’instances de ressources qu’il doit encore obtenir
(déduite).
Pour avoir une image complète de l’état du système, il faut encorepréciser : Nb_total : le nombre total d’instances de chaque ressource dans le système
(donnée sur les ressources), Nb_disponible : le nombre d’instances disponibles de chaque ressource (déduite).
10/10/2016 Khaled Hassine 23
Exemple de Matrice d’allocationdes ressources aux processus
Nb_Détenue Nb_Max Nb_Requis
Ra Rb Rc Rd Ra Rb Rc Rd Ra Rb Rc Rd
P1 0 5 1 0 P1 0 10 3 2 P1 0 5 2 2
P2 4 3 5 4 P2 5 5 5 5 P2 1 2 0 1
P3 0 0 0 1 P3 4 5 3 5 P3 4 5 3 4
P4 2 2 2 2 P4 3 2 2 2 P4 1 0 0 0
P5 3 2 1 1 P5 3 3 1 3 P5 0 1 0 2
10/10/2016 Khaled Hassine 24
Nb_total Nb_disponible
Ra Rb Rc Rd Ra Rb Rc Rd
10 13 9 11 1 1 0 3
Faculté des Sciences de GabesDépartement d’informatique
10/10/2016
Cours Système d'exploitation 9
Modélisation del’interblocage
Graphe d’allocation des ressourcesMatrice d’allocation des ressourcesConditions de Coffman
10/10/2016 Khaled Hassine 25
Etats possibles d’un système On considère qu’un système informatique peut être dans l'un des
états suivants : Etat d’interblocage ou un ensemble de processus reste indéfiniment
bloqués. Etat risqué (unsafe state, incertain dit aussi NON SAIN) : à partir
duquel l’interblocage est inévitable. Etat sûr (safe state, SAIN) : à partir duquel il existe au moins une
séquence d’allocation des ressources au processus qui permet d’éviterl’interblocage et terminer leurs travaux dans un temps garanti commefini.
Afin d’éviter l’interblocage, il suffit donc, lorsque un processusprésente au système une demande d’allocation de ressources, devérifier si le nouvel état obtenu serait un état risqué. Si c’est le cas ilfaut refuser la demande sinon le processus obtient la ressource.
10/10/2016 Khaled Hassine 26
Les conditions de Coffman (1971)
Quatre (4) conditions qui doivent être vérifiéessimultanément pour qu’un interblocage seproduise.
Si une seule des conditions n'est pas remplie,l'interblocage peut être évité .
10/10/2016 Khaled Hassine 27
Faculté des Sciences de GabesDépartement d’informatique
10/10/2016
Cours Système d'exploitation 10
Les 4 conditions de Coffman(1971)
1) L'exclusion mutuelle (mutual exclusion condition) : Il doit exister au moinsdeux ressources qui ne sont pas partageables. Chaque ressource est soitassignée à un seul processus, soit libre. Les processus demandent le contrôleexclusif des ressources qu'ils demandent.
2) La détention et l'attente (hold and wait condition) : Les processus quidétiennent des ressources peuvent en demander d'autres. Il existe donc au moinsun processus qui détient au moins une ressource et attend des ressources détenuspar d’autres processus.
3) Pas de réquisition (non preemption condition) : Les ressources obtenues par unprocessus ne peuvent lui être retirées, c'est le processus qui les détient qui doitexplicitement les libérer. Un processus ne peut pas être forcé par un autreprocessus à relâcher des ressources déjà acquises. Des ressources ne peuvent êtreenlevées à des processus qui les détiennent tant qu'elles ne sont pascomplètement utilisées.
4) L'attente circulaire (circular wait condition) : Il doit y exister une chaînecirculaire d’au moins deux processus dont chacun attend une ressource détenuepar le membre suivant de la chaîne.
10/10/2016 Khaled Hassine 28
Esquive des interblocages
Prévention des interblocages
Généralités
Détection et guérison
PLAN
10/10/2016 29
Modélisation de l’interblocage
Khaled Hassine
Feux de circulation Rajouter des feux de
circulation Dans les conditions de
Coffman, si une seule des4 conditions n'est pasvérifiée nous évitonsl'interblocage.
Les stratégies suivantespermettent chacuned'éviter le deadlock ensupprimant le risqued'apparition d'une des 4conditions.
10/10/2016 Khaled Hassine 30
Faculté des Sciences de GabesDépartement d’informatique
10/10/2016
Cours Système d'exploitation 11
Condition d'exclusion mutuelle
Attacking the mutual exclusion condition
Empêcher qu'une ressource soit attribuée demanière exclusive à un processus
La condition d'exclusion mutuelle n'est doncpas remplie et nous évitons ainsi le deadlock.
Solution possible : utiliser un spooler (filed’attente).
10/10/2016 Khaled Hassine 31
Exemple : impression via spooler
Déplacer le problème en amont pour éviter le deadlock. Forcer la demande de la ressource via un spooler.
Utilise des files d'attentes N'est pas exclusif La ressource en aval est accédée de manière séquentielle.
Problème : Le spooler utilise le disque dur pour stocker les files
d'attentes, blocage si l'espace disque est insuffisant.
10/10/2016 Khaled Hassine 32
Condition de détention et d'attente
Attacking the hold and wait condition Idée de base : l'acquisition des ressources en
"tout ou rien": demander toutes les ressources dont on a besoin en
une seule fois doit attendre en cas d’impossibilité de les obtenir
Ce type de procédure peut être valable dans le casd'un batch (traitement par lots) qui liste toutes lesressources nécessaires en début de job.
10/10/2016 Khaled Hassine 33
Faculté des Sciences de GabesDépartement d’informatique
10/10/2016
Cours Système d'exploitation 12
Inconvénients
Il est généralement impossible de prédire lesressources effectivement utilisées.
Un processus risque d'attendre longtemps avantd'obtenir ses ressources.
Il peut y avoir un gaspillage (gâchis) éventuel deressources (quelques unes très utilisées, les autrespeu utilisées mais mobilisées).
Solution possible : le découpage d'un processusen sous processus.
10/10/2016 Khaled Hassine 34
Condition de non réquisition
Attacking the non preemption condition Difficilement contournable :
Certaines ressources ne supportent pas la préemption. Une préemption sur une impression !!! recommencer
entièrement le processus. Solution possible :
Si un processus détient certaines ressources et si on luirefuse une ressource supplémentaire, il doit libérer lesressources détenus.
Inconvénient : le risque de faire attendre longtempscertains processus.
10/10/2016 Khaled Hassine 35
Condition d'attente circulaire
Attacking the circular wait condition
Solution possible : numérotation des ressources Permet de briser la condition d'attente circulaire.
Les processus peuvent demander toutes les ressourcesdont ils ont besoin, à condition de respecter l'ordrecroissant de la numérotation des ressources.
Si un processus détient des ressources d'un typedonné, il ne peut demander que des ressources dont lesnuméros sont plus élevés.
10/10/2016 Khaled Hassine 36
Faculté des Sciences de GabesDépartement d’informatique
10/10/2016
Cours Système d'exploitation 13
Numérotation desressources
10/10/2016 Khaled Hassine 37
ProcessusProcessus
R1 R2 R3 R4 R5 R6 R7
Non
Oui
Numéro
Esquive des interblocages
Prévention des interblocages
Généralités
Détection et guérison
PLAN
10/10/2016 38
Modélisation de l’interblocage
Khaled Hassine
Principe de l'évitement (deadlockavoidance)
Constatation :
Généralement, un processus ne demande pas la totalité des
ressources dont il a besoin.
Les ressources sont demandées une à la fois.
Problème : chercher un algorithme qui permet de déterminer quelle
ressource accorder à quel processus pour éviter l'interblocage
La représentation graphique ne fournit pas directement un
algorithme utilisable. Elle nous permet quand même de déterminer
des régions sûres et d'autres qui peuvent mener à un deadlock.
10/10/2016 Khaled Hassine 39
Faculté des Sciences de GabesDépartement d’informatique
10/10/2016
Cours Système d'exploitation 14
Principe de l’algorithme
Utiliser les matrices pour détecter les deadlocks. Permet de déterminer qu'il existe pour un instant
donné un état courant sûr : Il n'est pas en deadlock, Il est possible de satisfaire toutes les demandes de
ressources en exécutant les processus dans un certainordre.
Cet ordre est très important, car un mauvais choix audépart peut mener à un deadlock.
10/10/2016 Khaled Hassine 40
L'algorithme du "banquier"(Dijkstra - 1965)
N Processus et R types de ressources identiques. Les règles de l'algorithme :
Chaque processus indique à l'avance le nombre maximum deressources dont il a besoin .
Le système d'exploitation accepte une demande si celle-ci nedépasse pas R.
Un processus peut acquérir ou libérer les ressources une parune .
Une attente est possible, mais elle doit rester finie. L'algorithme du banquier consiste à allouer les ressources
(d'après les règles précédentes) de manière à passer d'unétat sain à un autre état sain.
10/10/2016 Khaled Hassine 41
Exemple 1 : Etat sein
Allocation courante Maximum demandé
P(1) 1 4
P(2) 4 6
P(3) 5 8
Disponible 2
10/10/2016 Khaled Hassine 42
Scénario qui mène à la terminaison de tous les processus :1. On donne 2 ressources à P(2), il peut finir et il libère alors 6
ressources.2. On en prend 3 que l'on donne à P(1) qui peut alors finir et
libérer ainsi 4 ressources, total disponible 7.3. On prend 3 autres ressources pour P(3) qui peut alors finir.
Faculté des Sciences de GabesDépartement d’informatique
10/10/2016
Cours Système d'exploitation 15
Exemple 2 : Etat non sein
Allocation courante Maximum demandé
P(1) 8 10
P(2) 2 5
P(3) 1 3
Disponible 1
10/10/2016 Khaled Hassine 43
L'unique ressource disponible ne suffit pas à contenter n'importelequel des processus
Exemple 3
Un état sain peut devenir non sain parmauvaise allocation des ressources
10/10/2016 Khaled Hassine 44
Allocation
courante
Maximum
demandé
P(1) 1 4
P(2) 4 6
P(3) 5 8
Disponible 2
Allocation
courante
Maximum
demandé
P(1) 2 4
P(2) 4 6
P(3) 5 8
Disponible 1
P(1)acquiert
1 ressource
L'algorithme du banquier Les données sont :
L : La liste de tous les processus bloqués. N : Le nombre de processus bloqué (cardinal de L). R : Nombre de types de ressources dans le système. Nb_Détenue : Nombre de ressources détenues par chaque processus. Nb_Max : Nombre maximum de ressources nécessaires pour chaque processus. Nb_Total : Nombre total d'instances de chaque ressource au niveau du système.
Les sorties sont : Etat : Etat du système (interblocage, risqué : incertain, sûr) Scénario : La séquence des processus dans l'ordre d'allocation des ressources qui permet la
terminaison de tous les processus de la liste bloquée (si elle existe).
Les variables internes : Nb_Requis : Nombre de ressources requis pour chaque processus (Nb_Max – Nb_Détenue). Nb_Disponible : Nombre d'instances de chaque ressource actuellement disponible au niveau du système
On représentera les états : sûr par 0, incertain par 1, interblocage par 2. Scénario : donne la séquence de processus pour avoir un état sûr.
10/10/2016 Khaled Hassine 45
Faculté des Sciences de GabesDépartement d’informatique
10/10/2016
Cours Système d'exploitation 16
Algorithme du banquier
Action Banquier (Données : N, R : entier, L : [N]Entier, Nb_DétenueNb_Max: [N][R]entier, Nb_Total: [R]entier, Résultat : Etat : entier,Scénario : [N]entier)
VariablesNb_Requis : [N][R]entierNb_Disponible : [R]entier;k : entier;
DébutNb_Requis (NB_Max – NB_Détenue)Nb_Disponible Nb_Total - des instances requis par chaqueprocessus {somme de chaque colonne de Nb_Détenu}k 0
10/10/2016 Khaled Hassine 46
Algorithme du banquier
RépéterChercher (L, N, Nb_Disponible, Nb_Requis, P, Existe)Si Existe
AlorsEliminer (P, L, N)N N-1Nb_Disponible Nb_Disponible + Nb_Détenue[P]Sénario[k] Pk k+1
FinSiJusqu'à (Not Existe) Or (L=)
10/10/2016 Khaled Hassine 47
Algorithme du banquier
Si L=Alors état sûrSinon
Si (k=0) si L est resté inchangéAlors
Etat InterblocageSinon
Etat incertainFinSi
FinSiFin
10/10/2016 Khaled Hassine 48
Faculté des Sciences de GabesDépartement d’informatique
10/10/2016
Cours Système d'exploitation 17
Action Chercher
Cherche parmi tous le processus de L s’il y a unprocessus P dont les besoins peuvent êtresatisfaits (le nombre d’instances de ressourcesrequises ≤ au nombre d’instances de ressourcesdisponibles) …
S’il existe plusieurs choix, c'est-à-dire plusieursprocessus dont les besoins peuvent être satisfaits,peu importe le choix qu'on fait puisqu'il peut êtrealéatoire.
10/10/2016 Khaled Hassine 49
Heuristiques de choix
Le choix peut être amélioré par des heuristiquespermettant d'améliorer le temps de réponse du système.
On peut définir les heuristiques suivantes : Le processus ayant le plus grand nombre de ressources
détenues. Ceci permet de disposer de plus de ressources après lafin de ce processus et par conséquent permet de débloquer plusde processus plus tard et améliorer le temps de réponse dusystème.
Le processus ayant le plus petit nombre de ressourcesrequises. Ceci permet de laisser un nombre plus important deressources et permettant ainsi de débloquer plus de processus enparallèle et par conséquent améliorer le temps de réponse dusystème.
10/10/2016 Khaled Hassine 50
Action Chercher
Les données de l'action Chercher sont : L : Liste des descripteurs des processus bloqués, N : entier qui indique Nombre de processus bloqués, Nb_Disponible, Nb_Requis : Matrice d'entier de taille
NxR,
Les résultats de l'action Chercher sont : P : Entier indiquant le numéro du processus dont les
besoins peuvent être satisfaits, Existe : Booléen
10/10/2016 Khaled Hassine 51
Faculté des Sciences de GabesDépartement d’informatique
10/10/2016
Cours Système d'exploitation 18
L’action ChercherChercher (Données : N : entier
L : [N]Entier,Nb_Disponible, Nb_Requis :[N][R]entier,Résultat P : Entier, Existe :Booléen)
Variables i : Entier – variablede parcours.
Débuti 0Existe Faux
Tant que (i< N) et (Nb_Requis[i] >Nb_Disponible)
Faire
i i+1
FinFaire
Si (i< N)
Alors
Existe Vrai
P i
Sinon
Existe Faux
FinSi
Fin
10/10/2016 Khaled Hassine 52
Exemple d’application
Nb_Max Nb_Total
R1 R2 R3 R1 R2 R3
P1 3 2 2 9 3 6
P2 6 1 3
P3 3 1 4
P4 4 2 2
10/10/2016 Khaled Hassine 53
Les états
A un instant donné, le système est dans l'un des états suivants.Indiquez si ces états sont sains ou non sains au sens del'algorithme du Banquier et dans l'affirmative, indiquer la suited'états permettant d'exécuter complètement les processus.
10/10/2016 Khaled Hassine 54
Etat 1 Etat 2 Etat 3
R1 R2 R3 R1 R2 R3 R1 R2 R3
P1 1 0 0 P1 1 0 0 P1 2 0 1
P2 6 1 2 P2 5 1 1 P2 5 1 1
P3 2 1 1 P3 2 1 1 P3 2 1 1
P4 0 0 2 P4 0 0 2 P4 0 0 2
Faculté des Sciences de GabesDépartement d’informatique
10/10/2016
Cours Système d'exploitation 19
Etat 1
10/10/2016 Khaled Hassine 55
Etat 1
R1 R2 R3
P1 1 0 0
P2 6 1 2
P3 2 1 1
P4 0 0 2
Nb_Max Nb_Total
R1 R2 R3 R1 R2 R3
P1 3 2 2 9 3 6
P2 6 1 3
P3 3 1 4
P4 4 2 2
Nombre requis et disponibles
Nb_Requis Nb_Disponibles
R1 R2 R3 R1 R2 R3
P1 2 2 2 0 1 1
P2 0 0 1
P3 1 0 3
P4 4 2 0
10/10/2016 Khaled Hassine 56
Requis P2 ≤ disponiblesP2 se termine et libre ses ressources
Nb_Requis Nb_Disponibles
R1 R2 R3 R1 R2 R3
P1 2 2 2 6 2 3
P3 1 0 3
P4 4 2 0
Nombre requis et disponibles
Nb_Requis Nb_Disponibles
R1 R2 R3 R1 R2 R3
P1 2 2 2 6 2 3
P3 1 0 3
P4 4 2 0
10/10/2016 Khaled Hassine 57
Requis P1, P3 et P4 ≤ disponiblesOn choisit P1, qui se termine et libre sesressources
Nb_Requis Nb_Disponibles
R1 R2 R3 R1 R2 R3
P3 1 0 3 7 2 3
P4 4 2 0
Faculté des Sciences de GabesDépartement d’informatique
10/10/2016
Cours Système d'exploitation 20
Nombre requis et disponibles
Nb_Requis Nb_Disponibles
R1 R2 R3 R1 R2 R3
P3 1 0 3 7 2 3
P4 4 2 0
10/10/2016 Khaled Hassine 58
Requis P3 et P4 ≤ disponiblesOn choisit P3, qui se termine et libre sesressources
Nb_Requis Nb_Disponibles
R1 R2 R3 R1 R2 R3
P4 4 2 0 9 3 4
Nombre requis et disponibles
Nb_Requis Nb_Disponibles
R1 R2 R3 R1 R2 R3
P4 4 2 0 9 3 4
10/10/2016 Khaled Hassine 59
Requis P4 ≤ disponiblesOn choisit P4, qui se termine et libre sesressources
Nb_Requis Nb_Disponibles
R1 R2 R3 R1 R2 R3
9 3 6L'état 1 est un état sain.
Etat 2
10/10/2016 Khaled Hassine 60
Etat 2
R1 R2 R3
P1 1 0 0
P2 5 1 1
P3 2 1 1
P4 0 0 2
Nb_Max Nb_Total
R1 R2 R3 R1 R2 R3
P1 3 2 2 9 3 6
P2 6 1 3
P3 3 1 4
P4 4 2 2
Faculté des Sciences de GabesDépartement d’informatique
10/10/2016
Cours Système d'exploitation 21
Nombre requis et disponibles
Nb_Requis
R1 R2 R3
P1 2 2 2
P2 1 0 2
P3 1 0 3
P4 4 2 0
10/10/2016 Khaled Hassine 61
Requis P2 ≤ disponiblesP2 se termine et libre ses ressources
Nb_Requis Nb_Disponibles
R1 R2 R3 R1 R2 R3
P1 2 2 2 6 2 3
P3 1 0 3
P4 4 2 0
Nb_Disponibles
R1 R2 R3
1 1 2
Etat 2 est un état sein
P2 va ainsi se terminer.
Il libère les ressources qu’il détient. Ceci permettra, comme dans le cas de l'état 1
d'aller au terme des exécutions.
10/10/2016 Khaled Hassine 62
Etat 3
10/10/2016 Khaled Hassine 63
Nb_Max Nb_Total
R1 R2 R3 R1 R2 R3
P1 3 2 2 9 3 6
P2 6 1 3
P3 3 1 4
P4 4 2 2
Etat 3
R1 R2 R3
P1 2 0 1
P2 5 1 1
P3 2 1 1
P4 0 0 2
Faculté des Sciences de GabesDépartement d’informatique
10/10/2016
Cours Système d'exploitation 22
L'état 3 …
Nb_Requis
R1 R2 R3
P1 1 2 1
P2 1 0 2
P3 1 0 3
P4 4 2 0
10/10/2016 Khaled Hassine 64
C'est un état d'interblocage
Pour tous les processusRequis > disponibles
Nb_Disponibles
R1 R2 R3
0 1 1
Limites de l'algorithme dubanquier
Le choix dans l'allocation des ressources suppose que le systèmed'exploitation possède à l'avance certaines informations, ce quin'est généralement pas possible : le nombre maximum de ressources disponibles dans le système,
chose difficile à connaître surtout en cas de panne. le nombre de processus dans le système, chose difficile à connaître
dans les systèmes multitâches et multi utilisateurs. L'algorithme assure la fin des tâches mais n'assure pas d'autres
critères intéressants au niveau d'un système d'exploitation tel quel'équité entre les processus. On peut améliorer ceci parl'introduction de critères de choix du processus élus en cas ouplusieurs choix sont possibles (FIFO, SJF, …).
10/10/2016 Khaled Hassine 65
Esquive des interblocages
Prévention des interblocages
Généralités
Détection et guérison
PLAN
10/10/2016 66
Modélisation de l’interblocage
Khaled Hassine
Faculté des Sciences de GabesDépartement d’informatique
10/10/2016
Cours Système d'exploitation 23
Avertissement et Evacuation
10/10/2016 Khaled Hassine 67
Détection des interblocages
La méthode se base sur l'utilisation des graphesd'allocation de ressources.
La détection des interblocages s'effectue par réductiondu graphe : si une demande de processus peut être satisfaite, on
l'effectue et on libère la ressource ; le graphe est alors réduit de ce processus et des ressources
acquises. Il n'y a pas d'interblocage si le graphe peut être réduit
de tous ses processus, sinon l'irréductibilité indiqueun interblocage.
10/10/2016 Khaled Hassine 68
Exemple
10/10/2016 Khaled Hassine 69
Ra
P1
P2
Rb
P3
Faculté des Sciences de GabesDépartement d’informatique
10/10/2016
Cours Système d'exploitation 24
Guérison : Policier
10/10/2016 Khaled Hassine 70
Guérison dans la douleur
Plusieurs techniques pour résoudre l’interblocage: Suspension de tous les processus bloqués,
Solution radicale Guérison dans la douleur
Faire repartir le traitement à partir d'un point decontrôle antérieur,
Suspension successive des processus bloqués, Retrait successif des ressources des processus
bloqués
10/10/2016 Khaled Hassine 71
Guérison par reprise
Reprise au moyen de la préemption : ce type de reprise n'est pas souvent possible, les ressources n'étant pas toutes réquisitionnables (préemptives).
Reprise au moyen du rollback : il est possible de placer des points de reprise sur les processus, en
sauvegardant l'état du processus dans un fichier. Le point de reprise contient l'image mémoire du processus, ainsi que l'état des
ressources. Ce type de reprise est extrêmement coûteux et lourd à mettre en œuvre.
Reprise au moyen de la suppression du processus : si nous tuons un des processus, il libèrera peut-être des ressources nécessaires
à l'exécution d'un des autres du cycle, rompant ainsi le deadlock. problème du choix du processus à tuer.
10/10/2016 Khaled Hassine 72
Faculté des Sciences de GabesDépartement d’informatique
10/10/2016
Cours Système d'exploitation 25
Politique de l'autruche
10/10/2016 Khaled Hassine 73
Politique de l'autruche (Ostrichalgorithm)
Principe : mettre la tête dans le sable comme l'autruche prétendre qu'il n'y a pas de problème
Solution simpliste qui porte ses fruits si le risque d'un deadlock pèse faiblement dans la balance face au coût
(en temps processeur, etc.) des autres algorithmes (enjeu économiquefaible).
la probabilité d’interblocage est faible Exemple, UNIX
ne détecte pas les deadlocks, préférer un éventuel interblocage à des restrictions trop contraignantes
(un seul processus, un seul fichier, etc.) éviter le surcharge du système
10/10/2016 Khaled Hassine 74
10/10/2016 75Khaled Hassine