SOP wyk nr 11-Slajd25: Różnice pomiędzy wersjami
m formatowanie |
m uzupełnienie brakujących słów |
||
| Linia 8: | Linia 8: | ||
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 ''P<sub>i</sub>'' rywalem jest ''P<sub>j</sub>'' i odwrotnie). Jeśli ''znacznik'' na pozycji rywala ma wartość false, proces przerywa pętlę '''while''' i tym samym wchodzi do sekcji krytycznej. | 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 ''P<sub>i</sub>'' rywalem jest ''P<sub>j</sub>'' 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 ''P<sub>i</sub>'' oznacza to, że podstawienie true pod ''znacznik''[''j''] wykonało się po zakończeniu przez niego pętli '''while'''. Dla ''P<sub>j</sub>'' sytuacja jest odwrotna, więc ''P<sub>i</sub>'' musiałby wykonać pętlę po podstawieniu true pod ''znacznik''[''j'']. | Własność bezpieczeństwa łatwo można 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 ''P<sub>i</sub>'' oznacza to, że podstawienie true pod ''znacznik''[''j''] wykonało się po zakończeniu przez niego pętli '''while'''. Dla ''P<sub>j</sub>'' sytuacja jest odwrotna, więc ''P<sub>i</sub>'' musiałby wykonać pętlę po podstawieniu true pod ''znacznik''[''j'']. | ||
Własność postępu nie jest spełniona, gdyż mogą nastąpić podstawienia true pod odpowiednie pozycje znacznika, czyli: | Własność postępu nie jest spełniona, gdyż mogą nastąpić podstawienia true pod odpowiednie pozycje znacznika, czyli: | ||
Aktualna wersja na dzień 23:42, 4 wrz 2006
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 można 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 przez niego pętli while. Dla Pj sytuacja jest odwrotna, więc Pi musiałby wykonać pętlę po podstawieniu true pod znacznik[j].
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).
