Transakcje (c.d.) I Administracja

Transcript

Transakcje Wykład 11 Prowadzący: dr Paweł Drozda Algorytmy zarządzania współbieżnym wykonaniem transakcji  blokowanie - uszeregowanie transakcji wynika z kolejności uzyskiwanych blokad  znaczników czasowych – uszeregowanie wynika z wartości znaczników czasowych związanych z transakcjami  optymistyczne – walidacja poprawności uszeregowania dr Paweł Drozda Metody znaczników czasowych (1)  znacznik czasowy (TS) – unikalny identyfikator wyznaczający kolejność transakcji (wg kolejności uruchomienia)  generowane przez zegar bądź przez licznik (poprzez zwiększenie o jeden)  znaczniki czasowe jednostek danych:  ReadTS(x) – znacznik ostatniej transakcji czytającej x  WriteTS(x) – znacznik ostatniej transakcji piszącej do x dr Paweł Drozda Metody znaczników czasowych (2)  Algorytm  T chce odczytać x  jeśli TS(T) < WriteTS(x), to T wycofywana i restartowana z nowym TS(T)  gdy TS(T) >= WriteTS(x), to T czyta x; wartość ReadTS(x)= max(TS(T),ReadTS(x))  T chce pisać do x  jeśli TS(T) < WriteTS(x) lub TS(T) < ReadTS(x), to T wycofywana i restartowana z nowym TS(T)  wpp T pisze do x; WriteTS(x)=TS(T) dr Paweł Drozda Metody znaczników czasowych (3)  Zasada zapisu Thomasa (modyfikacja podstawowej metody)  T chce pisać do x  jeśli TS(T) < WriteTS(x) – można pominąć operację zapisu do x (wartość jest przestarzała – później uruchomiona transakcja zmodyfikowała tą wartość)  pozostałe przypadki bez zmian  zapewnia szerszy wielodostęp  nie odrzuca transakcji z niepotrzebnymi zapisami (tylko nie dokonuje zapisu) dr Paweł Drozda Metoda znaczników czasowych – przykład (1) T1 t1 start t2 r(x) t3 x=x+10 t4 w(x) t5 T2 T3 start r(y) start t6 t7 y=y+20 t8 w(y)  r(y) t9 y=y+30 t10 w(y) t11 start dr Paweł Drozda Metoda znaczników czasowych – przykład (2) T1 T2 T3 t12 z=100 t12 w(z) t14 z=50 t15 w(z)  t16 commit commit r(y) t17 y=y+20 t18 w(y) t19 commit dr Paweł Drozda Podstawowa metoda znaczników czasowych - cechy  gwarantuje szeregowalność transakcji transakcje wykonywane według znaczników czasowych  nie gwarantuje odtwarzalności harmonogramu przykład: H1= w1(x)r2(x)w2(x)c2a1, gdzie TS(T1)< TS(T2) dr Paweł Drozda Modyfikacja metody  Zapewnienie odtwarzalności – konieczna modyfikacja metody  główna idea – buforowanie operacji odczytu i zapisu aż do momentu zatwierdzenia transakcji  T1 zapisuje x: WriteTS(x) – aktualizowany, x – zmieniony dopiero po zatwierdzeniu transakcji T1  T2 odczytuje daną x zaktualizowaną przez T1: gdy warunek odczytu jest spełniony to odczyt odsunięty do momentu zatwierdzenia T1 dr Paweł Drozda Algorytmy optymistyczne (1)  Trzy stany:  Faza odczytu – modyfikacje przechowywane w obszarach roboczych transakcji  Faza walidacji – badanie uszeregowalności transakcji; transakcje niespełniające uszeregowalności wycofywane i restartowane  Faza zapisu – po pomyślnej walidacji modyfikacje wprowadzane do bazy dr Paweł Drozda Algorytmy optymistyczne (2)  Faza walidacji – określa czy transakcje mogą spowodować kolizję  znaczniki czasowe dla transakcji:  start(T) – rozpoczęcie transakcji  validation(T) – rozpoczęcie walidacji  finish(T) – po zakończeniu transakcji  walidacja pomyślna gdy:  finish(S)