Előadáshoz
kapcsolódó
elméleti feladatok a
"zöldkönyvből" Feladatok
konkurenciavezérlésre I.
Feladatok - Molina-Ullman-Widom:
Adatbázisrendszerek
megvalósítása
a "zöld könyv" 9.1.-9.4.
Konkurenciavezérlés
és 10.3. Holtpontkezelés fejezetei alapján. Segédanyagok:Kiss
Attila - Adatbázisok 2 előadások
>> konkurencia.ppt
Molina-Ullman 9.1. fejezete: Soros és
sorolható ütemezések 9.1.2 Feladat
(ehhez
hasonló)
Adott az alábbi három tranzakció.
Adjuk meg az X adatbáziselem lehetséges
értékeit a tranzakciók
lefutása után, feltéve, hogy a
tranzakciók ütemezése soros,
és X kezdeti értéke 100.
T1: READ(X,t); t:=t+100; WRITE(X,t);
T2: READ(X,t); t:=t*2; WRITE(X,t);
T3: READ(X,t); t:=t+10; WRITE(X,t);
a.) Hányféle soros ütemezése
van
a fenti 3 tranzakciónak?
b.) Hányféle különböző
ütemezése van a fenti 3 tranzakciónak?
9.2.1 Feladat
Adott az alábbi két
tranzakció.
T1: READ(A,t); t:=t+2; WRITE(A,t); READ(B,t); t:=t*3; WRITE(B,t);
T2: READ(B,s); s:=s*2; WRITE(B,s); READ(A,s); s:=s+3; WRITE(A,s);
a.) Igazoljuk, hogy a (T1,T2) és (T2,T1) soros
ütemezések ekvivalensek,
vagyis az adatbázison
való
hatásuk azonos. A két tranzakció
hatását
tetszőleges A=a és B=b
kezdeti
adatbázis-állapotból
vizsgáljuk meg!
b.) Adjunk példát a fenti műveletek
sorolható és nem sorolható
ütemezésére is.
9.2.2 Feladat
Az előző feladat tranzakcióiban csak az
írási és olvasási
műveleteket jelölve
a következő két tranzakciót kapjuk:
T1: R1(A); W1(A); R1(B); W1(B);
T2: R2(B); W2(B); R2(A); W2(A);
A fenti 8 művelet ütemezései
közül hány darab konfliktusekvivalens
a (T1,T2) soros sorrenddel?
9.2.3 Feladat
Adjuk meg a konfliktus-sorolható
ütemezések
számát az
alábbi tranzakciókra:
T1: R1(A); W1(A); R1(B); W1(B);
T2: R2(A); W2(A); R2(B); W2(B);
9.2.4 Feladat
Adjuk meg az alábbi ütemezések
megelőzési gráfját.
Állapítsuk meg,
hogy konfliktus-sorolható-e az ütemezés?
Ha
igen, akkor
melyek az ekvivalens soros ütemezések?
Válasszunk ki egyet
és
alakítsuk át konfliktus-mentes
cserékkel
az ütemezést a
kiválasztott soros
ütemezéssé:
a.) R1(A); R2(A); R3(B); W1(A); R2(C); R2(B); W2(B); W1(C);
b.) R1(A); R2(A); W1(B); W2(B); R1(B); R2(B); W2(C); W1(D);
c.) R1(A); R2(A); R1(B); R2(B); R3(A); R4(B); W1(A); W2(B);
Molina-Ullman 9.3. fejezete: A
sorolhatóság biztosítása
zárakkal
9.3.2 Feladat
T1: l1(A); R1(A); W1(A); l1(B); R1(B); W1(B); u1(A); u1(B);
T2: l2(B); R2(B); W2(B); l2(A); R2(A); W2(A); u2(B); u2(A);
a.) Kétfázisú-e a fenti két
tranzakció?
b.) Hány jogszerű ütemezést tudunk
készíteni a fenti tranzakciók
írási
és olvasási
műveleteiből?
9.3.4 Feladat
Tekintsük a következő, két műveletből
álló tranzakciót: r1(A), w1(B),
valamint a szükséges l1(A), u1(A), l1(B), u1(B)
zárkezelő műveleteket.
Adjuk meg, hogy a műveleteknek hányféle
lehetséges sorrendje lehet úgy,
hogy a tranzakció
a) konzisztens legyen
b) konzisztens de nem kétfázisú legyen
c) konzisztens és kétfázisú
legyen
d) kétfázisú legyen
e) se nem konzisztens, se nem
kétfázisú legyen
Molina-Ullman 9.4. fejezete: Osztott és
kizárólagos zárak
9.4.1 Feladat
A T1, T2 és T3 tranzakciók minden
alábbi
ütemezésére:
a) r1(A); r2(B); r3(C); w1(B); w2(C); w3(D);
b) r1(A); r2(B); r3(C); w1(B); w2(C); w3(A);
c) r1(A); r2(B); r3(C); r1(B); r2(C); r3(D); w1(C); w2(D); w3(E);
d) r1(A); r2(B); r3(C); r1(B); r2(C); r3(D); w1(A); w2(B); w3(C);
e) r1(A); r2(B); r3(C); r1(B); r2(C); r3(A); w1(A); w2(B); w3(C);
Végezzük el a következőket:
i) Illesszük be az osztott és a
kizárólagos
zárakat, és illesszük be a
zárak
feloldási
műveleteit! Helyezzünk osztott zárat
közvetlenül minden olyan olvasási művelet
elé,
amelyik után nem következik ugyanannak a
tranzakciónak ugyanarra az elemre való
írási művelete! Helyezzünk
kizárólagos
zárat minden más olvasási
és
írási művelet elé!
Helyezzük el minden tranzakció
végére a
szükséges
zárfeloldásokat!
ii) Adjuk meg mi történik, amikor minden
ütemezést osztott és
kizárólagos
zárakat
támogató ütemező futtat!
iii) Illesszük be az osztott és
kizárólagos
zárakat oly módon, amely lehetővé
teszi
a felminősítést. Helyezzünk osztott
zárat
minden olvasás elé, és
kizárólagos
zárat
minden írás elé, és
helyezzük el a
szükséges zárfeloldásokat a
tranzakciók végére.
iv) Adjuk meg mi történik, amikor az
iii)-ból minden
ütemezést osztott,
kizárólagos
zárakat és felminősítést
támogató ütemező futtat.
v) Illesszük be az osztott, kizárólagos
és
módosítási zárakat a
feloldási műveletekkel
együtt. Helyezzünk osztott zárat
minden
olyan
olvasási művelet elé, amelyiket
nem fogunk felminősíteni, helyezzünk
módosítási zárat minden
olyan
olvasási művelet
elé, amelyeket felminősítünk,
és
helyezzünk kizárólagos zárat
minden
írási művelet elé!
Helyezzük el a zárfeloldásokat
a
tranzakciók végére, mint rendszerint!
vi) Adjuk meg mi történik, amikor az v)-ből minden
ütemezést osztott,
kizárólagos és
módosítási zárakat
támogató
ütemező futtat!
9.4.7 Feladat
Az alábbi ütemezésből egy művelet
hiányzik a
kérdőjelek helyén:
R1(A); R2(B); ???; W1(C); W2(A);
a) Adjunk meg egy olyan olvasási műveletet ide, amely
esetén az ütemezés nem
sorolható.
b) Adjunk meg egy olyan írási műveletet ide,
amely
esetén az ütemezés nem
sorolható.
További feladatok
Rajzoljuk fel a következő ütemezéshez
tartozó várakozási gráfot a
7., és 9. lépés után.
l1(A); l2(B); l3(C); l1(D); l2(A); l3(D); l3(B); u1(A); l2(C); ...
Rajzoljuk fel a következő ütemezéshez
tartozó várakozási gráfot a
10. lépés után (S/X modell).
rl1(A); wl2(B); wl3(C); wl3(D); rl1(B); wl4(C); rl2(D); rl4(A); rl1(D);
u3(D); ...
Molina-Ullman 10.3. fejezete: Holtpontkezelés
10.3.1 Feladat
Tegyük fel, hogy az alábbi műveletsorozatokban
minden egyes
olvasás illetve
írásműveletet közvetlenül
megelőzi az osztott, illetve
kizárólagos zár
igénylése.
Tegyük fel továbbá, hogy a
zárak
feloldása rögtön a
tranzakció
utolsó művelete
után történik meg. Adjuk meg
azokat a műveleteket, amelyeknek a
végrehajtását
az ütemező megtagadja, és mondjuk meg, hogy
létrejön-e holtpont
vagy sem!
Adjuk meg, hogy hogyan alakul a műveletek
végrehajtása
során
a várakozási gráf!
Ha holtpont jön létre, akkor
szakítsuk meg (abort) az egyik
tranzakciót, és
mutassuk meg hogyan folytatódik a műveletsorozat!
Vissza az AB2
gyakorlat oldalára
Vissza
a Kezdőlapra