05 - Sisqlhlp - Ispitni Zadaci Transakcije

BAZE PODATAKA 1 – TRANSAKCIJE Zadatak: Dat je redosled izvršavanja transakcija T1, T2, T3, i T4, kao na Slici. Vreme

T1

t01

Read(F)

t02

F := F - 1

t03

Write(F)

T2

T3

T4

t04

Read(B)

t05

B := B - 1

t06

Write(B)

t07

Read(B)

t08

B := B + 1

t09

Write (B)

t10

Read(D)

t11

D := D / 5

t12

Read(C)

t13

C := D * 2

t14

Write(C)

t15

Write(D)

t16

Read(F)

t17

F := F - 1

t18

Write(F)

t19

Commit

t20

Read(E)

t21

E := E - 1

t22

Write(E)

t23

Commit

t24

Read(A)

t25

A := A + B

t26

Write(A)

t27

Commit

t28

Read(D)

t29

D := D / 3

t30

Write(D)

t31

Commit

Za oporavak od kvara se koristi mehanizam Prateće stranice. Podaci A, B, C, D, E, i F nalaze se na različitim stranicama na disku (podatak A u stranici 1,..., D u stranici 4,..., F u stranici 6). a.) Prikazati izgled relevantnih delova sistema u trenutku neposredno posle Commit operacija transakcija T2 i T4, i u trenutku kvara, neposredno posle trenutka t31? Koje operacije mehanizam Prateće Stranice vrši posle popravke sistema u cilju vraćanja baze u konzistentno stanje?

Rešenje a.) Prvo određujemo sve moguće serijalizovane redoslede, imamo sledeća ograničenja: – – –

T1 prethodi T4 po podatku F. T4 prethodi T2 po podatku B. T3 prethodi T1 po podatku D.

Kada nacrtamo graf serijalizovanosti koji je u ovom slučaju veoma jednostavan vidimo da nema ciklusa, pa postoji bar jedan serijalizovani redosled. U ovom slučaju postoji samo jedan i to: T3 -> T1 -> T4 -> T2. T1 T4 T2 T1

67

01

A

6

T1

02

B

28

03

C

2

T4

7 12

04

D

7

89

05

E

8

T2

06

F

4 11

07

F1

4

T3

3 10

08

B1

3

09

B2

10

C1

11

D1

12

F2

Tabela Tekućih Stranica

Tabela Pratećih Stranica

13 14 15 Operativna Memorija

Izgled relevantnih delova sistema posle izvršavanja operacije T4 commits T4 pokušava da izvrši commit operaciju, međutim, to nije moguće jer se pre nje u serijskom redosledu dolaze T1 i T3. Tako da ova transakcija čeka da transakcije T1 i T3 izvrše commit, pa tek onda izvršava svoju commit operaciju. Zbog ovoga se TTS transakcije T4 ne prepisuje u odgovarajuću TPS. Kada bi se kvar desio u ovom trenutku odgovarajući oporavak bi izgledao ovako: TTS(T1) = TPS(T1) TTS(T3) = TPS(T3) Restart {T1, T2, T3, T4}. Kod transakcija T2 i T4 se ne vrši prepisivanje iz TPS u TTS, jer njihove TTS pokazuju na bar jednu ne konzistentnu stranicu. Stranica je konzistentna, ako je početna, ili ako je nastala kao posledica upisa commit-ovane transakcije.

T1 T4 T2 T3

67

01

A

6

T1

02

B

28

03

C

2

T4

7 12

04

D

7

89

05

E

8

1 14

06

F

1

4 11

07

F1

11 4

3 10

08

B1

10 3

5 13

09

B2

13 5

10

C1

11

D1

12

F2

13

E1

14

A1

Tabela Tekućih Stranica

T2 T3

Tabela Pratećih Stranica

15 Operativna Memorija

Izgled relevantnih delova sistema posle izvršavanja operacije T2 commits U trenutku t23 transakcija T3 izvršava commit operaciju, i ona se bez smetnji izvršava (jer T3 ne “čeka” ni jednu drugu transakciju). Posledica ovoga je prepisivanja U trenutku t27 transakcija T2 pokušava da izvrši commit operaciju, međutim to joj ne uspeva, jer commit nisu još odradile transakcije T1 i T4. Iz sličnog razloga ni commit operacija transakcije T4 koja je još pre inicirane ne može da se izvrši (jer T1 commits, još nije izvršeno). U slučaju da se kvar desio u trenutku t27 odgovarajući oporavak bi izgledao ovako: TTS(T1) = TPS(T1) Restart {T1, T2, T4}

T1 T4 T2 T3

67

01

A

76

11 15

02

B

15 11

28

03

C

82

7 12

04

D

12 7

89

05

E

98

1 14

06

F

14 1

4 11

07

F1

11 4

3 10

08

B1

10 3

5 13

09

B2

13 5

10

C1

11

D1

12

F2

13

E1

14

A1

15

D2

Tabela Tekućih Stranica

T1 T4 T2 T3

Tabela Pratećih Stranica

Operativna Memorija

Izgled relevantnih delova sistema posle izvršavanja operacije T1 commits U trenutku t31 pokuša se operacija T1 commits. To uspeva jer je jedina transakcija koja joj u serijskom redosledu prethodi T3 već izvršila commit. Sada je ispunjen uslov da se i T4 izvrši, a zatim i T2. Posledica ovoga je da transakcije T1, T4 i T2 prepisuju svoje TTS u TPS. Ukoliko se kvar desi u trenutku t31, nećemo preduzimati nikakve operacije oporavka jer je stanje konzistentno. Međutim, moramo razmatrati još jednu mogućnost, pošto se commit operacija transakcije T1 inicirala neposredno pre kvara moguće je da nije stigla da se izvrši iako je na to imala pravo. Prethodna slika prikazuje konačno stanje sistema pod uslovom da je transakcija T1 stigla da se izvrši. Ukoliko T1 nije stigla da se izvrši onda ne bi stigle da se izvrše transakcije T4 i T2 koje slede. Dakle ne bi bila izvršena ni prepisivanja iz TTS u TPS za T1, T4 i T2. Odgovarajući oporavak od kvara bi bio: Restart {T1, T2, T4} Ne vrše se nikakva prepisivanja iz TPS u TTS jer TPS svih transakcija T1, T2 i T4 prikazuju na nekonzistentne podatke.

b.) Da li bi se nešto promenilo, ako se promenljive nalaze u istoj stranici na disku? Prikazati izgled relevantnih delova sistema u trenutku kvara? Koje operacije mehanizam Prateće stranice vrši posle popravke sistema u cilju vraćanja sistema u konzistentno stanje. Rešenje b.) Pod ovakvim uslovima se situacija dosta komplikuje, naime pošto se sada svi podaci nalaze na istoj stranici, tada: T1 prethodi transakcijama: T4, T2, T3. T4 prethodi transakcijama: T2, T3, T1. T2 prethodi transakcijama: T3, T4, T1. T3 prethodi transakcijama: T4, T2, T1. Npr. Ako T1 upiše F, a zatim T2 upiše B, to znači da T1 prethodi T2, jer se F i B nalaze na istoj stranici. Dakle relaciju “prethodi” posmatramo identično kao u slučaju pod a, međutim ovde gledamo kao da postoji samo jedna promenjljiva nad kojom transakcije vrše Read, Write i modifikacije. Jasno je da ovde ne postoji serijalizovan redosled, tako da u principu ni ne treba razmatrati situaciju. Međutim posmatrajmo ishod bez obzira na to. T1

1 2 10

01

A, B, C, D, E, F

1

T1

T4

237

02

A, B, C, D, E, F1

2

T4

T2

349

03

A, B1, C, D, E, F1

3

T2

T3

4568

04

A, B2, C, D, E, F1

05

A, B2, C1, D, E, F1

06

A, B2, C1, D1, E, F1

07

A, B1, C, D, E, F2

08

A, B2, C1, D1, E1, F1

09

A1, B2, C, D, E, F1

10

A, B, C, D1, E, F1

Tabela Tekućih Stranica

4 T3 Tabela Pratećih Stranica

Operativna Memorija

Stanje relevantnih delova sistema neposredno pre izvršavanja T1 commits. Pretpostavimo prvo da operacija T1 commits nije stigla da se izvrši, tada je stanje sistema kao na prethodnoj slici, i u cilju oporavka se vrši: TTS(T1) = TPS(T1) Restart {T1, T2, T3, T4} Prepisivanja iz TPS u TPS se vrše samo kod T1, jer samo njena TPS pokazuje na konzistentno stanje.

Pretpostavimo sada drugi slučaj, to jest da je T1 stigla da se commit-uje. To u principu nije moguće jer postoje ciklične zavisnosti (npr. T1 commits čeka T4 commits, a T4 commits čeka T1 commits). Ali pošto su u ovom slučaju sve transakcije inicirale commit operaciju, pretpostavimo da sistem na neki način obezbedi da se te commit operacije izvrše na kraju nekim redosledom, tako da dobijamo sledeći izgled sistema. T1

1 2 10

01

A, B, C, D, E, F

10 1

T1

T4

237

02

A, B, C, D, E, F1

72

T4

T2

349

03

A, B1, C, D, E, F1

93

T2

T3

4568

04

A, B2, C, D, E, F1

05

A, B2, C1, D, E, F1

06

A, B2, C1, D1, E, F1

07

A, B1, C, D, E, F2

08

A, B2, C1, D1, E1, F1

09

A1, B2, C, D, E, F1

10

A, B, C, D1, E, F1

Tabela Tekućih Stranica

8 4 T3 Tabela Pratećih Stranica

Operativna Memorija

Konačan izgled sistema. Dakle, izvršena su odgovarajuća prepisivanja iz TTS u TPS, kako bi se dobilo novo stanje. Međutim ovime nismo dobili ništa jer se sada baza nalazi u nekom kvazi-konzistentnom stanju, jer su sve transakcije završene, sve vrednosti upisane, ali problem je to što sada imamo netačne podatke upisane u TPS. Naravno nikakav oporavak od kvara nije potrebno vršiti u ovom slučaju, s obzirom da su se sve transakcije uspešno commit-ovale.

c.) Ako se koristi mehanizam Sistemskog Dnevnika sa Neodloženim Upisom dati izgled sistemskog dnevnika i operacije koje zadaje posle popravke sistema, u cilju vraćanja baze podataka u konzistentno stanje: c1.) Ako je kvar nastao neposredno posle trenutka t25, c2.) Ako je kvar nastao neposredno posle trenutka t31? Rešenje c1.) Napomena: u sistemski dnevnik upisujemo <Ti commits> čak i ako Ti nije izvršena u tom trenutku već čeka izvršavanje nekih drugih transakcija koje joj prethode u serijalizovanom redosledu. U trenutku kvara status transakcija je sledeći: T3 je delimično izvršena. T1, T2, T4 su aktivne. Napomena: u zadacima sa sistemskim dnevnikom se radi jednostavnosti ne traži provera da li je neka transakcija stigla da izvrši commit (kao kod prateće stranice), već se uvek pretpostavlja da je stigla da se izvrši. U cilju oporavka od kvara preduzimamo sledeće mere: Undo(T2) Undo(T4) Undo(T1) Redo(T3) Restart {T1, T2, T4} Rešenje c2.)

(--> povlači izvršavanje T4 commits i T2 commits). Stanje transakcija u ovom trenutku je: T1, T2, T3, T4 su delimično izvršene. Dakle kao postupak oporavka od kvara je potrebno odraditi sledeću rutinu: Redo(T3) Redo(T1) Redo(T4) Redo(T2)

d.) Kako će izgledati transakcije ako se uvede mehanizam zaključavanja po dvofaznom protokolu. Da li će u tom slučaju redosled izvršavanja izgledati kao na slici? Dati mogući redosled izvršavanja polazeći od datog redosleda. Rešenje d.) Prvo određujemo pravilan redosled zaključavanja po dvofaznom protokolu unutar svake transakcije (lokalno). Vodimo računa naravno o osnovnim principima zaključavanja po dvofaznom protokolu, kao i tome da podatkle zaključavamo što je ranije moguće, a otključavamo što je kasnije moguće. T1

T2

T3

T4

Lock(F)

Lock(B)

Lock(D)

Lock(B)

Read(F)

Read(B)

Read(D)

Read(B)

Write(F)

Write(B)

Lock(C)

Write(B)

Lock(D)

Lock(A)

Read(C)

Lock(F)

Unlock(F)

Read(A)

Write(C)

Unlock(B)

Read(D)

Write(A)

Write(D)

Read(F)

Write(D)

Unlock(B)

Lock(E)

Write(F)

Unlock(D)

Unlock(A)

Unlock(D)

Unlock(F)

Commit

Commit

Unlock(C)

Commit

Read(E) Write(E) Unlock(E) Commit

Sada trebamo nekako da uklopimo ove redoslede, tako da protokol dvofaznog zaključavanja bude zadovoljen globalno, na nivou svih transakcija. Ukoliko u nekom koraku zatražimo naredbom Lock(X) kontrolu nad nekim podatkom X, tada osenčimo taj red u tabeli, jer je došlo do blokiranja. Zatim prekidamo izvršavanje trenutne instrukcije, i nastavljamo je čim taj podatak zbog koga je došlo do blokade bude ponovo dostupan (to jest otključan). Vreme

T1

t01

Lock(F)

t02

Read(F)

t03

Write(F)

t04

Lock(D)

t05

Unlock(F)

T2

T3

T4

t06

Lock(B)

t07

Read(B)

t08

Write(B)

t09

Lock(F)

t10

Unlock(B)

t11

Lock(B)

t12

Read(B)

t13

Write(B)

t14

Lock(A)

t15

Lock(D)

t16

Read(F)

t17

Write(F)

t18

Unlock(F)

t19

Commit

t20

Read(A)

t21

Write(A)

t22

Unlock(B)

t23

Unlock(A)

t24

Commit

t25

Read(D)

t26

Write(D)

t27

Unlock(D) (!!!)

t28

Read(D)

t29

Lock(C)

t30

Read(C)

t31

Write(C)

t32

Write(D)

t33

Lock(E)

t34

Unlock(D)

t35

Unlock(C)

t36

Read(E)

t37

Write(E)

Vreme

T1

T2

T3

t38

Unlock(E)

t39

Commit

t40

T4

Commit

Dakle, u trenutku t15, transakcija T3 traži lock nad podatkom D, međutim ovaj podatak je već zaključan, tako da dolazi do blokade transakcije T3, i ona prestaje sa izvršavanjam, sve dok se podatak D ponovo ne od ključa. To se događa u trenutku t27, tako da odmah u trenutku t28 transakcija T3 nastavlja sa radom. Kada se ona završi kontrola se ponovo vraća transakciji T1, i ona se commit-uje. Zadaci urađeni u ovom dokumentu su rešeni dosta detaljnije nego što se to traži na ispitu, radi lakšeg razumevanja. Nadam se da nema grešaka, ako ima javite mi na e-mail.