Bankár algoritmus

A Wikipédiából, a szabad enciklopédiából

A bankár algoritmus egy E. W. Dijkstra [1] által kidolgozott algoritmus holtpont elkerülésére erőforrá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-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 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-ROM-ot nem tudja semmilyen más folyamat se 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 a működése során 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 annak, hogy a bankár algoritmust a gyakorlatban alig használják operációs rendszerekben.

Az algoritmus menete[szerkesztés | forrásszöveg szerkesztése]

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 P1, P2, … Pn sorbarendezése, hogy ∀ i-re Pi processz csak szabad erőforrásokat igényel, vagy olyanokat, amiket valamilyen Pj 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 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 ↔, 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 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;
        egyebkent
                i. folyamatot várakoztatjuk

Története[szerkesztés | forrásszöveg szerkesztése]

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.

Jegyzetek[szerkesztés | forrásszöveg szerkesztése]

  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.
  3. E. W. Dijkstra "EWD108: Een algorithme ter voorkoming van de dodelijke omarming"

Hivatkozások[szerkesztés | forrásszöveg szerkesztése]

Források[szerkesztés | forrásszöveg szerkesztése]