Informatyka MIMUW

Zapobieganie zakleszczeniom — wzajemne wykluczanie

Zapobieganie, podobnie jak unikanie, jest podejściem polegającym na niedopuszczaniu do zakleszczenia. W przeciwieństwie do unikania, decyzja o akceptacji lub odłożeniu realizacji zamówienia podejmowana jest wyłącznie w oparciu o bieżący stan systemu. Nie są tu uwzględniane żadne dane na temat przyszłych zachowań procesów. Podejście takie musi być zatem bardziej zachowawcze — w większym stopniu i często nadmiarowo ograniczające aktywność procesów.

Zapobieganie polega na kontrolowaniu zaistnienia warunków koniecznych. Wystarczy nie dopuścić do spełnienia jednego z nich, a nie dojdzie do zakleszczenia.

Ze względu na sposób korzystania z niektórych zasobów nie można podjąć żadnych kroków w celu przeciwdziałania warunkowi wzajemnego wykluczania.

• Konieczność zagwarantowania wzajemnego wykluczania wynika z charakterystyki zasobu — wzajemne wykluczanie musi być zachowane w przypadku dostępu do zasobów niepodzielnych.
• Zasoby współdzielone nie wymagają dostępu w trybie wyłącznym, więc używanie zasobu przez jeden proces nie blokuje dostępu do niego innym procesom.

Zapobieganie zakleszczeniom — przetrzymywanie i oczekiwanie

Podejście ma wiele wad. Uzyskanie wszystkich zasobów przed rozpoczęciem przetwarzania może oznaczać przetrzymywanie zasobów, które przez długi czas nie będą wykorzystywane (np. rezerwacja przestrzeni dyskowej dla stopniowo powiększanego pliku). W konsekwencji mamy do czynienia ze słabym wykorzystaniem zasobów, blokowanie dostępu innym procesom i tym samym zmniejszenie przepustowości systemu.

Sama realizacja praktyczna tego podejścia może być kłopotliwa, gdyż na początku przetwarzania wymagana jest wiedza o zasobach, niezbędnych do realizacji całego przetwarzania, podczas gdy pewne potrzeby ujawniają się dopiero w trakcie samego przetwarzania (np. zapotrzebowanie na dynamicznie alokowaną pamięć, czy przestrzeń dyskową).

Problemem może też być głodzenie procesu ze względu na fakt, że nigdy nie będą jednocześnie dostępne wszystkie zasoby żądane przez proces.

• Przeciwdziałanie warunkowi przetrzymywania i oczekiwania polega na uniemożliwieniu procesowi zamawiania zasobów w czasie, gdy proces sam przetrzymuje jakieś zasoby i blokuje do nich dostęp.
• Metoda 1: proces musi zamówić i uzyskać wszystkie zasoby, zanim rozpocznie realizację zadania, do którego zasoby te są potrzebne.
• Metoda 2: przed zamówieniem dodatkowych zasobów proces musi zwolnić zasoby przydzielone dotychczas (ewentualnie zamówić je ponownie łącznie z nowymi zasobami).

Zapobieganie zakleszczeniom — brak wywłaszczeń

Wywłaszczenie musi zostać zrealizowane we właściwym momencie. Sensowny jest moment, kiedy proces zamawia zasób, ale zasób ten nie jest natychmiast dostępny. Zwalniane są wówczas zasoby przez niego przetrzymywane (od tego momentu są wolne) i dopisywane do bieżącego zamówienia. Wznowienie procesu nastąpi po zrealizowaniu całego zamówienia.

Inny dogodny moment ma miejsce, kiedy proces zamawia zasób, który jest przetrzymywany przez inny oczekujący proces. Zasób ten (lub zasoby) jest wówczas odbierany procesowi oczekującemu i przydzielany zamawiającemu. Jeśli zasób nie jest dostępny, ale jest przetrzymywany przez proces nie zablokowany w oczekiwaniu (domniemamy, że proces działa i używa tego zasobu), proces zamawiający sam przechodzi w stan oczekiwania. W stanie oczekiwania proces może stracić swoje zasoby, o ile pojawią się żądania od inny procesów. Wznowienie procesu następuje po odzyskaniu zasobów utraconych w czasie oczekiwania i uzyskaniu zasobów nowo zamawianych.

• Dopuszczenie wywłaszczeń oznacza możliwość odebrania procesowi zasobu.
• Metoda 1: zwolnienie zasobów procesu w momencie zamówienia dodatkowych zasobów, przetrzymywanych przez inne procesy.
• Metoda 2: odbieranie żądanych zasobów przetrzymującym je procesom, gdy procesy te są w stanie oczekiwania na inne zasoby.

Zapobieganie zakleszczeniom — cykl w oczekiwaniu

Wcześniejsze warunki konieczne związane są z projektem systemu lub charakterystyką zasobów. Cykl wynika natomiast z funkcjonowania samych procesów aplikacyjnych, więc znaczenie łatwiej można to kontrolować. Przeciwdziałanie cyklowi jest więc najczęściej stosowaną metodą zapobiegania zakleszczeniom.

Opisana metoda wymaga, żeby jednostki zasobów, oznaczone tym samym numerem, zamawiane były w jednym zleceniu dla zarządcy.

• W celu przeciwdziałania cyklowi w oczekiwaniu procesów na zasoby, należy zapewnić, że wszystkie zasoby będą zamawiane w tej samej dla wszystkich procesów kolejności.
• Metoda: nadanie unikalnych numerów wszystkim typom zasobów, czyli odwzorowanie zbiorów f : Z → N, i zamawianie zasobów zgodnie z zasadą: f(Z_j) > f(Z_i) ⇒ jednostka (lub jednostki) zasobu Z_j są zamawiane po zrealizowaniu zamówienia na jednostki zasoby Z_i,
• Inaczej: nie można zamawiać jednostek zasobu Z_i jeśli są przydzielone jednostki zasobu Z_j gdy f(Z_j) ≥ f(Z_i) .

Łączenie metod postępowania z zakleszczeniami

Ze względu na różnice w charakterystyce zasobów, pewne metody można stosować w przypadku określonych rodzajów zasobów, ale nie można w przypadku innych rodzajów. Przykłady tego typu przewijały się w omawianych podejściach do rozwiązywania problemu zakleszczenia. Podejście zintegrowane polega na tym, żeby zasoby o podobnej charakterystyce łączyć w grupy, a liniowe uporządkowanie grup z kolei ułatwia przeciwdziałanie cyklowi przy alokacji.

• W zależności od rodzaju zasobu systemu komputerowego stosowane są różne metody postępowania.
• Zasoby dzieli się na liniowo uporządkowane grupy. Żądania procesów realizowane są w kolejności wynikającej z porządku grup, w których znajdują się żądane zasoby.
• W obrębie zasobów w danej grupie stosowana jest właściwa dla tej grupy strategia realizacji żądań.

Przykład grup zasobów

• Pamięć pomocnicza — obszary pamięci w strefie wymiany na dysku
• Zasoby zadania — pliki, urządzenia itp.
• Pamięć główna — obszary pamięci w obrębie fizycznej przestrzeni adresowej
• Zasoby wewnętrzne — zasoby używane przez system do zarządzania procesami (np. bloki kontrolne, kanały wejścia-wyjścia)

Przykład metod w obrębie grup zasobów

• Wstępny przydział w przypadku pamięci pomocniczej jest możliwy, gdyż wymagany rozmiar obrazu procesu jest na ogół znany w momencie ładowania programu do pamięci.
• Zapotrzebowanie na pliki i urządzenia może być znane z góry (np. w systemach wsadowych).
• O możliwości wywłaszczenia pamięci fizycznej wspomniano już przy usuwaniu zakleszczenia.
• Zasoby wewnętrzne można uporządkować np. zgodnie z adresem w pamięci.