KSO-blokady i zagłodzenia.doc

Systemy operacyjne / Współbieżność: blokady i zagłodzenia                                23

Współbieżność: blokady i zagłodzenia

System komputerowy składa się ze skończonej liczby zasobów, o które ubiega się pewna liczba procesów. Jeżeli pewien proces zamówi zasób, a zasób nie jest dostępny, to proces przechodzi w stan zawieszenia Z,

Sytuację, w której oczekujące procesy nigdy nie zmienią swego stanu, ponieważ zamówione przez nie zasoby są przetrzymywane przez inne procesy, nazywamy blokadą (ang. deadlock).

Założenia odnośnie rozpatrywanego modelu

·      całość zasobów dzieli się na kilka grup, z których każda zawiera pewną liczbę identycznych egzemplarzy,

·      proces powinien zamówić zasób przed jego użyciem i zwolnić go po wykorzystaniu,

·      proces może żądać tyle zasobów, ile ich potrzebuje do wykonania zadania, przy czym nie potrzebuje ich więcej niż jest dostępne w systemie.

Kolejne kroki podczas korzystania z zasobu

1.             zamówienie, jeśli nie może być spełnione, to proces ® Z,

2.             korzystanie z zasobu (np. czytanie z pliku),

3.             zwolnienie zasobu.

Definicja blokady

Zbiór procesów pozostaje w stanie blokady, jeżeli każdy proces z tego zbioru czeka na zdarzenie, które może być spowodowane tylko przez inny proces z tego samego zbioru.

Najczęściej zdarzenia te dotyczą przydzielania i zwalniania zasobów, takich jak:

·      zasoby fizyczne (drukarki, miejsce w pamięci, cykle procesora),

·      zasoby logiczne (pliki, semafory).

Przykład z alokacją pamięci

·      dwa procesy żądają przydziału pamięci,

·      liczba dostępnej pamięci: 200kB,

·      proces A:

o    żądanie przydziału 80kB,

o    żądanie przydziału 60kB,

·      proces B:

o    żądanie przydziału 70kB,

o    żądanie przydziału 80kB,

Przykład z przekazywaniem komunikatów

·      proces A:

o    receive( B, M1),

o    send( B, M2),

·      proces B:

o    receive( A, M2),

o    send( A, M1),

Warunki konieczne istnienia blokady

Sytuacja blokady może powstać wtedy i tylko wtedy, gdy w systemie są jednocześnie spełnione cztery warunki (WKB):

1.       wzajemne wykluczanie

Przynajmniej jeden zasób musi być niepodzielny, tzn. że zasobu tego może używać w danym czasie tylko jeden proces. Jeżeli inny proces zamawia dany zasób, to jest zawieszany do czasu, aż zasób zostanie zwolniony.

2.       przetrzymywanie i oczekiwanie

Musi istnieć proces mający przydzielony co najmniej jeden zasób i oczekujący na przydział dodatkowego zasobu, który jest przetrzymywany przez inny proces.

3. 
   Brak wywłaszczeń

Zasoby nie podlegają wywłaszczaniu, tzn., że zasób może zostać zwolniony tylko z inicjatywy przetrzymującego go procesu, po zakończeniu działania tego procesu.

4.       Czekanie cykliczne

Musi istnieć zbiór {Po,P1,...,Pn} czekających procesów (w stanie Z) takich, że

Po czeka na zasób przetrzymywany przez proces P1

P1 czeka na zasób przetrzymywany przez proces P2

..

Pn czeka na zasób przetrzymywany przez proces Po

·      warunek czekania cyklicznego 4. implikuje warunek 2., więc warunki te nie są zupełnie niezależne. Rozpatrywanie ich z osobna jest jednak wygodne.

Graf przydziału zasobów

Blokady można dokładniej opisać za pomocą pojęcia grafu skierowanego, zwanego grafem przydziału zasobów systemu. Graf  ten składa się z dwóch zbiorów:

·                       zbioru wierzchołków W,

·                       zbioru krawędzi K.

Zbiór W jest podzielony na dwa podzbiory:

·   zbiór wszystkich procesów

P={Po,P1,...,Pn}

·   zbiór wszystkich zasobów

Za={Zo,Z1,...,Zn}

Oznaczenia

1.       Krawędź skierowaną od Pi od Zj zapisuje się w postaci Pi®Zj. Oznacza, że Pi zamówił egzemplarz    zasobu typu Zj i czeka na ten zasób. Krawędź tąka nazywamy krawędzią zamówienia,

2.       Krawędź skierowaną od Zj od Pi zapisuje się w postaci Zj®Pi. Oznacza, że egzemplarz zasobu typu Zj został przydzielony do Pi. Krawędź tą nazywamy krawędzią przydziału,

3.       Każdy proces Pi będzie przedstawiany w postaci kółka, a każdy typ zasobu Zj - w postaci prostokąta

Można wykazać, że:

·      jeśli graf nie zawiera cykli, to żaden proces w systemie nie uległ blokadzie,

·      jeśli graf zawiera cykl, to może dojść do blokady, przy czym:

·      jeżeli zasób każdego typu ma tylko jeden egzemplarz, to cykl implikuje, że wystąpiła blokada. Każdy proces występujący w cyklu tkwi w blokadzie. W tym przypadku istnienie cyklu jest warunkiem koniecznym i wystarczającym blokady,

·      jeżeli zasób każdego typu ma po kilka egzemplarzy, to obecność cyklu nie oznacza, że wystąpiła blokada. W tym przypadku cykl w grafie jest warunkiem koniecznym, lecz niewystarczającym.

Metody postępowania z blokadami

Dwa podejścia

1.       stosowanie protokołu gwarantującego, że system nigdy nie wejdzie w stan blokady, przy czym stosowane są dwie metody:

a.       zapobieganie blokadom,

b.       unikanie blokad.

2.       dopuszczanie sytuacji wystąpienia blokady, po czym podjęcie działań zmierzających do jej usunięcia.

1.a              Zapobieganie blokadom

Koncepcja oparta na założeniu, że jeżeli przynajmniej jeden z WKB nie będzie spełniony, to możemy zapobiec pojawieniu się blokady.

Dla poszczególnych warunków:

Wzajemne wykluczanie (WW)

Warunek WW musi być spełniony w odniesieniu do zasobów niepodzielnych (np.drukarki). Natomiast istnieje wiele zasobów dzielonych, które nie wymagają dostępu na zasadzie WW, a więc nie będą występować w blokadach. Przykładem mogą być pliki udostępniane tylko do czytania.

·      na ogół zapobieganie blokadom nie jest możliwe przez wyłączenie warunku WW.

Przetrzymywanie i Oczekiwanie (P&O)

W celu zapewnienia, aby warunek P&O nigdy nie wystąpił, musimy przestrzegać zasady:

·      jeżeli proces zamawia zasób, to nie powinien mieć (żadnych) innych przydzielonych zasobów

Dwa podejścia

1. każdy proces zanim rozpocznie swoje działanie powinien zamawiać i dostawać wszystkie swoje zasoby. Jednym ze sposobów może być zatem, umieszczanie w programie na wstępie wszystkich wywołań systemowych dotyczących zamówień zasobów,

2. alternatywnym rozwiązaniem może być wprowadzenie zasady, że proces może zamówić jakiś zasób tylko wówczas, jeśli odda wszystkie zasoby, które ma w danej chwili przydzielone.

Wady metod zapobiegającym spełnienie P&O:

·      wykorzystanie zasobów może być bardzo małe, ponieważ z wielu przydzielonych zasobów nikt nie będzie korzystał przez długie okresy czasu,

·      może dochodzić do blokowania nieskończonego, zwanego głodzeniem procesu.

Brak wywłaszczeń

W celu zapewnienia, aby warunek ten nigdy nie wystąpił, można zastosować jeden z następujących protokołow:

1. jeśli  proces (P) mający jakieś zasoby (Za) zgłasza zapotrzebowanie na inny Za, który nie może być mu natychmiast przydzielony (tzn. P musiałby czekać ® Z), wówczas traci wszystkie dotychczasowe Za. Są one zwalniane w sposób niejawny i dopisywane do listy Za, na które oczekuje. P zostanie wznowiony dopiero wtedy, gdy będzie można mu przywrócić wszystkie jego dawne Za oraz dodać nowy, który zamawiał;
2. jeśli  proces (P) mający jakieś zasoby (Za) zgłasza zapotrzebowanie na inny Za, który nie może być mu natychmiast przydzielony, wówczas sprawdza czy zasób ten jest przydzielony do innego P, który jest w stanie Z. Jesli tak, to odbiera mu się ten Za i przydziela procesowi aktualnie zamawiającemu. Jeśli Za nie jest ani dostępny, ani przetrzymywany przez inny czekający proces, to P® Z.

Protokół ten często stosuje się do zasobów, których stan można łatwo przechować i później odtworzyć, jak np. rejestry procesora, czy obszary pamięci. Na ogół nie można go stosować do takich zasobów, jak drukarki i stacje taśmy.

Czekanie cykliczne

Jednym ze sposobów zagwarantowania, że czekanie cykliczne nie wystąpi, jest wymuszenie uporządkowania całkowitego wszystkich typów zasobów i wymaganie, aby każdy proces zamawiał zasoby we wzrastającym porządku ich numeracji.

1.b              Unikanie blokad

Algorytmy zapobiegania blokadom uniemożliwiały powstawanie blokad przez nakładanie ograniczeń na wykonywanie zamówień. Gwarantowało to niespełnienie przynajmniej jednego z WKB, wobec czego blokada nie mogła wystąpić. Wadą tych algorytmów jest słabe wykorzystanie urządzeń i ograniczona przepustowość systemu.

Alternatywna metoda unikania blokad wymaga dodatkowych informacji (inf) o tym, jak będzie następowało zamawianie zasobów. Mając wszystkie informacje na temat kolejności występowania zamówień i zwolnień dla każdego procesu, system operacyjny może decydować przy każdym zamówieniu, czy P powinień czekać (P® Z), czy też nie.

Poszczególne algorytmy różnią się pod względem ilości i typu wymaganych informacji. W najprostszym i najbardziej użytecznym modelu zakłada się, że każdy proces zadeklaruje maksymalną liczbę zasobów każdego typu, których mógłby potrzebować. Dysponując tą informacją  można zbudować algorytm unikania blokady. Algorytm ten sprawdza stan przydziałów zasobów, aby zagwarantować, że nigdy nie dojdzie do warunku czekania cyklicznego.

Stan przydziału zasobów jest określony przez:

·      liczbę dostępnych i przydzielonych zasobów,

·      maksymalne zapotrzebowanie P.

Stan jest bezpieczny, jeśli istnieje porządek, w którym system operacyjny może przydzielić zasób każdemu procesowi stale unikając blokady. Mówiąc bardziej formalnie, system jest w stanie bezpiecznym tylko wtedy, gdy istnieje ciąg bezpieczny procesów.

...