GEF 435Principes des systèmes d’exploitation

Interblocage(Tanenbaum 3.1, 3.2, 3.3)

Revue

• Quels facteurs sont pris en ligne de compte quand on veut désigner une grandeur de quantum pour l’ordonnance tourniquet (Round-Robin)?

• Comment est-ce que l’ordonnance du processus le plus court le prochain fonctionne dans un système interactif?

Synopsis

• Ressources• Introduction aux interblocages• Conditions pour l’interblocage• Modélisation des interblocages• Stratégies pour faire face aux interblocages

L’algorithme de l’autruche (Plus à la prochaine classe)

Ressources

• Les processus on souvent besoin d’accès exclusifs aux ressources (mémoire, fichiers, périphériques, …) pour exécuter leurs fonctions

Peut être du matériel, ie: tape drivePeut être de l’information, ie: enregistrement dans une

base de donnéesOn peut avoir plusieurs copies des ressources qui

existent, ie, on peut avoir deux CD-ROMs sur un PCPour cette section sur les interblocages, nous référons à

la collection d’objets qui peuvent être réservés exclusivement par un processus comme étant des ressources

Ressources

• Les ressources nous viennent en deux saveurs:Une ressource qui est non-préemptible ne peut pas être enlevé

à un processus• eg: un écrivain de CD-ROM durant un enregistrement

Une ressource qui peut être préemptée est une ressource qui peut être enlevée

• La mémoire est une ressource. Un processus qui exécute dans la mémoire peut être swapé pour un autre processus pour exécuter

• Considérez: deux processus où un seul à la fois peur être en mémoire. Si le premier processus obtient l’imprimante et est ensuite swapé; et que par la suite le deuxième processus a besoin de l’imprimante, on pourrait avoir un interblocage.

• Cependant parce que la mémoire est préemptive la situation peut être résolue en suspendant un des processus.

Ressources

• En général les ressources non-préemptives sont un requis pour avoir un interblocageCe cours se penche sur les ressources qui ne sont pas

préemptives

• Notre abstraction des processus qui utilisent les ressources:Demande la ressource (bloque si la ressource n’est pas

disponible)Utilise la ressourceRelâche la ressource

Définition de l’interblocage

• Définition formelle:Un ensemble de processus sont en interblocage si chaque

processus attend pour un événement que seulement un autre processus dans l’ensemble peut causer

• Donc les processus dans l’ensemble ne vont pas s’éveiller parce qu’ils attendent après d’autres processus dans l’ensemble qui ne s’éveilleront jamais

• Supposition: chaque processus a un seul fil d’exécution et aucune interruption ne peut éveiller un processus qui est bloqué

Conditions pour l’interblocage

• Il y a quatre conditions pour engendrer un interblocage. Si une de ces conditions est absente, l’interblocage est impossible

1. Condition d’exclusion mutuelle. Chaque ressource est couramment utilisée par exactement un processus ou n’est pas disponible

2. Condition de tenir et attendre.(hold and wait) Les processus qui tiennent des ressources allouées plutôt, peuvent demander de nouvelles ressources (et possiblement attendre)

Conditions pour l’interblocage

• Il y a quatre conditions pour engendrer un interblocage:

3. Condition de non-préemption. Les ressources qui ont étés assignées auparavant ne peuvent pas être enlevées de force à un processus. Elles doivent être relâchées explicitement par le processus qui les tient

4. Condition d’attente circulaire. Il doit y avoir une chaîne d’attente circulaire avec deux processus ou plus, chacun d’entre eux attendant pour une ressource tenue par un autre membre dans la chaîne

Modélisation de l’interblocage

• Les graphes dirigés peuvent être utilisés pour modéliser les interblocages :

R A

Ressource ‘R’ Processus ‘A’

Ressource ‘R’ donnée au

processus ‘A’

R AProcessus ‘A’ attend pour la ressource ‘R’

Modélisation de l’interblocage

• Comment est-ce que les interblocages sont représentés graphiquement?C’est une boucle fermée dans un graphe dirigé

Modélisation de l’interblocage

• Comment peut-on utiliser les graphes dirigés?Ce sont des outils qui nous laissent voir si une

séquence d’allocation et relâche de ressources vont entraîner un interblocage

Exemple: trois processus, A, B, et C et trois ressources R, S, et T.

• A peut utiliser R et S, • B peut utiliser S et T, et • C peut utiliser T et R

Modélisation de l’interblocage

A demande RB demande SC demande T

• Est-ce que cela nous aide à prévenir les interblocages?• Pas encore; plus tard nous allons voir comment cette vérification

visuelle peut être implémentée comme un algorithme pour détecter les interblocages

A demande SB demande TC demande Rinterblocage!

Stratégies pour les interblocages

• On sait comment les interblocages arrivent, mais que peut-on faire pour les arrêter? Quatre stratégies: Ignorer le problème (L’algorithme de l’autruche)Détection et reprise

• Laisser l’interblocage arriver, mais les détecter et prendre action pour les corriger

Évitement dynamique• Allouer les ressources très judicieusement

Prévention• Empêcher une des quatre conditions discutées plus tôt

Stratégies pour les interblocages

• L’algorithme de l’autrucheAccepter les interblocages et n’avoir aucun plan pour

les réglerEntre amis que veut dire l’écran bleue de la mort de

toute façon?

Stratégies pour les interblocages

• L’algorithme de l’autrucheActuellement une solution très viable

• Si la probabilité d’interblocage est d’une fois par année, et que le matériel demande d’être redémarré chaque jour, est-ce qu’une solution d’interblocage très robuste est requise (temps et $)?

Ce genre d’algorithme est utilisé pour Unix et Windows:

• Il y a un nombre de processus limité (N) qui peut être démarré. Si X processus ont (N-1) processus enfants qui exécutent, et que cinq processus de plus sont requis par les processus pour finir leurs job, vous avez un interblocage

Quiz Time!

Questions?