Előadáshoz
kapcsolódó
elméleti feladatok a
"zöldkönyvből" Feladatok
konkurenciavezérlésre és
holtpontkezelésre
Feladatok - Molina-Ullman-Widom:
Adatbázisrendszerek
megvalósítása
Tk. "9. Konkurenciavezérlés"
és "10.3.
Holtpontkezelés" fejezetei alapján,
az alapfogalmak, definíciók ismerete
szükséges a feladatok
megoldásához. Segédanyag:Kiss
Attila - Adatbázisok 2 előadások
>> konkurencia.ppt
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?
c.) Hányféle különböző
ütemezése van két
tranzakciónak,
ha az egyik n db, a másik
pedig k db műveletből áll?
Molina-Ullman 9.2.
fejezete: Konfliktus sorosíthatóság -- Alapfogalmak: ekvivalens
ütemezés, konfliktus (conflict),
konfliktus-sorosítható
ütemezés (conflict-serializable schedule),
megelőzési gráf (precedence
graph) 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 nem soros, de
sorosítható valamint
nem sorosítható
ü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.) A fenti 8 művelet ütemezései
közül hány darab konfliktusekvivalens
a (T1,T2) soros sorrenddel?
b.) A 8 művelet hány darab
ütemezése ekvivalens a (T2,T1) soros
sorrenddel?
9.2.3 Feladat
Adjuk meg a konfliktus-sorosítható
ü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-sorosítható-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);
9.2.6 Feladat (Szorgalmi HF+)
Adjunk meg tetszőleges n-re egy olyan ütemezést,
amelynek megelőzési
gráfja tartalmaz n
hosszúságú kört, de nem
tartalmaz rövidebb kört.
Molina-Ullman 9.3.
fejezete: A sorosíthatóság
biztosítása
zárakkal -- Alapfogalmak:
tranzakciók konzisztenciája (consistency of
transactions),
az ütemezések
jogszerűsége (legality of schedules),
kétfázisú
zárolás (2PL) 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?
c.) Adjunk példát egy olyan tranzakcióra, amely nem kétfázisú.
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 és kétfázisú
zárolású legyen
b) konzisztens de nem kétfázisú
zárolású legyen
c) nem konzisztens,
de kétfázisú
zárolású legyen
d) se nem konzisztens, se nem
kétfázisú
zárolású legyen
További feladatok
Adjuk meg az alábbi ütemezésekre, hogy
jogszerűek-e,
valamint a bennük
szereplő tranzakciókról,hogy melyek konzisztensek
illetve
kétfázisúak.
a) l1(A); w1(A); l1(B); u1(A); l2(A); w2(A); u2(A); r1(B); l2(C);
w2(C); u2(C); u1(B)
b) l1(A); w1(A); u1(A); l2(A); w2(A); l1(B); u2(A); r1(B); l2(C);
w2(C); u2(C); u1(B)
c) l1(A); w1(A); l2(A); w2(A); l1(B); u1(a); u2(A); r1(B); l2(C);
w2(C); u2(C); u1(B)
Molina-Ullman
10.3. fejezete:
Holtpontkezelés -- Alapfogalmak: holtpont (deadlock),
várakozási gráf (waits-for graph) 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 a (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!
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); ...
A II.ZH-RA EDDIG KELL
ÁTNÉZNI A FELADATOKAT INNEN
A II.ZH UTÁN (az utolsó gyakorlaton folytatjuk)
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
sorosítható.
b) Adjunk meg egy olyan írási műveletet ide,
amely
esetén az ütemezés nem
sorosítható.
További feladatok Rajzoljuk fel a
következő ütemezéshez
tartozó várakozási gráfot a
10. lépés után
rl1(A); wl2(B); wl3(C); wl3(D); rl1(B); wl4(C); rl2(D); rl4(A); rl1(D);
u3(D); ...
Vissza
az AB2
gyakorlat oldalára
Vissza
a Kezdőlapra