Pr-1st-1.1-m08-Slajd38

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Algorytm kolorujący procesy i wiadomości: Koncepcja (1)

Algorytm kolorujący procesy i wiadomości: Koncepcja (1)


Wadą przedstawionego algorytmu Matterna jest zawieszanie przetwarzania aplikacyjnego procesu do momentu uzyskanie przez monitor potwierdzeń odebrania wiadomości kontrolnej zawierającej żądany moment zapamiętania w przyszłości stanu lokalnego od wszystkich pozostałych monitorów.

Problemu tego można uniknąć wprowadzając dodatkową n + 1 pozycję w wektorze czasu, której wartość jest zwiększana tylko przez wyróżniony monitor nie skojarzony z żadnym procesem aplikacyjnym. Należy zauważyć, że w nowym wektorze czasu istotne znaczenie będzie miała teraz tylko pozycja n +1, a wszystkie pozostałe mogą być pominięte. W konsekwencji można też pominąć całą fazę rozgłaszania wartości . W tym wypadku procesy będą zapamiętywać stan lokalny, gdy uzyskają wektor z nową, powiększoną wartością pozycji n + 1.

Algorytm można uprościć dalej zauważając, że w kontekście detekcji stanu globalnego znaczenie ma w istocie tylko zmiana stanu na pozycji n+1 , i stąd dwa stany tej pozycji są wystarczające dla rozróżnienia kolejnych faz wyznaczania obrazu globalnego:

  • White – przed zapamiętaniem stanu lokalnego procesu
  • Red – po zapamiętaniu stanu lokalnego.

Podobnie, kolory można przypisać pakietom. Kolor White i Red pakietu oznacza, że został on wysłany, odpowiednio, przed lub po zapamiętaniu stanu lokalnego procesu. Monitory procesów White wysyłają tylko pakiety White, a monitory procesów Red – tylko pakiety koloru Red.

  • Każdy proces pierwotnie ma kolor White, a staje się Red po zapamiętaniu jego stanu lokalnego a przed przekazaniem mu pierwszej wiadomości z pakietem koloru Red.
  • Inicjator detekcji stanu globalnego zapamiętuje stan lokalny procesu, staje się Red iwysyła pusty pakiet koloru Red do wszystkich monitorów.

Poprawność algorytmu wynika z faktu, że nie istnieje pakiet wysłany przez monitor Red, którego wiadomość przekazana zostałaby procesowi aplikacyjnemu koloru White, gdyż taki pakiet spowodowałby zmianę koloru procesu odbierającego na Red przed przekazaniem wiadomości.

Zakłada się, że inicjator nie inicjuje współbieżnie wielu detekcji, dlatego wprowadzenie większej liczby kolorów (wartości elementu czasu wektorowego) nie jest konieczne.

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