Algorithme du banquier
L'algorithme du banquier est un algorithme qui a été mis au point par Edsger Dijkstra en 1965 pour éviter les problèmes d'interblocage et gérer l'allocation des ressources.
Cet algorithme est nommé ainsi car il reproduit le modèle du prêt à des clients par un banquier.
Considérons les deux tableaux suivants qui résument l'état d'un ordinateur à l'instant t :
| Processus | Ressources attribuées | Ressources demandées | ||||||
|---|---|---|---|---|---|---|---|---|
| A | B | C | D | A | B | C | D | |
| P1 | 3 | 0 | 1 | 1 | 1 | 1 | 0 | 0 |
| P2 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 2 |
| P3 | 1 | 1 | 1 | 0 | 3 | 1 | 0 | 0 |
| P4 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 0 |
| P5 | 0 | 0 | 0 | 0 | 2 | 1 | 1 | 0 |
| Total | 5 | 3 | 2 | 2 | 6 | 4 | 3 | 2 |
Ressources existantes : exist = (6 4 3 2)
Ressources disponibles : dispo = exist - total = (6 4 3 2) - (5 3 2 2) = (1 1 1 0)
5 processus sont actifs (P1, P2, P3, P4, P5) et il existe 4 catégories de périphériques A à D.
Le tableau de gauche donne les ressources déjà allouées et le tableau de droite les ressources qui seront encore demandées pour achever l'exécution.
Un état est dit sûr s'il existe une suite d'états ultérieurs qui permette à tous les processus d'obtenir toutes leurs ressources et de se terminer.
L'algorithme suivant détermine si un état est sûr :
- Trouver dans le tableau de droite une ligne L dont les ressources demandées sont toutes inférieures ou égales à celles de dispo ( Li dispoi, pour tout i). S'il n'existe pas L vérifiant cette condition, il y a interblocage.
- Supposer que le processus associé à L obtient les ressources et se termine. Supprimer sa ligne et actualiser dispo.
- Répéter 1 et 2 jusqu'à ce que tous les processus soient terminés (l'état initial était donc sûr) ou jusqu'à un interblocage (l'état initial n'était pas sûr)
Dans cet exemple, l'état actuel est sûr car :
- on allouera à P4 les ressources demandées et il s'achèvera
- puis on allouera à P1 ou P5 les ressources demandées et P1 ou P5 s'achèvera
- enfin les autres
L'inconvénient de cet algorithme est le caractère irréaliste de la connaissance préalable des ressources nécessaires à l'achèvement d'un processus. Dans bien des systèmes, ce besoin évolue dynamiquement.
