Module Systèmes dexploitation Chapitre 8 Interblocage : Évitement et prévention Partie III École Normale Supérieure Tétouan Département Informatique 2008-2009

ModuleModuleSystèmes d’exploitationSystèmes d’exploitation

Chapitre 8

Interblocage : Évitement et prévention

Partie III

École Normale SupérieureÉcole Normale SupérieureTétouanTétouan

Département InformatiqueDépartement Informatique

2008-2009

2

RevueRevue

• Comment est-ce que l’on détecte des interblocages avec des instances multiples de ressources?

• Quelles sont les quatre conditions des interblocages?

3

SynopsisSynopsis

• Évitement des interblocages

• Prévention des interblocages

4

Évitement des interblocagesÉvitement des interblocages

• Jusqu’à date nous avons vue deux solutions aux problème des interblocages: On ignore ou on les détectes et on reprend

• Ne serait t’il pas mieux si, avec une allocation de ressources prudente, nous pourrions empêcher les interblocages?

• Ceci s’appel l’Évitement des interblocages (Deadlock Avoidance)

5


• Pour éviter les interblocages, il est important de ne pas s’avancer vers un état non sécuritaire– Un état est dit sécuritaire (sûr) si il n’est pas

en interblocage et qu’il existe un ordre d’ordonnancement dans lequel chaque processus peut exécuter jusqu’à la fin, même si tout les processus demanderaient immédiatement toutes les ressources dont ils ont besoin pour finir leurs travaux

6


• Un état est sûr si le système peut en sortir sans interblocages

• Ne pas allouer une ressource à un processus si l’état qui en résulte n’est pas sûr

États sûrsÉ. non-sûrs

Impasse

7


• Si tout les processus demandent leurs maximum de ressources, est-ce que l’état de départ est sécuritaire?

Parce que tout les processus pouvaient exécuter jusqu’à la fin, l’état initial était sécuritaire!

8

• Et si le processus A a demandé une ressource simple en premier et qu’il l’a obtenu?

Parce que pas tout les processus ne peuvent pas compléter, l’état vers lequel on est allé était non

sécuritaire!!!C’est ce déplacement vers un état non sécuritaire que

nous devons détecter...


9


• Une façon d’éviter les interblocages pour plusieurs instances d’une seul ressource est l’algorithme du banquier (Banker’s Algorithm)– Modélisé sur la façon qu’un banquier pourrait

approuver des demandes de prêts pour ses clients– L’idée est que chaque client a un montant de crédit

maximum qui est établit. Il est garantie que si ils sont alloués leurs crédit maximum, qu’ils seront capables de compléter leurs travaux pour lesquels les prêts étaient requis et qu’ils vont repayer la banque

10

SA

FES

AFE

UN

SA

FE

UN

SA

FE


• Algorithmes du banquier:– Quand un client fait une demande d’argent,

l’algorithme vérifie si la demande mènerait à un état non sécuritaire, si oui, la demande est refusée

• La détermination est comme nous avons vue précédemment

11

• L’algorithme du banquier fonctionne pour une ressource avec des instances multiples. Mais que faisons-nous pour les ressources multiples?– L’algorithme peut être généralisé en utilisant des

structures de données similaires à celles utilisées pour la détection des interblocages

• Un vecteur des ressources existantes (E) et disponibles (A)• Une matrice de ressources couramment assignées à chaque

processus (C)• Une matrice des ressources que chaque processus

pourraient encore avoir besoin (le maximum) pour compléter (R)


12

• Algorithme du banquier pour les ressources multiples:1) Trouve une rangé dans, R, pour laquelle les ressources

requises (ie: maximum potentiel) est plus petit ou égale au vecteur A. Si cette rangé n’existe pas, le système est non sécuritaire parce que si tout les processus demanderaient leurs maximum de ressources, aucun ne pourrait terminer

2) Assumez que le processus de la rangé choisi demande toutes les ressources dont il a besoin pour terminer. Marquez ce processus comme terminé et ajoutez les ressources au vecteur A

3) Répétez les étapes 1 et 2 jusqu’à ce que tout les processus soient marqués comme terminé (dans ce cas l’état est sécuritaire) ou jusqu’à ce qu’il soit démontré qu’un état non sécuritaire est présent


13

• Est-ce que cet état est sécuritaire?


14


• Est-ce que l’évitement des interblocages avec l’allocation prudente des ressources pratique?– Désavantage: La vérification pour chaque demande

prend du temps: overhead– Désavantage : Les processus doivent savoir a priori

toutes les ressources dont ils ont besoin– Désavantage : Les processus sur le système peuvent

changer, ce qui complique l’algorithme– Réponse: peu de système, si il y en a, utilise

l’algorithme du banquier pour éviter les interblocages

15

Prévention des interblocagesPrévention des interblocages

• Si on brise une des quatre conditions pour l’interblocage, ils n’arriveront jamais– Attaquer la condition de l’exclusion mutuelle

• Presque impossible à enlever. Au lieu d’avoir des interblocages, nous allons avoir des concurrences critiques et des données corrompus sur les CD-ROMs qui ont acceptés de l’information de deux processus simultanément

• Cependant, des fois les ressources peuvent être abstraites. Au lieu d’écrire sur une imprimante, dans Windows on écrit sur un spooler et les jobs sortent à leurs tour

16

• Attaquer la condition de Tenir et Attendre– Requiert que tout les processus demande toutes les

ressources dont ils ont besoin avant de commencer l’exécution. Cela fonctionne (et est utilisé parfois) mais il y a des problèmes

• Problème: Habituellement les processus ne savent pas de quelles ressources ils vont avoir besoin. Si ils le savaient tout le temps, on pourrait utiliser l’algorithme du banquier sans problèmes

• Problème: Si le traitement des données prend du temps avant que le périphérique est utilisé, on a une perte de ressources et un déclin de multiprogrammation

– Alternative: Demander à un processus de relâcher toutes les ressources qu’il a avant d’en demander un autre


17

Prévention des interblocages (note)Prévention des interblocages (note)

• Verrouillage à deux phases (Two-Phase Locking)– Une méthode qui brise la condition de tenir et

attendre et qui est utilisé dans la vraie vie pour les bases de données

– Un processus qui veut mettre à jour un nombre d’enregistrements (records) essaie de tout les verrouillés. Si un des enregistrements est déjà verrouillé, il relâche tout les enregistrements et essaie encore

– Si il réussi, il met à jour tout les records et relâche les verrous

• Pas un choix santé pour les systèmes en temps réel par contre...

18


• Attaquer la condition de non préemption– Ceci est essentiellement pas possible. Très

peux de périphériques peuvent souffrir une préemption durant l’utilisation et cela prendrait une grande quantité de matériel pour le permettre (si cela est possible en premier lieu!)

– C’est la même chose pour les ressources virtuelles. Il est très difficile de faire de la préemption sur les bases de données sans faire beaucoup de travail.

19


• Attaquer la condition de l’attente circulaire– Permettre au processus de tenir seulement une

ressource à la fois• Pas faisable. Pourquoi?

– Donner un numérotage des ressources global; exiger que tout les programmes demandes les ressources dans cet ordre

• De cette façon, un cycle ne peut jamais ce produire… un processus va toujours demander une ressource qui a été demandé et va bloquer

• Problème: Cela peut-être difficile de trouver un ordre qui fait à tout les processus. On peut ne pas savoir quel genre de brûleur CD à demander jusqu’à ce que nous ayons certaine autre information

20

• Sommaire– Les méthodes suivantes sont disponibles pour nous

permettre de prévenir les interblocages. La plus part sont difficile ou non pratique. La plus part des systèmes utilisent la méthode de l’autruche...

Condition Approche

Exclusion Mutuelle Spool tout

Tenir et attendreDemander toutes les ressources initialement

Pas de Préemption Enlever les ressources

Attente circulaire Ordre numérique des ressources


21

Quiz Time!Quiz Time!

Questions?

Documents

Module Systèmes dexploitation Chapitre 8 Interblocage : Évitement et prévention Partie III École Normale Supérieure Tétouan Département Informatique 2008-2009