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. 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 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 a működése során használni. Ez persze egy elég erős feltételezés, sajnos 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). Í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árakoztatjuk
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

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

↑ 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.
↑ A. N. Habermann, Prevention of System Deadlocks, Comm. ACM, vol. 12, no. 7, pp. 373–377, 385, July 1969.
↑ E. W. Dijkstra "EWD108: Een algorithme ter voorkoming van de dodelijke omarming"

Források

http://www.isi.edu/~faber/cs402/notes/lecture9.html Archiválva 2010. augusztus 31-i dátummal a Wayback Machine-ben
https://web.archive.org/web/20090111152440/http://algoritmo-del-banquero.veer.com.ar/ (spanyolul)

Matematikaportál
Informatikai portál

[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"

[1]

[2]

[3]