Algorithme du banquier

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

v · d · m
Synchronisation en programmation concurrente
Principes de base Atomicité • Section critique • Communication inter-processus • Thread Local Storage
Patrons de conception Barrière de synchronisation • Futex • Futures • Moniteur • Mutex • Sémaphore • Spinlock • Algorithme de Peterson • Algorithme de Dekker • Algorithme du banquier
Problèmes classiques Couplage fort • Famine • Interblocage • Inversion de priorité • Conditions de concurrence

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

  • 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

  • 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

  • Barrière de synchronisation — Une barrière de synchronisation permet de garantir qu un certain nombre de tâches ait passé un point spécifique. Ainsi, chaque tâche qui arrivera sur cette barrière devra attendre jusqu à ce que le nombre spécifié de tâches soient arrivées à… …   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

Share the article and excerpts

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