BD-2st-1.2-w09.tresc-1.1-Slajd16

From Studia Informatyczne

Algorytmy zapobiegania zakleszczeniom (1)

Algorytmy zapobiegania zakleszczeniom (1)


Przedstawimy obecnie krótko dwa podstawowe algorytmy zapobiegania zakleszczeniom. Oba algorytmy do rozwiązywania problemu zakleszczenia wykorzystują tzw. znaczniki czasowe transakcji. Znacznik czasowy transakcji T, oznaczany jako TS(T), jest nadawany transakcji w momencie jej inicjacji i stanowi konkatenację stanu zegara fizycznego (lub logicznego) oraz identyfikatora stanowiska. Cechą charakterystyczną znacznika czasowego transakcji jest jego unikalność.

Pierwszy z wymienionych algorytmów zapobiegania zakleszczeniom, algorytm wait-die, ma następującą postać:

Transakcja Ti próbuje uzyskać blokadę na danej X , tymczasem dana ta jest już zablokowana przez transakcję Tj . Jeżeli TS(Ti ) < TS(Tj ) (Ti jest starsza Tj ) wtedy transakcja Ti będzie czekać na zwolnienie blokady. W przeciwnym wypadku Ti będzie wycofana i restartowana z tym samym znacznikiem czasowym.

Drugi z wymienionych algorytmów zapobiegania zakleszczeniom, algorytm wound-wait, ma podobną filozofię działania ale nadaje inne priorytety działania transakcjom starszym i transakcjom młodszym. Transakcja Ti próbuje uzyskać blokadę na danej X , tymczasem dana ta jest już zablokowana przez transakcję Tj . Jeżeli TS(Ti ) < TS(Tj ) (Ti jest starsza Tj ) wtedy transakcja Tj będzie wycofana i restartowana z tym samym znacznikiem czasowym. W przeciwnym wypadku Ti będzie czekać na zwolnienie blokady.

Oba algorytmy zapobiegają wystąpieniu zakleszczenia. Ich wadą jest to, że czasami prowadzą do wycofania transakcji nawet jeżeli nie występuje niebezpieczeństwo zakleszczenia.




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