Wikipédia

Bankár algoritmus

Ez a szócikk vagy szakasz lektorálásra, tartalmi javításokra szorul. A felmerült kifogásokat a szócikk vitalapja részletezi (vagy extrém esetben a szócikk szövegében elhelyezett, kikommentelt szövegrészek). Ha nincs indoklás a vitalapon (vagy szerkesztési módban a szövegközben), bátran távolítsd el a sablont!
Csak akkor tedd a lap tetejére ezt a sablont, ha az egész cikk megszövegezése hibás. Ha nem, az adott szakaszba tedd, így segítve a lektorok munkáját! (2006 februárjá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 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 szerkesztés

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á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 szerkesztés

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

  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"

Források szerkesztés

A lap eredeti címe: „https://hu.wikipedia.org/w/index.php?title=Bankár_algoritmus&oldid=25408039”