Rozdział 7
ZAKLESZCZENIA*
W środowisku wieloprogramowym kilka procesów może rywalizować o skończoną liczbę zasobów. Proces zamawia zasoby i jeśli nie są one dostępne w danym czasie, wchodzi w stan oczekiwania. Może się zdarzyć, że oczekujące procesy nigdy już nie zmienią swego stanu, ponieważ zamawiane przez nie zasoby są przetrzymywane przez inne procesy. Sytuację taką nazywa się zakleszczeniem" (ang. deadlock). Zagadnienie to omawialiśmy już pokrótce w rozdz. 6 przy okazji semaforów.
Być może najlepszą ilustrację zakleszczenia można zaczerpnąć z prawa ustanowionego przez legislaturę stanu Kansas w początku tego wieku. Głosiło ono w szczególności, że: „Jeśli dwa pociągi zbliżają się do siebie po krzyżujących się torach, to każdy z nich powinien się zatrzymać i nie ruszać ponownie do czasu, aż drugi z nich odjedzie".
W tym rozdziale opisujemy metody, za pomocą których system operacyjny może pokonywać problem zakleszczenia. Zwróćmy jednak uwagę, że większość współczesnych systemów operacyjnych nie ma środków zapobiegania zakleszczeniom. We właściwości takie zostaną one prawdopodobnie wyposażone z upływem czasu, gdy problemy zakleszczeń zaczną pojawiać się częściej. Przyczyną takiego przebiegu zdarzeń będzie kilka tendencji, w tym rosnące liczby procesów, znaczny przyrost ilości zasobów (w tym procesorów) i większy nacisk kładziony na długowieczne serwery plików i baz danych aniżeli na systemy wsadowe.
' Przypominamy, że z uwagi na aktualną normę terminologiczną w tym przekładzie termin ..zakleszczenie" będzie stosowany w miejsce terminu „blokada" przyjętego w poprzednich wydaniach tej książki. - Przyp. tłum.
" Inaczej: blokada, zastój, impas. - Przyp. tłum.
242 Rozdział 7 Zakleszczenia
7.1 • Model systemu
System składa się ze skończonej liczby zasobów, które są rozdzielane między pewną liczbę rywalizujących ze sobą procesów. Zasoby dzieli się na typy, z których każdy zawiera pewną liczbę identycznych egzemplarzy. Przykładami typów zasobów są: obszar pamięci, cykle procesora, pliki i urządzenia wejścia-wyjścia (takie jak drukarki czy przewijaki taśmy). Jeśli system ma dwa procesory, to zasób typu procesor ma dwa egzemplarze. Podobnie, zasób typu drukarka może mieć pięć egzemplarzy.
Jeśli proces zamawia egzemplarz: zasobu jakiegoś typu, to jego zapotrzebowanie spełni przydział dowolnego egzemplarza danego typu. Gdyby tak się nie stało, oznaczałoby to, że egzemplarze nie są identyczne i klasy zasobów nie zostały właściwie zdefiniowane. Na przykład system może mieć dwie drukarki. Obie mogą być zaliczone do tej samej klasy zasobów, jeśli nikomu nie zależy na tym, która drukarka będzie wyprowadzała czyje wyniki. Jednakże, gdy jedna drukarka znajduje się na ósmym piętrze, a druga w piwnicy, wówczas ludzie z ósmego piętra mogą nie uważać obu drukarek za równoważne; w tej sytuacji byłoby pożądane zaliczyć je do oddzielnych klas.
Proces powinien zamówić zasób przed jego użyciem i zwolnić go po wykorzystaniu. Proces może żądać tylu zasobów, ile ich potrzebuje do wykonania zadania. Oczywiście liczba zamawianych zasobów nie może przekroczyć ogólnej liczby zasobów dostępnych w systemie. Innymi słowy, proces nic może zamówić trzech drukarek, jeśli system ma tylko dwie drukarki.
W normalnych warunkach działania proces może użyć zasobu tylko w następującym porządku:
1. Zamówienie: Jeśli zamówienie nie może być spełnione natychmiast (np. zasób jest użytkowany przez inny proces), to proces zamawiający musi czekać do chwili otrzymania zasobu.
2. Użycie: Proces może korzystać z zasobu (np. jeśli zasobem jest drukarka, to proces może drukować na tej drukarce).
3. Zwolnienie: Proces oddaje zasób.
Zasoby można zamawiać i zwalniać za pomocą funkcji systemowych, jak było wyjaśnione w rozdz. 3. Przykładami są funkcje systemowe przydzielania i zwalniania urządzenia, otwarcia i zamknięcia pliku oraz przydziału i zwolnienia pamięci. Zamawianie i zwalnianie innych zasobów może być dokonywane za pomocą semaforowych operacji czekaj i sygnalizuj. Dzięki temu przed każdym użyciem zasobu system operacyjny sprawdza, czy proces zamówił dany zasób i czy mu go przydzielono. W tablicy systemowej zapisuje się, czy zasób jest wolny czy też przydzielony, a jeśli jest przydzielony, to do
7.2 Charakterystyka zakleszczenia 243
którego procesu. Jeśli proces zamawia zasób, który jest aktualnie przydzielony innemu procesowi, to zamawiający proces dołącza się do kolejki procesów oczekujących na dany zasób.
Zbiór procesów jest w stanic zakleszczenia, gdy każdy proces z tego zbioru czeka na zdarzenie, które może być spowodowane tylko przez inny proces z tego samego zbioru. Zdarzenia, z którymi najczęściej mamy tu do czynienia, dotyczą przydziału i zwalniania zasobów. Może tu chodzić o zasoby fizyczne (np. drukarki, przewijaki taśmy, miejsce w pamięci i cykle procesora) lub logiczne (takie jak pliki, semafory i monitory). Niemniej jednak także i inne typy zdarzeń mogą prowadzić do zakleszczeń (np. schemat komunikacji międzyprocesowej omawiany w rozdz. 4).
Aby zobrazować zakleszczenie, rozważymy system z trzema przewija-kami taśmy. Załóżmy, że istnieją trzy procesy, z których każdy przetrzymuje jeden z tych przewijaków. Jeśli każdy proces zamówi teraz dodatkowy prze-wijak taśmy, to omawiane trzy procesy znajdą się w stanie zakleszczenia. Każdy będzie czekał na zdarzenie „zwolniono przcwijak taśmy", które mogłoby być spowodowane tylko przez któryś z pozostałych czekających procesów. Ten przykład ilustruje zakleszczenie dotyczące procesów rywalizujących o zasób tego samego typu.
Przyczyną zakleszczeń mogą być także zasoby różnych typów. Rozważmy na przykład system z jedną drukarką i jednym przewijakiem taśmy. Załóżmy, że proces P, ma przydzielony przcwijak taśmy, a proces P, przetrzymuje drukarkę. Jeśli P, zamówi teraz drukarkę, a /', zamówi przewijak taśmy, to wystąpi zakleszczenie.
7.2 • Charakterystyka zakleszczenia
Jest zrozumiałe, że zakleszczenia nie są zjawiskiem pożądanym. Będące w stanie zakleszczenia procesy nigdy nie skończą swoich działań, wiążąc zasoby systemowe i uniemożliwiając rozpoczęcie wykonywania innych zadań. Zanim omówimy różne metody postępowania z problemem zakleszczeń, opiszemy cechy, którymi zakleszczenia się charakteryzują.
7.2.1 Warunki konieczne
Do zakleszczeń może dochodzić wtedy, kiedy w systemie zachodzą jednocze-śnie cztery warunki:
1. Wzajemne wykluczanie: Przynajmniej jeden zasób musi być niepodzielny; to znaczy, że zasobu tego może używać w danym czasie tylko
244 Rozdział 7 Zakleszczenia
jeden proces. Jeśli inny proces zamawia dany zasób, to musi być opóźniany do czasu, aż zasób zostanie zwolniony.
2. Przetrzymywanie i oczekiwanie: Musi istnieć proces, któremu przydzielono co najmniej jeden zasób i który oczekuje na przydział dodatkowego zasobu, przetrzymywanego właśnie przez inny proces.
3. Brak wywłaszczeń: Zasoby nie podlegają wywłaszczaniu, co oznacza, że zasób może zostać zwolniony tylko z inicjatywy przetrzymującego go procesu, po zakończeniu pracy tego procesu.
4. Czekanie cykliczne: Musi istnieć zbiór {/><,, Ph ..., P„\ czekających procesów, takich że P0 czeka na zasób przetrzymywany przez proces Pu
P\ czeka na zasób przetrzymywany przez proces P2, ..., P„ -1 czeka na zasób przetrzymywany przez proces /',„ a P„ czeka na zasób przetrzymywany przez proces Po.
Podkreślmy, że do wystąpienia zakleszczenia jest niezbędne, aby były spełnionewszystkie cztery warunki. Warunek czekania cyklicznego implikuje warunek przetrzymywania i oczekiwania, wice wymienione cztery warunki nie są zupełnie niezależne. Wykażemy jednak w p. 7.4, że rozważanie każdego z nich z, osobna jest wygodne.
7.2.2 Graf przydziału zasobów
Zakleszczenia można dokładniej opisać za pomocą grafu skierowanego, zwanego tu grafem przydzielili zasobów systemu (ang. system resowce-allocation graph). Graf ten składa sic ze zbioru wierzchołków W i zbioru krawędzi K. Zbiór wierzchołków J^jest podzielony na dwa rodzaje węzłów: P = {Pi, Pi, ..., P„), czyli zbiór wszystkich procesów systemu, oraz Z = {Z,, Zj, ..., Z,,,} - oznaczający zbiór wszystkich typów zasobów systemowych.
Krawędź skierowaną od procesu P, do zasobu typu Zj zapisuje się w postaci P, -> 2,; oznacza ona, że proces P, zamówił egzemplarz zasobu typu Z, i obecnie czeka na ten zasób. Krawędź skierowana od zasobu typu Z, do procesu ?„ co zapisujemy w postaci Z,-> P„ oznacza, że egzemplarz zasobu typu Z, został przydzielony do procesu P,. Krawędź skierowaną P, -+ Z, nazywa się krawędzią zamówienia (ang. reąuest algę), a krawędź skierowaną Z, -» P, nazywa się krawędziąprzydziału (ang. assignmentedge).
Każdy proces P, jest przedstawiany na rysunku w postaci kółka, a każdy typ zasobu Zj - w postaci prostokąta. Ponieważ zasób typu Z, może mieć więcej niż jeden egzemplarz, każdy egzemplarz zasobu będziemy oznaczać kropką umieszczoną w prostokącie. Zauważmy, że krawędź zamówienia sięga
7.2 Charakterystyka zakleszczenia 245
tylko do brzegu prostokąta Z„ podczas gdy krawędź przydziału musi także wskazywać na jedną z kropek w prostokącie.
Kiedy proces P, zamawia egzemplarz zasobu typu Z,. wtedy w grafie przydziału zasobów umieszcza się krawędź zamówienia. Gdy zamówienie to zostaje spełnione, wówczas krawędź zamówienia natychmiast zamienia się na krawędź przydziału. Gdy zasób przestaje być procesowi potrzebny, wówczas proces zwalnia go. wskutek czego krawędź przydziału zostanie usunięta.
Graf przydziału zasobów na rys. 7.1 odzwierciedla nastfpującąsytoację:
• Zbiory/", Z i K:oP={Pl,P2,,,3}-oZ={Z,,Z,,Z,,Z4},
oK= {Pr^Zu Pi^-Zi, Z, -»Ą, Z, -► P2, Z2 -+Ą, Z, -h> P,}.
Egzemplarze zasobów: o jeden egzemplarz zasobu typu Z, ; o dwa egzemplarze zasobu typu Z2, o jeden egzemplarz zasobu typu Z,; o trzy egzemplarze zasobu typu Z,,.
• Stany procesów:
o proces P, utrzymuje egzemplarz zasobu typu Z, i oczekuje na egzemplarz zasobu typu Z,;
o proces Pi ma po egzemplarzu Z, i Z, i czeka na egzemplarz zasobu typu
Zr,
o proces ft ma egzemplarz zasobu Zj.
Mając definicję grafu przydziału zasobów, można wykazać, że jeśli graf nie zawiera cykli, to w systemie nie ma zakleszczonych procesów. Jeśli natomiast graf zawiera cykl, to może dojść do zakleszczenia.
Jeżeli zasób każdego typu ma tylko jeden egzemplarz, to cykl implikuje, że doszło do zakleszczenia. Jeśli cykl zawiera zbiór tylko takich typów zasobów, z których każdy ma tylko pojedynczy egzemplarz, to zakleszczenie jest faktem. Każdy proces występujący w cyklu tkwi w miejscu. W tym wypadku istnienie cyklu w grafie jest warunkiem koniecznym i wystarczającym do wystąpienia zakleszczenia.
246 Rozdział 7 Zakleszczenia
Rys. 7.1 Graf przydziału zasobów
Jeśli istnieje po kilka egzemplarzy zasobu każdego typu, to obecność cyklu nie oznacza jeszcze, że wystąpiło zakleszczenie. W tym wypadku cykl
w grafie jest warunkiem koniecznym, lecz nie wystarczającym do istnienia zakleszczenia.
Aby zilustrować tę koncepcję, powróćmy do grafu przydziału zasobów przedstawionego na rys. 7.1. Załóżmy, że proces Pi zamawia egzemplarz zasobu typu 7.7. Ponieważ w danej chwili nie ma żadnego wolnego egzemplarza tego zasobu, do grafu dodaje sie krawędź zamówienia 1\ -> Z2 (rys. 7.2). Od tej chwili w systemie istnieją dwa cykle minimalne:
P, -* Z, -* /', -> Z3 -+ /*,-*■ Zi-» Pi
Rys. 7.2 Graf przydziału zasobów / zakleszczeniem
P, _» Z,_i P, -ł 7,—i'7>,
Automation_Engineering