1 Synchronizacja Rozdział 5

2 Synchronizacja zegarówGdy każda maszyna ma własny zegar, to choć zdarzenie o następuje po zdarzeniu c, to może mu zostać przypisany wcześniejszy czas

3 Obliczanie średniego dnia słonecznego.Zegary fizyczne (1) Obliczanie średniego dnia słonecznego.

4 Zegary fizyczne (2) Sekundy TAI, w odróżnieniu od sekund słonecznych mają stałą długość. W celu zachowania zgodności z ruchem słońca, wprowadza się sekundy przestępne.

5 Algorytmy synchronizacji zegarów, Cp(t) = t ρ – maks. tempo odchylenia 2ρΔt – różnica po czasie Δt Zależność między czasem zegarowym a czasem UTC.

6 Algorytm Cristiana Pobieranie aktualnego czasu od serwera.Jeżeli różnica nie większa niż δ, to synchronizacja co δ/2ρ Pobieranie aktualnego czasu od serwera.

7 Algorytm z Berkley Demon czasu podaje innym maszynom swój czasMaszyny odpowiadają Demon oblicza średnią i powiadamia każdą maszynę jak wyregulować swój zegar

8 Znaczniki czasu LamportaTrzy procesy, każdy z własnym zegarem. Algorytm Lamporta koryguje zegary

9 Rozsyłanie całkowicie uporządkowaneUaktualnienie bazy danych z pozostawieniem jej w stanie niespójnym.

10 Stan globalny (1) Obcięcie spójne Obcięcie niespójne

11 Stan globalny (2) organizacja procesu i kanałów do migawki rozproszonej

12 Stan globalny (3) Proces Q odbiera znacznik po raz pierwszy i zapisuje swój stan lokalny Q zapisuje wszystkie przychodzące komunikaty Q odbiera znacznik dot. swojego kanału wejściowego i kończy zapisywanie stanu kanału wejściowego

13 Algorytm tyrana (1) proces 4 rozpoczyna elekcjęprocesy 5 i 6 odpowiadają „OK” procesy 5 i 6 kontynuują elekcję

14 Algorytm tyrana (3) Proces 6 odpowiada „OK.”Proces 6 wygrywa i powiadamia pozostałych

15 Algorytm pierścieniowyAlgorytm elekcji z użyciem pierścienia.

16 Wzajemne wykluczanie: algorytm scentralizowanyProces 1 prosi koordynatora o dostęp do sekcji krytycznej. Dostaje zezwolenie. Proces 2 prosi koordynatora o dostęp do tej samej sekcji krytycznej. Koordynator nie odpowiada (2 zostaje zablokowany). Gdy proces 1 opuszcza sekcję krytyczną, koordynator odpowiada procesowi 2

17 Algorytm rozproszony Dwa procesy (0,2) chcą wejść w tym samym momencie do sekcji krytycznej. Proces 0 ma mniejszy znacznik czasu, więc wygrywa. Gdy proces 0 wychodzi z sekcji krytycznej, wysyła OK do procesu 2, który wchodzi do sekcji krytycznej.

18 Algorytm pierścienia z żetonemNieuporządkowana grupa procesów w sieci. Pierścień logiczny zbudowany za pomocą oprogramowania.

19 Porównanie Porównanie algorytmów wzajemnego wykluczenia. AlgorytmLiczba komunikatów na wejście/wyjście Opóźnienie przed wejściem (liczba komunikatów) Problemy Scentralizowany 3 2 Awaria koordynatora Rozproszony 2 ( n – 1 ) Awaria dowolnego procesu Pierścień z żetonem 1 do  0 to n – 1 Utrata żetonu, awaria procesu Porównanie algorytmów wzajemnego wykluczenia.

20 Aktualizowanie taśmy głównej toleruje awarie.Model transakcji (1) Aktualizowanie taśmy głównej toleruje awarie.

21 Elementarne operacje transakcyjne.Model transakcji (2) Operacja elementarna Description BEGIN_TRANSACTION Zaznaczenie początku transakcji END_TRANSACTION Zakończenie transakcji i próba jest zatwierdzenia ABORT_TRANSACTION Likwidacja transakcji, „Rollback” READ Czytanie danych z pliku, tabeli, itp.. WRITE Zapisanie danych do pliku, tabeli, itp.. Elementarne operacje transakcyjne.

22 Model transakcji (3) Transakcja potwierdzonych rezerwacji 3 lotówBEGIN_TRANSACTION reserve WP -> JFK; reserve JFK -> Nairobi; reserve Nairobi -> Malindi; END_TRANSACTION (a) BEGIN_TRANSACTION reserve WP -> JFK; reserve JFK -> Nairobi; reserve Nairobi -> Malindi full => ABORT_TRANSACTION (b) Transakcja potwierdzonych rezerwacji 3 lotów Transakcja zaniechana na skutek braku miejsc

23 Transakcje rozproszoneTransakcja zagnieżdżona Transakcja rozproszona

24 Prywatna przestrzeń roboczaIndeks i bloki dyskowe trzyblokowego pliku Sytuacja po zmodyfikowaniu przez transakcje bloku 0 i dodaniu bloku 3 stan po zatwierdzeniu

25 Rejestrowanie z wyprzedzeniemx = 0; y = 0; BEGIN_TRANSACTION; x = x + 1; y = y + 2 x = y * y; END_TRANSACTION; (a) Log [x = 0 / 1] (b) [y = 0/2] (c) [x = 1/4] (d) a) Transakcja b) – d) Rejestr przed wykonaniem każdej instrukcji

26 Sterowanie współbieżnością (1)Organizacja zarządców obsługi transakcji.

27 Sterowanie współbieżnością (2)Organizacja zarządców transakcji rozproszonych.

28 Szeregowalność a) – c) Trzy transakcji T1, T2, and T3 d) Możliwe planyBEGIN_TRANSACTION x = 0; x = x + 1; END_TRANSACTION (a) BEGIN_TRANSACTION x = 0; x = x + 2; END_TRANSACTION (b) BEGIN_TRANSACTION x = 0; x = x + 3; END_TRANSACTION (c) Plan 1 x = 0; x = x + 1; x = 0; x = x + 2; x = 0; x = x + 3 Dozwolone Plan 2 x = 0; x = 0; x = x + 1; x = x + 2; x = 0; x = x + 3; Plan 3 x = 0; x = 0; x = x + 1; x = 0; x = x + 2; x = x + 3; Niedozwolone (d) a) – c) Trzy transakcji T1, T2, and T3 d) Możliwe plany

29 Blokowanie dwufazowe (1)

30 Ścisłe blokowanie dwufazowe (2)

31 Pessimistic Timestamp OrderingConcurrency control using timestamps.