Algorytm bankiera

Algorytm Bankera , czasami nazywany algorytmem wykrywania , jest algorytmem alokacji zasobów i unikania impasu opracowanym przez Edsgera Dijkstrę , który sprawdza bezpieczeństwo, symulując alokację z góry określonych maksymalnych możliwych ilości wszystkich zasobów , a następnie przeprowadza kontrolę stanu „s” przetestować możliwe warunki impasu dla wszystkich innych oczekujących działań przed podjęciem decyzji, czy należy zezwolić na kontynuację przydziału.

Algorytm został opracowany w procesie projektowania dla systemu operacyjnego THE i pierwotnie opisany (w języku niderlandzkim ) w EWD108. Kiedy nowy proces wchodzi do systemu, musi zadeklarować maksymalną liczbę wystąpień każdego typu zasobu, do których może kiedykolwiek zażądać; oczywiście liczba ta nie może przekroczyć całkowitej liczby zasobów w systemie. Ponadto, gdy proces otrzyma wszystkie żądane zasoby, musi je zwrócić w skończonym czasie.

Zasoby

Aby algorytm bankiera działał, musi wiedzieć trzy rzeczy:

  • Ile każdego zasobu może zażądać każdy proces („MAX”)
  • Ile każdego zasobu aktualnie przechowuje każdy proces („ALLOCATED”)
  • Ile każdego zasobu jest obecnie dostępne w systemie („DOSTĘPNE”)

Zasoby mogą być przydzielone do procesu tylko wtedy, gdy żądana ilość zasobów jest mniejsza lub równa dostępnej ilości; w przeciwnym razie proces czeka, aż zasoby będą dostępne.

Niektóre zasoby śledzone w rzeczywistych systemach to pamięć , semafory i dostęp do interfejsu .

Algorytm Bankiera wywodzi swoją nazwę od tego, że algorytm ten mógłby być zastosowany w systemie bankowym w celu zapewnienia, że ​​bankowi nie zabraknie zasobów, ponieważ bank nigdy nie rozdysponuje swoich pieniędzy w taki sposób, że nie będzie już w stanie zaspokoić potrzeb wszystkich swoich klientów. Korzystając z algorytmu Bankiera, bank zapewnia, że ​​gdy klienci żądają pieniędzy, bank nigdy nie wyjdzie ze stanu bezpiecznego. Jeśli prośba klienta nie spowoduje wyjścia banku ze stanu bezpiecznego, gotówka zostanie przydzielona, ​​w przeciwnym razie klient musi czekać, aż inny klient wpłaci wystarczającą ilość depozytów.

Podstawowe struktury danych, jakie należy zachować w celu realizacji algorytmu Bankiera:

Niech liczbą procesów w systemie i . Następnie potrzebujemy następujących struktur danych:

  • Dostępne: wektor o długości m wskazuje liczbę dostępnych zasobów każdego typu. Jeśli Dostępne[j] = k, dostępnych jest k instancji typu zasobu Rj .
  • : zapotrzebowanie każdego procesu . Jeśli Max[i,j] = k, to P i może zażądać co najwyżej k instancji typu zasobu Rj .
  • Alokacja: macierz określa liczbę zasobów każdego typu aktualnie . Jeśli Allocation[i,j] = k, to procesowi P i aktualnie przydzielono k instancji typu zasobu R j .
  • Potrzeba: wskazuje pozostałe zapotrzebowanie na . Jeśli Need[i,j] = k, to P i może potrzebować k więcej instancji typu zasobu Rj, aby wykonać zadanie.

Uwaga: Potrzeba[i,j] = Maks[i,j] - Przydział[i,j]. n=ma.

Przykład 

 Całkowite zasoby systemowe to: ABCD 6 5 7 6 
 Dostępne zasoby systemowe to: ABCD 3 1 1 2 
 Procesy (aktualnie przydzielone zasoby): ABCD P1 1 2 2 1 P2 1 0 3 3 P3 1 2 1 0 
 Procesy (maksymalne zasoby): ABCD P1 3 3 2 2 P2 1 2 3 4 P3 1 3 5 0 
 Potrzeba = maksymalne zasoby - aktualnie przydzielone zasoby Procesy (potencjalnie potrzebne zasoby): ABCD P1 2 1 0 1 P2 0 2 0 1 P3 0 1 4 0

Stany bezpieczne i niebezpieczne

Stan (jak w powyższym przykładzie) jest uważany za bezpieczny, jeśli możliwe jest zakończenie wykonywania (zakończenie) wszystkich procesów. Ponieważ system nie może wiedzieć, kiedy proces się zakończy ani ile zasobów będzie wymagał do tego czasu, system zakłada, że ​​wszystkie procesy w końcu spróbują uzyskać określone maksymalne zasoby i zakończą się wkrótce potem. W większości przypadków jest to rozsądne założenie, ponieważ system nie jest szczególnie zainteresowany tym, jak długo trwa każdy proces (przynajmniej nie z perspektywy unikania zakleszczenia). Ponadto, jeśli proces kończy się bez uzyskania maksymalnego zasobu, to tylko ułatwia systemowi. Za stan bezpieczny uważa się decydenta, jeśli zamierza przetworzyć gotową kolejkę.

Przy takim założeniu algorytm określa, czy stan jest bezpieczny , próbując znaleźć hipotetyczny zestaw żądań procesów, który pozwoliłby każdemu z nich uzyskać maksymalne zasoby, a następnie zakończyć (zwrócić swoje zasoby do systemu). Każdy stan, w którym taki zbiór nie istnieje, jest niebezpiecznym .

Możemy pokazać, że stan podany w poprzednim przykładzie jest stanem bezpiecznym, pokazując, że każdy proces może uzyskać maksymalne zasoby, a następnie zakończyć.

  1. P1 potrzebuje 2 A, 1 B i 1 D więcej zasobów, osiągając maksimum
    • [dostępny zasób: <3 1 1 2> - <2 1 0 1> = <1 0 1 1>]
    • W systemie nadal dostępne są 1 zasób A, brak B, 1 C i 1 D
  2. P1 kończy działanie, zwracając do systemu zasoby 3 A, 3 B, 2 C i 2 D
    • [dostępny zasób: <1 0 1 1> + <3 3 2 2> = <4 3 3 3>]
    • System ma teraz dostępne zasoby 4 A, 3 B, 3 C i 3 D
  3. P2 zdobywa dodatkowe zasoby 2 B i 1 D, po czym kończy działanie, zwracając wszystkie swoje zasoby
    • [dostępny zasób: <4 3 3 3> - <0 2 0 1> + <1 2 3 4> = <5 3 6 6>]
    • System ma teraz zasoby 5 A, 3 B, 6 C i 6 D
  4. P3 uzyskuje zasoby 1 B i 4 C i kończy działanie.
    • [dostępny zasób: <5 3 6 6> - <0 1 4 0> + <1 3 5 0> = <6 5 7 6>]
    • System ma teraz wszystkie zasoby: 6 A, 5 B, 7 C i 6 D
  5. Ponieważ wszystkie procesy mogły się zakończyć, stan ten jest bezpieczny

Jako przykład niebezpiecznego stanu rozważmy, co by się stało, gdyby proces 2 trzymał na początku 1 jednostkę zasobu B.

Upraszanie

Kiedy system otrzymuje żądanie zasobów, uruchamia algorytm Bankiera, aby określić, czy można bezpiecznie spełnić żądanie. Algorytm jest dość prosty, gdy zrozumie się rozróżnienie między stanami bezpiecznymi i niebezpiecznymi.

  1. Czy wniosek może zostać uwzględniony?
    • Jeśli nie, prośba jest niemożliwa i musi zostać odrzucona lub umieszczona na liście oczekujących
  2. Załóżmy, że żądanie zostało spełnione
  3. Czy nowe państwo jest bezpieczne?
    • Jeśli tak, spełnij prośbę
    • Jeśli nie, odrzuć wniosek lub umieść go na liście oczekujących

To, czy system odrzuci lub odłoży niemożliwe lub niebezpieczne żądanie, jest decyzją specyficzną dla systemu operacyjnego.

Przykład

Rozpoczynając w tym samym stanie, w którym rozpoczęto poprzedni przykład, załóżmy, że proces 1 żąda 2 jednostek zasobu C.

  1. Nie ma wystarczającej ilości dostępnego zasobu C, aby spełnić żądanie
  2. Prośba zostaje odrzucona


Z drugiej strony załóżmy, że proces 3 żąda 1 jednostki zasobu C.

  1. Istnieją wystarczające zasoby, aby spełnić żądanie
  2. Załóżmy, że żądanie zostało zaakceptowane.
    • Nowy stan systemu wyglądałby następująco: 
 Dostępne zasoby systemu ABCD Wolny 3 1 0 2 
 Procesy (zasoby aktualnie przydzielone): ABCD P1 1 2 2 1 P2 1 0 3 3 P3 1 2 2 0 
 Procesy (maksymalne zasoby): ABCD P1 3 3 2 2 P2 1 2 3 4 P3 1 3 5 0
  1. Określ, czy ten nowy stan jest bezpieczny
    1. P1 może zdobyć zasoby 2 A, 1 B i 1 D i zakończyć działanie
    2. Następnie P2 może zdobyć zasoby 2 B i 1 D i zakończyć działanie
    3. Wreszcie P3 może zdobyć zasoby 1 B i 3 C i zakończyć
    4. Dlatego ten nowy stan jest bezpieczny
  2. Ponieważ nowy stan jest bezpieczny, spełnij żądanie


Ostatni przykład: ze stanu, w którym zaczęliśmy, załóżmy, że proces 2 żąda 1 jednostki zasobu B.

  1. Jest wystarczająco dużo zasobów
  2. Zakładając, że prośba zostanie udzielona, ​​nowy stan wyglądałby następująco:
 Dostępne zasoby systemowe: ABCD Wolny 3 0 1 2 
 Procesy (aktualnie przydzielone zasoby): ABCD P1 1 2 5 1 P2 1 1 3 3 P3 1 2 1 0 
 Procesy (maksymalne zasoby): ABCD P1 3 3 2 2 P2 1 2 3 4 P3 1 3 5 0
  1. Czy ten stan jest bezpieczny? Zakładając, że P1, P2 i P3 żądają więcej zasobu B i C.
    • P1 nie jest w stanie pozyskać wystarczającej ilości zasobów B
    • P2 nie jest w stanie pozyskać wystarczającej ilości zasobów B
    • P3 nie jest w stanie pozyskać wystarczającej ilości zasobów B
    • Żaden proces nie może zdobyć wystarczającej ilości zasobów, aby zakończyć, więc ten stan nie jest bezpieczny
  2. Ponieważ stan jest niebezpieczny, odrzuć żądanie
   

  
  

       import  numpy  as  np  n_processes  =  int  (  input  (  "Liczba procesów? "  ))  n_resources  =  int  (  input  (  "Liczba zasobów? "  ))  available_resources  =  [  int  (  x  )  for  x  in  input  (  "Wektor żądania? "  )  .  podziel  (  " "  )] 

  
        
     


   obecnie_przydzielone  =  np  .  array  ([  [  int  (  x  )  for  x  in  input  (  f  "Obecnie przydzielone dla procesu  {  i  +  1  }  ? "  )  .  split  (  " "  )]  for  i  in  range  (  n_processes  )  ])  max_demand  =  np  .  tablica  ([ 
        
     


      [  int  (  x  )  dla  x  na  wejściu  (  f  "Maksymalne żądanie od procesu  {  i  +  1  }  ?"  )  .  split  (  ""  )]  dla  i  w  zakresie  (  n_procesów  )  ]  )  total_available  =  available_resources  -np  .  suma  (  obecnie_przydzielona  ,  oś 0
    

   0
      
       
         
               =  )  bieganie  =  np  .  jedynki  (  n_procesów  )  # Tablica z n_procesami 1 wskazującymi, czy proces nie został jeszcze uruchomiony,  podczas gdy  np  .  count_nonzero  (  running  )  >  :  at_least_one_allocated  =  Fałsz  dla  p  w  zakresie  (  n_procesów  ):  jeśli  działa  [  p  ]:  jeśli  wszystkie  (  i  > =  0        
                  
                
                  0
                  
       dla  i  w  total_available  -  (  max_demand  [  p  ]  -  aktualnie_przydzielone  [  p  ])):  at_least_one_allocated  =  True  print  (  f  "  {  p  }  działa"  )  działa  [  p  ]  =  total_available  +=  aktualnie_przydzielone  [  p  ]  , jeśli  nie  at_least_one_allocated 
        
          
    
         :  print  (  "Niebezpieczne"  )  break  # wyjdź  else  :  print  (  "Bezpieczne"  )

Ograniczenia

Podobnie jak inne algorytmy, algorytm bankiera ma pewne ograniczenia podczas implementacji. W szczególności musi wiedzieć, ile każdego zasobu może zażądać proces. W większości systemów informacja ta jest niedostępna, co uniemożliwia wdrożenie algorytmu Bankiera. Ponadto nierealistyczne jest założenie, że liczba procesów jest statyczna, ponieważ w większości systemów liczba procesów zmienia się dynamicznie. Co więcej, wymaganie, aby proces ostatecznie zwolnił wszystkie swoje zasoby (po zakończeniu procesu) jest wystarczające dla poprawności algorytmu, jednak nie jest wystarczające dla praktycznego systemu. Oczekiwanie godzinami (lub nawet dniami) na zwolnienie zasobów jest zwykle nie do przyjęcia.

Dalsza lektura

Pobrano z „ https://en.wikipedia.org/w/index.php?title=Banker%27s_algorithm&oldid=1135112901 ”