Algorytm bankiera

Z Wikipedii

Algorytm bankiera - z angielskiego banker's algorithm. Służy on do lokacji zasobów w taki sposób, aby uniknąć zakleszczeń. Jego autorem jest Edsger Dijkstra. Algorytm ten był po raz pierwszy wykorzystany w systemie operacyjnym zwanym THE, a opisany został w języku niderlandzkim w książce pod tytułem EWD108 "Een algorithme ter vooikoming van de dodelijke omarming".

[edytuj] Algorytm

Algorytm bankiera stosowany jest przez system operacyjny kiedy jakikolwiek proces zażąda zasobu. Zapobiega on wystąpieniu zakleszczeń przez odmówienie lub zawieszenie dostępu do zasobu w przypadku, gdyby dostęp do tego zasobu mógł spowodować wejście systemu w stan niebezpieczny (ang. unsafe state).

[edytuj] Zasoby

Aby algorytm bankiera działał potrzebuje wiedzieć trzy rzeczy:

1. Jaką część każdego zasobu każdy proces może zażądać
2. Jaką część każdego zasobu każdy proces aktualnie używa
3. Jaką część każdego zasobu system ma aktualnie dostępną

[edytuj] Przykład

Zakładając, że system rozróżnia 4 rodzaje zasobów (A, B, C i D), następujący przykład obrazuje jak te zasoby mogą być rozmieszczane. Obrazuje on system w momencie przed otrzymaniem nowego żądania o zasób. W przykładzie tym typy i rodzaje zasobów są abstrakcyjne. Prawdziwe systemy zajmowały by większymi ilościami zasobów.

Dostępne zasoby systemu:  
A B C D
3 1 1 2

Procesy (aktualnie zaalokowane zasoby):
   A B C D
P1 1 2 2 1
P2 1 0 3 3
P3 1 1 1 0

Procesy (wartości maksymalne poszczególnych zasobów):
   A B C D
P1 3 3 2 2
P2 1 2 3 4
P3 1 1 5 0