Algorithme du banquier

L'algorithme du banquier est un algorithme qui a été mis au point par Edsger Dijkstra en 1965^[1] 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.

Énoncé du problème

On considère un système disposant de ${\displaystyle n}$ types de ressource, dont la quantité totale est connue, constante et finie. Sur ce système, un nombre fini ${\displaystyle m}$ processus. L'état initial du système est caractérisé par la quantité de ressource de chaque type que consomme chacun des processus.

Lorsqu'on alloue à un processus l'ensemble des ressources dont il a besoin, le processus se termine en temps fini et libère les ressources qu'il utilisait. Ceci correspond à un changement d'état.

Le but du problème est de déterminer s'il existe au moins une séquence d'états permettant de terminer l'ensemble des processus. Dans ce cas, l'état initial est dit sûr.

Algorithme

L'algorithme du banquier part du principe que si l'on alloue les ressources à un processus et que celui-ci se termine, on se retrouve dans une situation avec plus de ressources disponible. En conséquence, on peut choisir de manière gloutonne un processus parmi ceux en cours d'exécution et dont les besoins sont compatibles avec les ressources disponibles.

Si l'on parvient à exécuter tous les processus, on a mis en évidence que l'état initial était sûr.

Si par contre, l'algorithme ne parvient plus à progresser alors certains processus sont toujours en cours d'exécution, l'état initial n'est pas sûr et l'algorithme s'interrompt car l'état initial n'est pas sûr.

Paramètres :

• ${\displaystyle n\in \mathbb {N} ^{*}}$ le nombre de ressources.
• ${\displaystyle m\in \mathbb {N} ^{*}}$ le nombre de processus.
• ${\displaystyle available}$ le vecteur de taille ${\displaystyle n}$ tel que ${\displaystyle available[j]}$ indique la quantité de ressource ${\displaystyle j}$ disponible.
• ${\displaystyle allocated}$ la matrice de taille ${\displaystyle m\times n}$ telle que ${\displaystyle allocated[i,j]}$ indique la quantité de ressource ${\displaystyle j}$ initialement allouée au processus ${\displaystyle i}$.
• ${\displaystyle need}$ la matrice de taille ${\displaystyle m\times n}$ telle que ${\displaystyle need[i,j]}$ indique la quantité de ressource ${\displaystyle j}$ requises par le processus ${\displaystyle i}$.

Algorithme :

• Soit ${\displaystyle remaining}$ le vecteur de taille ${\displaystyle n}$ qui indique la quantité de ressource de chaque type encore disponible: ${\displaystyle \forall j\in \{1,...,n\},remaining[j]\leftarrow available[j]-\sum _{i=1}^{m}allocated[i,j]}$.
• Soit ${\displaystyle R}$ l'ensemble des processus en cours de lancement: ${\displaystyle R\leftarrow \{1,...,m\}}$.
• Tant que ${\displaystyle R\neq \emptyset }$:
  • Chercher ${\displaystyle i\in R}$ tel que ${\displaystyle \forall j\in \{1,...,n\},remaining[j]-(need[i,j]-allocated[i,j])\geq 0}$.
  • Si ${\displaystyle i}$ n'existe pas :
    • Retourner l'état initial n'est pas sûr.
  • Sinon :
    • Allouer au processus ${\displaystyle i}$ les ressources qu'il demande et attendre qu'il se termine
    • Terminer le processus ${\displaystyle i}$ : ${\displaystyle R\leftarrow R\backslash \{i\}}$
    • Libération des ressources consommées par ${\displaystyle i}$ : ${\displaystyle \forall j\in \{1,...,n\},remaining[j]\leftarrow remaining[j]+allocated[i,j]}$
• Retourner l'état initial est sûr.

Exemple

On considère dans cet exemple 5 processus actifs ${\displaystyle \{P1,P2,P3,P4,P5\}}$ et mettant en jeu 4 ressources ${\displaystyle \{A,B,C,D\}}$.

État à l'instant t d'un ordinateur : ressources actuellement attribuées et ressources demandées, pour cinq processus (P1 à P5) et quatre ressources (A à D)

Processus	Ressources attribuées				Ressources supplémentaires 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

La partie gauche du tableau correspond à l'état initial du système (${\displaystyle allocated}$). Il indique la quantité de ressource déjà allouée à chaque processus pour chacun des types de ressource. La somme de chaque colonne correspond donc à la quantité de ressources consommées d'un type donnée (on appelle ce vecteur intermédiaire ${\displaystyle total}$).

La partie droite du tableau correspond aux ressources supplémentaires demandées par chaque processus pour chaque type de ressource (${\displaystyle requested}$). Pour faire le lien avec les notations de la section précédente : ${\displaystyle \forall i\in \{1,...,m\},\forall j\in \{1,...,n\},need[i,j]=allocated[i,j]+requested[i,j]}$.

Enfin, on suppose que la quantité restante pour chaque ressource correspond à ${\displaystyle remaining=(1,1,1,0)}$.

L'algorithme du banquier revient à :

1. Trouver dans le tableau de droite un processus ${\displaystyle P_{i}}$ dont les ressources demandées sont toutes inférieures ou égales à celles de disponibles (${\displaystyle \forall j\in \{1,...,n\},requested[i,j]\leq remaining[i]}$). Si ${\displaystyle i}$ n'existe pas, il y a interblocage.
2. Allouer à ${\displaystyle P_{i}}$ les ressources demandées et attendre se termine.
3. Supprimer la ligne associée à ${\displaystyle P_{i}}$ et mettre à jour ${\displaystyle remaining}$.
4. Répéter les étapes précédentes jusqu'à ce que tous les processus soient terminés. Si on y parvient, l'état initial était donc sûr. Sinon il y a eu un interblocage et l'état initial n'était pas sûr.

Dans cet exemple, l'état actuel est sûr car :

1. À la première itération, on choisit forcément ${\displaystyle P_{4}}$ les ressources demandées (car ${\displaystyle (0,0,1,0)\leq (1,1,1,0)}$). On attend que ${\displaystyle P_{4}}$ s'achève. Une fois ${\displaystyle P_{4}}$ terminé, ${\displaystyle remaining}$ passe à ${\displaystyle (1,1,1,0)+(1,1,0,1)=(2,2,1,1)}$.
2. À l'itération suivante, on peut choisir arbitrairement parmi ${\displaystyle P_{1}}$ (car ${\displaystyle (1,1,0,0)\leq (2,2,1,1)}$) ou ${\displaystyle P_{5}}$ (car ${\displaystyle (2,1,1,0)\leq (2,2,1,1)}$). Choisissons ${\displaystyle P_{5}}$. Une fois qu'il se termine, ${\displaystyle remaining}$ passe à ${\displaystyle (2,2,1,1)+(0,0,0,0)=(2,2,1,1)}$.
3. À l'itération suivante, ${\displaystyle P_{1}}$ est le seul processus que l'on peut choisir. Une fois qu'il se termine, ${\displaystyle remaining}$ passe à ${\displaystyle (2,2,1,1)+(3,0,1,1)=(5,2,2,2)}$.
4. À l'itération suivante, on peut choisir arbitrairement parmi ${\displaystyle P_{2}}$ ou ${\displaystyle P_{3}}$. Choisissons ${\displaystyle P_{2}}$. Une fois qu'il se termine, ${\displaystyle remaining}$ passe à ${\displaystyle (5,2,2,2)+(0,1,0,0)=(5,3,2,2)}$.
5. À l'itération suivante, on choisit ${\displaystyle P_{3}}$. Comme tous les processus ont été exécutés avec succès, l'état initial était un état sûr.

Limitations

D'un point de vue pratique, l'algorithme du banquier n'est pas réaliste, car il suppose que l'on connaisse au préalable les ressources dont chaque processus à besoin pour s'achever. Il suppose que ces quantités sont fixes alors qu'en pratique, les besoins d'un processus évoluent dynamiquement.

Voir aussi

• Algorithme de l'autruche
• Dîner des philosophes

Notes et références

1. Edsger Wybe Dijkstra, Selected writings on computing : a personal perspective, Springer-Verlag, 1982 (ISBN 0-387-90652-5, 978-0-387-90652-2 et 3-540-90652-5, OCLC 8533598, lire en ligne)