J. Ułasiewicz Programowanie aplikacji współbieżnych 1

14 Synchronizacja w systemach rozproszonych

14.1 Wstęp

Zagadnienia synchronizacji

1. Synchronizacja czasu

2. Synchronizacja dostępu – rozproszone wzajemne wykluczanie

3. Ustalanie koordynatora – algorytmy elekcji

Własności systemów rozproszonych

1. Informacja rozproszona po wielu maszynach.

2. Decyzje muszą być podejmowane na podstawie danych lokalnych.

3. Nie należy skupiać kluczowych danych i procesow w jednym węźle.

4. Nie isnieje wspólny zegar.

14.2 Synchronizacja czasu

W zagadnieniach synchronizacji procesów na wielu maszynach nie jest istotna znajomość czasu absulutnego. Istotne jest aby procesy mogły ustalić kolejność zdarzeń.

Zegary fizyczne – wskazują czas astronomiczny

Zegary logiczne – zegary o wzajemnie uzgodnionym czasie, niekoniecznie

astronomicznym.

Relacje uprzedniości zdarzeń (Lamport)

a -> b

a wystąpiło przed b – wszystkie procesy są zgodne że a wystąpiło przed b Relacja uprzedniości zdarzeń zachodzi w następujących przypadkach:

1. Jeżeli a i b są zdarzeniami w tym samym procesie i a występuje przed b to relacja a -> b jest prawdziwa.

2. Jeżeli a jest zdarzeniem wysłania komunikatu b zdarzeniem odbioru

komunikatu przez inny proces to relacja a -> b jest prawdziwa (komunikat nie może być odebrany przed wysłaniem)

Uprzedniość jest relacją przechodnią: a -> b i b -> c to a -> c.

Konstrukcja zagara logicznego polega na opracowaniu funkcji T(a) spelniającej założenia:

Synchronizacja w systemach rozproszonych

PDF created with pdfFactory trial version www.pdffactory.com

J. Ułasiewicz Programowanie aplikacji współbieżnych 2

1. Gdy a -> b to T(a) < T(b)

2. Czas T zegara musi rosnąć.

3. Poprawki można wprowadzać tylko przez dodawanie.

Algorytm Lamporta

1. Każdy proces utrzymuje swój zegar logiczny zwiększając go.

2. Procesy wymieniają komunikaty znakując je własnym czasem logicznym

3. Gdy proces P1 ma czas T1 a z P2 otrzyma komunikat z czasem T2 i T1 < T2

to przyjmuje się T1 = T2 + 1.

1

2

1

2

A

A

2

4

2

4

3

6

3

6

B

B

4

8

4

8

5

10

7

10

6

12

8

12

7

14

9

14

8

16

10

16

Brak

Jest

synchronizacji

synchronizacja

Przebieg synchronizacji czasów w systemie rozproszonym

W niektórych zastosowaniach wymaga się aby żadne dwa zdarzenia w systemie nie zaszły w tym samym czasie. Aby to osiągnąć, do czasu logicznego po przecinku dodaje się numer procesu.

Algorytm Lamporta umożliwia przypisanie czasu logicznego wszystkim zdarzeniom w systemie.

1. Jeżeli a poprzedza b w tym samym procesie to T(a) < T(b) jest prawdziwa.

2. Jeżeli a jest zdarzeniem wysłania komunikatu b zdarzeniem odbioru

komunikatu przez inny proces to T(a) < T(b).

3. Dla wszystkich zdarzeń a i b zachodzi T(a) # T(b).

Synchronizacja w systemach rozproszonych

PDF created with pdfFactory trial version www.pdffactory.com

J. Ułasiewicz Programowanie aplikacji współbieżnych 3

14.3 Wzajemne wykluczanie w systemach rozproszonych

Algorytm scentralizowany

W systemie istnieje proces bądący koordynatorem zasobów. Wymienia on z

procesami następujące typy komunikatów:

Z

Zamówienie zasobu

Proces aplikacyjny -> Koordynator

P

Przedzielenie zasobu

Koordynator -> Proces aplikacyjny

O

Oddanie zasobu

Proces aplikacyjny -> Koordynator

Proces aplikacyjny działa według algorytmu:

1. Wysyła do koordynatora zamówienie zasobu.

2. Czeka na przydzielenie zasobu.

3. Używa zasobu.

4. Wysyła do koordynatora komunikat o zwolnieniu zasobu.

P1

P2

Koordynator

Z1

P1

Z2

O1

P2

O1

Przebieg koordynacji w dostępie do zasobu

Wady metody:

Wrażliwość na awarie – gdy koordynator ulegnie awarii nie sposób odróżnić braku odpowiedzi od awarii.

Synchronizacja w systemach rozproszonych

PDF created with pdfFactory trial version www.pdffactory.com

J. Ułasiewicz Programowanie aplikacji współbieżnych 4

Algorytm Ricarda Aagrawali wzajemnego wykluczania

1. Algorytm zapewnia wzajemne wykluczanie w systemie rozproszonym.

2. Algorytm wymaga aby w systemie występowało całkowite uporządkowanie

zdarzeń – zegary logiczne.

Rodzaje komunikatów:

Z – Zamówienie

P – Pozwolenie

W komunikacie wysyła się:

N – Nazwa zasobu

P - Identyfikator procesu

T - Wartość zegara logicznego

I. Komunikat z zamówieniem wysyłany jest do wszystkich procesów łącznie z samym sobą.

II. Gdy proces otrzyma zamówienie od innego procesu reakcja jest następująca: 1. Gdy proces nie jest w sekcji krytycznej danego zasobu i nie zamierza w nią wejść wysyła P (Ppozwolenie).

2. Gdy proces jest w sekcji krytycznej to nie odpowiada i ustawia zlecenie w kolejce. Odpowie gdy wyjdzie z sekcji.

3. Gdy proces zamierza wejść do sekcji krytycznej ale jeszcze tego nie uczynił

porównuje znaczniki czasu otrzymanych komunikatów ze znacznikiem czasu

wysłanego komunikatu z zamówieniem. Ten kto ma mniejszy (wcześniejszy)

czas wygrywa.

III. Po wysłaniu zamówień do wszystkich procesów, proces oczekuje zgody od wszystkich procesów. Gdy ją otrzyma może wejść do sekcji krytycznej.

P1

P2

T=8

Z(P1,8)

T=12

Z(P1,8)

Z(P2,12)

Z(P2,12)

12 > 8 -> brak P(P1)

P(P2)

8 < 12 -> wyślij P(P2)

sekcja kryt.

P(P1)

sekcja kryt.

Synchronizacja procesów P1 i P2

Własności:

Synchronizacja w systemach rozproszonych

PDF created with pdfFactory trial version www.pdffactory.com

J. Ułasiewicz Programowanie aplikacji współbieżnych 5

1. Dowodzi się że algorytm poprawnie realizuje rozproszone wzajemne

wykluczanie.

2. Nie występuje zagłodzenie gdyż zamówienia są uporządkowane czasowo.

3. Awaria jednego procesu powoduje awarę całego systemu

4. Proces musi być gotowy na odbiór zamówień i odpowiedzi na nie –

asynchroniczny model programowania.

Algorytm pierścienia z żetonem

1. Procesy połączone są w pierścień logiczny.

2. Z każdym zasobem związany jest jeden żeton (ang. token).

3. Tylko proces posiadający żeton może wejść do sekcji krytycznej.

P1

P2

P3

PN

X

Procesy połączone w pierścień logiczny

Algorytm procesu:

I. Gdy proces chce wejśc do sekcji krytycznej:

1. Oczekuje na żeton.

2. Gdy otrzyma żeton wchodzi do sekcji

3. Po wyjściu przekazuje żeton do następnego procesu w pierścieniu.

II. Gdy proces nie chce wejśc do sekcji krytycznej przekazuje żeton następnemu procesowi.

Wady algorytmu:

1. Duża liczba komunikatów gdy żaden z procesów nie jest w sekcji krytycznej.

2. Możliwość utraty żetonu – konieczny algorytm elekcji.

3. Konieczny asynchroniczny model programowania.

Synchronizacja w systemach rozproszonych

PDF created with pdfFactory trial version www.pdffactory.com

J. Ułasiewicz Programowanie aplikacji współbieżnych 6

Porównanie metod synchronizacji

Algorytm

Liczba komunikatów Opóźnienie wejścia Możliwe problemy

na tranzakcję

w komunikatach

Scentralizowany

3

2

Awaria

koordynatora

Rozproszony

2(n-1)

2(n-1)

Awaria dowolnego

procesu

Pierścień z żetonem 0d 1 do ∞

0d 0 do ∞

Utrata żetonu,

awaria procesu

Porownanie algorytmów synchronizacji rozproszonej

1. Wszystkie algorytmy są wrażliwe na awarię - najmniej algorytm

scentralizowany, najbardziej rozproszony i z żetonem.

2. Najmniejsze opóźnienie – algorytm scentralizowany

3. Algorytmy rozproszony i z żetonem wymagają asynchronicznego modelu

programowania.

Synchronizacja w systemach rozproszonych

PDF created with pdfFactory trial version www.pdffactory.com

J. Ułasiewicz Programowanie aplikacji współbieżnych 7

14.4 Algorytmy elekcji

W wielu algorytmach rozproszonych wymaga się aby istniał tam dokładnie jeden wyróżniony proces pełniący funkcję koordynacji, inicjacji lub inne funkcje specjalne.

Założenia:

1. Każdy z procesów ma jeden niepowtarzalny numer, pełniący funkcję

priorytetu. Zwykle funkcje koordynatora pełni proces o najwyższym numerze.

2. Każdy proces zna numery wszystkich pozostałych.

3. Nie wiadomo które z istniejących procesów działają.

Cel algorytmu elekcji:

Wybranie z pośród działających procesów dokładnie jednego koordynatora. Gdy elekcja się rozpocznie to musi być wiadomo że zakończy się powodzeniem.

Musi istnieć mechanizm za pomocą którego wznowiony proces dowiaduje się kto jest koordynatorem.

Algorytm tyrana ( ang. bully algorithm)

Rodzaje komunikatów:

ELEKCJA

– podejmij elekcję

ANSWER

- odpowiedź na ELEKCJA

KOORDYNATOR - jestem koordynatorem

Proces który zauważył że koordynator nie odpowiada rozpoczyna elekcję.

Proces elekcji:

1. Proces P wysyła komunikat ELEKCJA do wszystkich procesów o wyższych numerach.

2. Jeżeli nikt nie odpowie proces P staje się koordynatorem. Wysyła komunikat KOORDYNATOR do wszystkich innych procesów.

3. Jeżeli jakiś proces o wyższym numerze odpowie to rola procesu P w elekcji się kończy. Proces o wyższym numerze dalej prowadzi elekcję.

Proces który otrzymał komunikat ELEKCJA:

1. Wysyła komunikat ANSWER ze swoim numerem do procesu od którego

dostał komunikat elekcja.

2. Podejmuje proces elekcji o ile jej nie prowadził.

W końcu wszyskie procesy z wyjątkiem jednego zaniechają elekcji. Ten proces stanie się koordynatorem.

Synchronizacja w systemach rozproszonych

PDF created with pdfFactory trial version www.pdffactory.com

J. Ułasiewicz Programowanie aplikacji współbieżnych 8

2

3

2

3

1

4

1

4

8

E

5

8

5

E

E

A

A

7

6

7

6

2

3

2

3

1

4

1

4

8

5

8

5

E

E

7

E

6

7

A

6

2

3

1

4

E

ELEKCJA

K

K

K

K

A

ANSWER

8

5

K

K

KOORDYNATOR

7

K

6

Przebieg elekcji – proces 5 inicjuje elekcję

1. Proces 5 zauważa brak koordynatora i rozpoczyna elekcję. Wysyła

komunikaty ELEKCJA do procesów P6, P7, P8.

2. Proces P6 otrzymuje komunikat ELEKCJA i wysyła ANSWER do do P5.

3. P5 po otrzymaniu ANSWER zaprzestaje elekcji.

4. Proces P6 wysyła komunikaty ELEKCJA do P7 i P8.

5. Proces P7 otrzymuje komunikat ELEKCJA od P5 i P6. Odpowiada im

komunikatem ANSWER.

6. Proces P6 otrzymuje od P7 ANSWER i zaprzestaje elekcji.

7. Proces P7 nie otrzymuje żadnego komunikatu ANSWER i zostaje

koordynatorem.

8. Proces P7 wysyła komunikaty KOORDYNATOR do P1,...,P6.

Do wyznaczenia koordynatora potrzeba n2 komunikatów.

Synchronizacja w systemach rozproszonych

PDF created with pdfFactory trial version www.pdffactory.com

J. Ułasiewicz Programowanie aplikacji współbieżnych 9

14.5 Pierścieniowy algorytm elekcji

Założenia:

1. Procesy są uporządkowane w strukture w kształcie pierścienia.

2. Każdy proces zna swego bezpośredniego następcę i może przesłać do niego komunikat.

W systemie przekazywane są dwa typy komunikatów:

- ELEKCJA, lista odwiedzonych procesów

- KOORDYNATOR numer koordynatora ,lista odwiedzonych procesów

1. Gdy proces zauważy brak koordynatora buduje komunikat ELEKCJA z listą do której dołącza swój numer. Komunikat wysyła do następnego czynnego

procesu.

2. Gdy proces otrzyma komunikat ELEKCJA dołącza do listy swój numer i wysyła komunikat do następnego czynnego procesu.

3. Gdy komunikat powróci do procesu inicjującego elekcję to wybiera on proces o najwyższym numerze jako koordynatora i wysyła komunikat

KOORDYNATOR( NrProcesuKoordynatora) z dołączonym swoim numerem.

4. Gdy komunikat KOORDYNATOR okrąży pierścień, usuwany jest z pierscienia.

Synchronizacja w systemach rozproszonych

PDF created with pdfFactory trial version www.pdffactory.com

J. Ułasiewicz Programowanie aplikacji współbieżnych 10

1

2

E

E

E 2

E 0,5,6

0

3

E E 2,3

E 0,1,5,6

E

7

E 5,6

4

1

E

2

E

E

E 2

E 0,5,6

6

E

5

0

3

E 5

E E 2,3

E

7

E 5,6

4

1

E

2

E

E

E

E 2,3,4

6

E

5

0

3

E 5

E

E

7

4

E

K6 - 5

6

E

5

E 0,1,2,3,4,5,6

Proces 7 uległ awarii - proces 6 zostaje koordynatorem

Do wyznaczenia koordynatora potrzeba n2 komunikatów.

Synchronizacja w systemach rozproszonych

PDF created with pdfFactory trial version www.pdffactory.com

J. Ułasiewicz Programowanie aplikacji współbieżnych 11

14.6 Zakleszczenia w systemie rozproszonym

Wykrywanie zakleszczeń – znajdowanie zakleszczeń w grafie oczekiwania

Model

System składa się z wielu maszyn (stanowisk) na których wykonywane są procesy używające zasobów lokalnych i zdalnych.

Procesy mogą przesyłać pomiędzy sobą komunikaty.

Graf oczekiwania

Węzły – procesy które oczekują na jakieś zasoby lokalne lub zdalne

Łuki - występuje łuk od Pi do Pj gdy proces Pi czeka na zasób zajmowany przez Pj P1

P2

P2

P4

P5

P3

P3

Maszyna A

Maszyna B

Lokalne grafy oczekiwania

Konstrukcja:

Jeżeli proces Pi wykonywany na maszynie A potrzebuje zasobu z maszyny B

zajmowanego przez proces Pj to wysyła do maszyny B komunikat z numerem

procesu Pi i zasobu. Komunikat powoduje dodanie do lokalnego grafu węzla Pi i łuku od Pi do Pj.

Znajdowanie zakleszczeń:

Gdy lokalny graf ma cykl to wystąpiło zakleszczenie.

Gdy lokalny graf nie ma cyklu nie jest to dowodem ze brak zakleszczeń.

Należy skonstruować graf globalny jako sumę grafów lokalnych.

Zbadać czy w grafie globalnym występuje cykl.

P1

P2

P2

P5

P3

Graf globalny dla maszyn 1 i 2

Są możliwe dwa podejścia do wykrywania zakleszczeń:

Scentralizowane i rozproszone

Synchronizacja w systemach rozproszonych

PDF created with pdfFactory trial version www.pdffactory.com

J. Ułasiewicz Programowanie aplikacji współbieżnych 12

Znajdowanie cykli w grafie oczekiwania - Algorytm rozproszony

Każda z maszyn wykonuje proces nadzorczy i konstruuje lokalny graf oczekiwania.

Wprowadza się dodatkowy węzeł Pex reprezentujący procesy zewnętrzne.

W lokalnym grafie:

1. Łuk od Pi do Pex gdy proces Pi czeka na zasób z odległej maszyny zajęty przez inny proces.

2. Łuk od Pex do Pj istnieje gdy jakiś odległy proces czeka na zasób zajęty przez proces Pj.

P1

P2

Pex

P2

P4

P5

P3

P3

Pex

Maszyna A

Maszyna B

Rozszerzone grafy lokalne

Należy wykonać procedurę wykrywania cykli w grafie oczekiwania.

1. Gdy lokalny graf oczekiwania zawiera cykl be węzła Pex to system jest w stanie zakleszczenia.

2. Gdy lokalny graf oczekiwania zawiera cykl z węzłem Pex to należy wykonać procedurę sprawdzającą opisaną niżej.

Procedura sprawdzająca:

Niech na maszynie Mi graf zawiera węzeł Pex: Pex -> P1 -> P2 -> ... -> Pk -> Pex Gdy proces Pk żąda zasobu znajdującego się na maszynie Mj wtedy:

1. Proces nadzorczy maszyny Mi wysyła do maszyny Mj komunikat zawierający informację o cyklu.

2. Proces nadzorczy maszyny Mj dodaje do lokalnego grafu oczekiwania węzły i łuki zawarte w komunikacie.

3. Proces nadzorczy Mj przegląda zaktualizowany graf w poszukiwaniu cykli.

Gdy zaktualizowany graf zawiera cykl to może zajść jeden z trzech przypadków: 1. Brak cyklu – brak zakleszczenia

2. Jest cykl nie zawierający węzła Pex – wystąpiło zakleszczenie.

3. Jest cykl zawierający węzeł Pex – wtedy należy przesłać komunikat o cyklu do koordynatora maszyny Mk (na której znajdują się żądane zasoby).

Zakleszczenie zostaje wykryte w skończonej liczbie kroków albo algorytm się zakończy.

Synchronizacja w systemach rozproszonych

PDF created with pdfFactory trial version www.pdffactory.com

J. Ułasiewicz Programowanie aplikacji współbieżnych 13

Przykład:

Koordynator maszyny A wykrywa cykl; Pex -> P2 -> P3 -> Pex.

P1

P2

Pex

P2

P4

Komunikat

P5

P3

P3

Pex

Maszyna A

Maszyna B

Koordynator maszyny B otrzymuje komunikat o cyklu i aktualizuje graf oczekiwania P1

P2

Pex

P2

P4

Cykl

P5

P3

P3

Pex

Maszyna A

Maszyna B

W grafie oczekiwania maszyny B wystąpił cykl – zakleszczenie.

Synchronizacja w systemach rozproszonych

PDF created with pdfFactory trial version www.pdffactory.com

J. Ułasiewicz Programowanie aplikacji współbieżnych 14

Algorytm Chandy-Misra-Haasa

Gdy jakiś proces ma być zablokowany w oczekiwaniu na pewien zasób używany przez inny proces do tego procesu wysyła się komunikat próbny ( ang. probe message).

Komunikat składa się z trzech liczb:

1. Numeru procesu rozpoczynającego czekanie.

2. Numeru procesu wysyłającego komunikat.

3. Numeru procesu do którego komunikat jest kierowany.

Gdy komunikat nadejdzie do innego procesu ten sprawdza czy nie czeka na inne procesy i go aktualizuje.

1. Pierwsze pole jest zachowane.

2. Drugie jest zastąpione własnym numerem procesu

3. Trzecie numerem procesu na który czeka dany proces.

(0,8,0)

P4

P6

P8

P0

P1

P2

P3

(0,4,6)

(0,2,3)

P5

P7

(0,5,7)

Maszyna 0

Maszyna 1

Maszyna 2

Jeżeli proces jest zablokowany w oczekiwaniu na inne procesy to komunikat zostaje wysłany do kazdego z nich.

Jeżeli komunikat powróci do procesu wysyłającego komunikat kontrolny to w systemie istnieje cykl a więc i blokada.

Przykład: (0,0,1), (0,1,2), (0,2,3), (0,4,6), (0,6,8), (0,8,0)

Gdy możliwość blokady zostanie wykryta należy skasować jeden z procesów w cyklu. Jak wybrać taki proces?

Może być tak że kilka procesów wykryje cykl i należy zapobiec temu aby

niepotrzebnie nie kończyć wielu procesów z cyklu gdy wystarczy jeden.

Rozwiązanie: Do komunikatu dołączać numery procesów „przejściowych” i kasować ten o najwyższym numerze.

Synchronizacja w systemach rozproszonych

PDF created with pdfFactory trial version www.pdffactory.com

J. Ułasiewicz Programowanie aplikacji współbieżnych 15

14.7 Bibliografia

[1] A. Silberschatz, P. Galvin. Podstawy systemów operacyjnych. WNT 2000 (Rozdz 18: Koordynacja rozproszona).

[2] G. Coulouris, J. Dollimore, T. Kindberg. Systemy rozproszone, podstawy i projektowanie. WNT, 1998 (Rozdz. 10: Czas i koordynacja).

[3] A. Tanenbaum. Rozproszone systemy operacyjne, PWN, 1997 (Rozdz 3:

Synchronizacja w systemach rozproszonych).

[4] M. Ben-Ari, Programowanie współbieżne, WNT Warszawa 1996.

Synchronizacja w systemach rozproszonych

PDF created with pdfFactory trial version www.pdffactory.com