Les politiques de détection et reprise

Le principe consiste à détecter, à intervalles réguliers, les attentes circulaires, puis de permettre la reprise par une action curative.

debut
tant que vrai faire debut
     trouverAttenteCirculaire;
     traiterCycle;
     attendre delaiPeriode;
     fin
fin

traiterCycle utilise généralement une des deux méthodes suivantes :

reprise préemptive :

le système provoque une préemption en retirant une ressource à un processus. Ce processus continue comme il peut.

reprise par élimination :

le système tue un processus, afin que les ressources qu'il détenait soit libérées.

Cas des ressources distinguables

Soit un système et son graphe d'allocation des ressources, trouverAttenteCirculaire est facilement implémentable :

debut
tant qu'il existe un sommet sans prédécesseur faire debut
     enlever les arcs sortants de ce sommet;
     enlever le sommet;
     fin
attenteCirculaire = non (graphe résultant est vide)
fin

Cas général

Il existe des ressources non distinguables (ex : un bloc du disque libre) pour le problème de l'interblocage. Dans ce cas, le graphe des allocations est complexe, et une représentation matricielle est plus aisée et plus efficace.

Un système est composé de $m$ processus et de $n$ types de ressources. Le problème de l'interblocage est décrit par : un vecteur $E=(e_1,e_2,\dots,e_n)$ des ressources existantes, une matrice $T=(t_{11},\dots,t_{mn})$ des ressources tenues, et une matrice $R=(r_{11},\dots,r_{mn})$ des requêtes. On note $O=(0,0,\dots,0)$

trouverAttenteCirculaire(E,T,R) peut alors s'écrire :
debut
$D = E - \sum_{i=1}^{i=m}T_i$;
tant qu'il existe un processus $P_i$ tel que $O < R_i \leq D$ faire debut
$D = D + T_i$;
$R_i = O$;
fin
attenteCirculaire = $(E \neq D)$;
fin

$D$ représente les ressources disponibles. L'idée intuitive est donc : si le système satisfait la requête $R_i$, alors $P_i$ peut terminer son exécution, et rendre ainsi les ressources $T_i$ qu'il détient.

Un exemple

Soit un système composé de 3 processus et de 4 types de ressources.
$E = (5, 2, 3, 1)$, $T = \left( \begin{array}{cccc} 1 & 0 & 1 & 0 \\ 2 & 0 & 0 & 1 \\ 0 & 1 & 2 & 0 \end{array} \right)$, $R = \left( \begin{array}{cccc} 2 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 2 & 1 & 0 & 0 \end{array}\right)$.

L'algorithme trouverAttenteCirculaire(E,T,R) donne :

1. $D = (2, 1, 0, 0)$
2. $O < R_3 \leq D$, donc $R_3 = O$ et $D = (2, 2, 2, 0)$
3. $O < R_2 \leq D$, donc $R_2 = O$ et $D = (4, 2, 2, 1)$
4. $O < R_1 \leq D$, donc $R_1 = O$ et $D = (5, 2, 3, 1)$
5. pas d'attente circulaire

Pour $R = \left( \begin{array}{cccc} 2 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 2 & 1 & 0 & {\mathbf 1} \end{array}\right)$.

L'algorithme trouverAttenteCirculaire(E,T,R) donne :

1. $D = (2, 1, 0, 0)$
2. attente circulaire

Pour $R = \left( \begin{array}{cccc} 2 & 0 & 0 & 1 \\ {\mathbf 3} & 0 & 1 & 0 \\ 2 & 1 & 0 & 0 \end{array}\right)$.

L'algorithme trouverAttenteCirculaire(E,T,R) donne :

1. $D = (2, 1, 0, 0)$
2. $O < R_3 \leq D$, donc $R_3 = O$ et $D = (2, 2, 2, 0)$
3. attente circulaire

Le maintien de l'information

trouverAttenteCirculaire utilise soit un graphe, soit des matrices. Cette information peut être obtenue de deux façons :

• elle est maintenue en permanence à jour par le système (en fait un processus particulier), en tenant compte de tous les appels systèmes (requêtes et libérations).
• elle est calculée chaque fois que nécessaire en utilisant les tables de ressources présentes dans les contextes de chaque processus (liste des périphériques utilisés, listes des fichiers ouverts ...).

Les deux solutions sont coûteuses en temps CPU, la première utilise également de la mémoire en permanence.