Optimista konkurenciavezérlés Léteznek zárolás nélküli módszerek is a tranzakciók sorba rendezhet ségének a biztosítására. − id pecsét − érvényesítés. Optimista: − feltételezik, hogy nem fordul el nem sorba rendezhet viselkedés. − ha netán mégis el fordul, akkor az optimista megközelítések egyetlen megoldása, hogy azt a tranzakciót, amelynek a viselkedése nem sorba rendezhet abortálja (visszagörgeti) és utána újraindítja. A zárolási ütemez k késleltetik a tranzakciókat.
Konkurenciavezérlés id pecsét módszerrel ütemezés alapelve: − minden tranzakcióhoz rendel egy születési dátumot, vagy id pecsétet, amely jelzi, hogy mikor is jött létre a tranzakció a többi tranzakcióhoz viszonyítva. − az id pecsét egy sorszámnak is tekinthet , amely megadja, hogy hol helyezkedik el a tranzakció a többi tranzakcióhoz viszonyítva a létrehozási id pont tekintetében: korábban létrejött tranzakció id pecsétje kisebb, kés bb létrejött tranzakció id pecsétje nagyobb. − Az id pecsét generálását a rendszeróra segítségével oldják meg vagy az ütemez egy számlálót tart karban, mely 1-el növekszik, akárhányszor egy tranzakció indul. − Jelöljük TS(T)-el a T tranzakcióhoz rendelt id pecsétet (timestamp).
− A tranzakciókezel filozófiája az id pecsét módszer esetén: a különböz tranzakciókhoz tartozó egymással konfliktusban álló m veletek esetén a m veletek végrehatási sorrendje feleljen meg a tranzakciók id pecsét sorrendjének. azon m veleteknek kell el bb végrehajtódniuk, amelyek id pecsétje kisebb. ha a tranzakciókezel a végrehajtás során olyan kísérletet tapasztal, hogy egy tranzakció olyan adatbáziselemet akar olvasni vagy módosítani, melyet egy fiatalabb tranzakció már egyszer módosított, akkor ezen m veletet megakadályozza, méghozzá úgy, hogy ezen id sebb tranzakciót abortálja. a visszagörgetés után újraindítja a tranzakciót, amely most egy nagyobb id pecséttel újrapróbálkozhat a m veletek végrehajtásával.
A zárolás és id pecsét alapú módszerek közötti különbségek: − a zárolásnál a lefoglalás felengedése után bármely tranzakció hozzáférhet az adatbáziselemhez, − az id pecsét módszer esetén nincs lezárás, az adatbáziselem bármikor elérhet , viszont csak azon tranzakciók férhetnek hozzá, melyek fiatalabbak, mint az utolsó foglalást végz tranzakció. − a zárolás hátránya, hogy sokat várakoztat, és holtpont léphet fel, − az id pecsét hátránya, hogy túlságosan könnyen kerülhet abortálásra egy tranzakció. − az id pecséten alapuló módszer akkor jobb, ha sok tranzakció csak olvasási. − az id pecsét esetén nincs várakozás, de hibák léphetnek fel, mivel nem azt figyeli, hogy az adatbáziselem feldolgozás alatt áll-e vagy sem, hanem csak az utolsó hozzáférést végz tranzakció id pecsétjét figyeli.
Az id pecsét sorrenden alapuló ütemezés esetén a m ködés alapelve: − tudnunk kell, mely tranzakció használta az egyes adatbáziselemet utoljára, ezért nyilván kell tartani az utolsó hozzáféréseket. − az ütemez ezen jelz és az új igénnyel fellép tranzakció id pecsétjének összehasonlítása alapján dönti el, hogy engedélyezi-e az adatbáziselemhez való hozzáférést, vagy abortálnia kell az igényl tranzakciót. − külön nyilván kell tartani mind az olvasásra, mind az írásra, hogy mely id pecsét tranzakció volt az utolsó engedélyezett m velet igényl je. Ezen jelz knek egyre növeked értékeket kell tartalmazniuk.
Minden X adatbáziselemhez két id pecsétet társítanak, és egy bitet. 1. RT(X), az X olvasási ideje (read time), mely a legnagyobb id bélyegz , ami ahhoz a tranzakcióhoz tartozik, mely utoljára olvasta az X adatbáziselemet. 2. WT(X), az X írási ideje (write time), mely a legnagyobb id bélyegz , ami ahhoz a tranzakcióhoz tartozik, mely utoljára írta az X adatbáziselemet. 3. C(X), az X véglegesítési bitje (commit bit), melynek értéke akkor 1, ha a legújabb tranzakció, amely az X-et írta, már véglegesítve van. Ennek a bitnek az a célja, hogy elkerüljük azt a helyzetet, amelyben egy T tranzakció egy másik U tranzakció által írt adatokat olvas be és utána az U-t abortáljuk. (piszkos adat olvasása).
Az id pecséten alapuló ütemezés esetén felmerül problémák: a) Túl kés i olvasás: − egy T tranzakció megpróbálja olvasni az X adatbáziselemet, − de az X írási ideje nagyobb, mint a T id pecsétje, vagyis WT(X) > TS(T), − azt jelenti, egy fiatalabb tranzakció már módosította az X-et. − legyen U a tranzakció, mely módosította az X-et. − mivel U-t T után indítottuk, T az U által írt értéket olvasná, viszont Tnek azt az értéket kellett volna olvasnia, mely U módosítása el tt volt, ez viszont már nem ismert, ezért T-t az ütemez visszagörgeti.
b) Túl kés i írás: − T tranzakció megpróbálja írni az X adatbáziselemet, − az X olvasási ideje azt mutatja, hogy egy másik tranzakció, mely a T által beírt értéket kellett volna olvasnia, mivel fiatalabb a T-nél, már beolvasta az X értékét, még miel tt T-nek sikerült volna írni az X-et: TS(T) < RT(X). c) Piszkos adat olvasás: A T tranzakció olvassa az X adatbáziselemet, melyet utoljára az U tranzakció írt (TS(U) < TS(T)) és nem is lenne semmi baj, ha U-t nem pörgetné vissza valamilyen hiba miatt a rendszer. − ajánlott a T olvasását akkorra halasztani, mikor U véglegesítve van − a véglegesítési bit segítségével oldja meg az ütemez a feladatot.
Az id pecséten alapuló ütemezés szabályai: Legyen egy T tranzakció, mely olvasási vagy írási kéréssel fordul az ütemez höz. Az ütemez választásai a következ k lehetnek: – Engedélyezi a kérést. – Visszagörgeti T-t, ha az id pecsétje megsérti a szabályokat és egy új id bélyegz vel újraindítja. – Késlelteti T-t és kés bb dönti el, hogy abortálja-e vagy engedélyezi Tt.
Az abortálások számának csökkentésére számos elgondolás született, mindenik alapja a tranzakciók konkurenciájának a csökkentése. Egyik megoldás: − az ütemez létrehoz egy várakozó listát, a végrehajtásra jelentkez m veletekkel − a várakozó m veletek végrehajtása során a bejegyzett m veletek közül mindig a legkisebb sorszámú m veletet veszi sorra. − biztosítható a m veletek soros végrehajtása, mert egy T tranzakció els m velete csak akkor kerülhet végrehajtásra, ha a rendszerben már nem létezik nála kisebb id pecséttel rendelkez és még futó tranzakció. − ha a tranzakció megkapta a vezérlést, nem engedi el, míg maga be nem fejez dik, − a kés bb keletkez tranzakciók mindig egyre növekv id pecsétet, azaz sorszámot kapnak. De így már ez a módszer esetén is megjelenik a várakozás.
Szabályok, melyet az id pecséten alapuló ütemez betart: 1. Legyen rT(X) az ütemez höz érkez kérés. a) Ha TS(T) ≥ WT(X) az olvasás megvalósítható. Ha C(X) = 1 az ütemez engedélyezi a kérést. ha TS(T) > RT (X), akkor RT(X) : = TS(T) különben RT(X) nem változik. különben késlelteti T-t, amíg C(X) értéke 1 lesz vagy az X-et író tranzakció abortál. b) különben az olvasás fizikailag nem megvalósítható. − az ütemez T-t visszagörgeti, − majd újraindítja nagyobb id pecséttel.
2. Ha az ütemez höz érkez kérés wT(X), a) Ha TS(T) ≥ RT(X) és TS(T) ≥ WT(X), − az írás fizikailag megvalósítható. − X új értékét beírjuk. − WT(X) := TS(T). − C(X) := 0. b) Ha TS(T) ≥ RT(X) és TS(T) < WT(X), − az írás fizikailag megvalósítható, − de X-nek már egy kés bbi értéke van. Ha C(X) = 1, X el z írását végz tranzakció véglegesítve van, − T írását egyszer en figyelmen kívül hagyjuk − (egy fiatalabb tranzakció által írt érték a helyes), − az ütemez engedi, hogy T folytatódjon. különben késlelteti T-t addig, amíg C(X) értéke 1 lesz vagy az X-et író tranzakció abortál.
c) Ha TS(T) < RT(X), − az írás fizikailag nem megvalósítható − az ütemez T-t visszagörgeti. 3. Legyen az ütemez höz érkez kérés T véglegesítése. – Az ütemez a karbantartási listája alapján megkeresi az összes olyan X adatbáziselemet, amelybe T írt és a C(X)-et 1-re állítja. – Az ütemez egy másik listájában megkeresi azon tranzakciókat, melyek a T által írt X adatbáziselemek véglegesítésére vártak, ezeknek megengedi, hogy folytatódjanak. 4. Legyen az ütemez höz érkez kérés a T visszagörgetése. (1-es és 2-es esetben is el fordult). − Minden olyan tranzakcióra, amely T tranzakció írásaira várakozott, az ütemez meg kell ismételje azok írási vagy olvasási kísérleteit.
példa: T1 15 r1(Z); w1(Z);
T2 20 r2(Y); w2(X); rollback
T3 25
r3(X);
w3(Z);
X RT = 0 WT = 0 RT = 25
Y RT = 0 WT = 0 RT = 20
Z RT = 0 WT = 0 RT = 15 WT = 15 WT = 25
w1(Z) végrehajtható, TS(T1) = RT(Z) és TS(T1) ≥ WT(Z), (2.a.) w2(X): TS(T2) < RT(X), az írás nem megvalósítható, (2.c) w3(Z) : TS(T3) > RT(Z) és TS(T3) > WT(Z), az írás megvalósítható. A kereskedelmi rendszerek egy kompromisszumot alkalmaznak a zárolás és id pecséten alapuló módszer között. − lehet séget adnak a felhasználónak, hogy a tranzakciót csak olvasásinak (READ ONLY) vagy olvasási/írási tranzakciónak deklarálja. − a csak olvasási tranzakciókat az id pecséten alapuló módszerrel hatják végre, − az olvasási/írási tranzakciók esetén pedig a kétfázisú zárolást alkalmazzák és a csak olvasási tranzakciók el l is lezárják az olvasási/írási tranzakciók által használt adatbáziselemeket.
Módszerek a konkurenciavezérlésre: mindegyiknek vannak el nyei.
zárolás
és
id bélyegz ,
tár felhasználása: − mindegyik az összes aktív tranzakciók által hozzáfért adatbáziselemek számának az összegével arányos megközelít leg. − az id bélyegzés kicsit több helyet használ, mivel nyomon kell kövessék a korábban véglegesített tranzakciók bizonyos hozzáféréseit.
késleltetés nélkül fejez dnek-e be a tranzakciók: − egy módszer hatékonysága attól függ, hogy a tranzakciók közötti egymásra hatás er s vagy gyenge, vagyis milyen valószín séggel akar egy tranzakció hozzáférni olyan elemhez, amelyhez egy konkurens tranzakció már hozzáfért. − a zárolás késlelteti a tranzakciókat, azonban elkerüli a visszagörgetéseket, még ha er s is az egymásra hatás. − az id bélyez nem késlelteti a tranzakciókat, azonban visszagörgetést okozhat, amely a késleltetésnek egy problémásabb formája és még er forrásokat is pazarol. − ha gyenge a tranzakciók közötti egymásra hatás, akkor az id bélyegzés, nem okoz sok visszagörgetést és el nyösebb lehet a zárolásnál.
