Zeitstempelverfahren

Jede Transaktion erhält beim Eintritt ins System einen eindeutigen Zeitstempel durch die System-Uhr (bei 1 tic pro Millisecunde $\Rightarrow$ 32 Bits reichen für 49 Tage). Das entstehende Schedule gilt als korrekt, falls seine Wirkung dem seriellen Schedule gemäß Eintrittszeiten entspricht.

Jede Einzelaktion drückt einem Item seinen Zeitstempel auf. D.h. jedes Item hat einen

Lesestempel	$\equiv$	höchster Zeitstempel, verabreicht durch eine Leseoperation
Schreibstempel	$\equiv$	höchster Zeitstempel, verabreicht durch eine Schreiboperation

Die gesetzten Marken sollen Verbotenes verhindern:

1. Transaktion mit Zeitstempel $t$ darf kein Item lesen mit Schreibstempel $t_w > t$
   (denn der alte Item-Wert ist weg).
2. Transaktion mit Zeitstempel $t$ darf kein Item schreiben mit Lesestempel $t_r > t$
   (denn der neue Wert kommt zu spät).

Bei Eintreten von Fall 1 und 2 muß die Transaktion zurückgesetzt werden.

Bei den beiden anderen Fällen brauchen die Transaktionen nicht zurückgesetzt zu werden:

3.

Zwei Transaktionen können dasselbe Item zu beliebigen Zeitpunkten lesen.

4.

Wenn Transaktion mit Zeitstempel $t$ ein Item beschreiben will mit Schreibstempel $t_w > t$, so wird der Schreibbefehl ignoriert.

Also folgt als Regel für Einzelaktion $X$ mit Zeitstempel $t$ bei Zugriff auf Item mit Lesestempel $t_r$ und Schreibstempel $t_w$:

if (X = read) and (t $\geq t_w$)
führe X aus und setze $t_r$ := max{t$_r$, t}
if (X = write) and (t $\geq t_r$) and (t $\geq t_w$) then
führe X aus und setze t$_w$ := t
if (X = write) and ( $t_r \leq t < t_w$) then tue nichts
else $\{$(X = read and $t < t_w$) or (X = write and $t < t_r)\}$
setze Transaktion zurück

Tabelle 13.14 und 13.15 zeigen zwei Beispiele für die Synchronisation von Transaktionen mit dem Zeitstempelverfahren.

	$T_1$	$T_2$
	Stempel 150	160	Item a hat $t_r = t_w = 0$
1.)	read(a)
	$t_r$ := 150
2.)		read(a)
		$t_r$ := 160
3.)	a := a - 1
4.)		a := a - 1
5.)		write(a)	ok, da $160 \geq t_r = 160$ und $160 \geq t_w = 0$
		$t_w := 160$
6.)	write(a)		$T_1$ wird zurückgesetzt, da
			$150 < t_r = 160$

Tabelle 13.14: Beispiel für Zeitstempelverfahren

In Tabelle 13.14 wird in Schritt 6 die Transaktion $T_1$ zurückgesetzt, da ihr Zeitstempel kleiner ist als der Lesestempel des zu überschreibenden Items a $(150 < t_r = 160)$. In Tabelle 13.15 wird in Schritt 6 die Transaktion $T_2$ zurückgesetzt, da ihr Zeitstempel kleiner ist als der Lesestempel von Item c $(150 < t_r(c) = 175)$. In Schritt 7 wird der Schreibbefehl von Transaktion $T_3$ ignoriert, da der Zeitstempel von $T_3$ kleiner ist als der Schreibstempel des zu beschreibenden Items a $(175 < t_w(a) = 200)$.

	T$_1$	T$_2$	T$_3$	a	b	c
	200	150	175	t$_r$ = 0	t$_r$ = 0	t$_r$ = 0
				t$_w$ = 0	t$_w$ = 0	t$_w$ = 0
1.)	read(b)				t$_r$ = 200
2.)		read(a)		t$_r$ = 150
3.)			read(c)			t$_r$ = 175
4.)	write(b)				t$_w$ = 200
5.)	write(a)			t$_w$ = 200
6.)		write(c)
		Abbruch
7.)			write(a)
			ignoriert

Tabelle 13.15: Beispiel für Zeitstempelverfahren