Wpisany przez Tomasz Lubiński,
26 lipca 2005 21:34
Algorytm tan służy do detekcji zakleszczenia procesów korzystających z zasobów systemu. Rozpatrzmy jednak najpierw problem bankiera. Zakładamy, że nasz bankier ma 100 PLN. Przychodzi do niego pierwszy klient i chce pożyczyć 50 PLN na rozwój swojej działalności. Twierdzi jednak, że w tej chwili wystarczy mu 30 PLN, a później zgłosi się po resztę. Zastrzega sobie jednak, że kwotę zwróci dopiero, gdy bankier pożyczy mu całą sumę (50 PLN). Po pewnym czasie przychodzi drugi klient i chce pożyczyć 80 PLN, ale podobnie jak poprzedni chce na razie tylko 30 PLN. W końcu przychodzi trzeci klient i również chce pożyczkę, tym razem na kwotę 60 PLN, ale podobnie jak poprzednicy na początek wystarczy mu 30 PLN. W tym momencie bankier znalazł się w stanie zakleszczenia: ma 10 PLN, ale nie wystarczy to na zaspokojenie, żadnego z klientów (wszyscy zastrzegli sobie, że zwrócą całą kwotę, ale dopiero gdy dostaną całą sumę). Zauważmy przy tym, że po obsłużeniu drugiego klienta bankier nie był jeszcze w stanie zakleszczenia. Dysponował bowiem kwotą 40 PLN, co wystarczyłoby dla pierwszego klienta - miał mu dopłacić jeszcze 20 PLN. Następnie klient pierwszy oddałby całą kwotę 50 PLN. Bankier miałby wówczas pieniądze dla drugiego klienta, któremu miał dopłacić 50 PLN. Przejdźmy teraz do zakleszczenia w systemie komputerowym.
Załóżmy, że mamy w systemie s różnych zasobów. Każdy z nich składa się z mk (k=1,2,..,s) jednostek. Jednostki zasobów tego samego typu są równoważne. Każda jednostka w każdej chwili może być przydzielona tylko do jednego zadania - dostęp do nich jest wyłączny. Zasoby są także nieprzywłaszczalne tzn. zwolnienie ich może nastąpić jedynie z inicjatywy zadania dysponującego danymi zasobami.
W każdej chwili zadanie Pj, (j=1,2,..,n) jest scharakteryzowanie przez:
Wektor maksymalnych żądań - czyli maksymalna ilość zasobów jaką może dysponować:
Żądanie przydziału dodatkowych zasobów:
Wektor zasobów w systemie (wolne+przydzielone):
Proces nie może żądać więcej zasobów niż wynika to z wektora rang:
Warunki konieczne wystąpienia zakleszczenia:
Rozwiązania problemu zakleszczenia:
Algorytm Habeman'a - detekcja zakleszczenia:
1. Zainicjuj zbiór D:={1,2,...,n} oraz wektor zasobów wolnych f.
2. Szukaj zadania o indeksie j należącym do zbioru D takiego, że: H(Pj)≤f
3. Jeżeli zadanie takie nie istnieje, to zbiór zadań odpowiadający zbiorowi D jest zbiorem zadań zakleszczonych.
4. W przeciwnym razie podstaw: D:=D-{j}; f:=f+A(Pj).
5. Jeżeli zbiór D jest pusty zakończ wykonywanie algorytmu. W przeciwnym razie przejdź do kroku 2.
Algorytm ten działa w sposób intuicyjny. W kroku 2 szukamy zadania, dla którego system jest w stanie spełnić żądania zasobowe. Jeśli zadanie takie istnieje to po zaspokojeniu tych żądań odda ono wszystkie zasoby, które posiada (krok 4). Jeśli natomiast nie możemy spełnić żądań zasobowych procesów, to znaczy, że nie możemy zagwarantować ich zakończenia a więc znajdują się one w stanie zakleszczenia.
W algorytmie zamiast macierzy rang (H), może pojawić się macierz żądań zasobowych, zależy to od metody której używamy do rozwiązania problemu zakleszczenia. W unikaniu jest to macierz rang, natomiast w detekcji jest to macierz żądań zasobowych.
- kolejne kolumny w macierzach odpowiadają kolejnym procesom, wiersze natomiast zasobom (np. w przykładzie poniżej proces drugi posiada trzy jednostki zasobu drugiego):
D={1,2,3,4,5}, f=[2,1,0,3]T
Punkt 2 algorytmu jest spełniony, dla j=4, zatem D={1,2,3,5}, f=[2,1,2,4]T
Punkt 2 algorytmu jest spełniony, dla j=3, zatem D={1,2,5}, f=[3,2,4,5]T
Punkt 2 algorytmu jest spełniony, dla j=1, zatem D={2,5}, f=[4,4,5,7]T
Punkt 2 algorytmu jest spełniony, dla j=2, zatem D={5}, f=[6,7,7,10]T
Punkt 2 algorytmu jest spełniony, dla j=5, zatem D={ }, f=[8,8,8,11]T
Spełniony jest punkt 5 algorytmu, zatem dla podanych danych nie ma zakleszczenia.
Rozpatrzmy teraz ten sam system, ale dla nieco zmienionych danych:
D={1,2,3,4,5}, f=[2,1,0,3]T
Punkt 2 algorytmu jest spełniony, dla j=4, zatem D={1,2,3,5}, f=[2,1,2,4]T
Punkt 2 algorytmu jest spełniony, dla j=3, zatem D={1,2,5}, f=[3,1,4,5]T
W tym momencie spełniony jest punkt 3 algorytmu, istnieje zatem zakleszczenie, a zbiór zadań zakleszczonych to D={1,2,5}
Załóżmy, że mamy w systemie s różnych zasobów. Każdy z nich składa się z mk (k=1,2,..,s) jednostek. Jednostki zasobów tego samego typu są równoważne. Każda jednostka w każdej chwili może być przydzielona tylko do jednego zadania - dostęp do nich jest wyłączny. Zasoby są także nieprzywłaszczalne tzn. zwolnienie ich może nastąpić jedynie z inicjatywy zadania dysponującego danymi zasobami.
W każdej chwili zadanie Pj, (j=1,2,..,n) jest scharakteryzowanie przez:
Wektor maksymalnych żądań - czyli maksymalna ilość zasobów jaką może dysponować:
C(P_j)=[C_1(P_j), C_2(P_j), ... , C_s(P_j)]^T
Wektor aktualnego przydziału - czyli ilość zasobów jaką dysponuje j-ty proces:
A(P_j)=[A_1(P_j), A_2(P_j), ... , A_s(P_j)]^T
Wektor rang - czyli maksymalna ilość zasobów jaką może zażądać j-ty proces:
H(P_j)=C(P_j)-A(P_j)
Każde zadanie Pj może generować:Żądanie przydziału dodatkowych zasobów:
q^a(P_j)=[q^a_1(P_j), q^a_2(P_j), ... , q^a_s(P_j)]^T
Żądanie zwolnienia zasobów:
q^r(P_j)=[q^r_1(P_j), q^r_2(P_j), ... , q^r_s(P_j)]^T
System scharakteryzowany jest przez:Wektor zasobów w systemie (wolne+przydzielone):
m=[m_1, m_2, ... , m_s]^T
Wektor zasobów wolnych:
f=[f_1, f_2, ... , f_s]^T
Oczywiście spełnione są następujące nierówności:Proces nie może żądać więcej zasobów niż wynika to z wektora rang:
q^a_k(P_j)\leq H_k(P_j) \text{ dla }(k=1,2,..,s) \text{ oraz }(j=1,2,..,n)
Proces nie może zwolnić więcej zasobów niż sam posiada:
q^r_k(P_j)\leq A_k(P_j) \text{ dla }(k=1,2,..,s) \text{ oraz }(j=1,2,..,n)
Żądanie przydziału dodatkowego zasobu może być spełnione gdy jest wystarczająca ilość zasobów wolnych:
q^a_k(P_j)\leq f_k(P_j) \text{ dla }(k=1,2,..,s) \text{ oraz }(j=1,2,..,n)
Powiemy, że system jest w stanie zakleszczenia jeżeli istnieje niepusty zbiór zadań, które żądają przydziału dodatkowych zasobów nieprzywłaszczalnych będących aktualnie w dyspozycji innych zadań tego zbioru. Innymi słowy, system jest w stanie zakleszczenia, jeżeli istnieje niepusty zbiór zadań, których żądania przydziału dodatkowych zasobów nieprzywłaszczalnych nie mogą być spełnione nawet, jeśli wszystkie zadania nie należące do tego zbioru zwolnią wszystkie zajmowane zasoby. Zbiór tan nazywamy zbiorem zadań zakleszczonych.Warunki konieczne wystąpienia zakleszczenia:
- wzajemne wykluczanie - w każdej chwili zasób może być przydzielony co najwyżej jednemu zadaniu,
- zachowanie zasobu - proces oczekujący na przydzielenie dodatkowych zasobów nie zwalnia zasobów będących aktualnie w jego dyspozycji,
- nieprzywłaszczalność - zwolnienie zasobu może być zainicjowane jedynie przez proces dysponujący w danej chwili tym zasobem,
- istnienie cyklu oczekiwań - cykl procesów, z których każdy ubiega się o przydział dodatkowych zasobów będących w dyspozycji kolejnego procesu w cyklu.
Rozwiązania problemu zakleszczenia:
- konstrukcje systemów immanentnie wolnych od zakleszczenia - wyposażenie systemu w taką ilość zasobów, aby wszystkie możliwe żądania zasobowe były możliwe do zrealizowania,
- detekcja zakleszczenia i odtwarzanie stanu wolnego od zakleszczenia - stan systemu jest okresowo sprawdzany i jeśli wykryty zostanie stan zakleszczenia, system podejmuje specjalne akcje w celu odtworzenia stanu wolnego od zakleszczenia (zabijanie procesów),
- unikanie - każda potencjalna tranzycja stanu jest sprawdzana i jeśli jej wykonanie prowadziłoby do stanu niebezpiecznego, to żądanie zasobowe nie jest w danej chwili realizowane,
- zapobieganie - polega na wyeliminowaniu możliwości zajścia jednego z warunków koniecznych zakleszczenia.
Algorytm Habeman'a - detekcja zakleszczenia:
1. Zainicjuj zbiór D:={1,2,...,n} oraz wektor zasobów wolnych f.
2. Szukaj zadania o indeksie j należącym do zbioru D takiego, że: H(Pj)≤f
3. Jeżeli zadanie takie nie istnieje, to zbiór zadań odpowiadający zbiorowi D jest zbiorem zadań zakleszczonych.
4. W przeciwnym razie podstaw: D:=D-{j}; f:=f+A(Pj).
5. Jeżeli zbiór D jest pusty zakończ wykonywanie algorytmu. W przeciwnym razie przejdź do kroku 2.
Algorytm ten działa w sposób intuicyjny. W kroku 2 szukamy zadania, dla którego system jest w stanie spełnić żądania zasobowe. Jeśli zadanie takie istnieje to po zaspokojeniu tych żądań odda ono wszystkie zasoby, które posiada (krok 4). Jeśli natomiast nie możemy spełnić żądań zasobowych procesów, to znaczy, że nie możemy zagwarantować ich zakończenia a więc znajdują się one w stanie zakleszczenia.
W algorytmie zamiast macierzy rang (H), może pojawić się macierz żądań zasobowych, zależy to od metody której używamy do rozwiązania problemu zakleszczenia. W unikaniu jest to macierz rang, natomiast w detekcji jest to macierz żądań zasobowych.
Przykład:
- kolejne kolumny w macierzach odpowiadają kolejnym procesom, wiersze natomiast zasobom (np. w przykładzie poniżej proces drugi posiada trzy jednostki zasobu drugiego):
A=\begin{bmatrix}
1 & 2 & 1 & 0 & 2\\
2 & 3 & 1 & 0 & 1\\
1 & 2 & 2 & 2 & 1\\
2 & 3 & 1 & 1 & 1
\end{bmatrix}
H=\begin{bmatrix}
2 & 1 & 2 & 1 & 1\\
2 & 2 & 1 & 1 & 2\\
1 & 1 & 1 & 0 & 1\\
0 & 1 & 0 & 2 & 2
\end{bmatrix}
f=\begin{bmatrix}
2 \\
1 \\
0 \\
3
\end{bmatrix}
D={1,2,3,4,5}, f=[2,1,0,3]T
Punkt 2 algorytmu jest spełniony, dla j=4, zatem D={1,2,3,5}, f=[2,1,2,4]T
Punkt 2 algorytmu jest spełniony, dla j=3, zatem D={1,2,5}, f=[3,2,4,5]T
Punkt 2 algorytmu jest spełniony, dla j=1, zatem D={2,5}, f=[4,4,5,7]T
Punkt 2 algorytmu jest spełniony, dla j=2, zatem D={5}, f=[6,7,7,10]T
Punkt 2 algorytmu jest spełniony, dla j=5, zatem D={ }, f=[8,8,8,11]T
Spełniony jest punkt 5 algorytmu, zatem dla podanych danych nie ma zakleszczenia.
Rozpatrzmy teraz ten sam system, ale dla nieco zmienionych danych:
A=\begin{bmatrix}
1 & 2 & 1 & 0 & 2\\
3 & 3 & 0 & 0 & 1\\
1 & 2 & 2 & 2 & 1\\
2 & 3 & 1 & 1 & 1
\end{bmatrix}
H=\begin{bmatrix}
2 & 1 & 2 & 1 & 4\\
2 & 2 & 1 & 1 & 1\\
1 & 1 & 1 & 0 & 1\\
0 & 1 & 0 & 2 & 2
\end{bmatrix}
f=\begin{bmatrix}
2 \\
1 \\
0 \\
3
\end{bmatrix}
D={1,2,3,4,5}, f=[2,1,0,3]T
Punkt 2 algorytmu jest spełniony, dla j=4, zatem D={1,2,3,5}, f=[2,1,2,4]T
Punkt 2 algorytmu jest spełniony, dla j=3, zatem D={1,2,5}, f=[3,1,4,5]T
W tym momencie spełniony jest punkt 3 algorytmu, istnieje zatem zakleszczenie, a zbiór zadań zakleszczonych to D={1,2,5}
Implementacje
| Autor | Język programowania | Komentarz | Otwórz | Pobierz | Ocena |
| Tomasz Lubiński | C/C++ | .cpp | .cpp | ***** / 2 | |
| Tomasz Lubiński | Delphi/Pascal | .pas | .pas | ***** / 1 | |
| Tomasz Lubiński | Java | .java | .java | ***** / 1 |
Poprawiony: 15 sierpnia 2012 18:34
