BD-2st-1.2-w09.tresc-1.1-Slajd18
Metody wykrywania i rozwiązywania zakleszczeń (1)
Drugą z popularnych metod rozwiązywania problemu zakleszczenia jest metoda wykrywania i rozwiązywania zakleszczeń. Idea tej metody polega na wykrywaniu zakleszczenia i następnie na jego rozwiązywaniu.
Idea algorytmu wynika ze spostrzeżenia, że zakleszczenie jest zjawiskiem stosunkowo rzadkim i, najczęściej, obejmuje niewiele transakcji. Stąd, taniej jest wykrywać zakleszczenia i je rozwiązywać w momencie wystąpienia, niż zapobiegać wystąpieniu zakleszczeń. Do wykrywania zakleszczeń metody te wykorzystują graf oczekiwania transakcji (waits-for-graphs – WFG), który reprezentuje stan wzajemnego oczekiwania transakcji na uwolnienie zasobów. Węzłami grafu są transakcje, natomiast łuki reprezentują stan oczekiwania transakcji na uwolnienie zasobu.
Przykładowo, na grafie FWG przedstawionym na slajdzie transakcja T1 oczekuje na zwolnienie danej Y blokowanej przez transakcję T2. Transakcja T2 oczekuje na uwolnienie danej Z blokowanej przez transakcję T3, która, z kolei oczekuje na zwolnienie danej X blokowanej przez transakcję T1.
Cykl w grafie FWG oznacza wystąpienie zakleszczenia w systemie.
