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:
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:
Also folgt als Regel für Einzelaktion mit Zeitstempel
bei Zugriff auf Item mit Lesestempel
und Schreibstempel
:
if (X = read) and (t)
führe X aus und setze:= max{t
, t}
if (X = write) and (t) and (t
) then
führe X aus und setze t:= t
if (X = write) and () then tue nichts
else(X = read and
) or (X = write and
![]()
setze Transaktion zurück
Tabelle 13.14 und 13.15 zeigen zwei Beispiele für die Synchronisation von Transaktionen mit dem Zeitstempelverfahren.
![]() |
![]() |
||
Stempel 150 | 160 | Item a hat ![]() |
|
1.) | read(a) | ||
![]() |
|||
2.) | read(a) | ||
![]() |
|||
3.) | a := a - 1 | ||
4.) | a := a - 1 | ||
5.) | write(a) | ok, da
![]() ![]() |
|
![]() |
|||
6.) | write(a) | ![]() |
|
![]() |
Tabelle 13.14: Beispiel für Zeitstempelverfahren
In Tabelle 13.14
wird in Schritt 6 die Transaktion zurückgesetzt, da ihr Zeitstempel
kleiner ist als der Lesestempel des zu überschreibenden
Items a
. In Tabelle 13.15 wird in Schritt 6 die
Transaktion
zurückgesetzt, da ihr
Zeitstempel kleiner ist als der Lesestempel von Item c
.
In Schritt 7 wird der Schreibbefehl von Transaktion
ignoriert, da der Zeitstempel von
kleiner ist als der
Schreibstempel des zu beschreibenden Items a
.
T![]() |
T![]() |
T![]() |
a | b | c | |
200 | 150 | 175 | t![]() |
t![]() |
t![]() |
|
t![]() |
t![]() |
t![]() |
||||
1.) | read(b) | t![]() |
||||
2.) | read(a) | t![]() |
||||
3.) | read(c) | t![]() |
||||
4.) | write(b) | t![]() |
||||
5.) | write(a) | t![]() |
||||
6.) | write(c) | |||||
Abbruch | ||||||
7.) | write(a) | |||||
ignoriert |
Tabelle 13.15: Beispiel für Zeitstempelverfahren