Databázové a informační systémy NÁVRH IMPLEMENTACE 3 PARALELNÍ PROCESY V DATABÁZÍCH
1
PARALELNÍ PROCESY V DATABÁZÍCH • teorie dosud - aplikace jednouživatelské • praxe - databáze současně přístupná více uživatelům, paralelní běh aplikací • příklady - systémy pro rezervaci místenek, jízdenek, letenek, firmy s účetnictvím, skladem, osobní evidencí ap., prakticky všechny větší aplikace • nový problém – zajistit při paralelním zpracování dat v databázi konzistenci 4 pokud programy data jen čtou – vhodná co největší míra paralelismu (hodnoty dat se nemění a nemůže vzniknout nekonzistence) 4 u programů modifikujících databázi je nutné zajistit v každém okamžiku přístup k datům jen pro jediný program 4 současně je nutná dostatečná průchodnost systému • problémy s řízením paralelních procesů vznikají u IS provozovaných prostřednictvím počítačové sítě a u databází distribuovaných 2
PARALELNÍ PROCESY V DATABÁZÍCH Transakce, požadavek sériovosti • opět používáme základní jednotky zpracování = transakce • u víceuživatelského provozu navíc požadavek sériovosti transakcí = výsledek po paralelním provedení řady transakcí je stejný, jako když by byly provedeny celé transakce postupně za sebou. • i při sériovém zpracování transakcí není jednoznačný výsledek
3
PARALELNÍ PROCESY V DATABÁZÍCH Příklad: převodu mezi bankovními konty. Dvě transakce T0 a T1 přísluší dvěma paralelně běžícím programům. Počáteční stav kont je A = 1000, B = 2000. Transakce T0: T1: read(A) read(A) A:=A-50 pom:=A*0.1 write(A) A:=A-pom read(B) write(A) B:=B+50 read(B) write(B) B:=B+pom write(B) Provádíme-li transakce v pořadí T0-T1, je výsledek A=855, B=2145 Provádíme-li transakce v pořadí T1-T0, je výsledek A=850, B=2150. Pro obě transakce je zde podmínka konzistence A+B= konst, při obou výsledcích zůstává konzistence zachována. 4
PARALELNÍ PROCESY V DATABÁZÍCH Platí • Pro n paralelně běžících transakcí existuje n! možností sériového pořadí. • Sériové zpracování transakcí může vést k různým výsledkům, zůstává však zachována konzistence databáze. • Sériové provádění transakcí je časově velmi omezující, transakce mohou být dlouhé, pracovat nad velkou částí databáze, všechny ostatní čekají. • Pro větší průchodnost je nutné paralelní zpracování, střídání operací různých transakcí a tak lepší využití procesoru. • Říkáme, že transakce jsou prováděny podle určitého schématu.
Paralelní zpracování • • • •
Paralelní zpracování transakcí je takové, že se příkazy různých transakcí (příslušející různým procesům) střídají. Schémat paralelního zpracování je velmi mnoho. Některá z nich vedou k porušení konzistence, některá ne. Úkolem je najít schémata, která splňují požadavek sériovosti. 5
PARALELNÍ PROCESY V DATABÁZÍCH Příklad schématu 1, při kterém dochází k porušení konzistence dat T0
T1
paměť T0
paměť T1
databáze
.
A=1000,B=2000 read(A) A=1000 A:=A-50 A=950 ---------------------------------------------------------------------------------------------------------read(A) A=1000 pom:=A*0.1 pom=100 A:=A-pom A=900 write(A) A=900 read(B) B=2000 ---------------------------------------------------------------------------------------------------------write(A) A=950 read(B) B=2000 B:=B+50 B=2050 write(B) B=2050 ---------------------------------------------------------------------------------------------------------B:=B+pom B=2100 write(B) B=2100 6
PARALELNÍ PROCESY V DATABÁZÍCH Příklad schématu 2, při kterém nedochází k porušení konzistence dat T0
T1
paměť T0
paměť T1
databáze
.
A=1000,B=2000 read(A) A=1000 A:=A-50 A=950 write(A) A=950 ---------------------------------------------------------------------------------------------------------read(A) A=950 pom:=A*0.1 pom=95 A:=A-pom A=855 write(A) A=855 ---------------------------------------------------------------------------------------------------------read(B) B=2000 B:=B+50 B=2050 write(B) B=2050 ---------------------------------------------------------------------------------------------------------read(B) B=2050 B:=B+pom B=2145 write(B) B=2145 7
PARALELNÍ PROCESY V DATABÁZÍCH •
Je možno vysledovat, že důležité jsou operace read ( ) a write ( ) a jejich pořadí, ostatní operace nemají na výsledek paralelního zpracování z hlediska konzistence vliv.
8
PARALELNÍ PROCESY V DATABÁZÍCH Precendenční graf Kdy paralelní schéma splňuje požadavek sériovosti a kdy ne ? Když každá transakce nejprve přečte objekt operací READ a teprve potom jej zapíše operací WRITE, je možno sestrojit tzv. precendenční graf = orientovaný graf, jehož uzly jsou transakce a jehož hrany jsou orientovány Ti → Tj , jestliže (1) Ti provede WRITE(A) dříve, než Tj provede READ(A) (2) Ti provede READ(A) dříve, než Tj provede WRITE(A). Jestliže získaný orientovaný graf obsahuje cyklus, pak testované schéma paralelního zpracování transakcí nesplňuje požadavek sériovosti.
9
PARALELNÍ PROCESY V DATABÁZÍCH Příklad precendenčního grafu schématu 1 pro objekt A Schéma 1: T0 T1 -------------------------------------read(A) 2 read(A) T0 T1 write(A) write(A) 2 --------------------------------------Ti → Tj T0 provede READ(A) dříve než T1 provede WRITE, dle (2) platí T0→T1 T1 provede READ dříve než T0 provede WRITE, dle (2) platí T1→ T0
10
PARALELNÍ PROCESY V DATABÁZÍCH Příklad precendenčního grafu schématu 2 pro objekt A Schéma 2: T0 T1 --------------------------------------read(A) write(A) 1 T0 T1 read(A) write(A) --------------------------------------Ti → Tj T0 provede WRITE dříve než T1 provede READ, dle (1) platí T0 → T1 T1 neprovede dříve než T0 nic
11
PARALELNÍ PROCESY V DATABÁZÍCH Když transakce zapisuje pomocí WRITE(A), aniž by předtím četla operací READ(A), pak neexistuje žádný efektivní algoritmus rozhodující, zda dané schéma paralelního zpracování transakcí splňuje požadavek sériovosti.
12
PARALELNÍ PROCESY V DATABÁZÍCH Zamykání • zajištění požadavku sériovosti se řeší pomocí zpřístupnění dat vždy jen jediné transakci: když jedna transakce získá k údaji výlučný přístup, pak údaj nemůže modifikovat jiná transakce dříve, než první transakce skončí a uvolní přístup k údaji; říkáme, že údaje jsou zamčeny • jediný klíč ke každému zámku přiděluje systém pro řízení paralelního zpracování (součást SŘBD) těm transakcím, které o něj požádají.
13
PARALELNÍ PROCESY V DATABÁZÍCH Úroveň zamykání údajů (CO se zamyká) 1. OS - soubor typu read-only 2. SŘBD příkazem v aplikačním programu § § § §
uzamčení databáze uzamčení datového souboru uzamčení jednoho nebo několika záznamů uzamčení jednotlivých položek (atributů) záznamu
Způsob zamykání (KDO zamyká) 1. Aplikační program (programátor) explicitním příkazem 2. SŘBD automaticky (implicitně) současně s některým příkazem pro manipulaci s daty
Flock Rlock
Expl Impl
14
PARALELNÍ PROCESY V DATABÁZÍCH Druhy zámků (JAK se zamyká) 1. Zámky pro sdílený přístup - umožňují údaje jen číst více transakcím současně, zapisovat jen jedné, 2. Zámky výlučné - umožní čtení i zápis vždy pouze jedné transakci.
Share Exclusive
Pokud má jedna transakce údaj uzamčený a další transakce jej chce uzamknout také, může dojít ke kolizi. Proto existují funkce testující, zda je údaj volný. Pokud není, je nutno situaci programově řešit.
15
PARALELNÍ PROCESY V DATABÁZÍCH Problémy zámků Zaveďme si následující označení pro žádosti transakcí o uzamčení: LS(A) ... zamkni položku A pro sdílený přístup (Lock Shared) LX(A) ... zamkni položku A pro výlučný přístup (Lock eXclus) UN(A) ... uvolni položku A (UNlock) • • •
Žádosti LS(A) lze zřejmě vyhovět vždy, není-li na A zámek typu LX(A). Žádosti LX(A) lze vyhovět pouze tehdy, je-li položka A ve stavu po provedení UN(A) – není zamčena žádným způsobem. Použití zámků však není jednoduché, nesprávné použití může vést k nesprávným výsledkům – k nekonzistenci, jak ukáží následující příklady.
16
PARALELNÍ PROCESY V DATABÁZÍCH Příklad transakcí T1 a T2 s počátečními hodnotami A=100, B=200 T1: LX(B) T2: LS(A) read(B) read(A) B:=B-50 UN(A) write(B) LS(B) UN(B) read(B) LX(A) UN(B) read(A) display(A+B) A:=A+50 write(A) UN(A) Sériová provedení transakcí T1-T2 i T2-T1 dají výsledek příkazu display(A+B) hodnotu 300. Při následujícím paralelním schématu 3 je však výsledek jen 250.
17
PARALELNÍ PROCESY V DATABÁZÍCH Příklad schématu 3, u kterého není dodržen požadavek sériovosti. T1 T2 paměť T1 paměť T2 LX(B) read(B) B:=B-50 write(B) UN(B)
B=200 B=150 B=150 . LS(A) read(A) UN(A) LS(B) read(B) UN(B) display(A+B)
LX(A) read(A) A:=A+50 write(A) UN(A)
databáze . A=100,B=200
A=100 B=150 A+B=250
.
A=100 A=150 A=150 18
PARALELNÍ PROCESY V DATABÁZÍCH Uváznutí • Zdálo by se tedy, že řešením je uvolnit položky až po ukončení celé transakce. • Následující příklad ukáže, k jakým dalším problémům by to mohlo vést. Příklad mějme upravené transakce T3 a T4 T3: LX(B) T4: LX(A) read(B) read(A) B:=B-50 LS(B) write(B) read(B) LX(A) display(A+B) read(A) UN(A) A:=A+50 UN(B) write(A) UN(B) UN(A) 19
PARALELNÍ PROCESY V DATABÁZÍCH Příklad: Schéma 4 paralelního zpracování, které uvolňuje položky pozdě. T3 T4 . LX(B) read(B) B:=B-50 write(B) -------------------------------------LX(A) read(A) LX(B) ... marně čeká na uvolnění položky B ------------------------------------LX(A) ... marně čeká na uvolnění položky A ...
20
PARALELNÍ PROCESY V DATABÁZÍCH •
• •
Takovou situaci, kdy obě transakce vzájemně čekají na uvolnění některých položek databáze, nelze žádný požadavek uspokojit a celý proces uvázne v mrtvém bodě, nazýváme uváznutím (deadlock). Pokud používáme zámků málo, hrozí nekonzistence. Používáme-li zámků mnoho, hrozí uváznutí.
Máme k řešení dva problémy: 1. splnění požadavku sériovosti – zamykáním částí databáze 2. nebezpečí uváznutí v mrtvém bodě – přílišným zamykáním
21
PARALELNÍ PROCESY V DATABÁZÍCH Požadavek sériovosti K řešení požadavku sériovosti se používá protokolu o zámcích = pravidla udávající, kdy může transakce zamknout a uvolnit objekty. Jednoduchou metodou pro sestavení takového protokolu je metoda dvoufázového zamykání. Spočívá v tom, že v první fázi zámky jen zamykáme a neuvolňujeme, ve druhé fázi naopak jen uvolňujeme a nezamykáme. Pokud transakce paralelního schématu vyhovují protokolu o zámcích, pak § je zajištěn požadavek sériovosti, § není vyloučena možnost uváznutí v mrtvém bodě. Příklad: 1. Výše uvedené transakce T1 a T2 nemají dodržen protokol o zámcích metodou dvoufázového zamykání, proto došlo k nekonzistenci. 2. Transakce T3 a T4 tento protokol dodržen mají, avšak u nich došlo k uváznutí. 22
PARALELNÍ PROCESY V DATABÁZÍCH Metoda dvoufázového zamykání. Příklad: T1: LX(B) read(B) B:=B-50 write(B) UN(B) LX(A) read(A) A:=A+50 write(A) UN(A)
T2: LS(A) read(A) UN(A) LS(B) read(B) UN(B) display(A+B)
Transakce T1 a T2 nemají dodržen protokol o zámcích metodou dvoufázového zamykání, proto došlo k nekonzistenci. 23
PARALELNÍ PROCESY V DATABÁZÍCH Metoda dvoufázového zamykání. Příklad: T1: LX(B) read(B) B:=B-50 write(B) LX(A) UN(B) read(A) A:=A+50 write(A) UN(A)
T2: LS(A) read(A) LS(B) UN(A) read(B) UN(B) display(A+B)
Transakce T1 a T2 mají dodržen protokol o zámcích metodou dvoufázového zamykání, proto nedojde k nekonzistenci – jedna transakce se nemůže včlenit mezi příkazy druhé transakce, pokud ta je v nekonzistentním stavu. 24
PARALELNÍ PROCESY V DATABÁZÍCH Problém uváznutí se řeší pomocí dvou typů metod • SŘBD umí nastalé uváznutí rozpoznat a řeší ho zrušením některých transakcí • prevence uváznutí, SŘBD operace zamykání a uvolňování řídí v transakcích tak, aby k uváznutí nedošlo, .
25
PARALELNÍ PROCESY V DATABÁZÍCH Řešení nastalého uváznutí Jestliže systém nepoužívá prevenci uváznutí, musí mít prostředky pro detekci (rozpoznání) uváznutí obnovu činnosti umrtvených transakcí. Detekce se provádí obvykle použitím grafu relace "kdo na koho čeká" = graf, jehož uzly jsou transakce a orientované hrany představují uvedenou závislost. Záznamem a analýzou grafu čekání se rozpoznává uváznutí. Je-li v grafu cyklus, systém uvázl v mrtvém bodě. Příklad T1
T2 T3
T1 čeká na T2 T2 čeká na T3 T3 čeká na T1
26
PARALELNÍ PROCESY V DATABÁZÍCH •
Jestliže taková situace nastane, systém musí jednu nebo více transakcí vrátit zpět, čímž se zablokovaný přístup k datům (pro tuto transakci) odblokuje a umožní se provedení ostatních transakcí.
•
Obnovení činnosti se provádí pomocí souboru log.
•
Systém vybírá takové transakce, aby s celým postupem byly spojeny co nejmenší náklady, k tomu bere v úvahu: • jaká část transakce již byla provedena, • kolik dat transakce použila a kolik jich ještě potřebuje pro dokončení, • kolik transakcí bude třeba celkem vrátit.
•
Podle těchto kriterií by se mohlo dále stát, že bude vracena stále tatáž transakce a její dokončení by bylo stále odkládáno. Je vhodné, aby systém měl evidenci o vracených transakcích a při výběru bral v úvahu i tuto skutečnost. 2.exe
27
PARALELNÍ PROCESY V DATABÁZÍCH Prevence uváznutí 1. metoda, nejjednodušší - uzamčení všech položek, které transakce používá, hned na začátku transakce ještě před databázovými operacemi a jejich uvolnění až na konci transakce. Transakce se nezahájí, dokud nemá zamknuty všechny potřebné údaje a tedy nemůže dojít k uváznutí uprostřed transakce (fakticky jde téměř o sériové zpracování transakcí). Tato metoda však má dvě velké nevýhody: § využití přístupu k položkám je nízké, protože jsou dlouhou dobu zbytečně zamčené, § transakce musí čekat až budou volné současně všechny údaje,které chce na začátku zamknout, a to může trvat velmi dlouho.
28
PARALELNÍ PROCESY V DATABÁZÍCH Prevence uváznutí 2. Jiná metoda využívá faktu, že k uváznutí nedojde, jestliže transakce zamykají objekty v pořadí respektujícím nějaké lineární uspořádání, definované nad těmito objekty (např. abecední ap.). Z hlediska uživatelského však takový požadavek je příliš omezující a v databázích se příliš nepoužívá. 7.exe 8.exe 3. Plánovače Některé SŘBD řeší problém uváznutí synchronizací paralelních transakcí pomocí speciálního modulu, tzv. plánovače, který předem rozhoduje, které transakce s jejich operacemi spustí a v jakém pořadí.
29
PARALELNÍ PROCESY V DATABÁZÍCH Plánovače v SŘBD jsou zabudovány tyto programové moduly: • Modul řízení transakcí (RT); je to fronta, na kterou se transakce obracejí se žádostí o vykonání operací READ(X) a WRITE(X). Každá transakce je doplněna příkazy BEGIN TRANSACTION a END TRANSACTION. • Modul řízení dat (RD) realizuje čtení a zápis objektů dle požadavků plánovače a dává plánovači zprávu o výsledku a ukončení. • Plánovač zabezpečuje synchronizaci požadavků z fronty dle realizované strategie a řadí požadavky do schémat. • Schéma pro množinu transakcí je pořadí, ve kterém se operace těchto transakcí realizují.
30
PARALELNÍ PROCESY V DATABÁZÍCH Plánovače Nejjednodušší schéma je sériové, ovšem je málo průchodné, cílem celé strategie je větší průchodnost systému. Plánovač při dvoufázovém zamykání vykonává tyto operace: • řídí zamykání objektů, • operace čtení a modifikace objektů povoluje jen těm transakcím, které mají příslušné objekty zamknuté, • sleduje, jestli transakce dodržují protokol dvoufázového zamykání; pokud zjistí jeho porušení, transakci zruší, • předchází uváznutí nebo ho detekují a řeší zrušením transakce.
31
PARALELNÍ PROCESY V DATABÁZÍCH Plánovač pomocí časových razítek Časové razítko (ČR) = číslo přidělené transakci nebo objektu databáze. • čísla přidělovaná transakcím tvoří rostoucí posloupnost, jsou jednoznačná pro všechny transakce a platí pro všechny operace transakce. • čísla používá plánovač pro řízení konfliktních operací READ(A) a WRITE(A). • konfliktními operacemi rozumíme dvě operace týkající se téhož objektu báze a alespoň jedna z nich je WRITE. Všechny páry konfliktních operací se provádějí v pořadí jejich ČR, pak vytvářejí sériová schémata. • nezamyká pomocí explicitních příkazů LS a LX, ale pomocí ČR hlídá sériové provedení transakcí nad stejnými záznamy. • nad různými záznamy připouští paralelnost.
32
PARALELNÍ PROCESY V DATABÁZÍCH Princip základního plánovače s ČR: plánovač eviduje pro každý objekt A databáze dvě čísla: • největší ČR, které měla operace READ(A), již provedená nad objektem A, označíme jej R/ČR(A) • největší ČR, které měla operace WRITE(A) provedená nad A, označíme jej W/ČR(A). Když plánovač obdrží požadavek s ČR na čtení objektu A, provede: je-li ČR < W/ČR(A) pak odmítne požadavek a zruší transakci, která požadavek zaslala, jinak vyhoví požadavku a aktualizuje hodnotu R/ČR(A) = max( ČR, R/ČR(A) ) Když plánovač obdrží požadavek s nějakým ČR na zápis objektu A, provede: je-li ČR < W/ČR(A) or ČR < R/ČR(A) pak odmítne požadavek a zruší transakci, která požadavek zaslala, jinak vyhoví požadavku a aktualizuje hodnotu W/ČR(A) = ČR • •
Zrušené transakce se znovu spustí s novou (vyšší) hodnotou ČR. Plánovač způsobuje časté rušení transakcí - existují modifikace nebo jiné strategie plánovačů, které snižují počet zrušení transakcí. 33
PARALELNÍ PROCESY V DATABÁZÍCH Příklad na časová razítka Transakce T1 a T2 provádějí čtení a zápis údajů v tomto pořadí: T1 T2 . 1. read (A) 2. read (B) 4.exe 3. write (B) 4. read (B) 5. write (A) 6. write (B) Postup přidělování časových razítek: R/ČR(A)
W/ČR(A)
R/ČR(B)
W/ČR(B)
0
0
0
0
T1: read(A)
ČR=1 R/ČR(A)=0 → 1
1
0
0
0
T2: read(B)
ČR=2 R/ČR(B)=0 → 2
1
0
2
0
T2:write(B)
W/ČR(B)=0 → 2
1
0
2
2
T1: read(B)
R/ČR(B)=0
X 34
PARALELNÍ PROCESY V DATABÁZÍCH Příklad: V IS Banka je definována databáze účtů a nad ní se provádějí tyto transakce: – – – – – –
Převod z účtu na jiný účet Vklady na účet Výběry z účtu Platby inkasa Platby za vedení účtu Připisování úroků
účet
suma
… účet A
1000
… účet B
3000
… účet C
2000
U které z následujících dvojic transakcí může dojít k uváznutí? 1. Pan A platí 100.- panu B, pan B vybírá 200.2. Panu A je připisován úrok, pan B platí panu A. 3. Pan B vrací panu A, pan A platí panu B. 4. Pan A platí panu B, pan B platí panu C. 5. Všem jsou připisovány úroky, pan A platí panu B. 35
PARALELNÍ PROCESY V DATABÁZÍCH Příklad: IS odborných lékařů eviduje lékaře, pacienty, objednávky a návštěvy pacientů (diagnóza a vykon se doplní při návštěvě, cena je pro pojišťovnu, ucto je logická hodnota = zaúčtováno pojišťovně). Lekar (RC_L, jmeno_L, spec) Pacient (RC_P, jmeno_P, pojistovna) Navsteva (id_navst, RC_L, RC_P, datum, hodina, diagnoza, id_vykon, ucto) Cisel_vykonu (id_vykon, cena)
U které z následujících dvojic transakcí může dojít k uváznutí? 1. Lékař A objednává pana X, lékař B objednává pana Y 2. Lékař B objednává pana Z, pan X ruší objednávku u lékaře A 3. Správce DB zapisuje nového lékaře F, pan U se objednává k lékaři A 4. Správce pořizuje měsíční seznam výkonů podle lékařů pro pojišťovnu, lékař A zapisuje informace o návštěvě pana X 5. Panu X provádí správce změnu pojišťovny, lékař B zapisuje panu X výsledek návštěvy 36
