Zeitstempelverfahren

Jede Transaktion erhält beim Eintritt ins System einen eindeutigen Zeitstempel durch die System-Uhr (bei 1 tic pro Millisecunde 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		höchster Zeitstempel, verabreicht durch eine Leseoperation
Schreibstempel		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 zu 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.

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

Tabelle 13.14: Beispiel für Zeitstempelverfahren

In Tabelle 13.14 wird in Schritt 6 die Transaktion T₁ 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₂ 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₃ ignoriert, da der Zeitstempel von T₃ kleiner ist als der Schreibstempel des zu beschreibenden Items a (175 < t_w(a) = 200).

	T1	T2	T3	a	b	c
	200	150	175	tr = 0	tr = 0	tr = 0
				tw = 0	tw = 0	tw = 0
1.)	read(b)				tr = 200
2.)		read(a)		tr = 150
3.)			read(c)			tr = 175
4.)	write(b)				tw = 200
5.)	write(a)			tw = 200
6.)		write(c)
		Abbruch
7.)			write(a)
			ignoriert

Tabelle 13.15: Beispiel für Zeitstempelverfahren