›
›

Bài giảng Hệ quản trị cơ sở dữ liệu - Chương 2: Giao tác - Điều khiển đồng thời - Phạm Thị Bạch Huệ

pdf 81 trang ngocly 30 Free
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Hệ quản trị cơ sở dữ liệu - Chương 2: Giao tác - Điều khiển đồng thời - Phạm Thị Bạch Huệ", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_he_quan_tri_co_so_du_lieu_chuong_2_giao_tac_dieu_k.pdf

Nội dung text: Bài giảng Hệ quản trị cơ sở dữ liệu - Chương 2: Giao tác - Điều khiển đồng thời - Phạm Thị Bạch Huệ

  1. Chương 2 Giao tác – điều khiển đồng thời GV: Phạm Thị Bạch Huệ Email: [email protected] 1 Nhắc lại nội dung môn học ‰ Chương I: Tổng quan về một HQT CSDL ‰ Chương II: Quản lý giao tác và truy xuất đồng thời ‰ Chương III: Phục hồi dữ liệu sau sự cố – An toàn dữ liệu ‰ Chương IV: Lưu trữ dữ liệu và các phương thức truy xuất ‰ Chương V: Xử lý và tối ưu hóa câu truy vấn 2
  2. Mục tiêu ‰ Biết xử lý công việc trên CSDL theo giao tác. ‰ Hiểu và/ hoặc vận dụng các kỹ thuật điều khiển đồng thời. 3 Nội dung 1. Dẫn nhập 2. Giao tác 3. Giao tác truy xuất đồng thời 4. Lịch thao tác 5. Điều khiển đồng thời dùng kỹ thuật khóa 6. Mức cô lập của giao tác 7. Deadlock 8. Cách sử dụng các phương thức khóa 9. Điều khiển đồng thời dùng kỹ thuật nhãn thời gian 10. Điều khiển đồng thời dùng phương pháp kiểm tra hợp lệ 4
  3. 1. DẪN NHẬP z Vì sao phải thực hiện giao tác? z Vì sao phải điều khiển đồng thời? 5 Dẫn nhập ‰ Ý tưởng giao tác để mô tả một đơn vị xử lý trongquátrìnhxửlýdữliệutrongCSDL. ‰ Nhiều người cùng thao tác trên CSDL có thể gây ra tình trạng CSDL sai Ỉ điều khiển đồng thời. 6
  4. 2. GIAO TÁC z Định nghĩa z Tính chất z Viết giao tác 7 ĐỊNH NGHĨA GIAO TÁC Giao tác là 1 tập hợp các thao tác có thứ tự truy xuất dữ liệu trên CSDL thành 1 đơn vị công việc logic (xem là 1 thao tác nguyên tố), chuyển CSDL từ trạng thái nhất quán này sang trạng thái nhất quán khác. 8
  5. GIAO TÁC ‰ Cho 2 quan hệ ¾ LOP (MALOP, TENLOP, SISO) ¾ SV (MASV, TENSV, MALOP) ‰ RBTV: SISO của 1 lớp phải bằng số sinh viên thuộc lớp đó. ‰ Hãy viết giao tác thêm 1 SV vào 1 lớp Giao tác Them_SV (v_masv, v_tensv, v_malop) Bắt đầu GT Nếu v_malop không tồn tại Rollback tran Insert into SV (v_masv,v_tensv,v_malop) Update LOP Set SoSV= SoSV + 1 Where Malop = v_malop Cuối giao tác Them_SV 9 Tính chất của giao tác: ACID ‰ Atomic – Tính nguyên tố Không thể chia nhỏ. ‰ Consistency – Tính nhất quán Chuyển CSDL từ trạng thái nhất quán này sang trạng thái nhất quán khác. ‰ Isolation – Tính cô lập Các giao tác xử lý đồng thời phải độc lập với những thay đổi của giao tác khác. ‰ Durability – Tính lâu dài, bền vững Khi giao tác hòan tất, tất cả thay đổi phải được ghi nhận chắc chắn lên CSDL. 10
  6. T-SQL đặc trưng của giao tác BEGIN TRANSACTION Bắt đầu giao tác. COMMIT Kết thúc giao tác thành TRANSACTION công. ROLLBACK Kết thúc giao tác không TRANSACTION thành công, CSDL được trả về tình trạng trước khi thực hiện giao tác. 11 Một số lưu ý ‰ Kiểm tra lỗi không có quyền, vi phạm ràng buộc, deadlock ‰ Biến tòan cục @@ERROR =0 : không lỗi, ≠ 0 : có lỗi ‰ GT Không tự rollback khi gặp lỗi trong quá trình thực hiện ‰ Cần kiểm tra giá trị biến @@ERROR sau mỗi câu lệnh thành phần và xử lý lỗi nếu có ‰ Biến @@ROWCOUNT. ‰ Lồng 32 tầng, lệnh rollback ở tầng bất kỳ làm rollback tòan bộ giao tác. 12
  7. 3. GIAO TÁC TRUY XUẤT ĐỒNG THỜI z Giới thiệu z Các vấn đề của xử lý đồng thời 13 Lý do điều khiển đồng thời ‰ Đảm bảo nhiều giao tác thực hiện đồng thời mà vẫn đảm bảo tính đúng đắn trên CSDL Transaction manager Bộ lập lịch nhận yêu cầu Yêu cầu Read/Write Read/Write từ các giao tác và điều khiển: cho thực thi Scheduler hoặc chờ hoặc hủy giao tác tùy vào kỹ thuật điều khiển đồng thời được cài đặt Reads & Writes Buffers 14
  8. Các vấn đề củaxửlý đồng thời 1. Mất dữ liệu cập nhật (Lost update) TH1: T1 T2 Begin Tran Read A Begin Tran Read A A:=A+10 Write A A:=A*100 Write A Commit Tran Commit Tran 15 Các vấn đề củaxửlý đồng thời 1. Mất dữ liệu cập nhật (Lost update) TH2: T1 T2 Begin Tran Begin Tran Write A Write A Commit Tran Commit Tran 16
  9. Các vấn đề củaxửlý đồng thời 2. Đọc dữ liệu chưa commit (Uncommit data, Dirty read) T1 T2 Begin Tran Read A A:=A+10 Write A Begin Tran Read A Print A Commit Tran Rollback Tran 17 Các vấnđềcủaxử lý đồng thời 3. Thao tác đọc không thể lặp lại (Unrepeatable data) T1 T2 Begin Tran Read A Begin Tran Read A A:=A+10 Write A Commit Tran Read A Commit Tran 18
  10. Các vấn đề củaxửlý đồng thời 4. Phantom T1 T2 Begin Tran Select * From SV Begin Tran Insert into SV values ( ) Commit Tran Select * From SV Commit Tran 19 4. LỊCH THAO TÁC z Các khái niệm: z Lịch biểu z Lịch biểu tuần tự z Lịch biểu khả tuần tự z Lịch biểu có thể phục hồi z Lịch biểu không rollback dây chuyền z Bộ lập lịch z Nghi thức 20
  11. Một số kháiniệm 1. Hoạt động của các giao dịch đồng thời được coi là đúng đắn nếu và chỉ nếu tác dụng của nó giống như tác dụng có được khi cho thực hiện chúng một cách tuần tự. 2. Lịch biểu (schedule) Đn1: Lịch biểu của một tập các giao tác là thứ tự trong đó các thao tác trong giao tác được thực hiện. Thứ tự của các thao tác trong lịch biểu phải tuân theo đúng thứ tự của chúng trong giao tác cho trước. Đn2: Một lịch biểu là một chuỗi sắp theo thời gian các hành động được thực hiện bởi một hoặc nhiều giao tác. 21 T1 T2 T1 T2 T1 T2 Read (A,t) Read (A,s) Read (A,t) Read (A,t) t:=t+100 s:=s*1 t:=t+100 Write(A,t) Write(A,s) t:=t+100 Write(A,t) Read(B,t) Read(B,s) Write(A,t) Read(A,s) t:=t+100 s:=s*1 Read(A,s) Write(B,t) Write(B,s) s:=s*1 s:=s*1 Write(A,s) Định nghĩa GT Write(A,s) Read (B,s) Read(B,t) s:=s*1 t:=t+100 Write(B,s) Write(B,t) Read(B,t) Read (B,s) t:=t+100 s:=s*1 Write(B,t) Write(B,s) Lịch biểu 1 22 Lịch biểu 2
  12. Một số khái niệm ‰ Lịch biểu được gọi là tuần tự (serial) nếu thứ tự thực hiện các thao tác trong lịch biểu là tất cả các thao tác của giao tác này rồi đến tất cả các thao tác của giao tác khác và cứ như vậy. ‰ Mọi lịch biểu tuần tự đều đảm bảo tính nhất quán cho cơ sở dữ liệu. ‰ Lịch biểu được gọi là khả tuần tự (serializable) nếu tác dụng của nó giống như tác dụng của một lịch biểu tuần tự nào đó. Tức là chúng sinh ra cùng một giá trị cho mỗi đơn vị dữ liệu. 23 Lịch biểu tuần tự T1 T2 Read (A,t) t:=t+100 Write(A,t) Read(B,t) t:=t+100 Write(B,t) Read(A,s) s:=s*1 Write(A,s) Read (B,s) s:=s*1 Write(B,s) Read(A,s) 24
  13. Lịch khả tuần tự T1 T2 A B T1 T2 A B 25 25 25 25 Read (A,t) Read (A,t) t:=t+100 t:=t+100 Write(A,t) 125 Write(A,t) 125 Read(A,s) Read(A,s) s:=s*2 s:=s*1 Write(A,s) 250 Write(A,s) 125 Read (B,s) Read (B,s) s:=s*2 s:=s*1 Write(B,s) 50 Write(B,s) 25 Read(B,t) Read(B,t) t:=t+100 t:=t+100 Write(B,t) 150 Write(B,t) 125 Lịch biểu không khả tuần tự Lịch biểu khả tuần tự nhưng không 25 phải là lịch tuần tự Lịch khả tuần tự ‰ Lịch biểu có thể là khả tuần tự do hành vi cụ thể của các giao tác trong lịch biểu. ‰ Bộ lập lịch không điều khiển đồng thời dựa vào hành vi cụ thể của từng thao tác trong giao tác. ‰ Bộ lập lịch dựa trên một nguyên tắc chung để điều khiển đồng thời. 26
  14. Ký hiệu ‰ ri (X) : giao tác Ti đọc đơn vị dữ liệu X ‰ wi (X) : giao tác Ti ghitrênđơnvịdữliệuX ‰ Giao tác Ti gồm một chuỗi các thao tác oi 27 Một số kháiniệm ‰ Lịch biểu có thể phục hồi được (Recoverable Schedule) T1 T2 T1 T2 Begin Tran Begin Tran Read A Read A Write A Write A Begin Tran Begin Tran Read A Read A Commit Read B Read B Commit Commit Commit Khi T1 có sự cố, T2 đã commit nên không thể thoát ⇒ tình trạng không thể phục hồi đúng được. 28
  15. Một số kháiniệm ‰ Lịch biểu có thể phục hồi được (Recoverable Schedule) Mọi HQT CSDL yêu cầu lịch biểu phải có thể phục hồi được. Định nghĩa: Một lịch biểu có thể phục hồi được là lịch biểu mà mọi cặp Ti, Tj, khi Tj đọc đơn vị dữ liệu vừa được ghi bởi Ti, thao tác commit của Ti xuất hiện trước thao tác commit của Tj. 29 Một số kháiniệm ‰ Lịch biểu không rollback dây chuyền (Uncascading rollback Schedule) T1 T2 T3 Khi T1 fail, phải rollback T2 và kéo Read A theo T3 phải bị rollback. Read B Write A Hiện tượng một transaction rollback, Read A dẫn đến một loạt các transaction khác phải Write A rollback gọi là Read A rollback dây chuyền (Cascading rollback). 30
  16. Một số kháiniệm ‰ Lịch biểu không rollback dây chuyền (Uncascading rollback Schedule) ‰ Định nghĩa: Lịch biểu không rollback dây chuyền là lịch biểu mà trong đó mọi cặp giao tác Ti, Tj, nếu Tj đọc đơn vị dữ liệu được viết trước đó bởi Ti, thao tác commit của Ti phải xuất hiện trước thao tác đọc của Tj. ‰ Một lịch biểu không rollback dây chuyền là lịch biểu có khả năng phục hồi được. 31 Một số khái niệm ‰Tính tương thích của 2 thao tác Định nghĩa: Hai thao tác Oi, Oj là tương thích nếu kết quả của việc thực hiện đồng thời Oi, Oj, giống như kết quả của việc thực hiện tuần tự Oi, Oj hoặc Oj, Oi Hai thao tác tương thích thì không xung đột nhau. T1 T2 T1 T2 T1 T2 Read (A) Read (A) Read (A) Read(A) Read(B) Write(B) Hai thao tác không tương thích nhau thì xung đột nhau. T1 T2 T1 T2 T1 T2 Read (A) Write(A) Write(A) Write(A) Read(A) Write(A) 32
  17. Một số khái niệm Tính khả hóan vị của 2 thao tác ‰ Định nghĩa: Hai thao tác Oi, Oj là khả hoán vị nếu kết quả của việc thực hiện Oi, Oj hay Oj, Oi là như nhau. ‰ Hai thao tác tương thích thì khả hóan vị. 33 Một số khái niệm ‰ Hai thao tác truy xuất trên cùng đơn vị dữ liệu, ma trận tương thích Read A Write A Read A 1 0 Write A 0 0 • Các thao tác truy xuất trên các đơn vị dữ liệu khác nhau thì tương thích và khả hóan vị. 34
  18. Một số khái niệm ‰ Với một lịch biểu S1 cho trước, ta có thể lặp lại việc hoán đổi vị trí của hai thao tác không xung đột liền kề, cho đến khi đạt được 1 lịch biểu tuần tự S2, nếu có thể. Khi đó, lịch biểu S1 ban đầu là lịch biểu khả tuần tự. ‰ Mọi tác động đến CSDL hoàn toàn không thay đổi khi ta thực hiện hóan đổi vị trí các thao tác không xung đột nhau. 35 Một số khái niệm ‰ Hai lịch biểu S1 và S2 là tương đương xung đột nếu ta có thể chuyển lịch biểu S1 thành lịch biểu S2 bằng một/một số các thao tác hóan đổi các thao tác không xung đột kề nhau. ‰ Một lịch biểu là khả tuần tự xung đột nếu nó tương đương xung đột với một lịch biểu tuần tự. 36
  19. Xét tính khả tuần tự của S SS’ T1 T2 T3 T4 T1 T2 T3 T4 1.Read A 1.Read A 2.Read A 3.Write B 3.Write B 2.Read A 4.Write A 4.Write A 5.Read B 5.Read B 6.Read B 7.Read A 7.Read A 8.Write C 8.Write C 6.Read B 9.Write A 9.Write A Lịch biểu S’ tương đương xung đột với S nên S là khả tuần tự xung đột Ỉ S khả tuần tự 37 Một số khái niệm ‰ Khả tuần tự xung đột là điều kiện đủ để đảm bảo tính khả tuần tự. Nghĩa là, một lịch biểu khả tuần tự xung đột là một lịch biểu khả tuần tự. ‰ Không đòi hỏi một lịch biểu phải khả tuần tự xung đột để là lịch biểu khả tuần tự, nhưng khả tuần tự xung đột là điều kiện để những bộ lập lịch trong các hệ thống thương mại bảo đảm tính khả tuần tự. 38
  20. Một số khái niệm ‰ Khả tuần tự xung đột không là điều kiện cần cho tính khả tuần tự. S1:w1(Y);w1(X);w2(Y);w2(X);w3(X) S2:w1(Y);w2(Y);w2(X);w1(X);w3(X) ‰ S1: T3 ghi X, T2 ghi Y ‰ S2: T1, T2 ghi trên X nhưng T3 ghi đè, T2 ghi Y. ‰ Hai lịch biểu trên cho giá trị trên X và Y giống nhau. ‰ S1 tuần tự ⇒ S2 khả tuần tự ⇒ nhưng không khả tuần tự xung đột do không thể chuyển S2 về 1 lịch biểu tuần tự bằng cách hóan đổi. Khả tuần tự Khả tuần tự xung đột 39 Một số khái niệm ‰ Đồ thị ưu tiên (đồ thị đụng độ) để kiểm tra một lịch biểu là khả tuần tự xung đột hay không. ¾ Input: Lịch biểu S. ¾ Output: S khả tuần tự? − Cho S là lịch biểu gồm các thao tác của 2 giao tác Ti và Tj. Ti ưu tiên hơn Tj (Ti <Tj ) nếu tồn tại cặp thao tác Oin ∈Ti, Ojm ∈Tj không khả hoán vị và Oin thực hiện trước Ojm. − Đồ thị ưu tiên có nút là các giao tác, cung có hướng đi từ nút i đến nút j nếu Ti < Tj. − Lịch biểu là khả tuần tự xung đột nếu đồ thị ưu tiên không có chu trình. − Nếu đồ thị ưu tiên có chu trình, lịch biểu là không khả tuần tự xung đột. 40
  21. Ví dụ ‰ S1:r2(A);r1(B);w2(A);r3(A);w1(B);w3(A);r2(B);w2(B) T1 T2 T3 r(A) r(B) w(A) r(A) w(B) w(A) r(B) w(B) 1 2 3 ‰ Lịch biểu đã cho khả tuần tự, tương đương với lịch tuần tự T1< T2 < T3 41 Ví dụ ‰ S:r2(A);r1(B);w2(A);r2(B);r3(A);w1(B);w3(A);w2(B) T1 T2 T3 r(A) r(B) w(A) r(B) r(A) w(B) 1 2 3 w(A) w(B) ‰ Lịch biểu đã cho không khả tuần tự xung đột. 42
  22. Một số khái niệm ‰ Khi thực hiện đồng thời các transaction phát sinh các vấn đề như: ¾ Lịch thao tác không khả tuần tự. ‰ Để giảm bớt những vấn đề này, ta có 2 công cụ: ¾ Bộ lập lịch. ¾ Nghi thức. 43 Một số khái niệm ‰ Bộ lập lịch (schedulers): sẽ tiến hành lập lịch các thao tác (thao tác sẽ được thực hiện trước, thao tác nào sẽ được thực hiện sau). ‰ Bộ lập lịch giải quyết các yêu cầu đụng độ, ép các transaction phải chờ trong trường hợp không đáp ứng được yêu cầu lock hoặc hủy bỏ các transaction. ‰ Bộ lập lịch là thành phần của hệ quản trị CSDL, có vai trò làm trọng tài phân xử các yêu cầu có xung đột. 44
  23. Một số khái niệm ‰ Nghi thức (Protocol): là một hạn chế trên chuỗi các bước nguyên tử mà một giao dịch có thể thực hiện. ¾ Ví dụ: Nghi thức giải quyết vấn đề deadlock (yêu cầu các giao tác lock các đơn vị dữ liệu theo 1 thứ tự cố định nào đó), nghi thức đảm bảo tính khả tuần tự (chiến lược lock 2 pha). 45 5. ĐIỀU KHIỂN ĐỒNG THỜI DÙNG KỸ THUẬT KHÓA ‰ Kỹ thuật khóa đơn giản: Lock (A), Unlock (A). ‰ Nghi thức khóa 2 giai đoạn (2PL). ‰ Kỹ thuật khóa Đọc/ Ghi: Rlock(A), Wlock(A), Unlock (A). ¾ Tăng cấp (upgrading). ¾ Khóa cập nhật (update lock). ¾ Khóa tăng/ giảm (increment lock) ¾ Khóa trên đvdl có kích thước khác nhau. ‰ Nghi thức khóa trên đvdl tổ chức phân cấp. 46
  24. Kỹ thuật khóa đơn giản ‰ Bộ lập lịch dùng kỹ thuật khóa yêu cầu: ¾ Phải khóa và nhả khóa ngoài việc Đọc/Ghi dữ liệu. ¾ Việc dùng khóa phải tuân theo 2 điều kiện sau: 1. Tính nhất quán của giao tác: a) Giao tác chỉ có thể đọc hoặc ghi trên đơn vị dữ liệu nếu trứơc đó có yêu cầu lock trên đơn vị dữ liệu và chưa nhả lock. b) Nếu giao tác đã lock trên đvdl thì sau đó phải unlock. 2. Tính hợp lệ của lịch biểu: – Không thể có 2 giao tác đồng thời khóa trên 1 đvdl. 47 Ký hiệu ‰ Ký hiệu: li(X): Ti yêu cầu lock trên đvdl X ui(X): Ti unlock trên trên đvdl X ‰ Ví dụ: T1 và T2 nhất quán ‰ T1: l1(A);r1(A);A:=A+100;w1(A);u1(A);l1(B);r1(B);B:=B+100; w1(B);u1(B); ‰ T2: l2(A);r2(A);A:=A*2;w2(A);u2(A);l2(B);r2(B);B:=B*2; w2(B);u2(B); 48
  25. T1 T2 A B 25 25 l1(A);r1(A); A:=A+100; w1(A);u1(A); 125 l2(A);r2(A); A:=A*2; w2(A);u2(A); 250 l2(B);r2(B); B:=B*2; w2(B);u2(B); 50 l1(B);r1(B); B:=B+100; w1(B);u1(B); 150 Lịch biểu hợp lệ, giao tác nhất quán nhưng lịch biểu không49 khả tuần tự Nghi thức khóa 2 giai đọan (Two-phase lock Protocol - 2PL) ‰ Phát biểu 2PL: Một giao tác thực hiện cơ chế khóa 2 giai đọan khi giao tác không thực hiện lock nào nữa sau khi đã unlock. Đơn vị dữ liệu giữ lock BOT EOT t Phase lock Phase unlock 50
  26. Nghi thức khóa 2 giai đoạn (tt) T1 T2 T3 T4 L(A) L(B) L(B) L(A) Read(A) Read(B) Read(B) Read(A) L(B) L(A) B=B-50 UL(A) Read(B) Read(A) Write(B) L(B) B:=B+A UL(B) UL(B) Read(B) Write(B) A:=A+B L(A) UL(B) UL(A) Write(A) Read(A) Print(A+B) UL(B) UL(A) A=A+50 Write(A) UL(A) T1, T2 thỏa nghi thức T3, T4 không thỏa nghi thức khóa 2 giai đoạn khóa 2 giai đoạn 51 2PL ‰ Ta có thể chuyển 1 lịch biểu S hợp lệ gồm các giao tác nhất quán và thoả 2PL sang 1 lịch biểu tuần tự tương đương xung đột với S. ¾ Chứng minh bằng phương pháp quy nạp. Chỉ quan tâm đến thao tác Read và Write. ¾ S: T1, T2, , Tn. Đặt Ti là giao tác unlock đầu tiên, ui(X). ¾ Ta hoàn toàn có thể chuyển tất cả các thao tác Read và Write của Ti ra đầu lịch biểu mà không gặp phải 1 thao tác xung đột nào.Thật vậy: z Xét wi(Y) nào đó của Ti. Giả sử có thao tác wj(Y) của S đi trước wi(Y): S: , wj(Y) , uj(Y), , li(Y), , wi(Y), z Vì Ti unlock đầu tiên, ui(X) phải đứng trước uj(Y): S: , wj(Y), , ui(X), , uj(Y), , li(Y), , wi(Y), hoặc S: , ui(X) , wj(Y), , uj(Y), , li(Y), , wi(Y), Ỉ Ti không thoả 2PL. ¾ S được viết lại: (các thao tác của Ti) (các thao tác của n-1 giao tác còn lại) Phần còn lại là lịch biểu hợp lệ gồm các GT nhất quán và thỏa 2PL Ỉ bằng quy nạp ta kết luận S là khả tuần tự xung đột. 52
  27. Hạn chế của PP ĐKĐT dùng khóa ‰ Livelock: tình trạng 1 giao tác chờ hoài để được làm việc trên 1 đvdl. ‰ Deadlock: tình trạng hai giao tác cứ chờ nhau mãi để được làm việc trên 1 đơn vị dữ liệu mà không có giao tác nào có thể thực hiện trước. 53 2PL: Deadlock & Rollback dây chuyền T1 T2 A B 25 25 l1(A);r1(A); l2(B);r2(B); A:=A+100; B:=B*2; w1(A); 125 w2(B); 50 l1(B); Denied l2(A); Denied ‰ Tình trạng rollback dây chuyền có thể xảy ra với lịch biểu thỏa nghi thức khóa 2 giai đoạn. 54
  28. Nghi thức khóa nghiêm ngặt (Strict locking) ‰ Khóa nghiêm ngặt: Tất cả các khóa độc quyền của 1 giao tác bất kỳ phải giữ cho đến khi giao tác commit hoặc abort, và lệnh commit/ abort phải được ghi nhật ký trên đĩa. ‰ Lịch biểu trong đó các giao tác tuân thủ cách khóa nghiêm ngặt là lịch biểu nghiêm ngặt (strict schedule). ¾ Mọi lịch biểu nghiêm ngặt là lịch biểu không rollback dây chuyền. ¾ Mọi lịch biểu nghiêm ngặt là khả tuần tự. z Vì lịch biểu nghiêm ngặt tương đương với lịch biểu tuần tự theo thứ tự mà GT commit. 55 Các biến thể của 2PL ‰ Conservative 2PL: GT phải yêu cầu khóa tất cả các mục dữ liệu cần thiết TRƯỚC khi GT bắt đầu thực hiện. ¾ Không bị deadlock, nhưng không thực tế. ‰ Strict 2PL: Sau khi GT đã commit/ abort, các khoá Ghi mới được nhả. ¾ Có thể deadlock, nhưng đảm bảo lịch biểu có thể phục hồi được. Lịch này được dùng phổ biến. ‰ Rigorous 2PL: chỉ được nhả tất cả khóa ở cuối GT. ¾ Vẫn phải giữ Read lock đến cuối GT, giảm tính đồng thời. 56
  29. Các phương thức khóa ‰ Shared lock (S) ¾ Shared Lock Ù Read Lock ¾ Khi đọc 1 đơn vị dữ liệu, SQL Server tự động thiết lập Shared Lock trên đơn vị dữ liệu đó ¾ Có thể được thiết lập trên 1 bảng, 1 trang, 1 khóa hay trên 1 dòng dữ liệu. ¾ Nhiều giao tác có thể đồng thời giữ Shared Lock trên cùng 1 đơn vị dữ liệu. ¾ Không thể thiết lập Exclusive Lock trên đơn vị dữ liệu đang có Shared Lock. ¾ Shared Lock thường được giải phóng ngay sau khi sử dụng xong dữ liệu được đọc, trừ khi có yêu cầu giữ shared lock cho đến hết giao tác. 57 Các phương thức khóa ‰ Exclusive Locks (X) ¾ Exclusive Lock Ù Write Lock ¾ Khi thực hiện thao tác ghi (insert, update, delete) trên 1 đơn vị dữ liệu, SQL Server tự động thiết lập Exclusive Lock trên đơn vị dữ liệu đó. ¾ Exclusive Lock luôn được giữ đến hết giao tác. ¾ Tại 1 thời điểm, chỉ có tối đa 1 giao tác được quyền giữ Exclusive Lock trên 1 đơn vị dữ liệu. 58
  30. Nguyên tắc khóa 1. Tính nhất quán của giao tác ¾ Thao tác đọc ri(X) phải đi sau sli(X) hoặc xli(X) mà không có thao tác ui(X) xen vào giữa. ¾ Thao tác ghi wi(X) phải đi sau xli(X) mà không có thao tác ui(X) xen vào giữa. ¾ Tất cả các lock phải được unlock trên cùng đvdl. 2. Giao tác thỏa 2PL ¾ Không có thao tác ui(Y) nào đi trước sli(X) hoặc xli(X) 3. Lịch biểu hợp lệ ¾ Nếu có thao tác xli(X) trong lịch biểu thì không thể có xlj(X) hoặc slj(X) theo sau, j ≠ i mà không có lệnh ui(X) nào ở giữa. ¾ Nếu có thao tác sli(X) trong lịch biểu thì không thể có xlj (X) theo sau, j ≠ i mà không có lệnh ui(X) ở giữa. 59 Ma trận tương thích SX Syesno Xnono Ví dụ: T1 T2 sl1(A);r1(A); sl2(A);r2(A); sl2(B);r2(B); xl1(B) denied u2(A);u2(B); xl1(B); r1(B); w1(B); u1(A);u1(B); Lịch biểu dùng Rlock và Wlock. LB khả tuần tự xung đột, tương đương xung đột với lịch tuần tự T2 < T1. 60
  31. Khoá tăng cấp ‰ Khóa tăng cấp (Upgrading lock) ¾ Shared lock: thân thiện ¾ T muốn đọc X trước, sau đó ghi X thì trước tiên khóa đọc trên X, sau đó khi muốn ghi thì nâng cấp (upgrade) khóa đọc thành khóa ghi. z Giao tác hoàn toàn có thể yêu cầu lock trên cùng một đvdl với nhiều chế độ lock khác nhau. ¾ Cách này cho phép tăng tính đồng thời. 61 Khóa tăng cấp T1 T2 sl1(A);r1(A); sl2(A);r2(A); sl2(B);r2(B); sl1(B);r1(B); xl1(B) denied u2(A);u2(B); xl1(B); w1(B); u1(A);u1(B); Nếu T1 khóa độc quyền trên B đầu tiên thì T1 và T2 không thể thực hiện được nhiều việc đồng thời. Upgrading lock giúp tăng tính đồng thời 62
  32. Khóa tăng cấp & Deadlock T1 T2 sl1(A); sl2(A); xl1(A) denied xl2(A); denied 63 Các phương thức khóa ‰ Update Lock uli(X) ¾ Update Lock sử dụng khi đọc dữ liệu với dự định ghi trở lại trên đơn vị dữ liệu này. ¾ Uli(X) chỉ cho phép giao tác Ti quyền đọc X, không cho phép Ti quyền ghi trên X. Tuy nhiên, chỉ có update lock mới có thể được nâng cấp lên thành khóa độc quyền sau đó, khóa đọc thì không thể nâng cấp. ¾ Update Lock là chế độ khóa trung gian giữa Shared Lock và Exclusive Lock. ¾ Update lock giúp tránh deadlock mà khóa tăng cấp gặp phải. ¾ Khi thực hiện thao tác ghi lên 1 đơn vị dữ liệu thì bắt buộc Update Lock phải được nâng cấp thành Exclusive Lock. ¾ Tại 1 thời điểm chỉ cho phép 1 giao tác giữ Update lock trên 1 đvdl 64
  33. Ma trận tương thích SXU SYesNoYes Cóthểcấplock U trên X khi đã có S lock trên XNoNoNo X. Nhưng khi đã có lock U trên X thì không thể UNoNoNo cấp bất cứ loại lock nào trên X, vì nếu cho phép thì lock U không bao giờ có cơ hội nâng cấp thành khóa độc quyền. 65 Ví dụ T1 T2 ul1(A), r1(A); ul2(A), Denied xl1(A), w1(A), u1(A); ul2(A), r2(A); xl2(A), w2(A), u2(A); 66
  34. Khóa tăng/giảm ‰ Increment lock ili(X) inci(X) ¾ Ý tưởng: z Hành động tăng giá trị / giảm giá trị nếu dùng khóa đọc/ ghi thì phải chờ nhau. z Thật ra chúng có thể hoán vị hoặc thực hiện đồng thời vẫn cho kết quả không thay đổi. z Thay thế read (A,t); t:=t+/-c; write(A,t); Bởi INC(A,c) để làm tăng tính đồng thời mà vẫn đảm bảo đúng đắn. 67 Bổ sung điều kiện ứng dụng khóa khi dùng khóa tăng/giảm ‰ Giao tác nhất quán GT chỉ có thể thực hiện hành động tăng giá trị X nếu nó khóa tăng trên đvdl X. Khoá tăng không cho phép đọc hoặc ghi đồng thời. ‰ Lịch biểu hợp lệ ¾ Nhiều giao tác có thể cùng khóa tăng trên X. ¾ Ma trận tương thích SXI S Yes No No X NoNoNo I No No Yes 68
  35. Ví dụ T1 T2 sl1(A), r1(A); sl2(A), r2(A); il2(B), inc2(B); il1(B), inc1(B); u2(A), u2(B); u1(A), u1(B); 69 Khóa trên các đvdl có kích thước khác nhau ‰ Ta quan tâm đến cấu trúc phân cấp của đvdl. ‰ Hệ thống khác nhau dùng các đơn vị dữ liệu có kích thước khác nhau để khóa. VD: bộ, block, relation. ‰ Có ứng dụng, có khi đvdl nhỏ sẽ có lợi, có khi đvdl lớn sẽ có lợi hơn. ‰ Ví dụ: T đọc toàn bộ quan hệ, U ghi 1 dòng của quan hệ. Khi T và U thực hiện đồng thời sẽ xảy ra tình trạng sai trên CSDL. ‰ Đvdl lớn thì hạn chế việc thực hiện đồng thời. Đvdl nhỏ thì quản lý phức tạp. 70
  36. Các tài nguyên có thể khóa Tài nguyên Giải thích Database Khóa trên toàn bộ cơ sở dữ liệu. Chỉ nên áp dụng khi tiến hành thay đổi trên lược đồ của CSDL. Table Khóa trên 1 bảngtrong cơ sở dữ liệu. Toàn bộ các đối tượng trong bảng này, bao gồm tất cả các dòng và tất cả các khóa trong các chỉ mục trong bảng, đều bị khóa. Extent Khóa trên 1 extend (= 8 trang). Page Khóa trên 1 trang. Tất cả dữ liệu và các khóa chỉ mục trong trang này đều bị khóa. Row Được đưa vào SQL Server từ version 7.0. Khóa trên 1 dòng dữ liệu trong 1 bảng. 71 Các tài nguyên có thể khóa ‰ Khi 1 đơn vị dữ liệu con bị khóa thì các đơn vị dữ liệu CSDL ở các cấp cao hơn sẽ bị khóa bằng khóa Intent tương ứng. Table Table page page row row row row row row 72
  37. Các phương thức khóa ‰ Intent Locks ¾ Không phải là 1 chế độ khóa riêng biệt mà được sử dụng kết hợp với các chế độ khóa khác: z Shared Lock => Intent Shared Lock (IS) z Update Lock => Intent Update Lock (IU) z Exclusive Lock => Intent Exclusive Lock (IX) ¾ Intent lock rất có ích khi dữ liệu được tổ chức theo cấu trúc lồng nhau hoặc cấu trúc cây. ¾ Intent Lock được SQL Server tự động thiết lập, không thể được yêu cầu thiết lập Intent Lock một cách tường minh. ¾ Khi 1 đơn vị dữ liệu thành phần bị khóa, các đơn vị dữ liệu ở cấp cao hơn cũng sẽ bị khóa bằng Intent Lock tương ứng. ¾ Mục đích: z Không cho GT khác lock đvdl cấp cao hơn khi không thể lock đvdl cấp thấp hơn. z Tăng tốc độ của hệ thống vì không cần kiểm tra lock ở tất cả các đvdl cấp con khi muốn khóa đvdl cấp cao hơn. 73 Nguyên tắc 1. Để đặt khóa S hoặc X trên 1 đvdl, phải bắt đầu tại gốc. 2. Nếu vị trí hiện tại là vị trí muốn khóa, không cần đi tiếp. Yêu cầu khóa S hoặc X tại đvdl hiện tại. 3. Nếu đvdl muốn khóa còn ở cấp dưới, thì: 1. Đặt khóa cảnh báo tại node hiện tại. 1. Nếu yêu cầu Slock thì đặt IS tại node hiện tại. 2. Nếu yêu cầu Xlock thì đặt IX tại node hiện tại. 2. Đi tiếp theo hướng đến được đvdl cần tìm (theo cây con chứa đvdl cần khóa). 4. Lặp lại bước 2 và 3. 74
  38. Các phương thức khóa ‰ Intent Locks CSDL IXLock Table Table page page IXLock row row row row row row XLock 75 Ma trận tương thích IS IX S X IS Yes Yes Yes No IX Yes Yes No No S Yes No Yes No X NoNoNoNo 76
  39. Khóa trên đvdl có kích thước khác nhau ‰ Có HQT áp dụng kỹ thuật khóa trên kích thước đvdl động. ¾ HQT CSDL hỗ trợ nhiều kích thước đvdl khác nhau. VD: record, page, file, ¾ Kích thước đvdl được dùng cho giao tác thay đổi tự động để phù hợp với giao tác. ¾ Có thể tự động nâng cấp khóa từ đvdl là record thành page thành file nếu giao tác đang khóa trên một số phần trăm (khá lớn) nào đó các record hoặc page của file. 77 Kiểm tra tính khả tuần tự ‰ Với lịch biểu có Rlock và Wlock ‰ Input: LB S gồm T1, T2, , Tk ‰ Output: S cókhảtuầntựhay không 1. Nếu Ti Rlock trên đvdl X, tiếp theo Tj yêu cầu Xlock trên X, thì có cung Ti Ỉ Tj. 2. Ti khóa Xlock trên X, Tj yêu cầu Xlock trên X, có cung từ TiỈTj. 3. Tm là GT giữ Slock trên X sau khi Ti nhả khóa độc quyền trên X, nhưng trước khi Tj khóa Xlock trên X, (nếu không có Tj thì Tm là giao tác yêu cầu Slock trên X sau khi Ti nhả khóa trên X), thì có cung từ Ti đến Tm. 4. Nếu đồ thị có chu trình thì S không khả tuần tự. Ngược lại thì S khả tuần tự và có thể tìm được lịch tuần tự tương đương. 78
  40. Kỹ thuật khóa Đọc / Viết T1 T2 RL(A) Read(A) UL(A) RL(B) B1 T1 T2 Read(B) UL(B) B2 T1 G WL(A) T2 Read(A) A:=A+B B3 G có chu trình => S không Write(A) khả tuần tự UL(A) WL(B) Read(B) B:=B+A Write(B) UL(B) 79 Nghi thức khóa phân cấp ‰ Dùng cho dữ liệu có cấu trúc cây. ¾ VD: B-tree. ‰ Đvdl phù hợp để khoá là node. ‰ Dùng 2PL không phù hợp, vì tất cả đều bắt đầu từ root, và chỉ cho phép 1 giao tác không phải là chỉ đọc truy cập cây tại 1 thời điểm. 80
  41. Nghi thức khoá phân cấp 1. GT có thể bắt đầu khoá tại node bất kỳ của cây. 2. Mục X chỉ có thể bị khóa bởi Ti nếu Ti đã khoá node cha của X trước đó. 3. Có thể nhả khóa trên 1 node bất cứ lúc nào. 4. GT không thể nhả lock trên 1 node rồi lock trở lại node đó, ngay cả khi vẫn còn khóa ở node cha. ‰ Lịch biểu hợp lệ gồm các GT nhất quán và tuân theo nghi thức khóa phân cấp trên thì khả tuần tự. ‰ Lịch tuần tự tương đương: Ti< Tj nếu trong S, GT Ti và Tj khóa cùng 1 node và Ti khóa node đó trước. 81 T1 T2 T3 Ví dụ l1(A), r1(A); l1(B), r1(B); l1(C), r1(C) w1(A), u1(A); l1(D), r1(D) w1(B), u1(B) l2(B), r2(B); A l3(E), r3(E); w1(D), u1(D); BCw1(C), u1(C); l2(E), DE l3(F), r3(F) w3(F), u3(F); l3(G), r3(G) w3(E), u3(E); FG l2(E), r2(E) w3(G), u3(G); w2(B), u2(B); w2(E), u2(E); 82
  42. Kiến trúc bộ lập lịch dùng phương thức khóa ‰ Bản thân giao tác không tự yêu cầu khóa. Việc chèn thao tác khoá vào trước các thao tác Đọc/ Ghi là công việc của Bộ lập lịch. ¾ Bộ lập lịch nhận yêu cầu read, write, commit hay abort từ giao tác. ¾ Bộ lập lịch lưu thông tin về việc quản lý khóa trong lock table. ‰ Giao tác không tự nhả khóa. Bộ lập lịch nhả khóa khi bộ quản lý giao tác (Transaction Manager - TM) báo cho Bộ lập lịch biết giao tác đãõ commit hay abort. 83 Kiến trúc bộ lập lịch dùng phương thức khóa Các giao tác Read (A); Write (B); Commit(T); Scheduler, Phần I Lock Lock (A); Read (A); table Scheduler, Phần II Read (A); Write (B); 84
  43. Nguyên tắc cấp khóa 1. Phần I Chọn phương thức lock phù hợp để chèn vào trước các thao tác Read, Write, Increment, update. Có những phương thức khóa nào là tùy thuộc vào HQT CSDL. 2. Phần II Nhận output của Phần I và thi hành: ‰ T delayed: vì chưa được đáp ứng yêu cầu lock, sẽ chèn các thao tác của giao tác đó vào hàng chờ. ‰ T not delayed: yêu cầu lock được đáp ứng: ¾ Nếu là thao tác truy cập CSDL thì được HQT thực hiện. ¾ Nếu là thao tác lock, Bộ lập lịch kiểm tra lock table xem có thể cấp lock không. z Nếu được, cho phép lock và cập nhật lock table với lock vừa cấp. z Nếu không, thêm 1 mục vào lock table, T delayed, cho đến khi lock được cấp. 3. Khi T commit hoặc abort, TM báo cho Phần I biết và nhả tất cả các lock giữ bởi T. Nếu có GT nào đang chờ những lock này, Phần I sẽ báo cho Phần II biết. 4. Khi nhận thông báo về các khóa trên X đã nhả từ Phần I, Phần 2 cấp khóa cho T đang chờ trên X, T thi hành tiếp cho đến khi thi hành xong hoặc tiếp tục chờ vì khóa chưa thể được đáp ứng. 85 Bảng quản lý khóa (Lock table) Element Info Group mode: U Waiting: Yes A List Tran Mode Wait? Tnext Next T1 S No T2 U no T3 X yes 86
  44. Bảng quản lý khóa ‰ ĐN: là một quan hệ lưu thông tin về 1 đơn vị dữ liệu và thông tin các khóa đang yêu cầu trên đvdl đó. ‰ Group mode: chứa khóa nghiêm ngặt nhất trong các khóa đang yêu cầu trên A. Căn cứ vào khóa này để grant/ deny yêu cầu khóa trên A. Với mô hình Shared-Exclusive-Update thì group mode sẽ là: ¾ S nếu chỉ có một/ một số shared lock đang được giữ. ¾ U nếu có 1 update lock và có thể có shared lock. ¾ X nếu có 1 exclusive lock và không có lock nào khác. ‰ Waiting bit: cho biết có ít nhất 1 GT đang chờ lock trên A. ‰ List: các GT đang giữ lock trên A hoặc chờ lock trên A: ¾ Tên GT đang giữ lock hoặc đang chờ. ¾ Mode của lock. ¾ Tình trạng là đang giữ lock hay đang chờ lock. 87 Quản lý yêu cầu lock ‰ T yêu cầu lock A: Nếu chưa có mục A trên lock table Tạo 1 mục mới và yêu cầu được đáp ứng. Ngược lại Dùng thông tin group mode để quyết định cấp lock hay không. Nếu không xung đột thì cấp, nếu xung đột sẽ denied và thêm vào list tên giao tác T, kiểu lock, và Wait? = ‘Yes’ ‰ Quản lý unlock ¾ T unlock A: z Xóa T trong danh sách liên quan đến A. z Cập nhật lại Group mode cho phù hợp. z Cấp một/ một số lock cho các GT chờ – First-come-first-served: no starvation. – Priority to shared lock: cấp tất cả các shared lock đang chờ, sau đó mới đến update lock (nếu có). Chỉ cấp exclusive lock nếu không có T nào chờ với mode khác. Có starvation, khi chờ U hoặc X lock. – Priority to updating: ưu tiên các GT giữ Ulock và đang chờ Xlock. 88
  45. 6. MỨC CÔ LẬP CỦA GIAO TÁC 89 Các mức độ cô lập (Isolation levels) ‰ Mức độ cô lập của 1 giao tác quy định mức độ nhạy cảm của 1 giao tác đối với những sự thay đổi trên CSDL do các giao tác khác tạo ra. ‰ Mức độ cô lập của giao tác quy định cách thức lock và thời gian giữ lock trên đơn vị dữ liệu mà giao tác có truy cập. ‰ Các mức độ cô lập được SQL Server hỗ trợ: ¾ Read Uncommitted. ¾ Read Committed (default). ¾ Repeatable Read. ¾ Serializable. 90
  46. Các mức cô lập ‰ Mỗi transaction đều làm việc ở 1 trong 4 mức độ cô lập nêu trên. ‰ Lệnh T-SQL thiết lập mức độ cô lập: ‰ SET TRANSACTION ISOLATION LEVEL 91 Read Uncommitted Không thiết lập Shared Lock trên những đơn vị dữ liệu cần đọc, thiết lập Exclusive lock khi ghi. Không bị ảnh hưởng bởi những lock của các giao tác khác trên những đơn vị dữ liệu cần đọc. Không phải chờ khi đọc dữ liệu (kể cả khi dữ liệu đang bị lock bởi giao tác khác). Ưu điểm: Tốc độ xử lý rất nhanh. Không cản trở những giao tác khác thực hiện ddoc dữ liệu. Khuyết điểm: Các vấn đề gặp phải khi xử lý đồng thời: Dirty Reads, Unrepeatable Read, Phantoms. Nhận xét: Chỉ nên dùng để đọc dữ liệu trong trường hợp cần dữ liệu tổng quan về CSDL, ví dụ như tạo những báo cáo về tình hình chung. Không dùng khi cần đọc những số liệu chính xác. 92
  47. Read Committed Là MCL mặc định của SQL Server Tạo Shared Lock trên đvdl được đọc, Shared Lock được giải phóng ngay sau khi đọc xong dữ liệu => Giải quyết vấn đề Dirty Reads Tạo Exclusive Lock trên đvdl được ghi, và giữ cho đến hết giao tác Ưu điểm: Giải quyết vấn đề Lost update, Dirty Reads Shared Lock được giải phóng ngay, không cần phải giữ cho đến hết giao tác nên không ngăn cản thao tác cập nhật của các giao tác khác. Khuyết điểm: Chưa giải quyết được vấn đề Unrepeatable Reads, Phantoms Phải chờ khi chưa thể được đáp ứng yêu cầu lock trên đơn vị dữ liệu đang bị giữ lock bởi giao tác khác. 93 Repeatable Read Repeatable Read = Read Committed+ Giải quyết Unrepeatable Reads Tạo Shared Lock trên đvdl được đọc, Shared Lock được giữ cho đến hết giao tác => Không cho phép các giao tác khác cập nhật trên đvdl này. Tạo Exclusive Lock trên đvdl được ghi, Exclusive Lock được giữ chođếnhếtgiaotác. Ưu điểm: Giải quyết vấn đề lost update, dirty Read và Unrepeatable Read Khuyết điểm: Chưa giải quyết được vấn đề Phantom. Phải chờ khi chưa thể được đáp ứng yêu cầu lock trên đơn vị dữ liệu đang bị giữ lock bởi giao tác khác. Các giao tác khác không được phép cập nhật trên những đơn vị dữ liệu đang bị giữ Shared Lock. Vẫn cho phép Insert những dòng dữ liệu thỏa mãn điều kiện thiết lập những Shared Lock => Phantoms 94
  48. Serializable Serializable = Repeatable Read + Giải quyết Phantom Tạo Shared Lock trên đvdl được đọc, Shared Lock được giữ cho đến hết giao tác => Không cho phép các giao tác khác cập nhậtrên đvdl này. Không cho phép Insert những dòng dữ liệu thỏa mãn điều kiện thiết lập những Shared Lock. Tạo Exclusive Lock trên đvdl được ghi, Exclusive Lock được giữ cho đến hết giao tác. Ưu điểm: Giải quyết được cả 4 vấn đề của TXĐT. Khuyết điểm: Phải chờ khi chưa thể được đáp ứng yêu cầu lock trên đvdl đang bị giữ lock bởi giao tác khác. 95 Thử nghiệm các mức cô lập ‰ Vào SQL Query Analyzer, tạo 2 connection trên 2 cửa sổ riêng biệt trong Query Analyzer, mỗi connection ứng với 1 giao tác. ‰ Trong mỗi giao tác, sử dụng lệnh WAITFOR DELAY để yêu cầu 1 giao tác tạm dừng xử lý. Cú pháp: WAITFOR DELAY ‘hh:mm:ss’ ‰ Giả sử có bảng SINHVIEN (MASV, TEN) MASV TEN 1Nam 2Toan 3Tam 96
  49. TH1: a. Read UnCommitted & Read Committed T1 T2 UPDATE SINHVIEN SET TEN = ’Minh’ WAITFOR DELAY‘00:00:20’ BEGIN TRAN SET TRANSACTION ISOLATION LEVEL READ UNCOMMITTED SELECT * FROM SINHVIEN WHERE TEN = ’Minh’ COMMIT TRAN ROLLBACK TRAN T2 cho ra tất cả các dòng97 của bảng SINHVIEN TH1: b. Read UnCommitted & Read Committed T1 T2 UPDATE SINHVIEN SET TEN = ’Minh’ WAITFOR DELAY‘00:00:20’ BEGIN TRAN SET TRANSACTION ISOLATION LEVEL READ COMMITTED SELECT * FROM SINHVIEN WHERE TEN = ’Minh’ ROLLBACK TRAN COMMIT TRAN T2 không cho dòng nào của bảng SINHVIEN 98
  50. TH2: a. Read Committed & Repeatable Read T1 T2 BEGIN TRAN BEGIN TRAN SET TRANSACTION ISOLATION LEVEL READ COMMITTED SELECT TEN FROM SINHVIEN WAITFOR DELAY ‘00:00:20’ UPDATE SINHVIEN SET TEN= ’Minh’ COMMIT TRAN SELECT TEN FROM SINHVIEN COMMIT TRAN Kết quả 2 câu SELECT của T1 là khác nhau. 99 TH3: a. Repeatable Read & Serializable T1 T2 BEGIN TRAN BEGIN TRAN SET TRANSACTION ISOLATION LEVEL REPEATABLE READ SELECT TEN FROM SINHVIEN WAITFOR DELAY ‘00:00:20’ INSERT INTO SINHVIEN VALUES (‘4’,‘Tuyet’) COMMIT TRAN SELECT TEN FROM SINHVIEN COMMIT TRAN Kết quả 2 câu SELECT của T1100 là khác nhau.
  51. TH3: a. Repeatable Read & Serializable T1 T2 BEGIN TRAN BEGIN TRAN SET TRANSACTION ISOLATION LEVEL SERIALIZABLE SELECT TEN FROM SINHVIEN WAITFOR DELAY ‘00:00:20’ INSERT INTO SINHVIEN VALUES (‘4’,‘Tuyet’) COMMIT TRAN SELECT TEN FROM SINHVIEN COMMIT TRAN Kết quả 2 câu SELECT của T1 là như nhau. 101 Kiểm tra mức cô lập? Read Uncommitted Read committed Repeatable read Serializable (MCL1) (MCL2) (MCL3) (MCL4) 1. Khóa ghi? 4. Khóa ghi? 7. Khóa ghi? 10. Khóa ghi? 2. Khóa đọc? 5. Khóa đọc? Thời 8. Khóa đọc? Thời 11. Khóa đọc? 3. Cịn xảy ra tình gian khóa đọc? gian khóa đọc? Thời gian khóa trạng gì của 6. Cịn xảy ra tình 9. Cịn xảy ra tình đọc? ĐKĐT? trạng gì của trạng gì của XLĐT? 12. Cịn xảy ra XLĐT? tình trạng gì của XLĐT? 3.1 Lost Update (TH1) 6.1 Lost Update (TH1) 9.1 Lost Update (TH1) 12.1 Lost Update (TH1) 3.2 Dirty read 6.2 Dirty read 9.2 Dirty read 12.2 Dirty read 3.3 Repeatable read 6.3 Repeatable read 9.3 Repeatable read 12.3 Repeatable read 3.4 Phantom 6.4 Phantom 9.4 Phantom 12.4 Phantom 102
  52. 7. DEADLOCK z Khái niệm z Phát hiện deadlock z Ngăn ngừa deadlock 103 Deadlock ‰ Deadlock là tình trạng trong đó những giao tác có liên quan không thể thực hiện tiếp các thao tác của nó mà phải chờ nhau mãi. ‰ Đây là tình trạng không mong muốn ở các hệ quản trị CSDL điều khiển đồng thời dùng cơ chế khóa. ‰ Các tình huống xảy ra Deadlock: − Cycle deadlock − Conversion deadlock 104
  53. Cycle deadlock ¾ T1 giữ X-lock trên TAB1, T2 giữ X-lock trên TAB2 ¾ T1 yêu cầu X-Lock trên TAB2 => T1 chờ T2 ¾ T2 yêu cầu X-Lock trên TAB1 => T2 chờ T1 GiaotácT1 GiaotácT2 Giữ X-lock Giữ X-lock trên bảng trên bảng TAB1 TAB2 Deadlock Yêu cầu X- Yêu cầu X- lock trên lock trên bảng TAB2 bảng TAB1 105 Conversion Deadlock Giao tác T1 và T2 cùng giữ S-Lock trên 1 tài nguyên R Giao tác T1 yêu cầu X-Lock trên R => T1 chờ T2 Giao tác T2 yêu cầu X-Lock trên R => T2 chờ T1 GiaotácT1 GiaotácT2 Giữ SLock Giữ SLock R Yêu cầu Yêu cầu XLock XLock Deadlock 106
  54. Giải pháp cho Deadlock ‰ Giải quyết Deadlock ¾ Hủy tất cả=> không phải là cách giải quyết tốt. ¾ Hủy giao tác gây ra deadlock. Giao tác nào gây ra? z Dùng thời gian quá hạn (timeout), giới hạn thời gian giao tác ở trạng thái kích hoạt, thời gian timeout nhỏ quá hoặc lớn quá đều không có lợi. z Dùng đồ thị chờ. ‰ Ngăn ngừa Deadlock ¾ Sắp xếp các đơn vị dữ liệu theo 1 thứ tự cố định và các giao tác yêu cầu lock trên chúng theo thứ tự này. z Các transaction chờ lẫn nhau => deadlock. Các transaction chờ theo 1 chiều nhất định => ngăn ngừa deadlock ¾ Dò tìm deadlock dùng nhãn thời gian: Thuật toán WAIT - DIE Thuật toán WOUND - WAIT 107 Đồ thị chờ ‰ Khi có tình trạng Deadlock xảy ra, hệ thống hủy tình trạng Deadlock, thực hiện lúc runtime. ‰ Dùng đồ thị chờ để phát hiện deadlock ¾ Cho S là lịch thao tác của các giao tác T1, T2, , Tn. ¾ Đồ thị có đỉnh là các giao tác ¾ Cung có hướng TiỈ Tj nếu Tj phải chờ Ti ¾ Đồ thị có chu trình Ù Deadlock ‰ Để giải quyết: Hủy đỉnh (ứng với giao tác) có nhiều cung vào ra nhất. 108
  55. Vídụ T1 T2 T3 Rlock(A) Rlock(C) Wlock(E) Wlock (B) Rlock(B) Rlock(B) Wlock(C) Wlock(E) Rlock(D) Wlock(C) Có xảy ra Deadlock không? 109 Dò tìm Deadlock dùng nhãn thời gian ‰ Nhãn thời gian này chỉ dùng cho việc dò tìm deadlock, không giống như nhãn thời gian dùng cho việc điều khiển đồng thời, mặc dù hệ thống có thể đang dùng pp điều khiển đồng thời dựa trên nhãn thời gian. ‰ Nhãn thời gian dùng cho việc dò tìm dead lock không thay đổi khi giao tác rollback. ‰ Nhãn thời gian cho biết thời điểm T đang chờ lock trên đvdl giữ bởi giao tác khác. 110
  56. Thuật toán WAIT - DIE Ti, Tj có timestamp tTi,tTj. Ti yêu cầu lock trên 1 đvdl đang bị giữ lock bởi Tj If tTi < tTj then Ti chờ Else Rollback Ti, Ti bắt đầu lại EndIf T1 T2 T1 T2 T1 chờ T2 rollback 111 Nhận xét TT WAIT- DIE ° Ưu tiên cho các transaction già (bắt đầu trước, timestamp nhỏ) ° Transaction thực hiện trước chỉ phải chờ khi tranh chấp lock với transaction được thực hiện sau. ° Transaction thực hiện sau phải bị rollback và thực hiện lại khi tranh chấp lock với transaction được thực hiện trước. 112
  57. Thuật toán WOUND - WAIT Ti, Tj có timestamp tTi,tTj. Ti yêu cầu lock trên 1 đvdl đang bị giữ lock bởi Tj If tTi < tTj then Rollback Tj Else Ti phải chờ EndIf T1 T2 T1 T2 T2 rollback 113 T2 chờ Nhận xét TT WOUND - WAIT °Ưu tiên cho các transaction già (bắt đầu trước, timestamp nhỏ) °Transaction thực hiện trước không bao giờ bị rollback hay chờ khi tranh chấp lock với 1 transaction thực hiện sau nhưng đang giữ lock. °Transaction thực hiện sau phải chờ khi tranh chấp lock với transaction thực hiện trước và phải bị rollback khi bị transaction thực hiện trước tranh chấp lock. 114
  58. Các pp quản lý deadlock PP dùng nhãn thời gian ĐT chờ Wait - Die Wound-Wait GT rollback ở thời Nếu GT yêu cầu lock gần Đồ thị có thể rất lớn, điểm xảy yêu cầu thời điểm GT bắt đầu, ít phân tích và tìm chu lock, là giai đoạn khi xảy ra tình trạng GT trình sẽ tốn nhiều thời sớm, nên có thể có già không yêu cầu được gian. nhiều GT bị rollback lock giữ bởi GT trẻ hơn, vì hơn, và GT rollback vậy rollback ít xảy ra. thường thực hiện ít GT bị rollback đã thực công việc hơn. hiện nhiều việc trước khi bị rollback. Có khi không có deadlock xảy ra vẫn yêu cầu GT Chỉ yêu cầu 1 GT rollback. rollback khi thực sự GT gây ra deadlock Ưu tiên GT “già”, GT “già” hơn sẽ kill giao tác “trẻ” hơn. Đảm bảo mọi GT đều hoàn tất, không có tình trạng starvation. Dễ cài đặt hơn đồ thị chờ Cài đặt khó, đặc biệt đối 115 với hệ thống phân tán. 8. CÁCH SỬ DỤNG CÁC PHƯƠNG THỨC KHÓA 116
  59. Chiến lược sử dụng lock ‰ Các phương thức lock: − FASTFIRSTROW − HOLDLOCK − NOLOCK − PAGLOCK − READCOMMITTED − READPAST − READUNCOMMITTED − REPEATABLEREAD − ROWLOCK − SERIALIZABLE − TABLOCK − TABLOCKX − UPDLOCK − XLOCK 117 Ví dụ ‰ SELECT COUNT(*) FROM SINHVIEN WITH (TABLOCK, HOLDLOCK) ‰ Các kiểu dùng chung: (TABLOCK, XLOCK): khóa độc quyền trên bảng. (ROWLOCK, XLOCK): khóa độc quyền trên dòng. 118
  60. Vídụ Giả sử STT GP (STT, NGAY CAP, SOXE, LYDOCAP) lớn nhất hiện tại =10 Số thứ tự bắt đầu từ 1, tăng dần, không nhảy số U1 gọi CGP U2 gọi CGP Thao tác Thủ tục CGP S1 S1 Begin Tran S1 S2 M= Select STT from GP where STT = (Select S2 max (STT) from GP) 10 S2 10 S3 S3 Insert into GP values 11 (M+1, ) S3 Lỗi! 11 S4 S4 Commit tran S4 119 Giải pháp ĐKĐT GP (STT, NGAY CAP, SOXE, LYDOCAP) Thao Thủ tục CGP U1 gọi CGP U2 gọi CGP tác S1 S1 Begin Tran S1 S2 M= Select STT from GP with (rowlock, xlock) where STT = S2 10 (Select max (STT) from GP) S2 U2 chờ S3 11 S4 S3 Insert into GP values (M+1, ) S2 11 S4 Commit tran S3 3 12 S4 120
  61. Bài tập Mỗi khi chuyên đề có mã là MACĐ ‰ Cho CSDL sau: được mở, số sv SV (MASV,TENSV,MANGANH) đăng ký không vượt quá SOSVTĐ NGANH (MANGANH, TENNGANH) CĐ (MACĐ, TENCĐ, SOSVTĐ) NG_CĐ (MANGANH, MACĐ) CĐ_MO (MACĐ, NAM, HOCKY) Cho biết sinh viên theo học ngành ĐK (MASV, MACĐ, NAM, HOCKY) có mã là MANGANH phải học những chuyên đề gì 1 bộ của CĐ_MO ‰ Sinh viên chỉ được cho biết chuyên đề đăng ký các chuyên có mã là MACĐ đề có mở được mở trong năm ‰SV không được đk NAM, học kỳ quá 3 chuyên đề HOCKY trong 1 học kỳ. 121 Giao tác đăng ký học chuyên đề 1. Thủ tục Đang_ky_CĐ (@msv, @mcđ, @nam, @hk) 2. @ng= ngànhmàsvmãlà@msvtheohọc(SV) 3. @mcđ thuộc ds các cđ mà ngành @ng phải học? (NG_CĐ) Nếu không thỏa => Báo lỗi và Rollback tran 4. KT CĐ @mcđ có mở trong hk @hk, năm @nam Nếu không mở => Báo lỗi và Rollback tran 5. @max = sốsvtốiđacóthểchođkhọccđmã@mcđ(CĐ) 6. @sosv = đếm số sv đã đk cđ @mcđ, vào năm @nam, học kỳ @hk 7. Nếu @sosv Báo hết chỗ và Rollback tran 8. Kết thúc thủ tục Đưa ra giải pháp sao cho hệ thống làm việc đồng thời hiệu quả. (Gt thống kê, cập nhật, thêm mới, đăng ký đồng thời) 122
  62. Thảo luận ‰ Đv các gt đơn giản: thêm, cập nhật, xóa ‰ Đv các giao tác thống kê. ‰ Đv giao tác đăng ký. Khóa độc quyền trên các bảng lq? Áp dụng mức cô lập Serializable? ‰ Hãy cho biết giải pháp? 123 9. ĐIỀU KHIỂN ĐỒNG THỜI DÙNG KỸ THUẬT NHÃN THỜI GIAN 124
  63. Ý tưởng ‰ Gán nhãn thời gian cho giao tác, ghi lại nhãn thời gian của giao tác cuối cùng đọc/ghi trên đvdl. ‰ Quản lý đồng thời theo nguyên tắc: đảm bảo việc thực hiện lịch biểu đã cho tương đương với lịch tuần tự theo thứ tự nhãn thời gian của giao tác. 125 Nhãn thời gian (timestamp) của giao tác ‰ Nhãn thời gian của giao tác T, TS(T), được phát sinh bởi bộ lập lịch. ¾ Dùng một giá trị số gắn vào các giao tác để chỉ thời điểm bắt đầu của giao tác. z Sử dụng đồng hồ hệ thống hoặc bộ đếm để tạo nhãn thời gian. ¾ Nhãn thời gian có tính chất duy nhất và tăng dần. (Ti<Tj thì TS(Ti) < TS(Tj) ‰ Nếu TS(Ti) < TS(Tj) thì bộ lập lịch phải đảm bảo rằng lịch biểu đã cho phải tương đương với lịch biểu tuần tự Ti < Tj. 126
  64. Nhãn thời gian của đơn vị dữ liệu ‰ Các đơn vị dữ liệu được gán cho 1 giá trị số gọi là nhãn thời gian của đơn vị dữ liệu. ¾ RT(X), thời điểm đọc X, là nhãn thời gian lớn nhất của giao tác đã đọc X. ¾ WT(X), thời điểm ghi X, là nhãn thời gian lớn nhất của giao tác đã ghi X. ¾ C(X), commit bit của X, = true nếu giao tác vừa mới thực hiện write(X) đã commit. z C(X) nhằm tránh tình trạng một giao tác T đọc dữ liệu ghi bởi giao tác U nhưng sau đó U abort. 127 Nguyên tắc ‰ Truy xuất theo thứ tự nhãn thời gian ¾ Khi T đọc X thì WT(X) phải < TS(T). ¾ Khi T ghi X thì WT(X) và RT(X) phải < TS(T). ¾ Abort T nếu không tuân theo thứ tự, T khởi tạo lại với nhãn thời gian mới. 128
  65. Vấn đề 1: Đọc quá trễ ‰ T muốn đọc X ‰ Nhưng TS(T) < WT(X)=TS(U) : X đã được ghi sau khi T đã được khởi tạo. U writes X T reads X U bắt đầu T bắt đầu 129 Vấn đề 2: Ghi quá trễ ‰ T muốn ghi X ‰ Nhưng WT(X) < TS(T) < RT(X): có một giao tác khác lẽ ra nên đọc giá trị ghi bởi T nhưng đã đọc giá trị khác U reads X T writes X U bắt đầu T bắt đầu 130
  66. Vấn đề 3: Dirty read ‰ T đọc X, X được ghi lần cuối bởi U. ‰ Nhưng T vừa đọc X xong, U abort ¾ Trì hoãn việc đọc của T cho tới khi U commit/abort. ¾ Dựa vào commit bit để nhận biết. U writes X T reads X T bắt đầu U bắt đầu U abort 131 Vấn đề 4 ‰ U bắt đầu sau nhưng lại ghi trước ‰ KhiT muốnghithìkhôngcầnlàmgìcả(Qui tắcghiThomas) ‰ Nếu U abort và T commit ¾ Giá trị cuối của X lẽ ra là giá trị do T ghi nhưng đã bị bỏ qua. ¾ Khi U abort, đặt C(X) = false, chép lại giá trị cũ của X và WT(X) U writes X T writes X U bắt đầu T bắt đầu T commit U abort 132
  67. Nguyên tắc ‰ Khi T yêu cầu Read/Write, bộ lập lịch phản hồi: ¾ Đáp ứng yêu cầu. ¾ Abort T và khởi tạo T với nhãn thời gian mới (Rollback). ¾ Trì hoãn T và sau đó quyết định Abort T hay đáp ứng yêu cầu 133 Thuật toán điều khiển 1. T yêu cầu Read X ¾ Nếu TS(T) >= WT(X) z Nếu C(X) = TRUE, đáp ứng yêu cầu –NếuTS(T) > RT(X) • RT(X) := TS(T) – Ngược lại không thay đổi RT(X) z Nếu C(X) = FALSE, trì hoãn T cho đến khi C(X) trở thành TRUE hay giao dịch đã ghi X abort. ¾ Nếu TS(T) < WT(X) z Rollback T (Đọc quá trễ) 134
  68. Thuật toán điều khiển 2. Giao dịch T yêu cầu Write X ¾ Nếu TS(T) >= RT(X) and TS(T) >= WT(X) z Ghi giá trị mới trên X z Đặt WT(X) := TS(T). z Đặt C(X) := FALSE. ¾ Nếu TS(T) >= RT(X) and TS(T) < WT(X) z Nếu C(X) = TRUE, bỏ qua việc ghi của T. z Nếu C(X) = FALSE, trì hoãn T cho đến khi C(X) = TRUE hoặc các giao tác ghi trên X đã abort. ¾ Nếu TS(T) < RT(X) z Rollback T (Ghi quá trễ) 3. Nếu T commit, bộ lập lịch đặt tất cả các đvdl X mà T ghi giá trị C(X):=TRUE. Các GT đang chờ trên X có thể tiếp tục. 4. Trường hợp T rollback, các GT khác đang chờ trên X yêu cầu đọc/ ghi lại. 135 Vídụ T1 T2 T3 T4 A B C 420 400 425 415 tr=tw=0 tr=tw=0 tr=tw=0 ReadA tr=415 ReadA tr =420 WriteB tw=415 WriteA tw=420 ReadB T2 rollback ReadB tr=425 ReadA WriteC WriteA tw=425 136
  69. Vídụ T1 T2 T3 T4 A B C 510 550 575 500 tr=tw=0 tr=tw=0 tr=tw=0 ReadA tr=500 ReadA tr =510 WriteB tw=500 WriteA tw=510 ReadB tr=550 ReadB tr=575 ReadA tr=550 WriteC Tw=550 WriteA tw=575 137 PP nhãn thời gian đa phiên bản ‰ Là một biến thể của pp nhãn thời gian. ‰ Ngoài phiên bản mới nhất của đvdl được lưu lại, còn có các phiên bản trước đó. ‰ Mục đích: giúp cho thao tác đọc không bao giờ làm giao tác rollback. ¾ Hỏi: Khi nào thì thao tác đọc làm giao tác rollback? ¾ PP nhãn thời gian đa phiên bản sẽ làm giao tác T thay vì abort vì lý do trên sẽ tiếp tục đọc phiên bản (của đvdl cần đọc) phù hợp với nhãn thời gian của T. 138
  70. PP nhãn thời gian đa phiên bản ‰ Mỗi đvdl X có nhiều phiên bản X1, X2, , Xk. ‰ Đối với mỗi phiên bản, lưu lại: ¾ Giá trị của phiên bản Xi, ¾ Nhãn thời gian đọc của Xi :rT (Xi), là nhãn thời gian lớn nhất trong các GT đã đọc Xi. ¾ Nhãn thời gian ghi của Xi wT(Xi), là nhãn thời gian của giao tác đã tạo ra phiên bản Xi. ‰ Khi T được phép ghi trên X, một phiên bản mới Xk+1 được tạo, và: ¾ rT (Xk+1) = wT(Xk+1) = TS(T). ‰ Khi T được phép đọc trên Xi, thì: ¾ rT (Xi) = max(rT (Xi), TS(T)) 139 PP nhãn thời gian đa phiên bản ‰ Để bảo đảm khả tuần tự, có 2 nguyên tắc sau phải được đảm bảo: 1. T yêu cầu ghi trên X: ¾ Trong các phiên bản của X có nhãn thời gian ghi TS(T) thì cho T rollback. z Nếu rT (Xi) wT(Xi) thì tạo phiên bản mới Xj, rT (Xj) = wT(Xj) =TS(T) 2. T yêu cầu đọc trên X: ¾ Trong các phiên bản của X có nhãn thời gian ghi <= TS(T), chọnphiênbảnXi cówT(Xi) lớn nhất: z Trả về giá trị Xi chogiaotácT. z rT (Xi) = max (rT (Xi), TS(T)) 140
  71. PP nhãn thời gian đa phiên bản ‰ Nếu T rollback thì tình trạng rollback dây chuyền có thể xảy ra. ‰ Để lịch biểu là phục hồi được, khi các GT ghi trên các đvdl mà T đã đọc commit thì T mới được phép commit. 141 PP nhãn thời gian đa phiên bản T1 T2 A0 BA01 A2 A3 RTS=0 RTS=0 TS(T1)=100 TS(T2)=200 WTS=0 WTS=0 Read(A) WTS=0 RTS=100 Write(A) RTS=0 WTS=100 Read(A) RTS=200 WTS=100 Write(A) RTS=0 WTS=200 Read(B) RTS=200 WTS=0 RTS=200 Read(B) WTS=0 Write(A) RTS=0 WTS=200 Read(A) RTS=200 WTS=100 142
  72. 10. Điều khiển đồng thời dùng phương pháp kiểm tra hợp lệ (Validation Technique) 143 Phương pháp kiểm tra hợp lệ ‰ KT khóa và KT nhãn thời gian là các PP điều khiển đồng thời bi quan: giả sử các GT sẽ đụng độ và tránh sự đụng độ này. ‰ KT khoá & KT nhãn thời gian điều khiển thực hiện đồng thời theo cú pháp, vì phân biệt đọc/ghi. ‰ PP kiểm tra hợp lệ là PP điều khiển đồng thời lạc quan. 144
  73. Phương pháp kiểm tra hợp lệ ‰ Cứ cho GT thực hiện. ¾ Cập nhật của GT chỉ trên biến cục bộ, không cập nhật trực tiếp trên CSDL cho đến khi GT kết thúc. ¾ Khi GT thi hành xong, kỳ xác nhận kiểm tra các cập nhật của GT có vi phạm tính khả tuần tự không. z Nếu không, GT commit và CSDL được cập nhật thật sự từ biến cục bộ. z Nếu vi phạm, GT abort và khởi động lại. 145 Phương pháp kiểm tra hợp lệ ‰ GT trải qua các kỳ: ¾ 1. Kỳ đọc (Read phase): z Ti đọc các mục dl cần thiết. z Các cập nhật chỉ thực hiện trên biến cục bộ, không phải trên CSDL. ¾ 2. Kỳ Kiểm tra hợp lệ (Validation phase): z Kiểm tra có vi phạm tính khả tuần tự hay không để cập nhật CSDL. – Nếu vi phạm thì rollback. – Nếu không thì làm tiếp kỳ 3. ¾ 3. Kỳ ghi (Write phase): z Ghi từ biến cục bộ xuống CSDL. 146
  74. Phương pháp kiểm tra hợp lệ ‰ Ghi nhận các nhãn thời gian: ¾ START(Ti) – thời điểm Ti start ¾ VAL(Ti) – thời điểm Ti thực hiện xong phase validate ¾ Finish(Ti) – thời điểm T thực hiện xong phase finish. 147 Phương pháp kiểm tra hợp lệ ‰ Bộ lập lịch theo dõi 3 tập hợp: ¾ START = {T, T đã start, nhưng chưa validate xong} & START (T) ¾ VAL = {T, T validate xong nhưng chưa xong phase finish} & START (T) & VAL(T) z VAL(T) là thời điểm để căn cứ vào đó điều khiển tuần tự. ¾ FIN = {T, T thực hiện xong phase finish} & START(T) & VAL(T) & FIN(T) z Bộ lập lịch không quan tâm đến GT T sao cho FIN(T) < START(U), U làgiaotácđangởtrạngtháikíchhoạt. StartValidate Finish 148
  75. Kiểm tra hợp lệ ‰ Giả sử có GT U: ¾ U ∈ VAL hoặc U ∈ FIN ¾ FIN(U) > START (T), nghĩa là U không finish trước khi T start. ¾ RS(T) ∩ WS(U) = {X} ≠∅: có thể U write X sau khi T read X. Ta không chắc T đã đọc giá trị U ghi trước đó hay không, tốt hơn hếtchoT rollback đểtránhrủiroT vàU khôngtuântheothứ tự tuần tự. Start Validate U Finish T 149 Kiểm tra hợp lệ ‰ Giả sử có GT U: ¾ U ∈ VAL, nghĩa là đã validate xong ¾ FIN(U) > VAL (T), nghĩa là U không finish trước khi T bắt đầu giai đoạn validate. ¾ WS(T) ∩ WS(U) = {X} ≠∅: cóthểT sẽghiX trướckhiU ghi X. Ta không chắc điều này có xảy ra hay không, tốt hơn hết là rollback T để không vi phạm tính tuần tự. Start Validate U Finish T 150
  76. Ví dụ U: RS(U)={B} W: RS(W)={A,D} WS(U)={D} WS(W)={A,C} T: RS(T)={A,B} V: RS(V)={B} WS(T)={A,C} WS(V)={D,E} Hãy điều khiển đồng thời dùng phương pháp kiểm tra hợp lệ cho 4 GT trên. 151 Ví dụ (tt) ‰ U có hợp lệ? ¾ Vì tại thời điểm U kiểm tra hợp lệ thì chưa có giao tác nào hợp lệ nên không cần kiểm tra. U kiểm tra hợp lệ thành công. 152
  77. Ví dụ(tt) ‰ T có hợp lệ? ¾ Khi T kiểm tra hợp lệ, U đã hợp lệ nhưng chưa kết thúc. Vì vậy ta kiểm tra tập các đơn vị dữ liệu đọc và ghi của T có giao với tập đvdl ghi của U hay không. Thật vậy: z RS(T) ∩ WS(U) = {A, B} ∩ {D} = ∅ z WS(T) ∩ WS(U) = {A, C} ∩ {D} = ∅ Vậy T hợp lệ. 153 Ví dụ (tt) ‰ V có hợp lệ? ¾ Khi V kiểm tra hợp lệ, U đã hợp lệ và kết thúc, T đã hợp lệ nhưng chưa kết thúc. Vì V bắt đầu trước khi U kết thúc nên ta phải kiểm tra: z RS(V) ∩ WS(U) = {B} ∩ {D} = ∅ z RS(V) ∩ WS(T) = {B} ∩ {A, C} = ∅ z WS(V) ∩ WS(T) = {D, E} ∩ {A, C} = ∅ Vậy V hợp lệ. 154
  78. Ví dụ (tt) ‰ W có hợp lệ? ¾ Khi W kiểm tra hợp lệ thì U, T, V đã kiểm tra hợp lệ, W bắt đầu sau khi U kết thúc. Khi đó T và V vẫn chưa kết thúc. Ta phải kiểm tra: z RS(W) ∩ WS(T) = {A, D} ∩ {A, C} = {A} z RS(W) ∩ WS(V) = {A, D} ∩ {D, E} = {D] z WS(W) ∩ WS (V) = {A, C} ∩ {D, E} = ∅ W không hợp lệ. 155 Nhận xét chung ‰ Lưu trữ: z PP lock: lock table, không gian lưu trữ tỉ lệ với số lượng đvdl bị lock. z PP nhãn thời gian: cần không gian lưu trữ cho nhãn thời gian đọc và ghi của từng đvdl, bất kể có đang được truy cập hay không. z Validation: cần lưu lại nhãn thời gian và read set, write set cho từng giao tác đang được kích hoạt. PP này cần không gian nhiều hơn vì theo dõi cả những giao tác đã commit nhưng chưa thực hiện ghi. ¾ Nói chung, không gian lưu trữ gần như tỉ lệ với số lượng đvdl được truy cập bởi các giao tác đang ở trạng thái kích hoạt. 156
  79. Nhận xét chung ‰ Về khả năng giao tác hoàn tất mà không bị trì hoãn: ¾ Hiệu quả của các phương pháp còn tùy thuộc vào sự ảnh hưởng lẫn nhau của các giao tác (truy cập cùng đvdl) là nhiều hay ít. z PP lock: trì hoãn GT nhưng tránh được tình trạng rollback, ngay cả khi sự ảnh hưởng lẫn nhau giữa các GT đồng thời là nhiều. PP nhãn thời gian và pp Kiểm tra hợp lệ không trì hoãn GT nhưng có thể gây ra tình trạng GT rollback Ỉ lãng phí tài nguyên. z Nếu sự ảnh hưởng lẫn nhau giữa các GT đồng thời là nhỏ thì cả PP nhãn thời gian lẫn Kiểm tra hợp lệ đều không gây ra rollback. Khi đó cả hai làm việc tốt hơn và tốn ít chi phí hơn PP lock. z Khi rollback xảy ra, pp Nhãn thời gian nhận biết sớm hơn và sẽ rollback sớm hơn pp Kiểm tra hợp lệ. 157 Phụ lục ‰ Lịch biểu dùng kỹ thuật này là không rollback dây chuyền vì thao tác ghi được thực hiện sau khi giao tác khác commit. 158
  80. TT NHÃN THỜI GIAN 1. T yêu cầu Read X Nếu TS(T) >= WT(X) T đọc X RT(X) := max (RT(X), TS(T)) Nếu TS(T) = RT(X) and TS(T) >= WT(X) T ghi X Đặt WT(X) := TS(T) Nếu TS(T) TS(T) thì cho T rollback. z Nếu rT (Xi) wT(Xi) thì tạo phiên bản mới Xj, rT (Xj) = wT(Xj) =TS(T) 2. T yêu cầu đọc trên X: ¾ Trong các phiên bản của X có nhãn thời gian ghi <= TS(T), chọn phiên bản Xi có wT(Xi) lớn nhất: z Trả về giá trị Xi cho giao tác T. z rT (Xi) = max (rT (Xi), TS(T)) 160
  81. Hết chương 2. 161