SOP wyk nr 11-Slajd25

Wzajemne wykluczanie 2 procesów — podejście 2

Podejście bazuje na współdzielonej tablicy znacznik , przy czy każdy z dwóch procesów modyfikuje w niej pozycję odpowiadającą swojemu numerowi. Traktując poszczególne pozycje tablicy znacznik w odseparowaniu można stwierdzić, że dla procesu Pi znacznik [i ] jest zmienną wyjściową, a dla Pj jest zmienną wejściową. Odwrotna zależność dotyczy oczywiście zmiennej znacznik [j ].

W rozwiązaniu tym proces sygnalizuje zamiar lub docelowo fakt wejścia do sekcji krytycznej, ustawiając znacznik na swojej pozycji na true. W celu stwierdzenia dostępności sekcji krytycznej sprawdza wartość znacznika na pozycji odpowiadającej rywalowi (dla Pi rywalem jest Pj i odwrotnie). Jeśli znacznik na pozycji rywala ma wartość false, proces przerywa pętlę while i tym samym wchodzi do sekcji krytycznej.

Własność bezpieczeństwa łatwo wykazać metodą nie wprost . Zakładając, że dwa procesy mogą jednocześnie wykonywać sekcję krytyczną, każdy z nich musiał odczytać wartość false z pozycji tablicy znacznik , odpowiadającej rywalowi. Wcześniej jednak każdy z nich ustawił wartość true na swojej pozycji. Przeplot z punktu widzenia każdego z procesów musi zatem uwzględniać fakt, że nie została ustawiona wartość true na pozycji rywala. Dla Pi oznacza to, że podstawienie true pod znacznik [j ] wykonało się po zakończeniu pętli while przez Pi . Dla Pj sytuacja jest odwrotna — to Pi musiałby wykonać pętli po podstawieniu true pod znacznik [i ].

Własność postępu nie jest spełniona, gdyż mogą nastąpić podstawienia true pod odpowiednie pozycje znacznika, czyli:

znacznik [i ] := true;

znacznik [j ] := true;

W takim stanie systemu oba procesy utkną w pętli while w swoich sekcjach wejściowych i żaden nie wejdzie do sekcji krytycznej. Stan taki będzie stabilny, tzn. nie zmieni się, jeśli nie nastąpi jakaś interwencja z zewnątrz (spoza zbioru procesów). Jest to przykład zakleszczenia (ang. deadlock).

<< Poprzedni slajd | Spis treści | Następny slajd >>