Pr-1st-1.1-m09-Slajd44

Z Studia Informatyczne
Wersja z dnia 16:02, 7 wrz 2006 autorstwa Szopen (dyskusja | edycje)
(różn.) ← poprzednia wersja | przejdź do aktualnej wersji (różn.) | następna wersja → (różn.)
Przejdź do nawigacjiPrzejdź do wyszukiwania

Twierdzenie 9.3

Twierdzenie 9.3


Twierdzenie 9.3

Jeżeli przetwarzanie dyfuzyjne uległo zakończeniu, fakt ten ulega wykryciu przez algorytm Dijkstry-Scholtena.

Dowód Jeżeli przetwarzanie dyfuzyjne ulega zakończeniu, oznacza to, że nie ma żadnego aktywnego procesu ani nie ma żadnych wiadomości ani sygnałów w kanałach komunikacyjnych. Oznacza to także, że żaden proces nie może wysyłać żadnych wiadomości ani potwierdzeń. W związku z tym, można wywnioskować, że jeżeli przetwarzanie ulegnie zakończeniu, to w każdym procesie (za wyjątkiem procesu-inicjatora) zachodzi: oraz . Spostrzeżenie to można uprościć do postaci .

Z kolei dla procesu inicjującego oczywiste jest, że zachodzi .

Dalej można wywnioskować, że w stanie zakończenia przetwarzania . Ponieważ żadne wiadomości ani sygnały nie są przesyłane, więc suma wszystkich wszystkich procesów musi być równa sumie wszystkich . Z tych dwóch wniosków oraz z spostrzeżenia tyczącego wartości zmiennych u inicjatora, wynika, że w wyniku zakończenia przetwarzania w procesie inicjatora zachodzi , a ponieważ proces ten jest pasywny, więc zostaną spełnione warunki wykrycia zakończenia.

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