Sr-7-wyk-2.0-Slajd35

From Studia Informatyczne

Podejście rozproszone

Podejście rozproszone


W przeciwieństwie do algorytmu scentralizowanego w podejściu rozproszonym konstrukcją globalnego grafu oczekiwania, a dokładniej jego części, zajmuje się wiele procesów. Odpowiedzialność za wykrywanie zakleszczeń jest więc podzielona pomiędzy tych kilka procesów. Jeżeli, któryś z takich procesów wykryje cykl w swojej części globalnego grafu, oznacza to, że wystąpiło zakleszczenie.

Graf lokalny każdego procesu różni się nieco od tego w algorytmie scentralizowanym, gdyż dodano do niego specjalny wierzchołek Pzew . Jeżeli istnieje łuk z pewnego procesu Pi do Pzew , to Pi czeka na zasób z innego stanowiska przetrzymywany przez dowolny proces. Jeżeli zachodzi sytuacja odwrotna tzn. pojawia się łuk od Pzew do Pi , znaczy to, że jakiś zdalny proces czeka na zasoby, do których dostęp ma w danej chwili lokalny proces.

Schemat działania algorytmu wygląda następująco. Jeżeli stanowisko wykryło w swoim grafie oczekiwania cykl, który nie zawiera Pzew , to w systemie jest zakleszczenie. Jeżeli cykl zawiera wierzchołek Pzew , to wykonywany jest algorytm rozproszony.

Jeżeli stanowisko Si wykryło cykl w grafie z wierzchołkiem Pzew , wysyła informacje o wystąpieniu zakleszczenia oraz dane o cyklu do stanowiska Sj , na którym znajduje się proces przetrzymujący aktualnie zasoby potrzebne procesowi czekającemu na Pzew . Stanowisko Sj po otrzymaniu informacji o wykryciu zakleszczenia, aktualizuje swój graf oczekiwania i szuka cyklu nie zawierającego Pzew . Jeżeli znajdzie, to jest zakleszczenie. Jeżeli w cyklu występuje natomiast Pzew , to informacje o wykryciu zakleszczenie wędrują do kolejnego stanowiska. Cała procedura powtarzana jest skończoną liczbę razy do momentu zakończenia algorytmu lub wykrycia zakleszczenia.

Do algorytmu wprowadzono pewną optymalizację komunikacji, tak aby w sytuacji, gdy kilka procesów wykryje zakleszczenie, nie wszystkie wysyłały o nim informację. Każdy proces oznaczono unikalnym identyfikatorem. Gdy stanowisko wykryje cykl, na który składa się ciąg procesów ( Pzew , P1 , P2 , …, PN , Pzew ), sprawdza czy zachodzi warunek identyfikator(PN ) < identyfikator(P1 ). Jeżeli warunek jest spełniony, informacja o zakleszczeniu jest wysyłana, w przeciwnym wypadku inicjatywę musi przejąć inne stanowisko.


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