Pr-1st-1.1-m09-Slajd22

Detekcja zakończenia dla synchronicznego modelu przetwarzania

Zostanie obecnie omówiony algorytm autorstwa Dijkstry, Feijen oraz van Gasterena detekcjizakończenia dla modelu przetwarzania synchronicznego. Wykorzystuje on koncepcję ciągu cykli detekcyjnych i zakłada, że wszystkie monitory procesów aplikacyjnych połączone są w logiczny pierścień iobserwują stany procesów aplikacyjnych.

• Monitorom (procesom) przypisany jest kolor White albo Black.
• Monitory przesyłają wzdłuż pierścienia wiadomość kontrolną – znacznik typu TOKEN, który również może mieć kolor White albo Black .
• Początkowo monitory mają kolor White, azmieniają kolor na Black, gdy odpowiadający im proces aplikacyjny wyśle wiadomości do procesu o indeksie większym.
• Monitor inicjujący detekcję zakończenia $Q_{\alpha }=Q_1$ wysyła znacznik koloru White do swego następnika w pierścieniu

$Q_n$ jeżeli obserwowany przezniegoproces aplikacyjny jest pasywny.

• Każdy kolejnymonitor $Q_i$ odbierający znacznik czeka aż obserwowany przez niego proces stanie się pasywny i wówczas wysyła znacznik o kolorze zgodnym z kolorem monitora.
• Po wysłaniu znacznika monitorowi przypisywany jest kolor White.

Algorytm kończy się, gdy znacznik koloru White dotrze do inicjatora. Dla uproszczenia prezentacji, w algorytmie wykorzystano funkcje:

$succ(i)=(i)modn+1$

$pred(i)=(i+n-2)modn+1$

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