|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
StromovΘ protokoly
Sφla dvoufßzovΘho uzamykacφho protokolu spoΦφvala v tom, ₧e protokol zajiÜ¥oval uspo°ßdatelnost pro ka₧d² legßlnφ rozvrh. Vφme ji₧ takΘ, ₧e v modelu ploch²ch transakcφ s jednoduch²mi objekty jde o podmφnku nutnou, tj. uspo°ßdatelnost implikuje dvoufßzovost. V jin²ch modelech transakcφ lze pou₧φt i jinΘ protokoly, obecn∞ nedvoufßzovΘ protokoly, vedoucφ takΘ ke korektnφm rozvrh∙m. Ukß₧eme zde specißlnφ p°φpad tzv. stromovΘho protokolu vhodnΘho nap°. pro hierarchickΘ databßze, ale i pro jinΘ stromovΘ struktury dat, jako jsou nap°. B-stromy. Budeme p°edpoklßdat pouze v²luΦnΘ zßmky W_LOCK, tj. po provedenφ W_LOCK(X) m∙₧e b²t objekt X jak Φten, tak zapisovßn. V stromovΘm protokolu m∙₧e ka₧dß transakce T pou₧φvat zßmky s nßsledujφcφmi pravidly:
Lze ukßzat, ₧e vÜechny rozvrhy, kterΘ jsou legßlnφ pod stromov²m uzamykacφm protokolem jsou uspo°ßdatelnΘ a na rozdφl od dvoufßzov²ch protokol∙ zde nedochßzφ k uvßznutφ. Uva₧ujme strom na obrßzku 1 a transakce T1: W_LOCK(B); W_LOCK(E); UNLOCK(E); W_LOCK(D); UNLOCK(B); W_LOCK(G); UNLOCK(D); UNLOCK(G). T2: W_LOCK(D); W_LOCK(H); UNLOCK(D); UNLOCK(H). T3: W_LOCK(B); W_LOCK(E); UNLOCK(E); UNLOCK(B). T4: W_LOCK(D); W_LOCK(H); UNLOCK(D); UNLOCK(H).
Obr. 1 Hierarchickß databßze Jeden z mo₧n²ch uspo°ßdateln²ch rozvrh∙ transakcφ T1,...,T4 je v tabulce 1.
Tab. 1 Uspo°ßdateln² rozvrh transakcφ T1,...,T4 DalÜφ p°φklad specißlnφho p°φpadu stromovΘho protokolu se t²kß B-strom∙. Ukß₧eme zßrove≥, jak se realizujφ fyzickΘ zßmky, tj. jak se °eÜφ p°φpad vφcenßsobnΘho vstupu do fyzickΘ struktury. Pro prßci s B-stromy budeme uva₧ovat operace READ(X) a operaci UPDATE(X). Prvnφ z nich znamenß nalezenφ a p°eΦtenφ listovΘho uzlu s objektem X z B-stromu, druhß p°edstavuje bu∩ INSERT(X) nebo DELETE(X), tj. aktualizaci B-stromu prost°ednictvφm objektu X. Pro operaci UPDATE lze u B-strom∙ objevit jednu p°irozenou vlastnost, kterß nßm urΦuje, jak velk² kus B-stromu musφ b²t uzamΦen, aby operace UPDATE mohla b²t provedena. Uzel B-stromu nazveme bezpeΦn², jestli₧e mß (i) mΘn∞ ne₧ m-1 klφΦ∙ (pro operaci INSERT) (ii) vφce ne₧ é m/2ù - 1 klφΦ∙ (pro operaci DELETE) Nenφ-li uzel bezpeΦn², bude UPDATE ovliv≥ovat p°edch∙dce tohoto uzlu (d∙sledek Üt∞penφ nebo slΘvßnφ uzl∙). Pro ka₧d² uzel v B-stromu bude existovat fronta, do kterΘ se budou uklßdat po₧adavky na zamykßnφ. Tyto po₧adavky budou ud∞leny v souladu s pravidly v²luΦn²ch a sdφlen²ch zßmk∙, tj. jeden uzel m∙₧e b²t uzamΦen souΦasn∞ nejv²Üe jednφm v²luΦn²m zßmkem nebo n∞kolika sdφlen²mi zßmky. Nesmφ vÜak b²t uzamΦen souΦasn∞ sdφlen²m (R_LOCK) a v²luΦn²m (W_LOCK) zßmkem. P°ipome≥me, ₧e sdφlenΘ zßmky umo₧≥ujφ pouze Φtenφ. Pro B-stromy ukß₧eme dva protokoly, zvlßÜ¥ pro Φtenφ B-stromu a zvlßÜ¥ pro aktualizaci. V obou algoritmech uzamykßnφ p°edpoklßdßme hloubku stromu v∞tÜφ ne₧ 1.
1. Umφsti R_LOCK do ko°ene B-stromu 2. P°eΦti ko°en B-stromu do vyrovnßvacφ pam∞ti (b∞₧n² uzel) 3. while b∞₧n² uzel nenφ list do begin umφsti R_LOCK na nßslednφka uzlu b∞₧nΘho uzlu; uvolni zßmek uzlu b∞₧nΘho uzlu; p°eΦti nßslednφka b∞₧nΘho uzlu end
1. Umφsti W_LOCK do ko°ene B-stromu 2. P°eΦti ko°en B-stromu do vyrovnßvacφ pam∞ti (b∞₧n² uzel) 3. while b∞₧n² uzel nenφ list do begin umφsti W_LOCK na nßslednφka uzlu b∞₧nΘho uzlu; p°eΦti nßslednφka do b∞₧nΘho uzlu; if b∞₧n² uzel je bezpeΦn² then uvolni zßmky vÜech uzamΦen²ch p°edch∙dc∙ end VÜimn∞me si, ₧e protokol pro READ udr₧uje v₧dy jen jeden uzamknut² uzel v transakci, u protokolu pro UPDATE jich m∙₧e b²t vφce. Uva₧ujme Φßst B-stromu s m=3 (obrßzek 2). B-strom obsahuje klφΦe z domΘny atributu nap°. JM╔NO_F (jmΘno filmu) a do stromu se bude pouze zapisovat (tj. pro bezpeΦnost staΦφ spln∞nφ vlastnosti (i)). Chceme-li nap°. vlo₧it do B-stromu klφΦ Filosofskß historie, vypl²vß z algoritmu vklßdßnφ do B-stromu, ₧e na cest∞ z ko°ene stromu 6 do listu 0 je bezpeΦn² uzel 6 a 2. Tedy W_LOCK bude aplikovßn t°ikrßt - sice na uzly 6, 2, 0, ovÜem s tφm, ₧e uzel 6 bude uvoln∞n jeÜt∞ p°ed vstupem do uzlu 0. Zarßmovanß Φßst obrßzku 2 ukazuje zamknutou v∞tev stromu t∞sn∞ p°ed operacemi Üt∞penφ uzlu 0 (bude se opravovat i uzel 2). Odemknutφ uzl∙ 2 a 0 bude nßsledovat a₧ po t∞chto operacφch.
6 Karla - - 2 5 -
2 5 F.L .V∞k - - Poklad - - 0 4 - 3 1 -
0 4 BabiΦka F.L.V∞k - Karla - - Z3 Z5 - Z1 - - Obr. 2 Zamykßnφ B-stromu Zßv∞rem poznamenejme, ₧e protokol pro aktualizaci B-stromu je specißlnφm p°φpadem stromovΘho protokolu. Je tedy garantovßna uspo°ßdatelnost pro jak²koli legßlnφ rozvrh, zajiÜt∞na je absence uvßznutφ. StromovΘ protokoly majφ proti dvoufßzov²m uzamykacφm protokol∙ dv∞ v²hody. Umo₧≥ujφ d°φve odmykat objekty a zabra≥ujφ uvßznutφ. Obojφ p°ispφvß k zv²Üenφ pr∙chodnosti transakΦnφho provozu. <seznam dφl∙ serißlu> <COMPUTERWORLD> |