Przetwarzanie rozproszone

Detekcja zakończenia

dr inż. Arkadiusz Danilecki

W oparciu o wykłady prof. J. Brzezińskiego

Plan wykładu

1. Wprowadzenie
2. Definicje
3. Algorytm Dijkstra, Feijen, van Gasteren
4. Algorytmy dla modelu atomowego
5. Algorytm detekcji zakończenia statycznego
6. Algorytm detekcji zakończenia dynamicznego
7. Algorytm Misra'83

Przypomnienie

$\Pi , \Sigma^i, \Sigma(\tau)$ - Proces globalny, $i$-ty stan globalny, stan globalny w chwili $\tau$ czasu globalnego

$P_i$ - $i$-ty proces

$S_i$ - stan $i$-tego procesu

$E_i^k$ - $k$-te zdarzenie w $i$-tym procesie

$C_{i,j} \in \mathcal{C}$ - kanał od $P_i$ do $P_j$

$\mathcal{P}, \mathcal{S}, \mathcal{T}, \mathcal{E}$ - zbiory elementów

Co właściwie nas interesuje?

Co właściwie nas interesuje?

Czy przetwarzanie rozproszone osiągnęło swój cel? Czy algorytm się zakończył? Czy jest jeszcze jakiś proces, który kontynuuje pracę?

Jak zawsze w środowisku rozproszonym, problem nie jest trywialny. Odpytanie po kolei procesów "czy już skończyliście pracę" może skutkować błędnym przeświadczeniem, że przetwarzanie się zakończyło.

Co właściwie nas interesuje?

Jak zawsze w środowisku rozproszonym, problem nie jest trywialny. Odpytanie po kolei procesów "czy już skończyliście pracę" może skutkować błędnym przeświadczeniem, że przetwarzanie się zakończyło.

A dlaczego właściwie nie wyznaczyć spójnego obrazu stanu globalnego?

"Czy zaszło zakończenie" jest predykatem stabilnym, więc jak najbardziej można!

Specjalizowane algorytmy bywają czasami wydatniejsze... A poza tym problem jest ciekawy sam w sobie

Definicja nieformalna

Nieformalnie problem detekcji zakończenia przetwarzania rozproszonego polega na sprawdzeniu, czy wszystkie procesy przetwarzania są w stanie pasywnym oraz czy żadna wiadomość będąca w kanale (transmitowana lub dostępna) nie uaktywni któregokolwiek z tych procesów.

Definicja nieformalna

Nieformalnie problem detekcji zakończenia przetwarzania rozproszonego polega na sprawdzeniu, czy wszystkie procesy przetwarzania są wstanie pasywnym oraz czy żadna wiadomość będąca w kanale (transmitowana lub dostępna) nie uaktywni któregokolwiek z tych procesów.

Przez proces aktywny rozumiemy tutaj wykonujący kroki algorytmu; w przeciwnym wypadku uznajemy go za pasywny.

Przez zakończenie obliczeń rozproszonych mamy tutaj na myśli osiągnięcie pewnej końcowej konfiguracji, w której nie są już możliwe dalsze kroki algorytmu.

Definicja nieformalna

Przez proces aktywny rozumiemy tutaj wykonujący kroki algorytmu; w przeciwnym wypadku uznajemy go za pasywny.

Zakładamy, że proces aktywny może spontanicznie w każdej chwili stać się pasywny. Proces pasywny może być uaktywniony dopiero po otrzymaniu jednej lub więcej wiadomości.

Zakończenie dynamiczne

Przetwarzanie rozproszone ${\mathit {\Pi }}$ jest w danej chwili w stanie zakończenia dynamicznego, jeżeli żaden proces składowy przetwarzania rozproszonego nie będzie już nigdy uaktywniony. Stan ten będzie utrzymywany pomimo, że pewne wiadomości są wciąż transmitowane, a pewne wiadomości są już dostępne.

Jest to oczywiście predykat stabilny.

Zakończenie statyczne

Przetwarzanie rozproszone ${\mathit {\Pi }}$ jest w danej chwili w stanie zakończenia statycznego, jeżeli:

• wszystkie procesy są pasywne,
• wszystkie wiadomości znajdujące się w kanałach są dostępne
• dla żadnego procesu nie jest spełniony warunek uaktywnienia, tj. żadna z dostępnych wiadomości nie uaktywni procesu po dostarczeniu.

Zakończenie klasyczne

W klasycznej definicji zakończenia przyjmowano, że przetwarzanie rozproszone jest w stanie zakończenia, jeżeli w danej chwili wszystkie procesy są pasywne i wszystkie kanały są puste.

Algorytmy detekcji zakończenia

Model przetwarzania synchronicznego

W modelu przetwarzania synchronicznego przyjmuje się, że transmisje są natychmiastowe. Stąd kanały mogą być uznane za puste przez cały czas i problem zakończenia sprowadza się do sprawdzenia czy wszystkie procesy są jednocześnie pasywne.

Stan zakończenia opisuja więc następujący predykat: $$Iterm({\mathcal {P}})\equiv P_{i}::P_{i}\in {\mathcal {P}}::passive_{i}$$

Detekcja zakończenia dla modelu przetwarzania synchronicznego

Algorytm Dijkstra, Feijen, van Gasteren.

Procesy łączymy w wirtualny pierścień na potrzeby algorytmu; wiadomości aplikacyjne przesyłane są jednak w topologii grafu w pełni połączonego!

Detekcja zakończenia dla modelu przetwarzania synchronicznego

Algorytm Dijkstra, Feijen, van Gasteren.

Procesy łączymy w wirtualny pierścień na potrzeby algorytmu; wiadomości aplikacyjne przesyłane są jednak w topologii grafu w pełni połączonego!

• Procesom przypisany jest kolor White albo Black.
• Procesy przesyłają wzdłuż pierścienia wiadomość kontrolną – znacznik typu TOKEN, który również może mieć kolor White albo Black .
• Początkowo procesy mają kolor White, a zmieniają kolor na Black, gdy wyślą wiadomość aplikacyjną do procesu "wstecz" pierścienia
• Proces inicjujący detekcję zakończenia $P_{\alpha }=P_{1}$ wysyła znacznik koloru White do swego następnika w pierścieniu gdy stanie się pasywny

Detekcja zakończenia dla modelu przetwarzania synchronicznego

Algorytm Dijkstra, Feijen, van Gasteren.

• Procesom przypisany jest kolor White albo Black.
• Procesy przesyłają wzdłuż pierścienia wiadomość kontrolną – znacznik typu TOKEN, który również może mieć kolor White albo Black .
• Początkowo procesy mają kolor White, a zmieniają kolor na Black, gdy wyślą wiadomość aplikacyjną do procesu "wstecz" pierścienia
• Proces inicjujący detekcję zakończenia $P_{\alpha }=P_{1}$ wysyła znacznik koloru White do swego następnika w pierścieniu gdy stanie się pasywny

• Każdy kolejny proces $P_{i}$ odbierający znacznik czeka aż stanie się pasywny i wówczas wysyła znacznik o kolorze zgodnym z kolorem procesu.
• Po wysłaniu znacznika procesowi przypisywany jest kolor White.

Detekcja zakończenia: Przykład

Detekcja zakończenia: Przykład 2

Detekcja zakończenia dla modelu przetwarzania synchronicznego

Dowód poprawności

Postęp: Czy jeżeli zakończenie zaszło, wykryjemy to w skończonym czasie?

Bezpieczeństwo: Czy jeżeli wykryliśmy zakończenie, to zakończenie zaszło?

Detekcja zakończenia dla modelu przetwarzania synchronicznego

Dowód poprawności

Postęp: Czy jeżeli zakończenie zaszło, wykryjemy to w skończonym czasie?

Co może powstrzymać algorytm przed zakończeniem:

• Token jest zatrzymany w procesach (kiedy?)
• Token podróżuje przez kanały (czy w końcu dotrze?)

Bezpieczeństwo: Czy jeżeli wykryliśmy zakończenie, to zakończenie zaszło?

Detekcja zakończenia dla modelu przetwarzania synchronicznego

Dowód poprawności

Postęp: Czy jeżeli zakończenie zaszło, wykryjemy to w skończonym czasie?

Bezpieczeństwo: Czy jeżeli wykryliśmy zakończenie, to zakończenie zaszło?

Co może się stać, by po zakończeniu algorytmu jakieś procesy były wciąż aktywne?