PA152 Notes 10 1

CS 245: Database System Principles

Notes 10: More TP

Hector Garcia-MolinaPavel Rychlý

PA152 Notes 10 2

Další oblasti souběžného zpracování• kaskádový rollback, obnovitelný

rozvrh• uváznutí

– prevence– detekce

PA152 Notes 10 3

Příklad: Tj Ti

Wj(A) ri(A) Commit Ti

Abort Tj

Řízení souběžného zpracování a obnova

……

… ……

… Kaskádový rollback (raději ne!)

PA152 Notes 10 4

• Rozvrh je konfliktně serializovatelný

• Tj Ti

• ale ne obnovitelný

PA152 Notes 10 5

• Pro každou transakci potřebujeme dělat konečné rozhodnutí:– commit - systém zajistí, že transakce

je nebo bude dokončena– abort - systém zajistí, že transakce je

nebo bude zrušena (nebude mít žádný efekt)

PA152 Notes 10 6

Přidáme další dvě akce:• Ci - commit Ti• Ai - abort Ti

PA152 Notes 10 7

......

......

Zpět k příkladu:

Tj Ti

Wj(A)ri(A)

Ci může být tady commit?

PA152 Notes 10 8

DefiniceTi čte z Tj v S (Tj S Ti) pokud

(1) wj(A) <S ri(A)

(2) aj <S ri(A) (< : není před)(3) If wj(A) <S wk(A) <S ri(A) then

ak <S ri(A)

PA152 Notes 10 9

Definice

Rozvrh S je obnovitelný pokudkdykoliv Tj S Ti a j i a Ci Stak Cj <S Ci

PA152 Notes 10 10

Poznámka: v transakcích jsou čtení i zápisy před commit nebo abort

If Ci Ti, then ri(A) < Ci wi(A) < Ci

If Ai Ti, then ri(A) < Ai wi(A) < Ai

• a navíc právě jedna akce Ci nebo Ai na transakci

PA152 Notes 10 11

Jak zajistit obnovitelné rozvrhy?

PA152 Notes 10 12

striktní 2PL: zámky pro zápis držíme až do commit Tj Ti

Wj(A)

Cjuj(A)

ri(A)

......

...

......

......

PA152 Notes 10 13

Kontroly (validation) beze změny!

PA152 Notes 10 14

• S je obnovitelný pokud má každá transakce commit až po dokončení (commit) všech transakcí, ze kterých čte.

• S zamezuje kaskádovému rollback pokud každá transakce čte hodnoty pouze dokončených transakcí.

PA152 Notes 10 15

• Rozvrh S je striktní pokud každá transakce čte a zapisuje hodnoty pouze dokončených transakcí.

Avoids cascading rollback

RC

ACR

ST SERIAL

PA152 Notes 10 16

Příklady• Obnovitelný:

– w1(A) w1(B) w2(A) r2(B) c1 c2

• Zamezuje kaskádovému Rollback:– w1(A) w1(B) w2(A) c1 r2(B) c2

• Striktní:– w1(A) w1(B) c1 w2(A) r2(B) c2

Předpokl. w2(A) dělámebez čtení

PA152 Notes 10 17

Uváznutí (Deadlocks)• detekce

– graf čekání• prevence

– upořádání zdrojů– časový limit– čekej-zemři– Wound-wait

PA152 Notes 10 18

Detekce uváznutí• vytváříme (inkrementálně nebo

opakovaně) graf čekání• používáme zámky• pokud najdeme cyklus, rollback viníka

T1

T3

T2

T6

T5

T4T7

PA152 Notes 10 19

Uspořádání zdrojů

• uspořádáme všechny elementy A1, A2, …, An

• transakceT může zamknout Ai po Aj pouze pokud i > j

Problém : žádosti o zámky jsou nepřirozené

PA152 Notes 10 20

Časový limit• Pokud transakce čeká více než L

sec., zrušit!

• jednoduché schéma• těžká volba L

PA152 Notes 10 21

Čekej-zemři• Transakce dostávají časovou

známku ts(Ti) při svém startu• Ti může čekat na Tj pouze pokud ts(Ti)< ts(Tj)

jinak umírá (je zrušena)

PA152 Notes 10 22

T1(ts =10)

T2(ts =20)

T3 (ts =25)

wait

wait

Příklad:

wait?

PA152 Notes 10 23

T1(ts =22)

T2(ts =20)

T3 (ts =25)

wait(A)

Druhý příklad:

žádá A: čeká na T2 nebo T3?

Pozn.: ts mezi20 a 25.

PA152 Notes 10 24

T1(ts =22)

T2(ts =20)

T3 (ts =25)

wait(A)

Druhý příklad (pokračování):

wait(A)

Jedna možnost: T1 čeká pouze na T3.Jakmile T2 získá zámek, T1 musí zemřít!

PA152 Notes 10 25

T1(ts =22)

T2(ts =20)

T3 (ts =25)

wait(A)

Druhý příklad (pokračování):

wait(A)

wait(A)

Jiná možnost: T1 získá zámek na A až po dokončeníT2i T3, tedy T1 čeká na T2i T3 T1 umírá okamžitě!

PA152 Notes 10 26

T1(ts =22)

T2(ts =20)

T3 (ts =25)

wait(A)

Druhý příklad (pokračování):

wait(A)

wait(A)

Další možnost: T1 má být před T2, tedy T1 čeká pouze na T3; T2 tedy čeká na T3 i T1... T2 může strádat?

redundantní hrana

PA152 Notes 10 27

zraň-čekej• Transakce dostávají časovou

známku ts(Ti) při svém startu• Ti zraňuje Tj pokud ts(Ti)< ts(Tj)

jinak čeká

“zraň”: rollback na Tj a přiděl zámek pro Ti

PA152 Notes 10 28

T1(ts =25)

T2(ts =20)

T3 (ts =10)

wait

wait

Příklad:

wait

PA152 Notes 10 29

T1(ts =15)

T2(ts =20)

T3 (ts =10)

wait(A)

Druhý příklad:

requests A: wait for T2 or T3?

Pozn.: ts mezi10 a 20.

PA152 Notes 10 30

T1(ts =15)

T2(ts =20)

T3 (ts =10)

wait(A)

Druhý příklad (pokračování):

wait(A)

Jedna možnost: T1 čeká pouze na T3. Ale jakmile T2 dostane zámek, T1 čeká na T2 a zraňuje T2.

PA152 Notes 10 31

T1(ts =15)

T2(ts =20)

T3 (ts =10)

wait(A)

Druhý příklad (pokračování):

wait(A)

wait(A)

Jiná možnost: T1 získá zámek na A až po dokončeníT2i T3, tedy T1 čeká na T2i T3 T2 zraní okamžitě!

PA152 Notes 10 32

T1(ts =15)

T2(ts =20)

T3 (ts =10)

wait(A)

Druhý příklad (pokračování):

wait(A)

wait(A)

Jiná možnost: T1 má být před T2, tedy T1 čeká pouze na T3; T2 tedy čeká na T3 a T1... T2 otočen!

PA152 Notes 10 33

Uživatelské příkazy

Mnoho různých variant, obecně• Begin_work• Commit_work• Abort_work