Algorytm Dijkstry-Hubermana

Informacje zawarte w notatce to: struktury danych, algorytm bezpieczeństwa, algorytm zamawiania zasobów.

Algorytm Dijkstry-Hubermana
Algorytm Dijkstry-Hubermana jest to inaczej Algorytm Bankiera. Służy on do lokacji zasobów w taki sposób, aby uniknąć zakleszczeń. Jego autorem jest Edsger Dijkstra. Algorytm ten był po raz pierwszy wykorzystany w systemie operacyjnym zwanym THE, a opisany został w języku niderlandzkim.
Algorytm bankiera stosowany jest przez system operacyjny kiedy jakikolwiek proces zażąda zasobu. Zapobiega on wystąpieniu zakleszczeń przez odmówienie lub zawieszenie dostępu do zasobu w przypadku, gdyby dostęp do tego zasobu mógł spowodować wejście systemu w stan niebezpieczny.
Aby algorytm bankiera działał potrzebuje wiedzieć trzy rzeczy:
Jaką część każdego zasobu każdy proces może zażądać Jaką część każdego zasobu każdy proces aktualnie używa Jaką część każdego zasobu system ma aktualnie dostępną.
SZCZEGÓŁY ALGORYTMU BANKIERA:
Struktury danych:
- Dostępne: Wektor o długości m, określający liczbę dostępnych zasobów każdego typu. Dostępne[j] = k - oznacza, że jest dostępnych k egzemplarzy zasobu typu Zj. - Maksymalne: Macierz o wymiarach n x m, definiująca maksymalne żądania każdego procesu. Jeśli Maksymalne[i,j]=k to proces Pi może zamówić co najwyżej k egzemplarzy zasobu typu Zj. - Przydzielone: Macierz o wymiarach n x m, definiująca liczbę zasobów poszczególnych typów, przydzielonych do każdego z procesów. Gdy Przydzielone[i, j] = k, wówczas proces Pi ma przydzielonych k egzemplarzy zasobu typu Zj. - Potrzebne: Macierz o wymiarach n x m, przechowująca pozostałe do spełnienia zamówienia każdego z procesów. Element Potrzebne[i,j]=k oznacza, że do zakończenia swojej pracy proces Pi może jeszcze potrzebować k dodatkowych egzemplarzy zasobu typu Zj. Zauważmy, że Potrzebne[i,j] = Maksymalne[i,j] - Przydzielone[i,j]
Jeśli wprowadzimy następującą notację: Jeśli X jest macierzą n x m, to Xi oznacza i-ty wiersz macierzy. Algorytm bezpieczeństwa
Niech Roboczy i Końcowy oznaczają wektory o długości odpowiednio m i n. Roboczy := Dostępne; Końcowy[i] := false dla i=1,2, ..., n
Znajdujemy i takie, że zachodzą równocześnie dwa warunki: Końcowy[i] = false
Potrzebnei <= Roboczy
Jeśli takie i nie istnieje, to wykonujemy krok 4.
Wykonujemy: Roboczy := Roboczy + Przydzielonei;
Końcowy[i] := true
Tu następuje skok do punktu 2.
Jeśli Końcowy[i]=true dla wszystkich i, to system jest w stanie bezpiecznym. Algorytm zamawiania zasobów
Niech Zamówieniai oznacza wektor zamówień dla procesu Pi. Jeśli Zamówieniai[j]=k, to proces Pi potrzebuje k egzemplarzy zasobu typu Zj. Kiedy proces Pi wykonuje zamówienie, wtedy są podejmowane następujące działania: ... zobacz całą notatkę