Interblocage

Concept

Les interblocages surviennent lorsque des processus essaient de réserver une ressource qui ne sera jamais libérée. La plupart des systèmes d'exploitation gèrent les interblocages à l'aide de l'Ostrich algorithm (le gain ne valant l'effort).
Définitions:
Deux types de ressources:
  1. Ressource non-retirable : ressource qui ne peut être retirée sans dommage au processus l'ayant réservée.
    Ex. imprimante, fichier, sémaphore, verrou d'une base de données.
  2. Ressource retirable : ressource qui peut être retirée sans dommage au processus l'ayant réservée (pose moins de problèmes puisque ces ressources peuvent être retirées au besoin au profit d'autres processus).
    Ex. Processeur et mémoire mais pas à n'importe quel moment, carte réseau, carte graphique.
L'utilisation de ressources se fait en trois étapes:

Exemple d'interblocage

Supposons un système possédant les ressources 1 et 2, ayant les processus A et B en exécution. Une façon de provoquer un interblocage est la suivante :
  1. Le processus A réserve la ressource 1;
  2. Le processus B réserve la ressource 2;
  3. Le processus A demande la ressource 2, et tombe en attente;
  4. Le processus B demande la ressource 1, et tombe en attente;
  5. Interblocage !

Représentation et détection

Apparition d'interblocages

Conditions (Coffman's conditions):

Modélisation des interblocages

On modélise les interblocages à l'aide de graphes orientés conçus de la façon suivante:
  • Les processus sont représentés pas des cercles.
  • Les ressources sont représentées par des carrés.
  • Une flèche qui va d'un carré à un cercle indique que la ressource est déjà attribuée au processus (figure a).
  • Une flèche d'un cercle vers un carré indique que le processus est bloqué en attente de cette ressource (figure b).
  • Les interblocages sont représentés dans ces graphiques par la présence d'un cycle (figure c)
Modélisation des interblocages

Exemple de graphe

Supposons que les trois processus A, B et C effectuent les demandes de ressources illustrées aux figures a), b) et c). Il est possible qu'il y ait interblocage si l'ordonnanceur permet à ces processus de réserver leurs ressources comme indiqué en d). En tel cas, la situation évolue de l'image e) à l'image j).
Apparition d'un interblocage

Si l'OS pouvait voir venir l'interblocage, il pourrait ordonnancer différemment les processus. Par exemple, il pourrait ne pas ordonnancer B avant l'étape q) et ainsi il n'y pas d'interblocage. Après q), B pourrait être ordonnancé et obtenir S et T, en quel cas il attendrait mais sans interblocage.

Nous réétudierons cette stratégie plus loin.
Évitement d'un interblocage

Exemple sous Windows d'interblocage

Exemple avec des threads interbloquants avec sémaphore: zip

Gestion des interblocages

Politique de gestion des interblocages:
  1. Ignorer les problèmes (cela n'est pas rentable).
  2. Les détecter et y remédier.
  3. Les éviter de manière dynamique en allouant les ressources avec précaution.
  4. Les prévenir en empêchant l'apparition d'une des quatre conditions.
Nous allons nous attarder aux politiques 2 à 4. Même si la première est largement utilisée, elle présente un intérêt théorique très limité. Signalons seulement que la rentabilité est le moteur de beaucoup de décisions et qu'il ne faut pas sous-estimer l'importance de ce facteur.

2) Détection des interblocages

On obtient le graphe a) à partir de la situation suivante :

Processus Ressources demandées Ressource détenues
A 2 1
B 3  
C 2  
D 2 et 3 4
E 5 3
F 2 6
G 4 5

Il y a interblocage des processus D, E et G puisqu'ils forment un cycle avec les ressources 3, 4 et 5 (figure b).
Détection : une ressource de chaque type

Exemple sous Windows de détection de cycles

Exemples de en C++ : zip (console)

Détection plusieurs ressources de chaque type

Les structures de données utilisées :
  • Il y a n processus et m types de ressources.
  • Les Ei représentent le nombre total d'instances de chaque ressource.
  • Les Ai représentent le nombre d'instances disponibles de chaque ressource.
  • La matrice C représente les allocations courantes. Les lignes correspondent aux processus (il y en a n), et les colonnes correspondent aux ressources (il y en a m). L'élément Ci,j indique le nombre de ressources détenues par le processus i de la ressource j.
  • La matrice R (request) représente les demandes de ressources, sur le même format que la matrice C. Ainsi, la case Ri,j donne le nombre de ressources de type j demandées par le processus i.
  • On dira que A < B, ssi Ai < Bi, pour tout i.
L'algorithme
  1. Tant qu'au moins un processus non marqué est tel que Ri,* < A
  2.     Choisir l'un des processus non marqué tel que Ri,* < A
  3.     on ajoute Ci,* à A
  4.     on marque Pi.

Cet algorithme choisit un processus dont les demandes peuvent être satisfaite, et l'exécute jusqu'à la fin. Il libère alors ses ressources et le marque. À la fin, tous les processus non marqués sont en interblocage.
Détection plusieurs ressource de chaque type

Exemple sans interblocage:
  • les demandes de P3 peuvent être remplies. Celui-ci libère ensuite ses ressources ce qui ajoute une table traçante et deux scanners par rapport à la situation initiale.
  • Le processus P2 peut ensuite s'exécuter et libérer ses ressources, dont un CD-ROM.
  • Le processus P1 peut alors terminer ses réservations.
Exemple de détection à plusieurs ressources (pas d'interblocage)


Exemple avec interblocage:
  • Le processus P1 ne peut être satisfait.
  • Le processus P2 ne peut être satisfait.
  • Le processus P3 ne peut être satisfait.                                                                                        
Exemple de détection à plusieurs ressources (avec interblocage)

Reprise d'un interblocage

Trois solutions possibles :
  1. La préemption : certaines ressources, de par leur nature peuvent être retirées temporairement (parfois avec une intervention humaine).
  2. Point de reprise (rollback) : à certains points clé, les états des processus sont enregistrés afin de pouvoir être restaurés ultérieurement. Lors d'un interblocage, un processus est ramené à un point de reprise antérieur à l'acquisition de la ressource.
  3. Suppression des processus : on peut tuer un processus pris en interblocage afin de libérer ses ressources. Un autre processus qui n'est pas dans le coup peut également être tué, si ça marche... ça marche.

3) Évitement des interblocages

Le schéma de l'allocation des ressources :
  • L'axe horizontal représente les instructions exécutées par le processus A.
  • L'axe vertical représente les instructions exécutées par le processus B.
  • Au point I1 le processus A demande l'imprimante.
  • Au point I2 le processus A demande la table traçante.
  • Au point I3 le processus A libère l'imprimante.
  • Au point I4 le processus A libère la table traçante.
  • Au point I5 le processus B demande table traçante.
  • Au point I6 le processus B demande l'imprimante.
  • Au point I7 le processus B libère table traçante.
  • Au point I8 le processus B libère l'imprimante.
  • Les zones grises sont interdites.
  • À partir du point t, il faut exécuter jusqu'à I4 sinon il y aura interblocage.
Allocation prudente des ressources

Les états sûrs et non sûrs

Un état est dit sûr s'il existe un ordonnancement qui permet à chaque processus de s'exécuter jusqu'au bout, même si chacun demande son maximum de ressources. Un état qui ne répond pas à ce critère est dit non sûr. Pour ces algorithmes, il faut que le nombre maximal de ressources pouvant être demandées par chaque processus soit connu.

a) est un état sûr puisqu'il existe un ordonnancement qui permet de terminer tous les processus :
  • Le processus P2 réserve ses ressources, puis les libère (b et c).
  • Le processus P3 réserve ses ressources, puis les libère (d et e).
  • Le processus P1 réserve ses ressources, puis les libère.
Un état sûr
Ici a) est un état sûr et b) est un état non sûr puisqu'il n'existe pas d'ordonnancement qui permet de terminer tous les processus :
  • À partir de b), seul le processus B peut réserver toutes ses ressources.
  • S'il le fait, on arrive à l'état c), et lorsqu'il les libère, on se retrouve en d).
  • En d), A a besoin de cinq ressource et B aussi. Hors, il n'y a que quatre ressources de libre, aucun ne libèrera ses ressources et il y a interblocage.
  • Conclusion, on ne pouvait pas accepter la demande de ressources de A au point a). Donc a) est un état sûr, mais b) est un état non sûr.
Un état non sûr

L'algorithme du banquier utilise la métaphore d'un banquier d'une petite ville qui dispose d'un certain montant d'argent à prêter à ses clients. Les clients sont des processus, l'argent correspond aux ressources et le banquier à l'OS.

L'algorithme vérifie si une requête mène à un état non sûr et la refuse en telle cas. Sinon, tant que les requêtes laissent un état sûr derrière, elles sont allouées.

  1. État initial
  2. Après quelques transactions, un état sûr.
  3. B réserve une ressource et l'état devient non sûr, on refuse la demande (en le bloquant).
Algorithme du banquier

Implantation de l'algorithme du banquier

Les données
  • Les deux tables conservent les ressources attribuées et demandées par les processus.
  • Le vecteur E garde le nombre de ressources existantes.
  • Le vecteur P garde le nombre de ressources attribuées.
  • Le vecteur A garde le nombre de ressources disponibles.
L'algorithme
  1. Rechercher une rangée non marquée dont les demandes peuvent être satisfaites (inférieures à A).
  2. Marquer ce processus et ajouter toutes ses ressources au vecteur A.
  3. Recommencer les étapes 1 et 2 jusqu'à ce que tous les processus soient marqués (état sûr) ou qu'il ne reste plus de processus dont les demandes peuvent être résolues (état non sûr).
L'état représenté ci-contre est sûr. En effet, il est possible de satisfaire D puis A puis B, C et E dans un ordre quelconque.
Algorithme du banquier avec plusieurs ressources


Ici l'état est encore sûr. Par contre, si E demande un lecteur CD-ROM, on doit la refuser car cela conduit à un état non sûr.
Algorithme du banquier avec plusieurs ressources (non sûr en vue)

4) La prévention des interblocages

On peut s'attaquer aux quatre conditions de l'interblocage en essayant de les éliminer, empêchant ainsi tout interblocage. L'idée est cependant plus simple à écrire qu'à comprendre !

  1. La condition d'exclusion mutuelle : le fait de ne pas réserver exclusivement les ressources permet d'éliminer cette condition. Un démon d'impression est un exemple de solution de ce type.
  2. La condition de détention et d'attente : on peut exiger que tous les processus commandent toutes leurs ressources avant de commencer à les utiliser. Cette solution, en plus de mal utiliser les ressources exigent de connaître par avance les ressources nécessaires. En tel cas, un algorithme du banquier ferait l'affaire.
  3. La condition de non-préemption : cette solution est au mieux très délicate et au pire impossible. Penser à une table traçante que l'on retirerait.
  4. la condition d'attente circulaire : on peut interdire l'accès à plusieurs ressources, ce qui est un peut contraignant. Une autre solution consiste à ordonner les ressources et exiger que celles-ci soient réservées dans un ordre précis. Un processus demandant une ressource d'ordre inférieure à l'une qu'elle détient se la verra alors refusée. Il peut arriver qu'il ne soit pas possible en pratique d'ordonner les ressources. De plus, cela est contraignant pour les processus.