Bankár algoritmus

A bankár algoritmus egy E. W. Dijkstra^[1] által kidolgozott algoritmus holtpont elkerülésére erőforrások kiosztásakor.

Erőforrások

Egy operációs rendszerben holtpont alakul ki, ha van az operációs rendszerben egy olyan folyamathalmaz, melynek minden eleme valamelyik másik e halmazbeli folyamat által lefoglalt erőforrásra várakozik.

Egy egyszerű példa: Az 'A' folyamat (kizárólagosan) lefoglalta a nyomtatót, és igényli a CD-ROM-ot . A 'B' folyamat lefoglalta a CD-ROM-ot, és igényli a nyomtatót. 'A' tehát arra vár, hogy megkapja 'B'-től a CD-ROM-ot, de 'B' nem engedi azt el amíg meg nem kapja a nyomtatót, és el nem végzi vele a szükséges műveletet. Azonban a nyomtatót épp 'A' használja és ő sem engedi azt el amíg meg nem kapja a CD-t. Így a két folyamat a végtelenségig kölcsönösen várhat egymásra, ráadásul sem a nyomtatót, sem a CD-t nem tudja semmilyen más folyamat sem használni.

Holtpontok kezelésére számos stratégia ismeretes, ezek közül az egyik a bankár algoritmus. A bankár algoritmus a holtpontot megelőző algoritmus (léteznek más stratégiák is, például felismerjük és feloldjuk a holtpontot). Itt az algoritmus többféle erőforrásra általánosított változatát^[2] közöljük.

Az algoritmus feltételezi, hogy minden folyamat az indulásakor előre be tudja jelenteni az operációs rendszernek, hogy melyik erőforrásból legfeljebb mennyit fog használni a működése során. Ez persze egy elég erős feltételezés, a valódi operációs rendszereken futó valódi folyamatok ilyesmire ritkán képesek. Ez is az oka annak, hogy a bankár algoritmust a gyakorlatban alig használják operációs rendszerekben.

Az algoritmus menete

Legyen m a rendszer erőforrásainak száma, és n a rendszerben levő folyamatok száma.

Az algoritmus a következő változókat tartja nyilván:

szabad[1..m]: m hosszú vektor, szabad[i]=k ↔ az i. erőforrásból k db szabad

max[n×m]: n×m-es mátrix, max[i, j]=k ↔ az i. processznek a j. erőforrásból max k db-ra lehet szüksége a teljes futása során.

foglalt[n×m]: n×m-es mátrix, foglalt[i, j]=k ↔ az i. processz a j. erőforrásból k darabot használ

tobbi[n×m]: n×m-es mátrix, tobbi=max-foglalt azaz tobbi[i, j]=k ↔ az i. processznek a j erőforrásból még k darab kellhet a hátralévő futása során

Magát az algoritmust két részben szokás megfogalmazni. Az első rész feladata eldönteni egy adott állapotról (azaz a szabad, max, foglalt, tobbi változók egy meghatározott értékéről), hogy az biztonságos-e, azaz lehetséges-e az adott állapotból kiindulva a folyamatokat olyan sorrendben ütemezni, hogy biztosan ne álljon elő holtpont. (Formálisan egy állapot akkor biztonságos, ha létezik a processzeknek egy olyan P₁, P₂, … P_n sorbarendezése, hogy ∀ i-re P_i processz csak szabad erőforrásokat igényel, vagy olyanokat, amiket valamilyen P_j processz tart lekötve, ahol j < i).

A biztonságosságot eldöntő algoritmus:

biztonsagos_e()
{
    munka[1..m] = szabad;
    vege[1..n] = [false, false, …, false];
    
    while (true) {
        ha (∀ i ∈ [1..n]-re vege[i] == true) {return "Az állapot biztonságos";}
        ha (∃ i ∈ [1..n], hogy tobbi[i, j] ≤ munka[j] (∀ j ∈ [1..m]-re) és vege[i] == false)
            /* azaz van olyan processz, amely, ha az összes erőforrásigényét
            egyszerre bejelenti akkor is kevesebbet fog igényelni minden erőforrásból,
            mint a szabad erőforrások*/
        {
            akkor erre az i-re
            munka[j] = munka[j] + foglalt[i, j] ∀ j-re; /* beregisztráljuk ennek a processznek az erőforrás igényét */
            vege[i] = true;
        } különben {
            return ("Az állapot nem biztonságos");
        }
    }
}

A biztonságos_e() algoritmust ezután úgy használjuk, hogy ha egy processz bejelenti, egy erőforrásra való igényét, akkor úgy teszünk mintha odaadnánk neki az igényelt erőforrást, és az így létrejött állapotról eldöntjük, hogy biztonságos-e. Ha igen, akkor valóban odaadjuk a processznek a megfelelő erőforrást és frissítjük a szabad, foglalt és többi változóinkat, ha nem akkor nem adjuk oda neki az erőforrást, hanem várakoztatjuk egy darabig (amíg esetleg változik a helyzet).

Formálisabban:

legyen keres[1..m] egy olyan vektor amit az i. processz küld, keres[j] = k akkor és csak akkor, ha az i. processz a j. erőforrásból k db-ot igényel

ha (∃ j : keres[j] > tobbi[i, j]) {a kérést megtagadjuk}

ha (∃ j : keres[j] > szabad[j]) {az i. processzt várakoztatjuk}
különben {
    minden k-ra {
        legyen szabad2[i, k] = szabad[i, k] - keres[k]
    }
    és ezzel a szabad2-vel futtassuk a biztonsagos_e() algoritmust
    
    ha biztonsagos_e() == "Az állapot biztonságos" akkor {
        szabad = szabad - keres;
        foglalt[i] = foglalt[i] + keres;
        tobbi[i] = tobbi[i] - keres;
    }
    különben {
        az i. folyamatot várakoztatjuk
    }
}

Története

Az algoritmust eredetileg Edsger Wybe Dijkstra fejlesztette ki a THE operációs rendszer tervezésekor, és először hollandul publikálta.^[3] Az algoritmus eredeti változata egyetlen erőforrástípust feltételez, de később általánosították többféle erőforrástípus kezelésére is.