Algorithme du banquier
Un article de Wikipédia, l'encyclopédie libre.
 |
Cet article est une ébauche concernant l’informatique.
Vous pouvez partager vos connaissances en l’améliorant. (Comment ?).
|
|
|
L'algorithme du banquier est un algorithme qui a été mis au point par Edsger Dijkstra en 1965 pour éviter les problèmes interblocages 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 :
| Ressource | Ressources attribuées | Ressources demandées | ||||||
|---|---|---|---|---|---|---|---|---|
| P1 | P2 | P3 | P4 | P1 | P2 | P3 | P4 | |
| A | 3 | 0 | 1 | 1 | 1 | 1 | 0 | 0 |
| B | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 2 |
| C | 1 | 1 | 1 | 0 | 3 | 1 | 0 | 0 |
| D | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 0 |
| E | 0 | 0 | 0 | 0 | 2 | 1 | 1 | 0 |
| Total | 5 | 3 | 2 | 2 | 6 | 4 | 3 | 2 |
Ressources existantes : exist = (6 3 4 2) ressources disponibles dispo = exist - total = (1 0 2 0)
5 processus sont actifs (A,B,C,D,E) et il existe 4 catégories de périphériques P1 à P4.
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 à 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 à D les ressources demandées et il s'achèvera
- puis on allouera à A ou E les ressources demandées et A ou E 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.
