Konkurenciavezérlés

A tranzakciós lépéseket az ütemező szabályozza
- (scheduler)
A konzisztencia megtartására indított általános folyamat a konkurenciavezérlés
- (concurency control)
Amint a tranzakció I/O műveletet kér egy adatbáziselement, az ütemezőhöz megy tovább a kérés
- Gyakorta azonnal lefut, ha már be van töltve az erőforrás, különben megy tovább a kérés a pufferkezelőnek
- Egyes kérések nem biztonságosak, ha azonnal lefuttantnánk
  - Az ütemező néhány kérsét késleltet
  - ... néhány esetében a kérő tranzakciót abortálja
Az ütemezés (schedule) egy vagy több tranzakció lényeges műveleteinek sorozata
- Ahol az utasítások a saját tranzakciójukhoz mérve sorban következnek

A konkurencia szempontjából lényeges műveletek a központi memória pufferében és nem a lemezen történik

Csak a READ és WRITE műveletek sorrendje számít, az INPUT/OUTPUT utasításokkal nem foglalkozunk

Naiv példa

Maradjunk a megszokott megkötésünknél, miszerint A=B1

$T_1$	$T_2$
`READ(A,t)`	`READ(A,s)`
`t:=t+100`	`s:=s*2`
`WRITE(A,t)`	`WRITE(A,s)`
`READ(B,t)`	`READ(B,s)`
`t:=t+1000`	`s:=s*2`
`WRITE(B,t)`	`WRITE(B,s)`

Egymás után, egyenként ezek a tranzakciók megőrzik a konzisztenciát
Viszont más sorrendben indítva más eredményt kapunk

Soros ütemezés

??? title="Soros ütemezés" | $T_1$ | $T_2$ | A | B | | ------------ | ------------ | --- | --- | | READ(A,t) | | 25 | | | t:=t+100 | | | | | WRITE(A,t) | | 125 | | | READ(B,t) | | | 25 | | t:=t+1000 | | | | | WRITE(B,t) | | | 125 | | | READ(A,s) | 125 | | | | s:=s*2 | | | | | WRITE(A,s) | 250 | | | | READ(B,s) | | 125 | | | s:=s*2 | | | | | WRITE(B,s) | | 250 |

---

| $T_1$        | $T_2$        | A   | B   |
| ------------ | ------------ | --- | --- |
|              | `READ(A,s)`  | 25  |     |
|              | `s:=s*2`     |     |     |
|              | `WRITE(A,s)` | 50  |     |
|              | `READ(B,s)`  |     | 25  |
|              | `s:=s*2`     |     |     |
|              | `WRITE(B,s)` |     | 50  |
| `READ(A,t)`  |              | 50  |     |
| `t:=t+100`   |              |     |     |
| `WRITE(A,t)` |              | 150 |     |
| `READ(B,t)`  |              |     | 50  |
| `t:=t+1000`  |              |     |     |
| `WRITE(B,t)` |              |     | 150 |

> Láthatjuk, hogy mindkét soros ütemezésnél `A=B` megmaradt, mégis más a végső állapot, kinda sus, ngl

Sorbarendezhető ütemezés

??? title="Sorbarendezhető ütemezés" | $T_1$ | $T_2$ | A | B | | ------------ | ------------ | --- | --- | | READ(A,t) | | 25 | | | t:=t+100 | | | | | WRITE(A,t) | | 125 | | | | READ(A,s) | 125 | | | | s:=s*2 | | | | | WRITE(A,s) | 250 | | | READ(B,t) | | | 25 | | t:=t+1000 | | | | | WRITE(B,t) | | | 125 | | | READ(B,s) | | 125 | | | s:=s*2 | | | | | WRITE(B,s) | | 250 |

> Sorbarendezhető, de nem [soros](#soros-ütemezés), mert így `A=B=c`-ből indulva, mindkettő `2(c + 100)` lesz, ami jó

Nem Sorbarendezhető ütemezés

??? title="Nem sorbarendezhető ütemezés" | $T_1$ | $T_2$ | A | B | | ------------ | ------------ | --- | --- | | READ(A,t) | | 25 | | | t:=t+100 | | | | | WRITE(A,t) | | 125 | | | | READ(A,s) | 125 | | | | s:=s*2 | | | | | WRITE(A,s) | 250 | | | | READ(B,s) | | 25 | | | s:=s*2 | | | | | WRITE(B,s) | | 50 | | READ(B,t) | | | 50 | | t:=t+1000 | | | | | WRITE(B,t) | | | 150 |

> Nem sorbarendezhető, nem konzisztens az eredmény semmiképp, az ilyen viselkedéseket ki kell küszöbölni(!)

Pesszimista ütemező

Hogy ha az előző példában kicserélük $T_2$-ben minden s:=s*2-t s:=s*1-re, akkor elvileg sorbarendezhető lenne, right?

Az ütemező viszont csak a WRITE utasítás meglétét nézi, hiszen bonyolultabb függvényhívásról nehezebb eldönteni a helyességet, mint abortálni lol

Úgyhogy az ütemező szerint nem lesz sorbarendezhető

Jelölés

Tranzakció

Beszéltük ugye, hogy csak az írások és olvasások számítanak...

$T_1:\;r_1(A);\,w_1(A);\,r_1(B);\,w_1(B);$

$T_2:\;r_2(A);\,w_2(A);\,r_2(B);\,w_2(B);$

$T_i$ az $i$ sorszámú műveletekből állós sorozat
$r_i(X)$ - A $T_i$ tranzakció olvassa az $X$ relációt
$w_i(X)$ - A $T_i$ tranzakció írja az $X$ relációt

Ütemezés

$S:\;r_1(A);\,w_1(A);\,r_2(A);\,w_2(A);\,r_1(B);\,w_1(B);\,r_2(B);\,w_2(B);$

$S$ ütemezés olyan műveletek sorozata, melyben $T_i$ műveleteinek sorendje megmarad $S$-ben ($\forall i$)
$S$ a tranzakciók műveleteinek átlapolása (interleaving)

Konfliktus-sorbarendezhetőség

Elégséges feltétel: biztosítja egy ütemezés sorbarendezhetőségét
Erősebb feltétel a konfliktus-sorbarendezhetőség
- Az ütemezők inkább ezt szokták teljesíteni, mert jobb ig

Konfliktus/konfliktuspár

Olyan egymást követő műveletpár, aminek sorrendjének megcserélése megváltoztathatja legalább az egyik tranzakció viselkedését

Konfliktushelyzetek

Legyen $T_i$ és $T_j$ tranzakciók ($i\ne j$)

Nincs konfliktus

$r_i(X);\,r_j(Y)$
- $\forall X,Y$
- $X = Y$ is ok, mert egyik lépés sem változtatja meg az értékeket
$r_i(X);\,w_j(Y)\quad(X\ne Y)$
- $T_j$ írhatja $Y$-t, mielőtt $T_i$ olvasná $X$-et, viszont amíg nem egyeznek, nem lehet baj
$w_i(X);\,r_j(Y)\quad(X\ne Y)$
- same here
$w_i(X);\,w_j(Y)\quad(X\ne Y)$
- itt leginkább azért, mert ha egyeznének, akkor más marad bennt, melyik a jó sorrend??!

Van konfliktus

$r_i(X);\,w_i(Y)$
- Mivel egy tranzakción belül van, így sorrendjük szent és sérthetetlen
$w_i(X);\,w_j(X)$
- Megint a kérdés, melyik a jó sorrend? (csak mert nincs itt jó sorrend)
$r_i(X);\,w_j(X)$ és $w_i(X);\,r_j(X)$
- Beírhatunk új értéket azután, hogy olvasna a másik, majd ő beír valamit, akkor most kinek van igaza?

Pro tipp sorbarendezhetőségre

Nem konfliktusos cserékkel az ütemezést megpróbáljuk soros ütemezéssé átalakítani
- Ha ez működik, akkor az eredeti ütemezés is sorbarendezhető volt

Fogalmak

Konfliktusekvivalens (conflict-equivalent)

Ha szomszédos műveletek nem konfliktusos cserlinek sorozatával A alakítható B ütemezésre

Konfliktus-sorbarendezhető (conflict-serializable schedule)

Ha A konfliktusekvivalens valamelyik soros ütemezéssel

Elégséges feltétel konfliktussorbarendezhetőségre

Akkor konfliktussorbarendezhető egy A ütemezés, ha sorbarendezhető ütemezés is

Fordítva nem szükséges feltétel, de a forgalomban levő rendszerek ezt szokták vizsgálni

Példa átalakítás

\[ S:\;r_1(A);\,w_1(A);\,r_2(A);\,w_2(A);\,r_1(B);\,w_1(B);\,r_2(B);\,w_2(B); \]

\[ r_1(A);\,w_1(A);\,r_2(A);\,\overset{\circlearrowleft}{\red{w_2(A);\,r_1(B)}};\,w_1(B);\,r_2(B);\,w_2(B); $$ $$ r_1(A);\,w_1(A);\overset{\circlearrowleft}{\red{\,r_2(A);\,r_1(B)}};\,w_2(A);\,w_1(B);\,r_2(B);\,w_2(B); $$ $$ r_1(A);\,w_1(A);\,r_1(B);\,r_2(A);\overset{\circlearrowleft}{\red{\,w_2(A);\,w_1(B)}};\,r_2(B);\,w_2(B); $$ $$ r_1(A);\,w_1(A);\,r_1(A);\overset{\circlearrowleft}{\red{\,r_2(A);\,w_1(B)}};\,w_2(A);\,r_2(B);\,w_2(B); $$ $$ \green{r_1(A);\,w_1(A);\,r_1(B);\,w_1(B);\,r_2(A);\,w_2(A);\,r_2(B);\,w_2(B);} \]

Tip

Épp ezért egy előző, nem sorbarendezhető példát le tudunk írni:

\[ S:\;r_1(A);\,w_1(A);\,r_2(A);\,w_2(A);\,r_2(B);\,w_2(B);\,r_1(B);\,w_1(B); \]

Amit most már látunk, mért nem tekintjük sorbaredezhetőnek

Példa sorba, de nem konfliktus-sorba rendezhető ütemezésre

Először sima példa:

\[ S_1:\green{w_1(Y);\,w_1(X)};\, \orange{w_2(Y);\,w_2(Y)};\,\blue{w_3(X)}\; \]

egy ezzel megegyező eredménnyel bíró példa:

\[ S_2:\green{w_1(Y)};\,\orange{w_2(Y);\,w_2(Y)};\,\green{w_1(X)};\,\blue{w_3(X)}\; \]

Persze, mivel $\blue{w_3(X)}$ felülírja X-et, így $\green{w_1}$ és $\orange{w_2}$ sorrendje mindegy

Ami miatt $S_2$ sorbarendezhető

Viszont a tanult szabályokkal nem alakítható át soros ütemezéssé, ezért lesz $S_2$ sorba, de nem konfliktus-sorba rendezhető