Wpisany przez Tomasz Lubiński,
26 lipca 2005 21:38
Algorytm ten 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ł pł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:
W algorytmie Holt'a przekształcamy macierz rang do trójwymiarowej macierzy E, w której znajdują się posortowane (wierszami) żądania z macierzy rang H wraz z numerami procesów.
- kolejne kolumny w macierzach odpowiadają kolejnym procesom, wiersze natomiast zasobom (np. w przykładzie poniżej proces drugi posiada trzy jednostki zasobu drugiego):
Utworzyliśmy macierz E. Duże liczby oznaczają żądania zasobowe i odpowiadają odwołaniom E[0,x,y], małe liczby natomiast informują, do którego procesu należy dane żądania i odpowiadają one odwołaniom E[1,x,y].
Następnie inicjujemy wektor c, wartość c[0] równa jest liczbie zadań w systemie (n), w naszym przypadku jest ich 5. Następnie wartości c[1..n] równe są liczbie zasobów w systemie (s), w naszym wypadku 4. Zatem ostatecznie otrzymujemy wektor:
c=[5,4,4,4,4,4]
Dalej inicjujemy wektor I, o rozmiarze równym ilości zasobów i wartościach 1. Wektor ten będzie informował nas, które żądanie zasobowe z macierzy E będziemy starali się spełnić (na początek oczywiście pierwsze) Zatem wektor ma postać:
I=[1,1,1,1]T
Dobrze, zainicjowaliśmy już wszystkie potrzebne zmienne, możemy zatem przejść do wykonywania algorytmu.
Z wektora zasobów wolnych pobieramy wartość pierwszego zasobu. Dysponujemy dwiema jednostkami. W macierzy E sprawdzamy ile żądań jesteśmy w stanie spełnić. Okazuje się, że wszystkie bo największe żądanie to 2 a tyloma właśnie wolnymi jednostkami dysponujemy. Wartość I[1] zwiększamy o ilość procesów, które zaspokoiliśmy, w naszym wypadku wszystkie 5 zatem I[1]=6. Teraz zmniejszamy wartości z wektora c dla tych procesów, dla których zasopokoiliśmy żądania zasobowe, czyli otrzymujemy: c=[5,3,3,3,3,3].
Teraz z wektora zasobów wolnych pobieramy drugą wartość (1) i sprawdzamy ile żądań zasobowych jesteśmy w stanie spełnić. Okazuje się, że tylko 2, zatem I[2]=3 Teraz zmniejszamy wartości z wektora c dla tych procesów, dla których zasopokoiliśmy żądania zasobowe, czyli otrzymujemy: c=[5,3,3,2,2,3].
Następnie z wektora zasobów wolnych pobieramy trzecią wartość (0) i sprawdzamy ile żądań zasobowych jesteśmy w stanie spełnić. Okazuje się, że tylko 1, zatem I[3]=2 Teraz zmniejszamy wartości z wektora c dla tych procesów, dla których zasopokoiliśmy żądania zasobowe, czyli otrzymujemy: c=[5,3,3,2,1,3].
Kolejno z wektora zasobów wolnych pobieramy czwartą - ostatnią wartość (3) i sprawdzamy ile żądań zasobowych jesteśmy w stanie spełnić. Okazuje się, że 5, zatem I[2]=6 Teraz zmniejszamy wartości z wektora c dla tych procesów, dla których zasopokoiliśmy żądania zasobowe, czyli otrzymujemy: c=[5,2,2,1,0,2]. I tutaj zauważamy, że dla procesu czwartego otrzymaliśmy wartość 0. Oznacza to, że jesteśmy w stanie zaspokoić żądania zasobowe tego procesu, zatem powiększamy wektor zasobów wolnych o wartość zasobów, które posiada ten proces, zatem f=[2,1,2,4]T. Oraz zmniejszamy licznik procesów c[0] o liczbę procesów, które jesteśmy w stanie zaspokoić zasobowo, czyli c[0]=4.
Ostatecznie po pierwszej iteracji otrzymujemy:
I=[6,3,2,6]T c=[4,2,2,1,0,2] f=[2,1,2,4]T
Teraz przeprowadzamy te same czynności dla nowej wartości wektora zasobów wolnych:
I=[6,3,6,6]T c=[3,1,1,0,0,1] f=[2,2,4,5]T
Kolejna iteracja:
I=[6,6,6,6]T c=[0,0,0,0,0,0] f=[8,8,8,11]T
c[0] jest równe zero zatem nie ma zakleszczenia.
Rozpatrzmy teraz ten sam system, ale dla nieco zmienionych danych:
I=[1,1,1,1]T c=[5,4,4,4,4,4] f=[2,1,0,3]T
Po pierwszej iteracji otrzymujemy:
I=[4,3,1,6]T c=[4,2,2,1,0,3] f=[2,1,2,4]T
Po kolejnej iteracji:
I=[4,3,6,6]T c=[3,1,1,0,0,1] f=[3,1,4,5]T
Następnie:
I=[4,3,6,6]T c=[3,1,1,0,0,1] f=[3,1,4,5]T
W tej iteracji w wektorze c nie otrzymalismy, żadanej nowej wartości 0, zatem możemy zakończyć wykonywanie algorytmu. Istnieją c[0]=3 zakleszczone procesy, są to te zadania, dla których wartości w wektorze c są różne od zera, zatem są to zadania {1,2,5}
Algorytm Holt'a - detekcja zakleszczenia:
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.
W algorytmie Holt'a przekształcamy macierz rang do trójwymiarowej macierzy E, w której znajdują się posortowane (wierszami) żądania z macierzy rang H wraz z numerami procesów.
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}
\\\\\\
E=\begin{bmatrix}
1_{2} & 1_{4} & 1_{5} & 2_{1} & 2_{3}\\
1_{3} & 1_{4} & 2_{1} & 2_{2} & 2_{5}\\
0_{4} & 1_{1} & 1_{2} & 1_{3} & 1_{5}\\
0_{1} & 0_{3} & 1_{2} & 2_{4} & 2_{5}
\end{bmatrix}
Utworzyliśmy macierz E. Duże liczby oznaczają żądania zasobowe i odpowiadają odwołaniom E[0,x,y], małe liczby natomiast informują, do którego procesu należy dane żądania i odpowiadają one odwołaniom E[1,x,y].
Następnie inicjujemy wektor c, wartość c[0] równa jest liczbie zadań w systemie (n), w naszym przypadku jest ich 5. Następnie wartości c[1..n] równe są liczbie zasobów w systemie (s), w naszym wypadku 4. Zatem ostatecznie otrzymujemy wektor:
c=[5,4,4,4,4,4]
Dalej inicjujemy wektor I, o rozmiarze równym ilości zasobów i wartościach 1. Wektor ten będzie informował nas, które żądanie zasobowe z macierzy E będziemy starali się spełnić (na początek oczywiście pierwsze) Zatem wektor ma postać:
I=[1,1,1,1]T
Dobrze, zainicjowaliśmy już wszystkie potrzebne zmienne, możemy zatem przejść do wykonywania algorytmu.
Z wektora zasobów wolnych pobieramy wartość pierwszego zasobu. Dysponujemy dwiema jednostkami. W macierzy E sprawdzamy ile żądań jesteśmy w stanie spełnić. Okazuje się, że wszystkie bo największe żądanie to 2 a tyloma właśnie wolnymi jednostkami dysponujemy. Wartość I[1] zwiększamy o ilość procesów, które zaspokoiliśmy, w naszym wypadku wszystkie 5 zatem I[1]=6. Teraz zmniejszamy wartości z wektora c dla tych procesów, dla których zasopokoiliśmy żądania zasobowe, czyli otrzymujemy: c=[5,3,3,3,3,3].
Teraz z wektora zasobów wolnych pobieramy drugą wartość (1) i sprawdzamy ile żądań zasobowych jesteśmy w stanie spełnić. Okazuje się, że tylko 2, zatem I[2]=3 Teraz zmniejszamy wartości z wektora c dla tych procesów, dla których zasopokoiliśmy żądania zasobowe, czyli otrzymujemy: c=[5,3,3,2,2,3].
Następnie z wektora zasobów wolnych pobieramy trzecią wartość (0) i sprawdzamy ile żądań zasobowych jesteśmy w stanie spełnić. Okazuje się, że tylko 1, zatem I[3]=2 Teraz zmniejszamy wartości z wektora c dla tych procesów, dla których zasopokoiliśmy żądania zasobowe, czyli otrzymujemy: c=[5,3,3,2,1,3].
Kolejno z wektora zasobów wolnych pobieramy czwartą - ostatnią wartość (3) i sprawdzamy ile żądań zasobowych jesteśmy w stanie spełnić. Okazuje się, że 5, zatem I[2]=6 Teraz zmniejszamy wartości z wektora c dla tych procesów, dla których zasopokoiliśmy żądania zasobowe, czyli otrzymujemy: c=[5,2,2,1,0,2]. I tutaj zauważamy, że dla procesu czwartego otrzymaliśmy wartość 0. Oznacza to, że jesteśmy w stanie zaspokoić żądania zasobowe tego procesu, zatem powiększamy wektor zasobów wolnych o wartość zasobów, które posiada ten proces, zatem f=[2,1,2,4]T. Oraz zmniejszamy licznik procesów c[0] o liczbę procesów, które jesteśmy w stanie zaspokoić zasobowo, czyli c[0]=4.
Ostatecznie po pierwszej iteracji otrzymujemy:
I=[6,3,2,6]T c=[4,2,2,1,0,2] f=[2,1,2,4]T
Teraz przeprowadzamy te same czynności dla nowej wartości wektora zasobów wolnych:
I=[6,3,6,6]T c=[3,1,1,0,0,1] f=[2,2,4,5]T
Kolejna iteracja:
I=[6,6,6,6]T c=[0,0,0,0,0,0] f=[8,8,8,11]T
c[0] jest równe zero zatem 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}
\\\\\\
E=\begin{bmatrix}
1_{2} & 1_{4} & 2_{1} & 2_{3} & 4_{5}\\
1_{3} & 1_{4} & 1_{5} & 2_{1} & 2_{2}\\
0_{4} & 1_{1} & 1_{2} & 1_{3} & 1_{5}\\
0_{1} & 0_{3} & 1_{2} & 2_{4} & 2_{5}
\end{bmatrix}
I=[1,1,1,1]T c=[5,4,4,4,4,4] f=[2,1,0,3]T
Po pierwszej iteracji otrzymujemy:
I=[4,3,1,6]T c=[4,2,2,1,0,3] f=[2,1,2,4]T
Po kolejnej iteracji:
I=[4,3,6,6]T c=[3,1,1,0,0,1] f=[3,1,4,5]T
Następnie:
I=[4,3,6,6]T c=[3,1,1,0,0,1] f=[3,1,4,5]T
W tej iteracji w wektorze c nie otrzymalismy, żadanej nowej wartości 0, zatem możemy zakończyć wykonywanie algorytmu. Istnieją c[0]=3 zakleszczone procesy, są to te zadania, dla których wartości w wektorze c są różne od zera, zatem są to zadania {1,2,5}
Algorytm Holt'a - detekcja zakleszczenia:
repeat
flaga:=false;
for j:=1 to z do
while ((I[j]<=n) and (E[0,I[j],j]<=f[j])) do
begin
c[E[1,I[j],j]]:=c[E[1,I[j],j]]-1;
if c[E[1,I[j],j]]=0 then
begin
c[0]:=c[0]-1;
flaga:=true;
for k:=1 to s do
f[k]:=f[k]+A[E[1,I[j],j],k];
end;
I[j]:=I[j]+1;
end;
until not((flaga)and(c[0]>0));
if flaga then writeln('Nie ma zakleszczenia')
else writeln('Istnieje zakleszczenie');
Implementacje
| Autor | Język programowania | Komentarz | Otwórz | Pobierz | Ocena |
| Tomasz Lubiński | C/C++ | .cpp | .cpp | ***** / 3 | |
| Tomasz Lubiński | Delphi/Pascal | .pas | .pas | ***** / 1 | |
| Tomasz Lubiński | Java | .java | .java | ***** / 2 |
Poprawiony: 15 sierpnia 2012 18:34
I=[4,3,1,6]T c=[4,2,2,1,0,3] f=[2,1,2,4]T
Nie powinno tutaj być? :
I=[4,3,1,5]T c=[4,2,2,1,0,2] f=[2,1,2,4]T