Les interblocages (Deadlocks)

Un ensemble de processus est en interblocage si chaque processus attend un évènement que seul un autre processus de l'ensemble peut engendrer.

Ressources

Nous avons constaté dans la partie concernant les processus, que lorsqu'un processus demande une ressource et que cette dernière n'est pas disponible, des systèmes sont mis en place (état bloqué, suspendu bloqué, etc). Le plus souvent, nous nous sommes penchés sur le cas de figure d'un processus qui nécessite une ressource, mais en réalité plusieurs processus peuvent être demandeurs de la même ressource, et chacun de ces processus peut demander plus d'une ressource.

Par ressource, nous pouvons comprendre périphérique matériel (lecteur de disquette, imprimante, etc.) ou information (par exemple, un enregistrement verrouillé dans une base de donnée), et dont l'OS peut avoir à gérer en plusieurs exemplaires (par exemple, plusieurs imprimantes).

Dans le cas qui nous préoccupe (les deadlocks), nous pouvons définir une ressource comme tout ce qui ne peut être accédé que par un seul processus à la fois.

Les ressources sont de deux types : réquisitionnables (preemptive ressource) ou non réquisitionnables (non-preemptive ressource).

• Ressource préemptible : elle peut être retirée au processus qui la détient sans risque.
  La mémoire est un exemple de ressource préemptible.
• Ressource non-préemptible : le fait de retirer cette ressource au processus qui la détient provoque des problèmes.

Conditions de Coffman et al

Coffman et al. (1971) ont déterminé les 4 conditions nécessaires à un deadlock. si une seule des conditions n'est pas remplie, nous pouvons éviter l'interblocage.

1. L'exclusion mutuelle (mutual exclusion condition) : Chaque ressource est soit assignée à un seul processus, soit libre.
2. La détention et l'attente (hold and wait condition) : Les processus qui détiennent des ressources peuvent en demander d'autres.
3. Pas de réquisition (non preemption condition) : Les ressources obtenues par un processus ne peuvent lui être retirées, c'est le processus qui les détient qui doit explicitement les libérer.
4. L'attente circulaire (circular wait condition) : Un cycle d'au moins 2 processus, chacun attendant une ressource détenue par un autre processus du cycle.

Stratégies

Quatre stratégies peuvent être mises en place pour traiter le cas des deadlocks :

1. Ignorer le problème
2. Détection et reprise
3. Evitement des interblocages par la gestion de l'allocation des ressources
4. Prévention

Politique de l'autruche (Ostrich algorithm)

Nous pouvons nous mettre la tête dans le sable comme l'autruche et prétendre qu'il n'y a pas de problème...

Cette solution qui semble simpliste porte pourtant ses fruits lorsque le risque d'un deadlock pèse faiblement dans la balance face au coût (en temps processeur, etc) des différents autres algorithmes. Par exemple, les systèmes d'exploitation UNIX ne détectent pas les deadlocks, les utilisateurs préférent un éventuel interblocage à des restrictions trop contraignantes (un seul processus, un seul fichier , etc.).

Détection et reprise (deadlock detection and recovery)

Détection

Dans le cas d'une détection de deadlock avec une seule ressource d'un type donné, nous devons recourir à des graphes. Il existe de nombreux algorithmes de détections des cycles dans les graphes.

Dans le cas d'une détection de deadlock avec plusieurs ressources d'un type donné, nous devons recourir à des matrices. Les algorithmes de détection se basent sur des comparaisons de vecteurs.

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 (preemptives).
• 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 couteux et lourd à mettre en œuvre.
• Reprise au moyen de la suppression du procesus : 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. Ce type de gestion pose le problème du choix du processus à tuer.

Eviter des interblocages (deadlock avoidance)

Un processus ne demande généralement pas la totalité des ressources dont il peut avoir besoin. Les ressourecs sont alors demandées une à la fois. Ce type de constatation peut nous amener à chercher un algorithme qui permet de déterminer quelle ressource accorder à quel processus pour éviter les deadlocks.

Effectuer le bon choix dans l'allocation des ressources implique que le système d'exploitation possède à l'avance certaines informations, ce qui n'est généralement pas possible.

La trajectoire des ressources nous permet une approche graphique assez intuitive, mais 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.

Nous avons vu que dans le cas d'une détection de deadlock avec plusieurs ressources d'un type donné, nous devions recourir à des matrices pour détecter les deadlocks. Ces matrices permettent de déterminer qu'il existe pour un instant donné un état courant.
Cet état est considéré comme sûr s'il n'est pas en deadlock, et s'il est possible de satisfaire toutes les demandes de ressources en exécutant les processus dans un certain ordre. Cet ordre est très important, car un mauvais choix au départ peut mener à un deadlock.
Cette manière de procéder porte le nom des états sûrs et non sûrs (safe and unsafe states).

Prévention

Dans les conditions de deadlock (Coffman et al.), si une seule des 4 conditions n'est pas vérifiée nous évitons l'interblocage. Les cas suivants permettent chacun d'éviter le deadlock en supprimant le risque d'apparition d'une de ces conditions (Havender).

Condition d'exclusion mutuelle (attacking the mutual exclusion condition)

Si nous pouvons empêcher qu'une ressource soit attribuée de manière exclusive, la condition d'exclusion mutuelle n'est pas remplie et nous évitons le deadlock.

L'idée générale est d'éviter d'allouer une ressource si ce n'est pas absolument nécessaire, et de s'assurer que le nombre de processus qui peuvent la demander soit le moins élevé.

Un des moyens est de déplacer le problème en amont. Une imprimante est une ressource qui doit être attribuée de manière exclusive, alors nous pouvons empêcher les processus de la demander directement, et de les forcer à demander la ressource via un spooler. Ce dernier n'est pas exclusif car il travaille avec des files d'attentes, ce qui fait que la ressource en aval est accédée de manière séquentielle.

Ce procédé permet en bien des cas d'éviter le deadlock, mais comme le spooler peut utiliser le disque dur pour stocker les files d'attentes, si l'espace mémoire vient à manquer sur le disque nous nous trouvons à nouveau face à un blocage.

Condition de détention et d'attente (attacking the hold and wait condition)

L'idée est d'empêcher d'allouer de nouvelles ressources aux processus qui en détiennent déjà.

Il est donc possible de briser la condition de détention et d'attente en allouant au processus avant son exécution toutes les ressources dont il peut avoir besoin. Ce type de gestion génère cependant un gaspillage des ressources.

La première approche est la suivante : Si une ou plusieurs ressources dont il peut avoir besoin sont déjà allouées à un autre processus, il attendra que les ressources soient disponibles.
Ce type de procédure peut être valable dans le cas d'un batch (traitement par lots) qui liste toutes les ressources nécessaires en début de job, mais il est généralement impossible de prédire quelles seront les ressources nécessaires.

Une autre approche vise à obliger les processus qui demandent une nouvelle ressource de libérer celle qu'ils détiennent. Ils ne s'exécuteront que quand il sera possible de leur allouer toutes les ressources en une seule fois.

Condition de non-réquisition (attacking the non preemption condition)

La condition de non-réquisition est difficilement contournable, car certaines ressources ne supportent absolument la préemption.

Imaginez une préemption sur un processus d'impression : il faudrait recommencer entièrement le processus.

Condition d'attente circulaire (attacking the circular wait condition)

Une numérotation des ressources permet de briser la condition d'attente circulaire.

Les processus peuvent demander toutes les ressources dont ils ont besoin, à condition de respecter l'ordre croissant de la numérotation des ressources.

Une autre manière de le présenter est de n'allouer à un processus qu'une ressource dont le numéro est supérieur au numéro le plus élevé des ressources qu'il détient.

Résumé

Structure du document