Bankarov algoritam

Bankarov algoritam je algoritam alokacije resursa i izbegavanja kružne blokade (engl. deadlock) koji je razvio Edsger Dajkstra. Algoritam testira bezbednost simulirajući maksimalnu predodređenu alokaciju svih resursa a zatim proverava da li je stanje sigurno odnosno da li može doći do kružne blokade i u zavisnosti od toga odlučuje da li će nastaviti sa alokacijom.

Algoritam je prvobitno razvijen za THE operativni sistem i opisan (na Holandskom jeziku) u EWD108.^[1] Kada se pojavi novi proces, on deklariše maksimalan broj primeraka svakog tipa resursa koji može da koristi, očigledno, ovaj broj ne može biti veći od ukupnog broja resursa u sistemu. Takođe kada proces dobije sve resurse koje je zahtevao, mora ih vratiti u ograničenom vremenu.

Resursi

Da bi Bankarov algoritam radio, tri stvari moraju biti poznate:

Količina svakog resursa koji svaki proces može da zahteva[MAKSIMALNO]
Količina svakog resursa koji svaki proces trenutno zauzima[ALOCIRANO]
Količina svakog resursa kojom sistem trenutno raspolaže[DOSTUPNO]

Resursi mogu biti dodeljeni procesu samo ako zadovoljava sledeće uslove:

traženo ≤ maksimalno, u suprotnom preći u stanje greške jer je proces prekoračio maksimalnu količinu resursa koje je zahtevao.
traženo ≤ dostupno, u suprotnom proces čeka dok se resursi ne oslobode.

Neki od resursa koji se zahtevaju u realnim situacijama su memorija, semafore i pristup interfejsu.

Bankarov algoritam je dobio ime po tome što bi mogao da se koristi u bankarskim sistemima i osigura da banka nikada ne ostane bez resursa jer banka nikada ne bi izdvojila novac na način koji bi onemogućio podizanje novca svih svojih mušterija. Korišćenjem Bankarovog algoritma, banka osigurava da kada mušterije podižu novac, banka nikada ne napušta sigurno stanje. Ako zahtev mušterije ne prouzrokuje napuštanje sigurnog stanja banke, mušterija će podići novac, u suprotnom mušterija mora čekati dok neka druga mušterija ne uloži dovoljno novca.

Osnovne strukture podataka koje se moraju koristiti za implementaciju Bankarovog algoritma:

Neka je n broj procesa u sistemu i m broj tipova resursa. Tada su nam potrebne sledeće strukture podataka:

Dostupno: Vektor dužine m koji označava broj slobodnih resursa svakog tipa. Ako je Dostupno[j] = k, postoji k primeraka resursa tipa R_j koji su dostupni.
Maks: n×m matrica koja definiše maksimalnu potražnju svakog resursa. Ako je Maks[i,j] = k, tada P_i može da zahteva najviše k primeraka resursa tipa R_j.
Alocirano: n×m matrica koja definiše količinu resursa svakog tipa koji su trenutno dodeljeni svakom od procesa. Ako je Alocirano[i,j] = k, tada proces P_i trenutno alocira k primeraka resursa tipa R_j.
Potrebno: n×m matrica koja označava resurse koje i dalje zahteva svaki od procesa. Ako je Potrebno[i,j] = k, tada P_i zahteva još k primeraka resursa R_j da bi završio svoj zadatak.

Napomena: Potrebno[i,j] = Maks[i,j] - Alocirano[i,j].

Primer

Pretpostavimo da sistem razlikuje 4 tipa resursa, (A, B, C i D), sledi primer kako bi ti resursi mogli biti raspoređeni. Primetiti da ovaj primer prikazuje sistem u trenutku pre pristizanja novog zahteva za resursima. Takođe, tip i broj resursa je apstraktan. Sistemi u stvarnosti bi koristili mnogo veće količine svakog resursa.

Ukupno resursa u sistemu:
A B C D
6 5 7 6

Dostupni resursi sistema:
A B C D
3 1 1 2

Procesi (trenutno alocirani resursi):
   A B C D
P1 1 2 2 1
P2 1 0 3 3
P3 1 2 1 0

Procesi (maksimalna potražnja resursa):
   A B C D
P1 3 3 2 2
P2 1 2 3 4
P3 1 3 5 0

Potrebno = maksimalna potražnja resursa - trenutno alocirani resursi
Procesi (potrebni resursi):
   A B C D
P1 2 1 0 1
P2 0 2 0 1
P3 0 1 4 0

Sigurna i nesigurna stanja

Stanje (kao u primeru iznad) se smatra sigurnim ako je moguće da se svaki od procesa završi. Pošto sistem ne može znati kada će se proces završiti, ili koliko će resursa tražiti do tada, sistem pretpostavlja da će svi procesi, posle nekog vremena, pokušati da dobiju maksimalno resursa i da se završe neposredno nakon toga. To je razumna pretpostavka u većini slučajeva pošto sistem ne interesuje koliko dugo se proces izvršava (makar ne iz perspektive izbegavanja kružne blokade). Takođe ako se proces završi a da ne zahteva svoj maksimum resursa, to samo olakšava posao sistemu. Od sigurnog stanja zavisi da li će proces biti smešten u red spremnih procesa. Sigurno stanje garantuje bezbednost.

Pod datom pretpostavkom, algoritam odlučuje da li je stanje sigurno tako što pokušava da pronađe hipotetički skup zahteva procesa koji bi omogućili svakom procesu da dobije svoj maksimum resursa i da se potom završi (i pritom vrati svoje resurse sistemu). Svako stanje u kom takav skup ne postoji se smatra nesigurnim stanjem.

Primer

Možemo pokazati da je stanje dato u prethodnom primeru sigurno tako što ćemo pokazati da je moguće da svaki proces dobije maksimum resursa i da se zatim završi.

P1 dobija još 2 A, 1 B i 1 D, pri čemu dostiže svoj maksimum
- [dostupni resursi: <3 1 1 2> - <2 1 0 1> = <1 0 1 1>]
- Sistem trenutno poseduje sledeće dostupne resurse: 1 A, 0 B, 1 C i 1 D
P1 se završava i vraća sledeće resurse sistemu: 3 A, 3 B, 2 C i 2 D
- [dostupni resursi: <1 0 1 1> + <3 3 2 2> = <4 3 3 3>]
- Sistem trenutno poseduje sledeće dostupne resurse: 4 A, 3 B, 3 C i 3 D
P2 dobija još 2 B i 1 D, zatim se završava i vraća sve svoje resurse
- [dostupni resursi: <4 3 3 3> - <0 2 0 1>+<1 2 3 4> = <5 3 6 6>]
- Sistem trenutno poseduje sledeće dostupne resurse: 5 A, 3 B, 6 C i 6 D
P3 dobija resurse 1 B i 4 C i završava se
- [dostupni resursi: <5 3 6 6> - <0 1 4 0> + <1 3 5 0> = <6 5 7 6>]
- Sistem sada poseduje sve resurse: 6 A, 5 B, 7 C and 6 D
Pošto su svi procesi mogli da se završe ovo stanje je sigurno

Primetimo da su ovi zahtevi i dobijanje resursa hipotetički. Algoritam ih generiše da proveri sigurnost stanja, ali resursi se zapravo nisu dodeljivali i procesi se nisu završili. Takođe primetiti redosled kojim se ovi zahtevi generišu – ako nekoliko zahteva može biti ispunjeno – nema razlike jer svi hipotetički zahtevi omogućavaju procesu da se završi, i na taj način povećavaju slobodne resurse sistema.

Kao primer nesigurnog sistema, razmotrimo šta bi se desilo da je proces 2 zauzimao 1 ili više resursa B na početku.

Zahtevi

Kada sistem primi zahtev za resursom, on pokreće Bankarov algoritam da odredi da li je bezbedno odobriti taj zahtev. Algoritam je jednostavan kada se razume razlika između sigurnog i nesigurnog stanja.

Da li se zahtev može odobriti?
- Ako ne, zahtev je nemoguć i mora se odbiti ili staviti na listu čekanja
Pretpostaviti da je zahtev odobren
Da li je novo stanje sigurno?
- Ako jeste odobriti zahtev
- U suprotnom odbiti zahtev ili ga staviti na listu čekanja

Da li operativni sistem odbija ili odlaže nemoguć ili nesiguran zahtev je odluka koja zavisi od konkretnog operativnog sistema.

Primer

Polazeći iz istog stanja kao u prethodnom primeru, pretpostavimo da proces 3 zahteva 2 jedinice resursa C.

Ne postoji dovoljno dostupnog resursa C da bi zahtev mogao biti odobren
Zahtev je odbijen

Sa druge strane, pretpostavimo da proces 3 zahteva jednu jedinicu resursa C.

Postoji dovoljno resursa da se zahtev odobri
Pretpostavimo da je zahtev odobren
- Novo stanje sistema bilo bi:

    Dostupni resursi sistema
         A B C D
Slobodno 3 1 0 2

    Procesi (trenutno alocirani resursi):
     A B C D
P1   1 2 2 1
P2   1 0 3 3
P3   1 2 2 0

    Procesi (maksimalna potražnja resursa):
     A B C D
P1   3 3 2 2
P2   1 2 3 4
P3   1 3 5 0

Odredimo da li je novo stanje sigurno
1. P1 može dobiti resurse 2 A, 1 B i 1 D i završiti se
2. Zatim, P2 može dobiti resurse 2 B i 1 D i završiti se
3. Na kraju, P3 može dobiti resurse 1B and 3 C i završiti se
4. Odatle sledi da je novo stanje sigurno
Pošto je novo stanje sigurno, odobravamo zahtev

Na kraju, polazeći od početnog stanja, pretpostavimo da proces 2 zahteva jednu jedinicu resursa B.

Postoji dovoljno resursa
Pretpostavljajući da je zahtev odobren, novo stanje će biti:

    Dostupni sistemski resursi:
         A B C D
Slobodno 3 0 1 2

    Procesi (trenutno alocirani resursi):
     A B C D
P1   1 2 2 1
P2   1 1 3 3
P3   1 2 1 0

    Procesi (maksimalna potražnja resursa):
     A B C D
P1   3 3 2 2
P2   1 2 3 4
P3   1 3 5 0

Da li je ovo stanje sigurno? Pretpostavimo da procesi P1, P2, i P3 zahtevaju više resursa B i C.
- P1 ne može dobiti dovoljno resursa B
- P2 ne može dobiti dovoljno resursa B
- P3 ne može dobiti dovoljno resursa B
- Nijedan proces ne može dobiti dovoljno resursa da bi se završio, tako da je stanje nesigurno
Pošto je stanje nesigurno, odbijamo zahtev

/*PROGRAM KOJI IMPLEMENTIRA BANKAROV ALGORITAM
  *   --------------------------------------------*/
#include <stdio.h>
int curr[5][5], maxclaim[5][5], avl[5];
int alloc[5] = {0, 0, 0, 0, 0};
int maxres[5], running[5], safe=0;
int count = 0, i, j, exec, r, p, k = 1;

int main()
{
    printf("\nUnesite broj procesa: ");
    scanf("%d", &p);

    for (i = 0; i < p; i++) {
        running[i] = 1;
        count++;
    }

    printf("\nUnesite broj resursa: ");
    scanf("%d", &r);

    for (i = 0; i < r; i++) { 
        printf("\nUnesite resurs za primerak %d: ", k++);
        scanf("%d", &maxres[i]);
    }

    printf("\nUnesite tabelu maksimalne potraznje resursa:\n");
    for (i = 0; i < p; i++) {
        for(j = 0; j < r; j++) {
            scanf("%d", &maxclaim[i][j]);
        }
    }

    printf("\nUnesite tabelu alociranih resursa:\n");
    for (i = 0; i < p; i++) {
        for(j = 0; j < r; j++) {
            scanf("%d", &curr[i][j]);
        }
    }

    printf("\nResursi primeraka: ");
    for (i = 0; i < r; i++) {
        printf("\t%d", maxres[i]);
    }

    printf("\nTabela alociranih resursa:\n");
    for (i = 0; i < p; i++) {
        for (j = 0; j < r; j++) {
            printf("\t%d", curr[i][j]);
        }

        printf("\n");
    }

    printf("\nTabela maksimalne potraznje :\n");
    for (i = 0; i < p; i++) {
        for (j = 0; j < r; j++) {
            printf("\t%d", maxclaim[i][j]);
        }

        printf("\n");
    }

    for (i = 0; i < p; i++) {
        for (j = 0; j < r; j++) {
            alloc[j] += curr[i][j];
        }
    }

    printf("\nAlocirani resursi:");
    for (i = 0; i < r; i++) {
        printf("\t%d", alloc[i]);
    }

    for (i = 0; i < r; i++) {
        avl[i] = maxres[i] - alloc[i];
    }

    printf("\nDostupni resursi:");
    for (i = 0; i < r; i++) {
        printf("\t%d", avl[i]);
    }
    printf("\n");

    //glavna procedura koja proverava da li je stanje sigurno.
    while (count != 0) {
        safe = 0;
        for (i = 0; i < p; i++) {
            if (running[i]) {
                exec = 1;
                for (j = 0; j < r; j++) {
                    if (maxclaim[i][j] - curr[i][j] > avl[j]) {
                        exec = 0;
                        break;
                    }
                }
                if (exec) {
                    printf("\nProces%d se izvrsava\n", i + 1);
                    running[i] = 0;
                    count--;
                    safe = 1;

                    for (j = 0; j < r; j++) {
                        avl[j] += curr[i][j];
                    }

                    break;
                }
            }
        }
        if (!safe) {
            printf("\nProcesi su u nesigurnom stanju.\n");
            break;
        } else {
            printf("\nProces je u sigurnom stanju");
            printf("\nSiguran redosled je:");

            for (i = 0; i < r; i++) {
                printf("\t%d", avl[i]);
            }

            printf("\n");
        }
    }
}

/*PRIMER IZLAZA
-----------------
Unesite broj procesa: 5

Unesite broj resursa: 4

Unesite resurs za primerak 1: 8

Unesite resurs za primerak 2: 5

Unesite resurs za primerak 3: 9

Unesite resurs za primerak 4: 7

Unesite tabelu maksimalne potraznje resursa:
3 2 1 4
0 2 5 2
5 1 0 5
1 5 3 0
3 0 3 3

Unesite tabelu alociranih resursa:
2 0 1 1
0 1 2 1
4 0 0 3
0 2 1 0
1 0 3 0

Resursi primeraka: 8 5 9 7
Tabela alociranih resursa:
 2 0 1 1
 0 1 2 1
 4 0 0 3
 0 2 1 0
 1 0 3 0

Tabela maksimalne potraznje :
 3 2 1 4
 0 2 5 2
 5 1 0 5
 1 5 3 0
 3 0 3 3

Alocirani resursi: 7 3 7 5
Dostupni resursi: 1 2 2 2

Proces3 se izvrsava

Proces je u sigurnom stanju
Siguran redosled je: 5 2 2 5

Proces1 se izvrsava

Proces je u sigurnom stanju
Siguran redosled je: 7 2 3 6

Proces2 se izvrsava

Proces je u sigurnom stanju
Siguran redosled je: 7 3 5 7

Proces4 se izvrsava

Proces je u sigurnom stanju
Siguran redosled je: 7 5 6 7

Proces5 se izvrsava

Proces je u sigurnom stanju
Siguran redosled je: 8 5 9 7
 ---------------------------------------------------------*/

Ograničenja

Kao i ostali algoritmi, Bankarov algoritam, kada se implementira, ima određena ograničenja. Preciznije, potrebno je da se zna koliko svakog resursa proces zahteva. U vecini sistemima, ova informacija nije dostupna, što čini implementaciju Bankarovog algoritma nemogućom. Takođe, nerealno je pretpostaviti da je broj procesa statičan pošto u većini sistema broj procesa se dinamički menja. Štaviše, zahtev da će proces osloboditi sve svoje resurse (kada se završi) je dovoljan da bi algoritam ispravno radio, ali takav zahtev nije adekvatan za sisteme u realnosti. Čekanje satima (ili čak danima) da se resursi oslobode obično nije prihvatljivo.

Reference

^ Dijkstra, Edsger W. Een algorithme ter voorkoming van de dodelijke omarming (EWD-108). E.W. Dijkstra Archive. Center for American History, University of Texas at Austin. (original; transcription) (na Holandskom; Algoritam za prevenciju kružne blokade)

Dodatna literatura

"Operating System Concepts" by Silberschatz, Galvin, and Gagne (pages 259-261 of the 7th edition)
"Operating System Concepts" by Silberschatz, Galvin, and Gagne (pages 298-300 of the 8th edition)
Dijkstra, Edsger W. The mathematics behind the Banker's Algorithm (EWD-623). E.W. Dijkstra Archive. Center for American History, University of Texas at Austin. (original; transcription) (1977), published as pages 308–312 of Edsger W. Dijkstra. Selected Writings on Computing: A Personal Perspective, Springer-Verlag. 1982. ISBN 978-0-387-90652-2..

Spoljašnje veze

Deadlock Recovery, Avoidance and Prevention Архивирано на сајту Wayback Machine (31. август 2010)

[1] Dijkstra, Edsger W. Een algorithme ter voorkoming van de dodelijke omarming (EWD-108). E.W. Dijkstra Archive. Center for American History, University of Texas at Austin. (original; transcription) (na Holandskom; Algoritam za prevenciju kružne blokade)

[1]