Банкаров алгоритам

Банкаров алгоритам је алгоритам алокације ресурса и избегавања кружне блокаде (енгл. deadlock) који је развио Едсгер Дајкстра. Алгоритам тестира безбедност симулирајући максималну предодређену алокацију свих ресурса а затим проверава да ли је стање сигурно односно да ли може доћи до кружне блокаде и у зависности од тога одлучује да ли ће наставити са алокацијом.

Алгоритам је првобитно развијен за ТХЕ оперативни систем и описан (на Холандском језику) у ЕWД108.^[1] Када се појави нови процес, он декларише максималан број примерака сваког типа ресурса који може да користи, очигледно, овај број не може бити већи од укупног броја ресурса у систему. Такође када процес добије све ресурсе које је захтевао, мора их вратити у ограниченом времену.

Ресурси

Да би Банкаров алгоритам радио, три ствари морају бити познате:

Количина сваког ресурса који сваки процес може да захтева[МАКСИМАЛНО]
Количина сваког ресурса који сваки процес тренутно заузима[АЛОЦИРАНО]
Количина сваког ресурса којом систем тренутно располаже[ДОСТУПНО]

Ресурси могу бити додељени процесу само ако задовољава следеће услове:

тражено ≤ максимално, у супротном прећи у стање грешке јер је процес прекорачио максималну количину ресурса које је захтевао.
тражено ≤ доступно, у супротном процес чека док се ресурси не ослободе.

Неки од ресурса који се захтевају у реалним ситуацијама су меморија, семафоре и приступ интерфејсу.

Банкаров алгоритам је добио име по томе што би могао да се користи у банкарским системима и осигура да банка никада не остане без ресурса јер банка никада не би издвојила новац на начин који би онемогућио подизање новца свих својих муштерија. Коришћењем Банкаровог алгоритма, банка осигурава да када муштерије подижу новац, банка никада не напушта сигурно стање. Ако захтев муштерије не проузрокује напуштање сигурног стања банке, муштерија ће подићи новац, у супротном муштерија мора чекати док нека друга муштерија не уложи довољно новца.

Основне структуре података које се морају користити за имплементацију Банкаровог алгоритма:

Нека је н број процеса у систему и м број типова ресурса. Тада су нам потребне следеће структуре података:

Доступно: Вектор дужине м који означава број слободних ресурса сваког типа. Ако је Доступно[ј] = к, постоји к примерака ресурса типа Р_ј који су доступни.
Макс: н×м матрица која дефинише максималну потражњу сваког ресурса. Ако је Макс[и,ј] = к, тада П_и може да захтева највише к примерака ресурса типа Р_ј.
Алоцирано: н×м матрица која дефинише количину ресурса сваког типа који су тренутно додељени сваком од процеса. Ако је Алоцирано[и,ј] = к, тада процес П_и тренутно алоцира к примерака ресурса типа Р_ј.
Потребно: н×м матрица која означава ресурсе које и даље захтева сваки од процеса. Ако је Потребно[и,ј] = к, тада П_и захтева још к примерака ресурса Р_ј да би завршио свој задатак.

Напомена: Потребно[и,ј] = Макс[и,ј] - Алоцирано[и,ј].

Пример

Претпоставимо да систем разликује 4 типа ресурса, (А, Б, C и D), следи пример како би ти ресурси могли бити распоређени. Приметити да овај пример приказује систем у тренутку пре пристизања новог захтева за ресурсима. Такође, тип и број ресурса је апстрактан. Системи у стварности би користили много веће количине сваког ресурса.

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

Сигурна и несигурна стања

Стање (као у примеру изнад) се сматра сигурним ако је могуће да се сваки од процеса заврши. Пошто систем не може знати када ће се процес завршити, или колико ће ресурса тражити до тада, систем претпоставља да ће сви процеси, после неког времена, покушати да добију максимално ресурса и да се заврше непосредно након тога. То је разумна претпоставка у већини случајева пошто систем не интересује колико дуго се процес извршава (макар не из перспективе избегавања кружне блокаде). Такође ако се процес заврши а да не захтева свој максимум ресурса, то само олакшава посао систему. Од сигурног стања зависи да ли ће процес бити смештен у ред спремних процеса. Сигурно стање гарантује безбедност.

Под датом претпоставком, алгоритам одлучује да ли је стање сигурно тако што покушава да пронађе хипотетички скуп захтева процеса који би омогућили сваком процесу да добије свој максимум ресурса и да се потом заврши (и притом врати своје ресурсе систему). Свако стање у ком такав скуп не постоји се сматра несигурним стањем.

Пример

Можемо показати да је стање дато у претходном примеру сигурно тако што ћемо показати да је могуће да сваки процес добије максимум ресурса и да се затим заврши.

П1 добија још 2 А, 1 Б и 1 D, при чему достиже свој максимум
- [доступни ресурси: <3 1 1 2> - <2 1 0 1> = <1 0 1 1>]
- Систем тренутно поседује следеће доступне ресурсе: 1 А, 0 Б, 1 C и 1 D
П1 се завршава и враћа следеће ресурсе систему: 3 А, 3 Б, 2 C и 2 D
- [доступни ресурси: <1 0 1 1> + <3 3 2 2> = <4 3 3 3>]
- Систем тренутно поседује следеће доступне ресурсе: 4 А, 3 Б, 3 C и 3 D
П2 добија још 2 Б и 1 D, затим се завршава и враћа све своје ресурсе
- [доступни ресурси: <4 3 3 3> - <0 2 0 1>+<1 2 3 4> = <5 3 6 6>]
- Систем тренутно поседује следеће доступне ресурсе: 5 А, 3 Б, 6 C и 6 D
П3 добија ресурсе 1 Б и 4 C и завршава се
- [доступни ресурси: <5 3 6 6> - <0 1 4 0> + <1 3 5 0> = <6 5 7 6>]
- Систем сада поседује све ресурсе: 6 А, 5 Б, 7 C анд 6 D
Пошто су сви процеси могли да се заврше ово стање је сигурно

Приметимо да су ови захтеви и добијање ресурса хипотетички. Алгоритам их генерише да провери сигурност стања, али ресурси се заправо нису додељивали и процеси се нису завршили. Такође приметити редослед којим се ови захтеви генеришу – ако неколико захтева може бити испуњено – нема разлике јер сви хипотетички захтеви омогућавају процесу да се заврши, и на тај начин повећавају слободне ресурсе система.

Као пример несигурног система, размотримо шта би се десило да је процес 2 заузимао 1 или више ресурса Б на почетку.

Захтеви

Када систем прими захтев за ресурсом, он покреће Банкаров алгоритам да одреди да ли је безбедно одобрити тај захтев. Алгоритам је једноставан када се разуме разлика између сигурног и несигурног стања.

Да ли се захтев може одобрити?
- Ако не, захтев је немогућ и мора се одбити или ставити на листу чекања
Претпоставити да је захтев одобрен
Да ли је ново стање сигурно?
- Ако јесте одобрити захтев
- У супротном одбити захтев или га ставити на листу чекања

Да ли оперативни систем одбија или одлаже немогућ или несигуран захтев је одлука која зависи од конкретног оперативног система.

Пример

Полазећи из истог стања као у претходном примеру, претпоставимо да процес 3 захтева 2 јединице ресурса C.

Не постоји довољно доступног ресурса C да би захтев могао бити одобрен
Захтев је одбијен

Са друге стране, претпоставимо да процес 3 захтева једну јединицу ресурса C.

Постоји довољно ресурса да се захтев одобри
Претпоставимо да је захтев одобрен
- Ново стање система било би:

    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

Одредимо да ли је ново стање сигурно
1. П1 може добити ресурсе 2 А, 1 Б и 1 D и завршити се
2. Затим, П2 може добити ресурсе 2 Б и 1 D и завршити се
3. На крају, П3 може добити ресурсе 1Б анд 3 C и завршити се
4. Одатле следи да је ново стање сигурно
Пошто је ново стање сигурно, одобравамо захтев

На крају, полазећи од почетног стања, претпоставимо да процес 2 захтева једну јединицу ресурса Б.

Постоји довољно ресурса
Претпостављајући да је захтев одобрен, ново стање ће бити:

    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

Да ли је ово стање сигурно? Претпоставимо да процеси П1, П2, и П3 захтевају више ресурса Б и C.
- П1 не може добити довољно ресурса Б
- П2 не може добити довољно ресурса Б
- П3 не може добити довољно ресурса Б
- Ниједан процес не може добити довољно ресурса да би се завршио, тако да је стање несигурно
Пошто је стање несигурно, одбијамо захтев

/*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
 ---------------------------------------------------------*/

Ограничења

Као и остали алгоритми, Банкаров алгоритам, када се имплементира, има одређена ограничења. Прецизније, потребно је да се зна колико сваког ресурса процес захтева. У вецини системима, ова информација није доступна, што чини имплементацију Банкаровог алгоритма немогућом. Такође, нереално је претпоставити да је број процеса статичан пошто у већини система број процеса се динамички мења. Штавише, захтев да ће процес ослободити све своје ресурсе (када се заврши) је довољан да би алгоритам исправно радио, али такав захтев није адекватан за системе у реалности. Чекање сатима (или чак данима) да се ресурси ослободе обично није прихватљиво.

Референце

^ Дијкстра, Едсгер W. Еен алгоритхме тер вооркоминг ван де доделијке омарминг (ЕWД-108). Е.W. Дијкстра Арцхиве. Центер фор Америцан Хисторy, Университy оф Теxас ат Аустин. (оригинал; трансцриптион) (на Холандском; Алгоритам за превенцију кружне блокаде)

Додатна литература

"Оператинг Сyстем Цонцептс" бy Силберсцхатз, Галвин, анд Гагне (пагес 259-261 оф тхе 7тх едитион)
"Оператинг Сyстем Цонцептс" бy Силберсцхатз, Галвин, анд Гагне (пагес 298-300 оф тхе 8тх едитион)
Дијкстра, Едсгер W. Тхе матхематицс бехинд тхе Банкер'с Алгоритхм (ЕWД-623). Е.W. Дијкстра Арцхиве. Центер фор Америцан Хисторy, Университy оф Теxас ат Аустин. (оригинал; трансцриптион) (1977), публисхед ас пагес 308–312 оф Едсгер W. Дијкстра. Селецтед Wритингс он Цомпутинг: А Персонал Перспецтиве, Спрингер-Верлаг. 1982. ISBN 978-0-387-90652-2..

Спољашње везе

Деадлоцк Рецоверy, Авоиданце анд Превентион Архивирано на сајту Wayback Machine (31. август 2010)

[1] Дијкстра, Едсгер W. Еен алгоритхме тер вооркоминг ван де доделијке омарминг (ЕWД-108). Е.W. Дијкстра Арцхиве. Центер фор Америцан Хисторy, Университy оф Теxас ат Аустин. (оригинал; трансцриптион) (на Холандском; Алгоритам за превенцију кружне блокаде)

[1]