Kỹ thuật nhãn thời gian
(Time stamp)

Kỹ thuật nhãn thời gian đơn giản
Kỹ thuật nhãn thời gian đọc / Viết
Kỹ thuật nhãn thời gian nhiều phiên bản

Kỹ thuật nhãn thời gian đơn
giản
Nguyên lý của kỹ thuật
!  Mỗi giao tác T được gán một nhãn
thời gian TS(T), ghi nhận thời điểm
phát sinh của T
!  Mỗi đơn vị dữ liệu A được gán một
nhãn thời gian TS(A) ghi nhận lại
TS(T) của giao tác T đã thao tác
thành công lên A gần nhất
Nguyên lý (tt)
!  Một giao tác T thao tác thành
công lên A nếu TS(T) >= TS(A)
!  Ngược lại thì T sẽ không được thao
tác lên A và bị hủy để thực hiện lại
với một nhãn TS(T) mới lớn hơn tất
cả các nhãn đang có
!  TS(A) > TS(T) ?

Thủ tục đọc
Procedure Read (T,A)
Begin
IF (TS(T) >= TS(A)) Then
Begin

Read(B) TS(B)=200
A:= A+10
Write(A) TS(A)=100
Read(A) TS(A)=200
B:=B+A
Write(B) TS(B)=200
Read(C) TS(C)=100
Write(c) TS(C)=200
Kỹ thuật nhãn thời gian
đọc/viết
Nguyên lý
!  Chia nhãn của đơn vị dữ liệu A
thành 2
◦  RTS(A) : Ghi nhận nhãn của giao tác
đã đọc A thành công gần nhất
◦  WTS(A): Ghi nhận nhãn của giao tác
đã viết lên A thành công gần nhất
Thủ tục đọc
Procedure Read(T,A)
Begin
IF (TS(T) >= WTS(A)) Then
Begin
Read(A);
RTS(A):= Max(TS(T),RTS(A))
End
Else
Abort T
End
Thủ tục viết
Procedure Write(T,A)

Luật Thomas
!  Nhận xét trường hợp giao tác T
muốn viết lên A, nhưng nhãn của T
như sau:
RTS(A) < TS(T)< WTS(A)
Thật sự có nên hủy T (Abort T) ?
Thuật toán viết cải tiến
Procedure Write(T,A)
Begin
IF (TS(T) >= RTS(A)) Then
IF(TS(T) >= WTS(A)) Then
Begin
Write(A);
WTS(A):= TS(T);
End
Else
Abort T
End
Nhãn thời gian nhiều phiên
bản
Nguyên lý
!  Mỗi giao tác có một nhãn thời gian
TS(T)
!  Mỗi đơn vị dữ liệu A được lưu trữ
thành nhiều phiên bản A
i
(version)
!  Mỗi phiên bản A
i
có các nhãn đọc/

Procedure Write(T,A)
Begin
i:= chỉ số của phiên bản cuối của A
While (TS(T) < WTS(A
i
))
i:=i-1;
IF(TS(T) >= RTS(Ai)) then
Begin
Write(A
i+1
);
WTS(A
i+1
):=TS(T);
RTS(A
i+1
):=0;
end
Else
Abort T
End Ví dụ
T1
TS=100
T2
TS=200
A

TS=200
A0
RTS=0
WTS=0
A1 A2 B0
RTS=0
WTS=0
B1
Read(A) RTS=100
WTS=0
Read(B) RTS=200
WTS=0
B:=B+10
Write(B) RTS=0
WTS=200
A:=A+10
Write(A) RTS=0
WTS=200
A:=A+20
Write(A) RTS=0
WTS=100
RTS=0
WTS=200