SOP wyk nr 11-Slajd25: Różnice pomiędzy wersjami
zmiana sformułowania |
m formatowanie |
||
| Linia 6: | Linia 6: | ||
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'' ]. | 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 '' | 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 ''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 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ść 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 przez niego pętli '''while'''. Dla ''Pj'' sytuacja jest odwrotna, więc ''Pi'' musiałby wykonać pętlę po podstawieniu true pod ''znacznik''[''j'']. | ||
| Linia 12: | Linia 12: | ||
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: | ||
''znacznik'' [''i | ''znacznik''[''i''] := true; | ||
''znacznik'' [''j | ''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). | 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). | ||
Wersja z 23:37, 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 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).
