![]() |
![]() | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Dvoufázový uzamykací protokol
Dnes ukážeme, že je možné konstruovat transakce podle jistých pravidel tak, že za určitých předpokladů bude každý jejich rozvrh uspořádatelný. Soustavě takových pravidel se obecně říká protokol. Připomeňme, že uspořádatelnost znamená ekvivalenci nějakému sériovému zpracování množiny transakcí. Nejznámější protokoly jsou založeny na dynamickém zamykání a odmykání objektů v databázi. Zamykání (operace LOCK) je akce, kterou vyvolá transakce na objektu, aby ho ochránila před přístupem od ostatních transakcí. Vedle dynamického přístupu existuje samozřejmě i statické zamykání a odmykání objektů, což znamená, že objekty používané v transakci jsou všechny uzamknuty na počátku provádění transakce a odemknuty těsně před ukončením transakce. V tomto přístupu mohou být zřejmě paralelně prováděny pouze takové transakce, které nejsou konfliktní, tj. nesdílí žádné objekty. Odemknutí (operace UNLOCK) je akce uvolňující objekt pro zpracování dalšími transakcemi. Transakce, která uzamkla objekt, má právo na něm provádět operace READ a WRITE (a další operace). Budeme uvažovat jednoduchý model, kdy objekt může být v daném čase uzamčen nejvýše jednou transakcí. Objekt bude nutné mít v transakci uzamknutý, kdykoliv k němu chce tato transakce přistupovat. Transakce se nebudou pokoušet uzamknout objekt již uzamknutý jinou transakcí (jinak musí čekat, až je objekt odemknut a to toutéž transakcí, která ho zamkla). Rozvrhy splňující druhou podmínku budeme nazývat legální. Nelegální rozvrh je takový, který není legální. Samotné uzamykání a odmykání libovolným způsobem ještě nevedou k uspořádatelnému rozvrhu. V případech některých nelegálních rozvrhů může dokonce nastat uváznutí (deadlock). V jedné transakci chceme uzamknout to, co je již uzamknuté druhou transakcí a naopak. Připomíná to situaci na křižovatce bez značek přednosti v jízdě, kdy všichni stojí, čekají na uplatnění přednosti zprava a nikdo nemůže vyjet jako první. Rozvrh S1 (torzo) v tabulce 1 pro prvních několik operací transakcí T1 a T2 ukazuje uváznutí. S1
Tab. 1 Příklad uváznutí Zřejmě v okamžiku, kdy v T2 je uzamykán objekt B, nelze rozvrhnout T1 tak, aby mohlo nastat LOCK(B). Prvních 6 kroků rozvrhu S1 již tedy předurčuje uváznutí. Na rozdíl od situace na křižovatce, kdy se jeden z řidičů dohodě s druhým a dá mu přednost, se uváznutí v transakčním zpracování obvykle řeší tak, že se provede ROLLBACK jedné transakce. Pak to, co bylo uzamknuto touto transakcí, bude odemknuto a lze pokračovat ve zpracování druhé transakce. Námět na "nadějnější" rozvrh naznačuje následující úvaha: kdyby v T1 byly předposlední dvě operace vyměněny, stačilo by "pozdržet" T2, v T1 odemknout B a pokračovat v provádění T2. Řešení s likvidací jedné transakce ovšem není nejvhodnější např. tehdy, když druhá transakce je dlouhá. Byly proto vyvinuty jiné metody pro řešení uváznutí nebo dokonce pro prevenci uváznutí. Omezíme se dále na tzv. dobře formované transakce, které podporují přirozené požadavky na transakce:
Máme-li množinu dobře formovaných transakcí, stále ještě neznáme postačující podmínku pro to, aby všechny legální rozvrhy byly uspořádatelné. Konzistence databáze totiž není zaručena tím, že objekt odemkneme bezprostředně po manipulaci s ním. Mezi dnes již klasické výsledky databázové teorie patří tvrzení, že k zajištění uspořádatelnosti všech legálních rozvrhů stačí, aby všechny transakce v množině uvažovaných transakcí byly dvoufázové, neboli, aby každá transakce splňovala tzv. dvoufázový (uzamykací) protokol. Uzamykací protokol je obecně množina pravidel, které udávají, kdy transakce bude uzamykat a odmykat objekty databáze. Dvoufázová transakce v první fázi uzamyká vše, co je potřeba, a od prvního odemknutí (druhá fáze) se transakcí zamknuté objekty pouze odmykají, tj. není již použito žádné operace LOCK. Tedy transakce musí mít všechny objekty uzamčené před tím, než nějaký objekt odemkne. Platí dokonce, že v případě, kdy není nic známo o sémantice transakcí, je dvoufázovost transakcí dokonce nutnou podmínkou pro zachování konzistence databáze. To ovšem nevylučuje případ, že někdy lze nalézt legální rozvrh nedvoufázových transakcí, který je uspořádatelný. Tabulka 2 ukazuje možný uspořádatelný rozvrh dvoufázových transakcí T3 a T4.
Tab. 2 Příklad rozvrhu dvoufázových transakcí V daném rozvrhu T4 jednou Tab. 1 Příklad uváznutí čeká na uvolnění zámku pro A, jednou na uvolnění zámku pro B. V opačném případě, tj. kdyby operace LOCK(A), resp. LOCK(B) byly v rozvrhu umístěny před UNLOCK(A), resp. UNLOCK(C) transakce T3, rozvrh by se stal nelegálním. Na obrázku 1 je ukázáno, jak může vypadat odpovídající volání operací v čase včetně čekání na uvolnění zámků.
požaduje a dostane požaduje a dostane zámek na A zámek na C T3 ¯ ¯ uvolňuje uvolňuje zámek na A zámek na C
dostane požaduje a dostane zámek na A zámek na C T4 ¯ ¯ požaduje a dostane požaduje zámek na A uvolňuje zámek na B je blokována (čeká) zámek na A,B,C Obr. 1 Souběžné volání transakcí T3 a T4 Protokol, ve kterém je každá transakce dvoufázová, se nazývá dvoufázový uzamykací protokol. Dvoufázový protokol tedy tvoří pouze jednu z možných postačujících podmínek pro uspořádatelnost každého legálního rozvrhu. Existují i jiné, nedvoufázové protokoly zaručující tuto vlastnost a korektnost dalších (v našem modelu) neuspořádatelných rozvrhů. Na prostředí transakcí však musí být kladeny další (sémantické) požadavky. Jejich znalost je pak využita v protokolech. Pozor ale, snadno lze nalézt příklad, který dokazuje, že dvoufázovost nemusí zajišťovat nepřítomnost uváznutí, která jsou pro dvoufázové uzamykání dost typická. U dvoufázových uzamykacích protokolů jim lze zamezit např. přiřazením priorit transakcím a čekáním na transakce s vyšší prioritou. Dalším problémem je též kaskádové rušení transakcí. Provede-li se ROLLBACK transakce T, může to znamenat ROLLBACK pro další transakce, které využívaly hodnoty aktualizované transakcí T. Tento nedostatek se dá odstranit pomocí striktních dvoufázových protokolů, které uvolňují zámky až po ukončení transakce (COMMIT). Nevýhodou těchto protokolů je ovšem omezení paralelismu. Na druhé straně je toto řešení v současných SŘBD nejobvyklejší. Nevýhodou dvoufázového uzamykacího protokolu je, že vždy nejvýše jedna transakce v čase uzamykala nějaký objekt. Kromě uvedených zámků existuje řada dalších metod zamykání, jako např. sdílené a výlučné zámky. Uzamykání může být provedeno precizněji, protože se uvažují rozdíly mezi operacemi READ a WRITE. Výlučný zámek může být aplikován na objekty jak pro operace READ a WRITE, sdílený zámek uzamyká objekty které chceme pouze číst. Více typů zámků vede k uzamykacího protokolu s podobnými vlastnostmi jako původní verze, ovšem s větším stupněm paralelismu. <seznam dílů seriálu> <COMPUTERWORLD> |