Konkurencia-kezelés összefoglalás --------------------------------- Az ütemezés egy vagy több tranzakció által végrehajtott lényeges műveletek sorozata. A lényeges műveletek az olvasási, írási és lokális értékadási műveletek. Soros ütemezés Egy ütemezés soros, ha a műveletei először egy tranzakció összes műveletét tartalmazzák, majd egy másik tranzakció összes műveletét, és így tovább. A műveletek összefésülése nem megengedett. Sorbarendezhető ütemezés Azt mondjuk, hogy egy S ütemezés sorbarendezhető, ha létezik olyan S' soros ütemezés, amelyre igaz, hogy tetszőleges kezdeti adatbázisállapotra S és S'-nek az adatbázisra vonatkozó hatása megegyezik. Vagyis minden adatelemnek ugyanaz lesz az ütemezés végén az értéke. A továbbiakban nem foglalkozunk lokális értékadási műveletekkel, csak olvasási és írási műveletekkel. 1. Egy művelet Ri(X) vagy Wi(X) alakú kifejezés, ami azt jelenti, hogy a Ti tranzakció olvassa vagy írja az X adatbáziselemet. 2. A Ti tranzakció i alsó indexű műveletek sorozatából áll. 3. Egy {Ti} tranzakcióhalmaz S ütemezése egy olyan műveletsorozat, amelyben minden {Ti}-beli Ti tranzakcióra igaz, hogy a Ti műveletei ugyanabban a sorrendben jelennek meg S-ben, mint ahogyan azok Ti definíciójában szerepelnek. Azt mondjuk, hogy S az őt alkotó tranzakciók műveleteinek összefésülése. Lásd a konfliktusok definícióját: Tankönyv (UW_sorbarendezhetoseg.docx) Konfliktusekvivalens ütemezések Két ütemezést konfliktusekvivalensnek mondunk, ha szomszédos műveletek nem konfliktusos cseréjével egyiket a másikká át lehet alakítani. Konfliktus-sorbarendezhető ütemezés Egy ütemezést konfliktus-sorbarendezhetőnek nevezünk, ha konfliktusekvivalens egy soros ütemezéssel. Adott egy S ütemezés, amely a T1 és T2 tranzakciókat tartalmazza, esetleg más tranzakciók mellett. Azt mondjuk, hogy T1 megelőzi T2-t az S ütemezésben, jelölése T1 Tj), ha Ti b él esetén az a csomópont megelőzi a b csomópontot a topológikus sorrendben. Zárak Egészítsük ki a tranzakciók műveleteit zárolási és zárfeloldási műveletekkel: li(X): A Ti tranzakció zárolást kér az X adatbáziselemre. ui(X): A Ti tranzakció feloldja (unlock) a zárolását az X adatbáziselemen. A tranzakciók konzisztenciája: A műveleteknek és a zárolásoknak az elvárt módon kell egymás után következniük: 1. Egy tranzakció csak akkor olvashat vagy írhat egy elemet, ha korábban már megkapta zárolást az adott elemre, és még nem oldotta fel a zárolást. 2. Ha egy tranzakció zárol egy elemet, akkor később fel kell oldania az elem zárolását. A tranzakciók konzisztencia feltétele másképpen megfogalmazva: Ha egy Ti tranzakciónak van egy Ri(X) vagy Wi(X) művelete, akkor kell lennie egy korábbi li(X) műveletének közbeeső ui(X) művelet nélkül, és kell lennie egy későbbi ui(X) műveletének. Ütemezések jogszerűsége: Két tranzakció nem zárolhatja ugyanazt az elemet anélkül, hogy az egyik először feloldotta volna a zárolást. Az ütemezések jogszerűsége másképpen megfogalmazva: Ha egy ütemezésben szerepel egy li(X) művelet, amelyet lj(X) követ, akkor ezen műveletek között valahol kell lennie egy ui(X) műveletnek. A zároláson alapuló ütemező feladata, hogy akkor és csak akkor engedélyezze a zárkéréseket, ha a kérés jogszerű ütemezést eredményez. Ha egy kérést nem engedélyeznek, a kérő tranzakció várakozik; megvárja, amíg az ütemező később engedélyezi a kérését. Az ütemezőnek van egy zárolási táblázata, amely minden adatbáziselemre megadja, hogy azt melyik tranzakció zárolja jelenleg (ha van ilyen). Kétfázisú zárolás (2PL) Egy tranzakciót kétfázisú-zárolásúnak nevezünk, ha a tranzakció összes zárolási művelete megelőzi a tranzakció összes zárfeloldási műveletét. Az első fázisban szerepelnek a zárolások, a második fázisban pedig zárfeloldások. Konzisztens 2PL tranzakciók jogszerű ütemezése Bármely konzisztens, kétfázisú zárolású tranzakciókból álló jogszerű S ütemezés átalakítható konfliktus-ekvivalens soros ütemezéssé. (Vagyis az ilyen ütemezés konfliktus-sorbarendezhető.) Holtpont Még kétfázisú zárolású tranzakciók esetén is előfordulhat holtpont, amikor az ütemező több tranzakciót is arra kényszerít, hogy örökké várjon egy másik tranzakció által birtokolt zárra. Várakozási gráf A várakozási gráfban minden olyan tranzakcióhoz tartozik egy csomópont amely jelenleg zárolást tart fenn, vagy egy zárolásra vár. A T csomóponttól (tranzakciótól) az U csomópontig akkor vezet irányított él (T -> U), ha van olyan A adatbáziselem, amelyre igazak a következők: 1. U zárolást tart fenn A-n, 2. T zárolásra vár A-n, és 3. T nem kaphatja meg a zárat A-n a kívánt módban, amíg U először fel nem oldja a zárolását A-n. Ha nincs kör a várakozási gráfban, akkor minden tranzakció be tud fejeződni valamikor. Ha viszont van kör, akkor a körben szereplő tranzakciók egyike sem tud továbblépni, így holtpont keletkezik. Zárolási rendszerek több zárolási móddal Megosztott zárolás: sli(X) --> Ti zárolja X-et megosztott módban (shared lock) Kizárólagos zárolás: xli(X) --> Ti zárolja X-et kizárólagos módban (exclusive lock) A tranzakciók konzisztenciája: Egy tranzakció nem írhat kizárólagos zárolás nélkül, és nem olvashat valamilyen zárolás nélkül. Tranzakciók kétfázisú zárolása: A zárolásoknak meg kell előzniük a zárfeloldásokat. Ütemezések jogszerűsége: Egy elemet kizárólagos módban egy tranzakció zárolhat, vagy megosztott módban több tranzakció, de ezek egyszerre nem fordulhatnak elő.