Pr-1st-1.1-m04-Slajd66

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Przykład (1) - bariera

Przykład (1) - bariera

Aby zilustrować pojęcie złożoności czasowej oraz komunikacyjnej, rozważmy bardzo prosty, przykładowy algorytm implementujący operację synchronizacji procesów tzw. bariery, w której każdy proces może kontynuować działanie tylko wtedy, gdy wszystkie inne procesy osiągną pewien określony stan. Załóżmy, że topologia połączeń ma strukturę grafu pełnego, czyli każdy proces jest połączony kanałem komunikacyjnym z wszystkimi pozostałymi procesami.

Rozważmy najpierw rozwiązanie, w którym pewien wydzielony, znany z góry proces-koordynator rozgłaszałby wiadomość typu BARRIER oznaczającą początek synchronizacji (bariery) i wstrzymywałby przetwarzanie. Każdy proces po otrzymaniu takiego komunikatu również wstrzymywałby przetwarzanie, odsyłając komunikat potwierdzający ten fakt do koordynatora. Po zebraniu wszystkich potwierdzeń koordynator rozsyłałby do wszystkich procesów komunikat typ END oznaczający koniec operacji bariery.

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