Sr-7-wyk-2.0-Slajd31
Zapobieganie zakleszczeniom w systemach rozproszonych
Wiele spośród algorytmów zapobiegania zakleszczeniom stosowanych w systemach nierozproszonych można zastosować również w środowiskach rozproszonych. Wymaga to oczywiście pewnych dodatkowych mechanizmów, jak m.in. odpowiedniego zastosowania globalnego porządku w systemie (np. wobec zasobów). Nieraz koszt takiego rozwiązania jest jednak nieopłacalny i trzeba zastosować inne rozproszone metody.
Poniżej prezentujemy zastosowanie znaczników czasowych, jako środek służący do zapobiegania zakleszczeń w systemach z wywłaszczaniem zasobów. Aby uprościć analizę, zakładamy istnienie jednego egzemplarza każdego zasobu.
W przedstawianym algorytmie każdy proces ma przypisany unikalny priorytet, który decyduje o tym, czy jeden proces powinien czekać na inny. Stosując informacje o priorytetach procesów, możemy nakazać, aby w razie konfliktu proces Pi o wyższym priorytecie mógł czekać na proces Pj o niższym priorytecie. W przeciwnym wypadku, gdy proces Pi ma niższy priorytet, usuwamy go z pamięci.
Stosując powyższy schemat pozbyliśmy się problemu zakleszczeń, ale pojawił się niestety problem w postaci możliwości zagłodzenia procesów o niskich priorytetach. Może się zdarzyć, że procesy takie będą wiecznie wywłaszczane przez procesy o wyższych priorytetach. W tym celu zaproponowano użycie znaczników czasowych i zaproponowano dwa podejścia do rozwiązania problemu. Unikalne znaczniki czasu nadaje się procesom raz, w trakcie ich utworzenia.
W pierwszej metodzie, zwanej czekanie albo śmierć (ang. wait-die ), nie używa się wywłaszczeń. Gdy proces Pi przetrzymuje zasób, którego chce użyć inny proces Pj , to Pj może poczekać aż zasób zostanie zwolniony tylko wtedy, gdy jego znacznik czasu jest mniejszy od znacznika czasu procesu Pi . W przeciwnym razie proces Pj jest usuwany z pamięci.
Zranienie albo czekanie (ang. wound-wait ) jest drugim zaproponowanym podejściem, które stosuje wywłaszczanie. W tym podejściu jeżeli proces Pj oczekuje zasobu używanego aktualnie przez Pi , to Pj może poczekać na zasób pod warunkiem, że znacznik czasu Pj jest większy. Inaczej Pj zostaje „zraniony”, czyli usunięty z pamięci.
Jak można zauważyć powyższe metody różnią się znacząco od siebie. Niemniej pozwalają na uniknięcie wcześniejszego problemu głodzenia, jeżeli usunięte procesy nie będą otrzymywały nowych znaczników.
Wadą obu schematów jest występowanie niepotrzebnych wywłaszczeń nawet, gdy nie ma zakleszczeń. W celu uniknięcia tego typu sytuacji można zastosować wykrywanie zakleszczeń.
