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 
   

Molina-Ullman 9.1. fejezete: Soros és sorosítható ütemezések
-- Alapfogalmak: ütemezés (schedule), soros ütemezés (serial schedule),
    sorba rendezhető, vagyis sorosítható ütemezés (serializable schedule)
   
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!
 
a) r1(A); r2(B); w1(C); r3(D); r4(E); w3(B); w2(C); w4(A); w1(D);
b) r1(A); r2(B); r3(C); w1(B); w2(C); w3(D);
c) r1(A); r2(B); r3(C); w1(B); w2(C); w3(A);
d) r1(A); r2(B); w1(C); w2(D); r3(C); w1(B); w4(D); w2(A);  
   
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árfelol­dá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 min­den í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