Bankers algoritm

Bankers algoritm , ibland kallad detektionsalgoritmen , är en resursallokerings- och dödlägesalgoritm utvecklad av Edsger Dijkstra som testar säkerheten genom att simulera allokeringen av förutbestämda maximalt möjliga mängder av alla resurser och sedan gör en "s-state " -kontroll att testa för eventuella dödlägesförhållanden för alla andra pågående aktiviteter, innan man beslutar om tilldelningen ska tillåtas fortsätta.

Algoritmen utvecklades i designprocessen för operativsystemet THE och beskrevs ursprungligen (på holländska ) i EWD108. När en ny process kommer in i ett system måste den deklarera det maximala antalet instanser av varje resurstyp som den någonsin kan göra anspråk på; uppenbarligen får det antalet inte överstiga det totala antalet resurser i systemet. Dessutom, när en process får alla sina begärda resurser måste den returnera dem inom en begränsad tid.

Resurser

För att bankens algoritm ska fungera måste den kunna tre saker:

  • Hur mycket av varje resurs varje process skulle kunna begära ("MAX")
  • Hur mycket av varje resurs varje process för närvarande innehåller ("ALLOCATED")
  • Hur mycket av varje resurs som systemet för närvarande har tillgänglig ("TILLgänglig")

Resurser kan tilldelas en process endast om mängden resurser som begärs är mindre än eller lika med det tillgängliga beloppet; annars väntar processen tills resurser finns tillgängliga.

Några av resurserna som spåras i verkliga system är minne , semaforer och gränssnittsåtkomst .

Bankirens algoritm har fått sitt namn från det faktum att denna algoritm skulle kunna användas i ett banksystem för att säkerställa att banken inte får slut på resurser, eftersom banken aldrig skulle allokera sina pengar på ett sådant sätt att den inte längre kan tillfredsställa alla sina kunders behov. Genom att använda Bankirens algoritm säkerställer banken att banken aldrig lämnar ett säkert tillstånd när kunder begär pengar. Om kundens begäran inte gör att banken lämnar ett säkert tillstånd kommer kontanterna att tilldelas, annars får kunden vänta tills någon annan kund sätter in tillräckligt.

Grundläggande datastrukturer som ska underhållas för att implementera bankirens algoritm:

Låt vara antalet processer i systemet och vara antalet resurstyper. Då behöver vi följande datastrukturer:

  • Tillgänglig: En vektor med längden m indikerar antalet tillgängliga resurser av varje typ. Om Tillgänglig[j] = k, finns det k instanser av resurstyp R j tillgängliga.
  • Max: En × -matris definierar det maximala behovet för varje process. Om Max[i,j] = k, så kan Pi begära högst k instanser av resurstyp Rj .
  • Allokering: En × -matris definierar antalet resurser av varje typ som för närvarande allokeras till varje process. Om Allokering[i,j] = k, så tilldelas process Pi för närvarande k instanser av resurstyp Rj .
  • Behov: En × -matris indikerar det återstående resursbehovet för varje process. Om Need[i,j] = k, så kan Pi behöva k fler instanser av resurstyp R j för att slutföra uppgiften.

Obs: Behov[i,j] = Max[i,j] - Allokering[i,j]. n=ma.

Exempel 

 Totala systemresurser är: ABCD 6 5 7 6 
 Tillgängliga systemresurser är: ABCD 3 1 1 2 
 Processer (för närvarande allokerade resurser): ABCD P1 1 2 2 1 P2 1 0 3 3 P3 1 2 1 0 
 Processer (maximala resurser): ABCD P1 3 3 2 2 P2 1 2 3 4 P3 1 3 5 0 
 Behov = maximala resurser - för närvarande tilldelade resurser Processer (eventuellt nödvändiga resurser): ABCD P1 2 1 0 1 P2 0 2 0 1 P3 0 1 4 0

Trygga och osäkra tillstånd

Ett tillstånd (som i exemplet ovan) anses vara säkert om det är möjligt för alla processer att slutföra exekveringen (avslutas). Eftersom systemet inte kan veta när en process kommer att avslutas, eller hur många resurser det kommer att ha begärt då, antar systemet att alla processer så småningom kommer att försöka få sina angivna maximala resurser och avslutas kort därefter. Detta är ett rimligt antagande i de flesta fall eftersom systemet inte är särskilt bekymrat över hur länge varje process pågår (åtminstone inte ur ett dödlägesperspektiv). Dessutom, om en process avslutas utan att få sin maximala resurs gör det det bara enklare för systemet. Ett säkert tillstånd anses vara beslutsfattare om det ska bearbeta färdig kö.

Givet det antagandet avgör algoritmen om ett tillstånd är säkert genom att försöka hitta en hypotetisk uppsättning förfrågningar av processerna som skulle tillåta var och en att förvärva sina maximala resurser och sedan avsluta (återföra sina resurser till systemet). Varje tillstånd där ingen sådan uppsättning existerar är ett osäkert tillstånd.

Vi kan visa att tillståndet i det föregående exemplet är ett säkert tillstånd genom att visa att det är möjligt för varje process att få sina maximala resurser och sedan avslutas.

  1. P1 behöver 2 A, 1 B och 1 D mer resurser för att nå sitt maximum
    • [tillgänglig resurs: <3 1 1 2> - <2 1 0 1> = <1 0 1 1>]
    • Systemet har nu fortfarande 1 A, ingen B, 1 C och 1 D resurs tillgänglig
  2. P1 avslutas och returnerar 3 A, 3 B, 2 C och 2 D resurser till systemet
    • [tillgänglig resurs: <1 0 1 1> + <3 3 2 2> = <4 3 3 3>]
    • Systemet har nu 4 A, 3 B, 3 C och 3 D resurser tillgängliga
  3. P2 förvärvar 2 B och 1 D extra resurser, avslutar sedan och returnerar alla sina resurser
    • [tillgänglig resurs: <4 3 3 3> - <0 2 0 1> + <1 2 3 4> = <5 3 6 6>]
    • Systemet har nu 5 A-, 3 B-, 6 C- och 6 D-resurser
  4. P3 förvärvar 1 B- och 4 C-resurser och avslutar.
    • [tillgänglig resurs: <5 3 6 6> - <0 1 4 0> + <1 3 5 0> = <6 5 7 6>]
    • Systemet har nu alla resurser: 6 A, 5 B, 7 C och 6 D
  5. Eftersom alla processer kunde avslutas är detta tillstånd säkert

För ett exempel på ett osäkert tillstånd, fundera på vad som skulle hända om process 2 innehöll 1 enheter av resurs B i början.

Förfrågningar

När systemet tar emot en begäran om resurser, kör det bankens algoritm för att avgöra om det är säkert att bevilja begäran. Algoritmen är ganska enkel när man väl förstår skillnaden mellan säkra och osäkra tillstånd.

  1. Kan begäran beviljas?
    • Om inte är begäran omöjlig och måste antingen avslås eller sättas upp på en väntelista
  2. Antag att begäran beviljas
  3. Är den nya staten säker?
    • Bifall i så fall begäran
    • Om inte, antingen avslå begäran eller sätt upp den på en väntelista

Huruvida systemet nekar eller skjuter upp en omöjlig eller osäker begäran är ett beslut specifikt för operativsystemet.

Exempel

Med start i samma tillstånd som föregående exempel startade i, anta att process 1 begär 2 enheter av resurs C.

  1. Det finns inte tillräckligt med resurs C tillgänglig för att bevilja begäran
  2. Begäran avslås


Å andra sidan, anta att process 3 begär 1 enhet av resurs C.

  1. Det finns tillräckligt med resurser för att bevilja begäran
  2. Anta att begäran beviljas
    • Det nya tillståndet för systemet skulle vara: 
 Tillgängliga systemresurser ABCD Gratis 3 1 0 2 
 Processer (för närvarande tilldelade resurser): ABCD P1 1 2 2 1 P2 1 0 3 3 P3 1 2 2 0 
 Processer (maximala resurser): ABCD P1 3 3 2 2 P2 1 2 3 4 P3 1 3 5 0
  1. Bestäm om detta nya tillstånd är säkert
    1. P1 kan förvärva 2 A, 1 B och 1 D resurser och avsluta
    2. Sedan kan P2 förvärva 2 B- och 1 D-resurser och avsluta
    3. Slutligen kan P3 förvärva 1 B- och 3 C-resurser och avsluta
    4. Därför är detta nya tillstånd säkert
  2. Eftersom den nya staten är säker, godkänn begäran


Sista exemplet: från det tillstånd vi började i, anta att process 2 begär 1 enhet av resurs B.

  1. Det finns tillräckligt med resurser
  2. Förutsatt att begäran beviljas, skulle den nya staten vara:
 Tillgängliga systemresurser: ABCD Gratis 3 0 1 2 
 Processer (för närvarande tilldelade resurser): ABCD P1 1 2 5 1 P2 1 1 3 3 P3 1 2 1 0 
 Processer (maximala resurser): ABCD P1 3 3 2 2 P2 1 2 3 4 P3 1 3 5 0
  1. Är detta tillstånd säkert? Förutsatt att P1, P2 och P3 begär mer av resurs B och C.
    • P1 kan inte skaffa tillräckligt med B-resurser
    • P2 kan inte skaffa tillräckligt med B-resurser
    • P3 kan inte skaffa tillräckligt med B-resurser
    • Ingen process kan få tillräckligt med resurser för att avslutas, så detta tillstånd är inte säkert
  2. Eftersom staten är osäker, avslå begäran
   

  
  

      

  
        
     


  
        
     


     0
    

   0
      
       
         
               0        
                  
                
                  0
                  
      
        
          
    
         importera  numpy  som  np  n_processes  =  int  (  indata  (  "Antal processer? "  ))  n_resources  =  int  (  input  (  "Antal resurser? "  ))  available_resources  =  [  int  (  x  )  för  x  i  indata  (  "Anspråk vektor? "  )  .  split  (  " "  )]  för närvarande_allokerad  =  np  .  array  ([  [  int  (  x  )  för  x  i  ingång  (  f  "För närvarande allokerad för process  {  i  +  1  }  ?"  )  .  split  (  ""  )]  för  i  i  intervall  (  n_processer  )  ])  max_demand  =  np  .  array  ([  [  int  (  x  )  för  x  i  ingång  (  f  "Maximal efterfrågan från process  {  i  +  1  }  ?"  )  .  split  (  ""  )]  för  i  i  intervall  (  n_processer  )  ])  total_available  =  tillgängliga_resurser  -  np  .  summa  (  för närvarande_allokerad  ,  axel  =  )  löpande  =  np  .  ones  (  n_processes  )  # En array med n_processes 1:or för att indikera om processen ännu inte körs  medan  np  .  count_nonzero  (  running  )  >  :  at_least_one_allocated  =  Falskt  för  p  i  intervallet  (  n_processes  ):  om  körs  [  p  ]:  om  alla  (  i  >=  för  i  totalt_tillgänglig  -  (  max_demand  [  p  ]  - för   närvarande_allokerad  [  p ])   )  :  at_least_one_allocated  =  True  print  (  f  "  {  p  }  körs "  )  körs  [  p  ]  =  total_tillgänglig  +  = för   närvarande_allokerad  [  p  ]  om  inte  minst_one_allocated  :  print  (  "Osäkert" )   break  # exit  else  :  print  (  "Safe"  )

Begränsningar

Liksom de andra algoritmerna har Bankers algoritm vissa begränsningar när den implementeras. Specifikt behöver den veta hur mycket av varje resurs en process kan begära. I de flesta system är denna information inte tillgänglig, vilket gör det omöjligt att implementera Bankirens algoritm. Det är också orealistiskt att anta att antalet processer är statiskt eftersom antalet processer i de flesta system varierar dynamiskt. Dessutom är kravet att en process så småningom kommer att frigöra alla sina resurser (när processen avslutas) tillräckligt för att algoritmen är korrekt, men det är inte tillräckligt för ett praktiskt system. Att vänta i timmar (eller till och med dagar) på att resurser ska släppas är vanligtvis inte acceptabelt.

Vidare läsning

Hämtad från " https://en.wikipedia.org/w/index.php?title=Banker%27s_algorithm&oldid=1135112901 "