A Wikipédiából, a szabad lexikonból.

[szerkesztés] A bankár algoritmus

A bankár algoritmus egy E. W. Dijkstra ^[1] által kidolgozott algoritmus holtpont elkerülésére erőforások kiosztásakor. 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-romot. A 'B' folyamat lefoglalta a CD-romot, és igényli a nyomtatót. 'A' tehát arra vár, hogy megkapja 'B'-től a CD-romot, de 'B' nem engedi azt el amíg meg nem kapja a nyomtatót, és el nem végzi rajta a dolgát. Sajnos 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 az idők végezetéig kölcsönösen várhat egymásra, s ráadásul sem a nyomtatót sem a CD-romot nem tudja semmilyen más folyamat se használni. Holtpontok kezelésére számos stratégia ismeretes ezek közűl egy a bankár algoritmus. A bankár algoritmus a holtpontot megelőző algoritmus (léteznek más stratégiák is, pl. felismerjük és feloldjuk a holtpontot). Az algoritmus eredeti változata egyetlen errőforrástípust feltételez, később általánosították többféle erőforrásra is^[2]. Itt ezt az általánosított változatot közöljük. Az algoritmus feltételezi, hogy minden folyamat indulásakor előre be tudja jelenteni az operációs rendszernek, hogy melyik erőforrásból mennyit fog a működése során legfeljebb használni. Ez persze egy elég erős feltételezés, sajnos a valódi op.rendszereken futó valódi folyamatok ilyesmire ritkán képesek, ez is az oka, hogy a bankár agoritmust gyakorlatban alig haszánlják operációs rendszerekben.

[szerkesztés] 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öntei egy adott állapotról (azaz a szabad, max, foglalt, tobbi valtozó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). Íme 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;
        }
egyebkent
        {       
        return ("Az állapot nem biztonságos");
        }
}
}

A biztonsagos_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 tobbi 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 <=>, ha az i. processz a j. erőforrásból k db-ot igényel.
ha (∃ j : keres[j] > tobbi[i, j]) a kerest megtagadjuk
ha (∃ j : keres[j] > szabad[j]) az i. processzt várakozatjuk
egyébként
        legyen szabad2[i, k]=szabad[i, k]-keres[k] minden k-ra 
        és evvel 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;
        egyebkent
                i. folyamatot várakoztatjuk

[szerkesztés] Hivatkozások

1. ↑ E. W. Dijkstra, Cooperating sequential processes, Technological University, Eindhoven, The Netherlands, September 1965. Reprinted in Programming Languages, F. Genuys, Ed., Academic Press, New York, 1968, 43-112.
2. ↑ A. N. Habermann, Prevention of System Deadlocks, Comm. ACM, vol. 12, no. 7, pp. 373-377, 385, July 1969.