Banker’s algoritme er en algoritme oppfunnet av Edsger Dijkstra. Algoritmen har som formål å unngå vranglås (deadlock) i operativsystemer. Navnet “Banker’s” kommer av at bank systemer teoretisk sett kunne dratt nytte av algoritmen for å ikke gå tom for ressurser i forhold til forespørselen fra kundene. Algoritmen vil sørge for at banker alltid har ressurser disponibelt for dem som trenger det.
Følgende opplysninger kreves for at algoritmen skal fungere:
- MAX – Hvor mye ressurser en prosess kan kreve
- ALLOCATED – Hvor mye ressurser en prosess har fått tildelt
- AVAILABLE – Hvor mye ressurser som systemet har tilgjengelig
Ressurser kan bare tildeles en prosess under følgende forutsetning:
Forespørselen er mindre, eller lik AVAILABLE
Dersom forespørselen er høyere enn AVAILABLE, må prosessen vente på ledige ressurser.
| Prosess | ALLOCATION | MAX | AVAILABLE | NEED |
| ABC | ABC | ABC | ABC | |
| P0 | 010 | 753 | 332 | 743 |
| P1 | 200 | 322 | 122 | |
| P2 | 302 | 902 | 600 | |
| P3 | 211 | 222 | 011 | |
| P4 | 002 | 433 | 431 |
Starter med å finne NEED ved å trekke fra ALLOCATION fra MAX for alle prosessene.
Ny AVAILABLE = AVAILABLE + ALLOCATION
| Prosess | ALLOCATION | MAX | AVAILABLE | NEED |
| ABC | ABC | ABC | ABC | |
| P0 | 010 | 753 | 332 | 743 |
| P1 | 200 | 322 | 532 | 122 |
| P2 | 302 | 902 | 743 | 600 |
| P3 | 211 | 222 | 745 | 011 |
| P4 | 002 | 433 | 755 | 431 |
| 1057 | ||||
P0 krever 743. Er 743 mindre eller lik 332? Nei. Gå videre til neste prosess.
P1 krever 122. Er 122 mindre eller lik 332? Ja. Ny AVAILABLE blir 332 + 200 = 532
P2 krever 600. Er 600 mindre eller lik 532? Nei. Gå videre til neste prosess.
P3 krever 011. Er 011 mindre eller lik 532? Ja. Ny AVAILABLE blir 532 + 211 = 743
P4 krever 431. Er 431 mindre eller lik 743? Ja. Ny AVAILABLE blir 743 + 002 = 745
Så går vi tilbake til toppen av lista, og fortsetter med de prosessene som vi hoppet over.
P0 krever 743. Er 743 mindre eller lik 745? Ja. Ny AVAILABLE blir 745 + 010 = 755
P2 krever 600. er 600 mindre eller lik 755? Ja. Ny AVAILABLE blir 755 + 302 = 1057
Rekkefølgen blir: P1, P3, P4, P0, P2
Oppgave
| Prosess | ALLOCATION | MAX | AVAILABLE | NEED |
| ABCD | ABCD | ABCD | ABCD | |
| P0 | 0012 | 0012 | 1520 | |
| P1 | 1000 | 1750 | ||
| P2 | 1354 | 2356 | ||
| P3 | 0632 | 0652 | ||
| P4 | 0014 | 0656 |
Spørsmål: Hva er innholdet i matrisen Need (trenger/behov)?
Starter med å finne NEED for hver prosess ved å trekke fra ALLOCATION fra MAX.
| Prosess | ALLOCATION | MAX | AVAILABLE | NEED |
| ABCD | ABCD | ABCD | ABCD | |
| P0 | 0012 | 0012 | 1520 | 0000 |
| P1 | 1000 | 1750 | 750 | |
| P2 | 1354 | 2356 | 1002 | |
| P3 | 0632 | 0652 | 0020 | |
| P4 | 0014 | 0656 | 0642 |
P0 krever 0000. Er 0000 mindre eller lik 1520? Ja. Ny AVAILABLE blir 1520 + 0012 = 1532
P1 krever 750. Er 750 mindre eller lik 1532? Ja. Ny AVAILABLE blir 1532 + 1000 = 2532
P2 krever 1002. Er 1002 mindre eller lik 2532? Ja. Ny AVAILABLE blir 2532 + 1354 = 3886
P3 krever 0020. er 0020 mindre eller lik 3886? Ja. Ny AVAILABLE blir 3886 + 0632 = 4518
P4 krever 0642. Er 0642 mindre eller lik 4518? Ja. Ny AVAILABLE blir 4518 + 0014 = 4532
| Prosess | ALLOCATION | MAX | AVAILABLE | NEED |
| ABCD | ABCD | ABCD | ABCD | |
| P0 | 0012 | 0012 | 1520 | 0000 |
| P1 | 1000 | 1750 | 1532 | 750 |
| P2 | 1354 | 2356 | 2532 | 1002 |
| P3 | 0632 | 0652 | 3886 | 0020 |
| P4 | 0014 | 0656 | 4518 | 0642 |
| 4532 | ||||
Rekkefølge: P0, P1, P2, P3, P4
Hvis systemet klarer å fordele ressurser til alle prosessene, er systemet i “safe state”. Hvis systemet ikke klarer å fordele ressurser til alle prosessene i systemet, er systemet i “unsafe state”. I begge eksemplene ovenfor er systemet i “safe state” siden det klarer å fordele ressurser til alle prosessene.
Spørsmål 2: Dersom en forespørsel fra prosess P1 kommer med verdiene (0,4,2,0). Kan denne forespørselen bli gitt umiddelbart?
P1 krever 0420. Er 0420 mindre eller lik 1520? Ja. Ny AVAILABLE blir 1532 + 1000 = 2532. Forespørselen kan bli gitt umiddelbart.
Håper dette ga en bedre forståelse for hvordan Banker’s algoritme fungerer.