Xem mẫu
- Tóm tắt
Kỹ thuật khóa
- Kỹ thuật khóa (Locking)
Gồm
Khóa 2 giai đoạn
Khóa đọc viết
Khóa đa hạt
Nghi thức cây
- Kỹ thuật khóa
Qui tắc
Giao tác đúng đắn
Ti : … l(A) … r(A) / w(A) … u(A) …
Lịch thao tác hợp lệ
S: … li(A) ……………… ui(A) …
không có lj(A)
- Kỹ thuật khóa 2 giai đoạn
(2PL: 2 phase lock)
Qui tắc
Giao tác 2PL
S: … li(A) ………………… ui(A) …
không có unlock không có lock
Thực hiện xong hết tất cả các yêu cầu lock rồi mới tiến hành unlock
- Kỹ thuật khóa 2 giai đoạn
Định l{
S thỏa qui tắc (1), (2), (3) S khả tuần tự
- Kỹ thuật khóa đọc viết
Qui tắc
Giao tác đúng đắn
Ti : … rl(A) … r(A) … u(A) …
Ti : … wl(A) … w(A) … u(A) …
- Kỹ thuật khóa đọc viết
Qui tắc
Lịch thao tác hợp lệ
S: … rli(A) ……………… ui(A) …
không có wlj(A)
S: … wli(A) ……………… ui(A) …
không có wlj(A)
không có rlj(A)
- Kỹ thuật khóa đọc viết
Qui tắc
Giao tác 2PL
• Ngoại trừ trường hợp nâng cấp khóa, các trường hợp
còn lại đều giống với nghi thức khóa
• Nâng cấp xin nhiều khóa hơn
S: … rli(A) … wli(A) ……………… ui(A) …
không có unlock không có lock
• Nâng cấp giải phóng khóa đọc
S: … rli(A) … uli(A) … wli(A) ………… ui(A) …
vẫn chấp nhận trong pha lock
- Kỹ thuật khóa đọc viết
Định l{
S thỏa qui tắc (1), (2), (3) S khả tuần tự
- Kỹ thuật khóa đa hạt
Gồm các khóa
Khóa thông thường
• Shared lock: S
• Exclusive lock: X
Khóa cảnh báo (warning lock)
• Warning (intention to) shared lock: IS
• Warning (intention to) exclusive lock: IX
IX IS
R1 R1
IX
IS
B1 B2 B3 B1 B2 B3
t1 t2 t3 t1 t2 t3 S
X
- Kỹ thuật khóa đa hạt
(1) Thỏa ma trận tương thích
(2) Khóa nút gốc của cây trước
(3) Nút Q có thể được khóa bởi Ti bằng S hay
IS khi cha(Q) đã bị khóa bởi Ti bằng IX hay IS
(4) Nút Q có thể được khóa bởi Ti bằng X hay
IX khi cha(Q) đã bị khóa bởi Ti bằng IX
(5) Ti thỏa 2PL
(6) Ti có thể giải phóng nút Q khi không có nút
con nào của Q bị khóa bởi Ti
- Nghi thức cây
Qui tắc
(1) Giao tác Ti có thể phát ra khóa đầu tiên ở bất kz nút
nào
(2) Nút Q sẽ được khóa bởi Ti khi cha(Q) cũng được khóa
bởi Ti
(3) Các nút có thể được giải phóng khóa bất cứ lúc nào
(4) Sau khi Ti giải phóng khóa trên Q, Ti không được khóa
trên Q nữa
- Tóm tắt
Kỹ thuật nhãn thời gian
- Kỹ thuật nhãn thời gian
(Timestamps)
Gồm
Nhãn thời gian toàn phần
Nhãn thời gian riêng phần
Nhãn thời gian nhiều phiên bản
Chiến lược cơ bản
Nếu ST(Ti) < ST(Tj) thì lịch thao tác được phát sinh
phải tương đương với lịch biểu tuần tự {Ti, Tj}
- Nhãn thời gian toàn phần
Read(T, X) Write(T, X)
If TS(X)
- Nhãn thời gian riêng phần
If WT(X)
- Nhãn thời gian nhiều phiên bản
i=“số thứ tự phiên bản sau cùng nhất của A”
While WT(Xi) > TS(T)
Read(T, X) i:=i-1; //lùi lại
Read(Xi);
RT(Xi):= max(RT(Xi), TS(T));
i=“số thứ tự phiên bản sau cùng nhất của A”
While WT(Xi) > TS(T)
i:=i-1; //lùi lại
If RT(Xi) > TS(T)
Rollback T //Hủy và khởi tạo TS mới
Write(T, X) Else
Tạo và chèn thêm phiên bản Ai+1;
Write(Xi+1);
RT(Xi+1) = 0;//chưa có ai đọc
WT(Xi+1) = TS(T);
nguon tai.lieu . vn
