Kolokwium Flashcards
Zakończenie dynamiczne
Żaden proces nie będzie już nigdy uaktywniony. Pewne wiadomości są transmitowane, a pewne są dostępne.
Dterm(P) = ∀Pi∈P((passivei) ∧ (˜activate(AVi ∪ ITi)))
Zakończenie statyczne
wszystkie są pasywne
wszystkie są dostępne
nie spełniony warunek uaktywnienia
Sterm(P) = ∀Pi∈P ((passivei) ∧(ITi= ∅) ∧( ¬activateiAVi))
Dterm(P) <~> Sterm(P)
Oznacza, że zajście Dterm(P) doprowadzi w skończonym czasie do Sterm(P). Dterm(P) jest wcześniejszym punktem w czasie od Sterm(P), ponieważ wiadomości, które są transmitowane, kiedyś dojdą i spełnią ostatni warunek Sterma(P).
Zakończenie klasyczne
Wszystkie pasywne
Kanały są puste
Cterm(P) = ∀Pi∈P ((passivei) ∧ (ITi = ∅) ∧(AVi= &empty))
Zakończenie dla modelu przetwarzania synchronicznego
wiadomości są dostarczcane natychmiastowo, tak więc spełnić trzeba tylko to, że wszystkie procesy są pasywne
Iterm(P) = ∀Pi∈P passivei
Algorytm Dijkstry, Feijena, van Gasterena
Koncepcja ciągu cykli detekcyjnych.
Założenia: wszystkie monitory połączone w pierścień.
Kolory: white (początkowy) lub black (gdy proces wyśle wiadomość do procesu o indeksie większym - czyli do tego co już przeszedł w pierścieniu, wcześniejszy)
Wysyłanie tokena (też o jakimś kolorze)
Inicjator wysyła token white do następnika, gdy proces passivei
Reszta odbiera token, czeka na pasywny, wysyła token o kolorze procesu, potem przypisuje sobie white.
Koniec gdy white trafi do inicjatora.
Zakończenie w modelu dyfuzyjnym
Inicjator - może w dowolnej chwili.
Procesy są w hierarchi np. drzewo
proces angażujący to proces który jest nadawcą wiadomości
Założenia
- aktywny zmienia się w pasywny tylko kiedy zajdzie zdarzenie wewnętrzne
- staje się aktywny gdy otrzyma wiadomość
- pasywny zmienia się w aktywny tylko gdy otrzyma wiadomość!
warunek uaktywnienia = model żądań OR
Algorytm Dijkstry-Scholten’a
Dla modelu dyfuzyjnego
wiadomość kontrolna - SIGNAL - odpowiedź na wiadomość
Koniec kiedy otrzyma signal od wszystkich związanych procesów.
Procesy połączone w drzewo.
W dół leci wiadomość o rozpoczęciu detekcji zakończenia, a w górę lecą SIGNAL.
Algorytm Misra wymagania
Model asynchroniczny
Wymagania
- niezawodność
- porzadek wysyłania (np FIFO)
TOKEN = wiadomość kontrolna, zawiera liczbę procesów odwiedzonych przez znacznik, które były pasywne + następników procesu.
Algorytm z licznikami wiadomości Matterna
Atomowy model przetwarzania.
W atomowym modelu przetwarzania, czasy przetwarzania lokalnego są zaniedbywane (zerowe), a opóźnienia są związane tylko z transmisją. Można przyjąć, że procesy (uaktywniane natychmiastowo) są przez cały czas pasywne i sprowadzić problem detekcji zakooczenia do wyznaczania stanów kanałów. Przyjmijmy dla uproszczenia, model żądao typu OR. Oznacza to, że dowolna wiadomośd w kanale uaktywni proces.
Kiedy Trzeba sprawdzić czy rc1=sc1=rc2=sc2? (alg z licznikami wiadomości Matterna)
Tb1<te1></te1>
<p></p>
<p>Trzeba sprawdzić czy rc1=sc1=rc2=sc2</p>
<p></p>
<p>Jesli t1 < t2 dla dowolnego procesu to:</p>
<p>* Liczba wysłanych w chwili t1 <= liczba wysłanych w chwili t2<br></br>* Liczba odebranych w chwili t1 <= liczba odebranych w chwili t2<br></br>* Suma wysłanych w chwili t1 <= suma wysłanych w chwili t2<br></br>* Suma odebrańych w chwili t1 <= suma odebranych e chwili t2<br></br>* Rc1 <= suma odebranych w chwili te1<br></br>* Suma wysłanych w chwili tb2 <= sc2</p>
<p></p>
<p>Z niezawodności wynika ze dla każdej chwili suma odebranych <= sumy wysłanych.</p>
<p></p>
<p>Podsumowując</p>
<p>Rc1 <= suma odebranych w te1 <= suma wysłanych w te1 <= suma wysłanych w tb2 <= sc2</p>
<p></p>
<p>Z założenia rc1 = sc2 tak wiec</p>
<p></p>
<p>Rc1 = suma odebranych w te1 = suma wyslańych w te1 = suma wysłanych w tb2 = sc2</p>
</te1>
Jednorazowy alg. Detekcji zakończenia
Założenie
* Połączone w pierścień
* Id
* Nr sekwencyjny
* Suma liczników
* Flagę invalid
MaxDetectNo - nr sekwencyjny wiadomosci wysłanej najpóźniej spośród wszystkich odebranych.
Wektorowy algorytm detekcji zakończenia
Procesy ńie zawsze sie ze sobą komunikują
Monitory w pierścień
Token zawiera wektor zawierający sumę wektorowych liczników monitorów odwiedzonych juz w detekcji.
Wektorowe liczniki trzymają info o tym ile juz wysłał i ile odebrał.
Firstwave == true gdy monitor otrzymał znaczńik porażka pierwszy
Cechy
* Brak etykiet
* Zatrzymańie znacznika
* W sposób ciągły
* Wada? Sporo info
Jednostkowy model żadań
Od ścisle określonego odbiorcy
Model żądań and
Od wszystkich ze zbioru warunkowego
Model żądań or
Od któregokolwiek ze zbioru warunkowego
Model żądań k spośród r
Od conajmniej ki rożnych procesów ze zbioru warunkowego
Model żądań or-and
Od każdego z procesów tworzących zbiór di1 lub od każdego tworzących zbiór di2 lub …. Lub od każdego ze zbioru d
Model żądań predykatywny
Dla każdego passywnego procesu ze zbioru warunkowego Di określony jest prefekta activate(x) gdzie x to podzbiór zbioru procesów. Dzięki temu mozna uzyskać dowolny poprzedni model.
Dysjunkcyjny model k spośród r
Od ki1 rożnych z di1 lub …lub od kini rożnych z dini
Redukuje sie do
* Or-and gdy każda ki jest równe liczbie elementów w zbiorze Di
* K spośród r gdy ilosc zbiorów różna sie 1 (ni=1)
* And gdy ilosc zbiorów równa sie 1 i każda ki jest równa liczbie elementów z zbiorze Di
* Or gdy ilosc zbiorów równa sie 1 i ki1 = 1
Algorytm Lamporta
Wyślij
Clock = clock + d
Odbierz
Clock = max(clock, clockR) + d
Poźniejszy + d
Clock = zegar aktualnego procesu
ClockR = zegar otrzymany w wiadomosci
Algorytm Matterna
Wyślij
Clock[i] = clock[i] + d
Moj wektor na pozycji mojego id
Odbierz
Clock[k] = max(clock[k], clockR[k]) + d
Clock[i] = clock[i] + d
Moj wektor ma pozycji mojego id
Moj wektor na pozycji id procesu od którego odebrałam wiadomość o wartość czasu późniejszego.
Definicja zakleszczenia
- Wszystkie procesy niepisanego zbioru oczekują na wiadomość od innych procesów tego zbioru.
- Oczekują na zdarzenie, ktore nigdy nie nastąpi.
4 warunki zakleszczeń
- Żądanie wyłącznego dostępu do zasobu.
- Przetrzymywanie zasobów gdy czekają na inne.
- Niemożność usunięcia zasobu z procesu oczekującego.
- Istnieje pierścień procesów, w którym każdy z nich przytrzymuje jeden lub wiecej zasobów wymaganych przez następny proces w łańcuchu.
Alg Bracha, Toueg’a
Done na każde notify
ACK na każdy confirm
Confirm na notify gdy nie ma “następników”
Detekcja zakończenia Dla modelu asynchronicznego
4 kolory
gray - request
black - request, odbiór
white - request, odbiór, grant
translucent - coś tam i nie odebrany cancel
Założenia algorytm Chandy-Lamporta
Założenia
* Niezawodne kanały
* Stan = złożenie lokalnych stanów procesów oraz kanałów
* Asynchroniczna komunikacja i przetwarzanie
* Brak zegara globalnego
Złożoność Algorytm Chandy-Lamporta
* Czasowa d+1 (d- średnica grafu)
* Komunikacyjna 2E
Inicjator Algorytm Chandy-Lamporta
Inicjator
- Inicjuj
- Zapisz stan procesu.
- Wyślij marker do incydentnych.
Każdy Proces Algorytm Chandy-Lamporta
Odbior pierwszego znacznika
- Zapamiętaj stan procesu.
- Wyślij marker do incydentnych.
Odbiór wiadomosci po zapisaniu stanu
Dodaj wiadomość do stanu kanału nadawcy.
Odbiór kolejnego znacznika
Inkrementuj liczbę odebranych znaczników.
Odebrano wszystkie znaczniki
Wyslij stan procesu i kanałów do inicjatora.
