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 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 :

État à l'instant t d'un ordinateur : ressources actuellement attribuées et ressources demandées, pour cinq processus (A à E) et quatre ressources (P1 à P4)
Processus 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 4 3 2) ressources disponibles dispo = exist - total = (1 1 1 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 :

  1. Trouver dans le tableau de droite une ligne L dont les ressources demandées sont toutes inférieures à celles de dispo ( Li \le \, dispoi, pour tout i). S'il n'existe pas L vérifiant cette condition, il y a interblocage.
  2. Supposer que le processus associé à L obtient les ressources et se termine. Supprimer sa ligne et actualiser dispo.
  3. 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.

Voir aussi


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Algorithme du banquier de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • Algorithme Du Banquier — Problèmes classiques des méthodes de synchronisation Couplage fort  Famine Interblocage  Inversion de priorité L algorithme du banquier est un algor …   Wikipédia en Français

  • Algorithme de la boulangerie — L algorithme de la boulangerie (Lamport s bakery algorithm en anglais) est un algorithme d exclusion mutuelle découvert par Leslie Lamport[1], dans le cadre général de machines multi processeurs à mémoire partagée ne fournissant aucune opération… …   Wikipédia en Français

  • Algorithme de Dekker — L algorithme de Dekker est un algorithme d exclusion mutuelle. Il est basé sur une approche par attente active et est divisé en deux parties, à savoir le protocole d entrée dans la section critique et le protocole de sortie. L algorithme présenté …   Wikipédia en Français

  • Algorithme de Peterson — L algorithme de Peterson est un algorithme d exclusion mutuelle. Cet algorithme est basé sur une approche par attente active. Il est constitué de deux parties : le protocole d entrée dans la section critique et le protocole de sortie. L… …   Wikipédia en Français

  • Parallélisme (informatique) — Pour les articles homonymes, voir parallèle. Blue Gene L cabinet., un des ordinateurs massivement parallèle les plus rapides des années 2000 En informatiqu …   Wikipédia en Français

  • Liste Des Algorithmes — Sommaire 1 Liste par catégories 1.1 Compression de données 1.2 Tri 1.2.1 Algorithmes en temps quadratique …   Wikipédia en Français

  • Liste des algorithmes — Sommaire 1 Liste par catégories 1.1 Compression de données 1.2 Tri 1.2.1 Algorithmes en temps quadratique …   Wikipédia en Français

  • Interblocage — Un interblocage (deadlock en anglais, appelé aussi « étreinte fatale ») est un phénomène qui peut survenir en programmation concurrente. L interblocage se produit lorsque deux processus concurrents s attendent mutuellement. Les… …   Wikipédia en Français

  • Couplage fort (programmation concurrente) —  Pour l’article homonyme, voir Couplage.  Le couplage fort se produit lorsqu un algorithme réalise un passage explicite de la main (flux de contrôle) entre les fils d exécution (thread) souhaitant entrer dans une section critique. Dans… …   Wikipédia en Français

  • Famine (informatique) — Pour les articles homonymes, voir Famine. La famine est un problème que peut avoir un algorithme d exclusion mutuelle. Il se produit lorsqu un algorithme n est pas équitable, c est à dire qu il ne garantit pas à tous les threads souhaitant… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”