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.

Énoncé du problème

On considère un système disposant de $n$ types de ressource, dont la quantité totale est connue, constante et finie. Sur ce système, un nombre fini $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 :

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

Algorithme :

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

La partie droite du tableau correspond aux ressources supplémentaires demandées par chaque processus pour chaque type de ressource ($requested$). Pour faire le lien avec les notations de la section précédente : $\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 à $remaining=(1,1,1,0)$.

L'algorithme du banquier revient à :

1. Trouver dans le tableau de droite un processus $P_{i}$ dont les ressources demandées sont toutes inférieures ou égales à celles de disponibles ($\forall j\in \{1,...,n\},requested[i,j]\leq remaining[i]$). Si $i$ n'existe pas, il y a interblocage.
2. Allouer à $P_{i}$ les ressources demandées et attendre se termine.
3. Supprimer la ligne associée à $P_{i}$ et mettre à jour $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 $P_{4}$ les ressources demandées (car $(0,0,1,0)\leq (1,1,1,0)$). On attend que $P_{4}$ s'achève. Une fois $P_{4}$ terminé, $remaining$ passe à $(1,1,1,0)+(1,1,0,1)=(2,2,1,1)$.
2. À l'itération suivante, on peut choisir arbitrairement parmi $P_{1}$ (car $(1,1,0,0)\leq (2,2,1,1)$) ou $P_{5}$ (car $(2,1,1,0)\leq (2,2,1,1)$). Choisissons $P_{5}$. Une fois qu'il se termine, $remaining$ passe à $(2,2,1,1)+(0,0,0,0)=(2,2,1,1)$.
3. À l'itération suivante, $P_{1}$ est le seul processus que l'on peut choisir. Une fois qu'il se termine, $remaining$ passe à $(2,2,1,1)+(3,0,1,1)=(5,2,2,2)$.
4. À l'itération suivante, on peut choisir arbitrairement parmi $P_{2}$ ou $P_{3}$. Choisissons $P_{2}$. Une fois qu'il se termine, $remaining$ passe à $(5,2,2,2)+(0,1,0,0)=(5,3,2,2)$.
5. À l'itération suivante, on choisit $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