Graphes d'allocation de ressources

Une des méthodes de détection des interblocages est de tracer un graphe d'allocation des ressources et des requêtes. Ensuite, on réduit ce graphe pour obtenir le graphe réduit d'allocation.

Le graphe représente donc l'état du système. Le point à l'intérieur de chaque ressource représente une instance de la ressource (un point d'accès). Pour chaque requête de ressource, une flèche est tracée à partir du processus jus'qu'au rectangle de la ressource. Pour chaque requête accordée, une flèche est tracée depuis le point de la ressource jusqu'au processus.

Il reste à déterminer si le système est en interblocage en réduisant ce graphe :

1. Si une ressource ne possède que des départs de flèches, il faut effacer toutes ses flèches.
2. Si un processus n'a que des arrivées de flèches, il faut effacer toutes ses flèches.
3. Si un processus a des flèches de départ, mais qu'aucun point de la ressource n'est disponible, on supprime tous les flèches du processus.

   On recommence cette procédure tant qu'on trouve un processus dont on peut effacer les flèches. Le système est en interblocage si il ne reste plus de flèche.