Sr-9-wyk-1.0-Slajd14

From Studia Informatyczne

Algorytm fast-read

Algorytm fast-read


Realizacja modelu spójności wymaga zaprojektowania odpowiedniego protokołu spójności. Przytoczony na przykładzie algorytm jest jednym z możliwych protokołów gwarantujących zachowanie spójności sekwencyjnej. Jak sama nazwa wskazuje preferuje on odczyty. Preferencja przejawia się tym, że odczyt nigdy nie jest blokowany – od razu zwracana jest lokalnie przechowywana wartość zmiennej.

Zapis algorytmu ma postać procedur obsługi zdarzeń. Zawartość pamięci reprezentowana jest w algorytmie jako tablica M , zwielokrotniona w postaci lokalnych tablic Mi w procesie pi .

Odczyt zwraca po prostu wartość przechowywaną na odpowiedniej pozycji w tablicy M . Zlecenie zapisu jest rozgłaszane (lub rozsyłane) do wszystkich procesów. Rozgłaszanie jest rozgłaszaniem niepodzielnym (ang. atomic broadcast ), co oznacza, że komunikat musi dotrzeć do wszystkich i to w tej samej kolejności. Warstwa komunikacji grupowej zajmie się więc w tym przypadku zapewnieniem uporządkowania operacji zapisu. Jest to wygodna (choć nie zawsze najbardziej efektywna) metoda implementacji protokołu spójności. Właściwa operacja modyfikacji zmiennej realizowana jest w procedurze obsługi odbioru wiadomości aktualizacyjnej. Dotyczy to również węzła, który inicjuje zapis. Jest to ważne, ponieważ zapisy mają być wszędzie realizowane w tej samej kolejności. Zapis powoduje wstrzymanie przetwarzania procesu, który go zleca, do czasu zakończenia niepodzielnego rozgłaszania. Wykonanie bieżącego zapisu może być więc poprzedzone wcześniejszym obsłużeniem zapisów zleconych na innych węzłach – o kolejności zadecyduje warstwa komunikacyjna. W procedurze obsługi odbioru wiadomości aktualizacyjnej, jeżeli komunikat dociera do procesu, który inicjował rozgłoszenie, następuje obudzenie procesu zlecającego (funkcja signal ). Proces był zawieszony w procedurze zapisu (funkcją wait ).


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