Sr-6-wyk-1.0-Slajd35
Pesymistyczne porządkowanie według znaczników czasu
Kolejny algorytm to pesymistyczne porządkowanie według znaczników czasu (ang. pessimistic timestamp ordering ). W algorytmie pesymistycznego sterowania współbieżnością każda transakcja T jest opisywana znacznikiem czasowym t(T ). Ponadto każda zmienna x również opatrywana jest dwoma znacznikami czasowymi: znacznikiem czasu zapisu tz(x ) oraz znacznikiem czasu odczytu tc(x ). Wartość tz(x ) jest równa znacznikowi transakcji, która jako ostatnio pisała do zmiennej x , analogicznie jest z wartością tc(x ), z tym że operacja dotyczy oczywiście odczytu. Algorytm wymaga, aby znaczniki czasu były unikalne. W tym celu można zastosować np. algorytm Lamporta.
W wypadku wystąpienia konfliktu między operacjami, w pierwszej kolejności obsługiwana jest ta, która ma mniejszy znacznik czasowy.
Zobaczmy teraz co się dzieje w przypadku, kiedy planista otrzyma od transakcji T zlecenie na operację odczytu lub zapisu zmiennej x . Jeżeli transakcja zleca odczyt, planista porównuje wartości znacznika t transakcji z wartością tz(x ). Jeżeli wystąpił zapis na zmiennej x w momencie, kiedy transakcja T była już wykonywana, czyli gdy t < tz(x ), T musi zostać zaniechana. W przeciwnym wypadku T wykonuje operację, a wartość tc(x ) zostaje ustawiona na max[t , tc(x )].
Podobna sytuacja występuje dla operacji zapisu. Po nadejściu zlecenia zapisu, porównujemy wartości t oraz tc(x ). Jeśli t < tc(x ), transakcja zostaje zaniechana, gdyż zmienna x została w tym przypadku odczytana po rozpoczęciu transakcji T . Gdy zachodzi natomiast sytuacja odwrotna operacja może być wykonana, a wartość tz(x ) odpowiednio ustawiona na max[t , tz(x )].
Porównując ten algorytm do algorytmu blokowania dwufazowego, można zauważyć, że przeploty operacji, które są akceptowalne dla jednego algorytmu, niekoniecznie są akceptowalne dla drugiego i odwrotnie.
Zaletą tego algorytmu jest to, że uwalnia nas od problemu zakleszczania.
