Bankárov algoritmus

Bankárov algoritmus slúži na alokáciu prostriedkov a ako prevencia k zabráneniu deadlocku. Tento algoritmus vyvinul Edsger Dijkstra, ktorý testuje bezpečnosť pomocou simulácie s vopred stanoveným maximálnym možným počtom všetkých prostriedkov a ich následne použitie pri teste podmienok na vznik deadlocku.

Algoritmus bol vyvinutý počas vývoja operačného systému a bol pôvodne popísaný v holandčine v dokumente EWD108. Tento algoritmus dostal meno podľa analogickej situácie, ktorú riešia bankári pri obmedzenej likvidite.

Bankárov algoritmus je spustený operačným systémom vždy, keď si nejaký proces vyžiada nejaký zdroj. Algoritmus zabráni deadlocku buď zamietnutím alebo pozdržaním požiadavky, ktorá by mohla spôsobiť nestabilitu systému. Keď vstúpi do systému nový proces, tak si musí deklarovať maximálny počet inštancií každého typu prostriedku, ktorý by ale nemal prekročiť celkový počet zdrojov v systéme. Taktiež keď si proces vyžiada všetky prostriedky, tak by ich mal vrátiť v rozumnom čase naspäť pre použitie inému procesu.

Zdroje

Bankárov algoritmus potrebuje vedieť tri hodnoty:

• Aký počet zdrojov si môže každý proces vyžiadať
• Aký počet zdrojov každý proces drží
• Aký počet zdrojov ma systém k dispozícii

Zdroj by mal byť poskytnutý iba za nasledovných podmienok:

• Požiadavka je menšia alebo rovná maximu – v inom prípade sa vytvorí chybová situácia pre proces prekračujúci maximálne množstvo požiadaviek
• Požiadavka je menšia alebo rovná prístupným zdrojom – v inom prípade bude proces čakať, kým sa mu neuvoľní nejaký zdroj

Niektoré zo zdrojov vedených v reálnych systémoch sú pamäť, semafory a užívateľský prístup.

Bankárov algoritmus jedného zdroja

Ide o model, ako si môže bankár v malom meste poradiť so zákazníckymi úvermi. Ukázalo sa, že jeho zákazníci málokedy vyčerpajú svoj úver až na limit. Toto samozrejme ponúka myšlienku rozšíriť úverové možnosti na väčšiu finančnú sumu ako v skutočnosti bankár má.

Možno si predstaviť nasledujúcu situáciu:

Zákazník	Využitý úver	Úverový limit
Martin	0	6
Michal	0	5
Monika	0	4
Michaela	0	7
Voľné zdroje	10	-
Maximálny záväzok	-	22

Bankár ma 10 kreditov na požičanie, no celková výška možných úverov je až 22. Jeho prácou je držať dostatočnú rezervu tak, aby prípadne mohol uspokojiť každého zákazníka v dlhodobom meradle. To znamená, že každý zákazník bude môcť dosiahnuť svoj úverový limit, len nebude možné aby sa táto situácia naskytla pre všetkých zákazníkov naraz.

Ako príklad môže slúžiť nasledovná situácia:

Zákazník	Využitý úver	Úverový limit
Martin	1	6
Michal	1	5
Monika	2	4
Michaela	4	7
Voľné zdroje	2	-
Maximálny záväzok	-	22

Osem kreditov bolo rozdelených medzi rôznych zákazníkov a dva ešte ostali nevyčerpané. Otázka zostáva, či existuje spôsob ako uspokojiť každého zákazníka. Môže byť každému zákazníkovi dopriata maximálna výška jeho úveru? Predpokladajme, že keď zákazník dosiahne svoj úverový limit tak je bankár schopný pozdržať ostatné úvery do času, kým zákazník nezaplatí svoj dlh. V tom momente sa stanú kredity prístupné pre zostávajúcich zákazníkov. Ak by sa bankár dostal do situácie, kde žiaden zo zákazníkov nemôže byť uspokojený pretože nezostalo dostatočné množstvo voľných kreditov, tak potom môže dôjsť k deadlocku. Vznik deadlocku bude podmienený požiadavkou jedného zo zákazníkov na kredity do výšky svojho limitu. Jeho požiadavka bude musieť počkať, no hrozí situácia, že bude čakať do nekonečna.

Ak chce bankár zistiť či takáto sekvencia existuje, musí nájsť zákazníka najbližšie k jeho úverovému limitu a zistiť či je so zvyšnými kreditmi schopný tento limit dosiahnuť. Bankár predpokladá, že zákazník po dosiahnutí tohto limitu mu všetko splatí. Potom si bankár vyberie ďalšieho zákazníka blízko svojho limitu. Ak takýmto spôsobom môže uspokojiť všetkých zákazníkov, tak je považovaný daný systém za bezpečný.

V prípade, keď Monika je najbližšie svojmu limitu a tým pádom aj k jeho splateniu, možno jej štyri kredity počítať za volné. Po Monike je najbližšie svojmu úverovému limitu Michaela (vlastne z tých štyroch kreditov sa dá uspokojiť buď Michaela alebo Michal). Predpokladajme, že sa uspokojí Michal. Keď to splatí, tak bude mať bankár päť voľných kreditov, čo mu postačí na to, aby splatil aj zákazníka s najväčším limitom, Martina. V takomto prípade sa dá považovať systém za bezpečný.

Nasledovný príklad ukazuje situáciu, pri ktorej sa bankár rozhodne odmeniť Michala ešte jedným kreditom, skôr ako uspokojí potreby Moniky.

Zákazník	Využitý úver	Úverový limit
Martin	1	6
Michal	2	5
Monika	2	4
Michaela	4	7
Voľné zdroje	1	-
Maximálny záväzok	-	22

Teraz je vidieť, že zo zvyšných kreditov nie je bankár schopný uspokojiť požiadavky žiadneho zo zákazníkov.
Takže bankárov algoritmus testuje každú požiadavku hneď ako vznikne a skúma, či vedie k bezpečnému stavu systému. Ak nie, tak ju jednoducho odloží do doby, keď bude bezpečné ju vykonať. Test prebieha tak, že si bankár overí, či ma dostatok voľných prostriedkov na uspokojenie zákazníka, ktorý je najbližšie ku svojmu úverovému limitu. V situácií, ktorá je načrtnutá vyššie, keď Michalovi bol priznaný ďalší kredit, sa nedá vyhovieť Monike, ktorá je najbližšie svojmu úverovému limitu a tým pádom sa vytvára nestabilita systému.

Ako väčšina algoritmov, tak aj Bankárov algoritmus zahrnuje určité kompromisy. Algoritmus potrebuje vedieť, koľko si môže jeden proces vyžiadať zdrojov. Vo väčšine systémov je táto informácia neprístupná, čo robí Bankárov algoritmus nepoužiteľným. Taktiež je nereálne počítať s fixným počtom procesov. Vo väčšine systémov sa počet procesov dramaticky mení. Navyše požiadavka na proces, aby po svojom skončení uvoľnil ním používane zdroje, je kľúčová pre správnosť algoritmu, ale nie je to postačujúce pre praktický systém. Čakať hodiny (ba dokonca dni) na uvoľnenie zdroja zvyčajne nie je prijateľný výsledok.

Pseudokód

function bankers_algorithm (set procesov P, práve teraz volné zdroje A) {
  while (P not empty) {
    boolean found = false
    for each (process p in P) {
      Cp = current_resource_allocation_for_process(p)
      Mp = maximum_resource_requirement_for_process(p)
      if (Mp − Cp ≤ A) {
        // p môže obsahovať všetko čo potrebuje.
        // Za predpokladu, že tak urobí, tak po skončení uvolní čo už použil.
        A = A + Cp
        remove_element_from_set(p, P)
        found = true
      }
    }
    if (not found) {
      return UNSAFE
    }
  }
  return SAFE
}

Zdroje

Tento článok je čiastočný alebo úplný preklad článku revízie Bankerers algorithm na anglickej Wikipédii.

• The Banker's Algorithm for Detecting/Preventing Deadlocks Archivované 2010-07-28 na Wayback Machine
• EWD108, holandsky Archivované 2010-05-14 na Wayback Machine