Wykład 9. Algorytmy zarządzania współbieżnym wykonywaniem transakcji - część I, PRIV 2, PRIV 3, Bazy ...
[ Pobierz całość w formacie PDF ]
Systemy baz danych
Algorytmy zarządzania współbieżnym
wykonywaniem transakcji
część I
Wykład przygotował:
Tadeusz Morzy
BD – wykład 9
Celem wykładu jest przedstawienie i omówienie podstawowych algorytmów
zarządzania współbieżnym wykonywaniem transakcji. Rozpoczniemy od
przedstawienia algorytmów blokowania. Omówimy podstawowy algorytm blokowania
– algorytm blokowania dwu-fazowego. Następnie przedstawimy zjawisko
zakleszczenia i omówimy podstawowe algorytmy rozwiązywania zakleszczenia. Na
zakończenie wykładu, przedstawimy i omówimy problem duchów.
1
Systemy baz danych
Klasyfikacja algorytmów
Algorytmy zarządzania współbieżnym wykonywaniem
transakcji możemy sklasyfikować następująco:
1.
algorytmy blokowania
algorytmy blokowania
- uszeregowanie transakcji
wynika z kolejności uzyskiwanych blokad (algorytm
blokowania dwufazowego – 2PL)
2.
algorytmy znacznik
w czasowych
- uszeregowanie
transakcji wynika z wartości znaczników czasowych
związanych z transakcjami
3.
algorytmy optymistyczne
algorytmy optymistyczne
- walidacja poprawności
uszeregowania
BD – wykład 9
(2)
algorytmy blokowania
- uszeregowanie transakcji wynika z kolejności uzyskiwanych
blokad (algorytm blokowania dwufazowego – 2PL);
algorytmy znacznik
w czasowych
- uszeregowanie transakcji wynika z wartości
znaczników czasowych związanych z transakcjami;
algorytmy optymistyczne
algorytmy optymistyczne
- walidacja poprawności uszeregowania.
2
1.
algorytmy znacznikó
w czasowych
2.
3.
Algorytmy zarządzania współbieżnym wykonywaniem transakcji możemy
sklasyfikować następująco:
algorytmy blokowania
algorytmy znacznikó
w czasowych
Systemy baz danych
Algorytmy blokowania (1)
• Blokada jest zmienną skojarzoną z każdą daną w bazie
danych, określającą dostępność danej ze względu na
możliwość wykonania na niej określonych operacji
• Ogólnie, z każdą daną mamy skojarzoną jedną blokadę
Ze względu na proces blokowania, dane w bazie danych
mogą występować w jednym z trzech stanów:
– dana nie zablokowana (
0)
– dana zablokowana dla odczytu
R
(współdzielona
S
)
– dana zablokowana dla zapisu
W
(wyłączna
X
)
BD – wykład 9
(3)
Podstawową grupą algorytmów zarządzania współbieżnym wykonywaniem transakcji
są algorytmy blokowania. Algorytmy te opierają się na mechaniźmie blokad
zakładanych przez transakcje. Blokada jest zmienną skojarzoną z każdą daną w
bazie danych, określającą dostępność danej ze względu na możliwość wykonania na
niej określonych operacji. Ogólnie, z każdą daną mamy skojarzoną jedną blokadę.
Ze względu na proces blokowania, dane w bazie danych mogą występować w
jednym z trzech stanów:
- dana nie zablokowana (
0)
,
- dana zablokowana dla odczytu
R
(współdzielona
S
),
- dana zablokowana dla zapisu
W
(wyłączna
X
).
3
Systemy baz danych
Algorytmy blokowania (2)
• System zarządzania bazą danych musi realizować trzy
dodatkowe operacje na bazie danych:
– Blokowanie danej x do odczytu (LR(x))
– Blokowanie danej x do zapisu (LW(x))
– Odblokowanie danej x (UNL(x))
• Operacje blokowania muszą poprzedzać wykonanie
operacji odczytu oraz zapisu danej
BD – wykład 9
(4)
Wprowadzenie blokad pociąga za sobą konieczność modyfikacji zbioru operacji
wykonywanych na bazie danych. Podstawowy zbiór operacji transakcji (odczyt, zapis,
zatwierdzenie, wycofanie) rozszerzamy o 3 dodatkowe operacje:
- Blokowanie danej x do odczytu (LR(x)),
- Blokowanie danej x do zapisu (LW(x)),
- Odblokowanie danej x (UNL(x)).
Operacje blokowania muszą poprzedzać wykonanie operacji odczytu oraz zapisu
danej. Z każdą operacją blokowania danej X skojarzona jest operacja odblokowania
danej X.
4
Systemy baz danych
Kompatybilność blokad
• Dwie blokady są kompatybilne jeżeli mogą być założone
na tej samej danej przez dwie różne transakcje
Blokada
uzyskana
Blokada
żądana
R
W
R
9
-
W
-
-
BD – wykład 9
(5)
Wprowadzimy obecnie pojęcie kompatybilności blokad. Mówimy, że dwie blokady są
kompatybilne jeżeli mogą być założone na tej samej danej przez dwie różne
transakcje. Macierz kompatybilności blokad przedstawiono na slajdzie. Jak łatwo
zauważyć, kompatybilne są blokady do odczytu, natomiast pozostałe kombinacje
blokad (RW, WR, WW) są niekompatybilne.
5
[ Pobierz całość w formacie PDF ]