›
›

Bài giảng Hệ quản trị dữ liệu - Chương II: Quản lý truy xuất đồng thời

pdf 140 trang hapham 2710
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Hệ quản trị dữ liệu - Chương II: Quản lý truy xuất đồng thời", để 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_du_lieu_chuong_ii_quan_ly_truy_xuat_do.pdf

Nội dung text: Bài giảng Hệ quản trị dữ liệu - Chương II: Quản lý truy xuất đồng thời

  1. Chương II. Quản lý truy xuất đồng thời 1
  2. Nội dung  Giới thiệu  Khái niệm về giao tác  Các vấn đề truy xuất đồng thời  Lịch thao tác  Các kỹ thuật khóa dữ liệu  Kỹ thuật nhãn thời gian  Các kỹ thuật khác 2
  3. Giới thiệu  Thực tế, CSDL được khai thác một cách đồng thời bởi nhiều người sử dụng. Thậm chí còn có nhiều tiến trình trong một chương trình cũng có thể được thực hiện đồng thời.  Ví dụ: hệ thống đặt chỗ trên các chuyến bay của một hãng hàng không. Nhiều đại lý có thể cùng bán vé. Hành khách có thể mua vé, đổi vé, trả vé do đó danh sách khách hàng và số ghế của các chuyến bay sẽ bị thay đổi. Chuyện gì sẽ xảy ra nếu hai hay nhiều đại lý cùng bán một ghế cho nhiều khách hàng? Hệ quản trị CSDL này phải có khả năng giải quyết vấn đề tranh chấp đó để không một ghế nào trên một chuyến bay có thể bán nhiều hơn một lần. 3
  4. Khái niệm về giao tác (Transaction)  Định nghĩa  Tính chất ACID của giao tác  Các thao tác của giao tác  Trạng thái của giao tác 4
  5. Định nghĩa  Giao tác là 1 đơn vị xử lý nguyên tố gồm 1 chuỗi các hành động tương tác lên CSDL. Khi thực hiện một giao tác hoặc phải thực hiện tất cả các hành động của nó hoặc thì không thực hiện hành động nào hết. CSDL nhất quán 1 Giao tác CSDL nhất quán 2 5
  6. Ví dụ 6
  7. Tính chất ACID của giao tác  Tính Nguyên tố (Atomicity)  Hoặc là toàn bộ hoạt động của giao dịch được phản ánh đúng đắn trong CSDL hoặc không có hoạt động nào cả.  Nói cách khác, tác dụng của các câu lệnh trong một giao tác phải như là một câu lệnh đơn. Không chia nhỏ ra được. 7
  8. Ví dụ 1 T:Read(A,t); t:=t-50; Write(A,t); Read(B,t); t:=t+50; Write(B,t);  A=100, B=200 (A+B=300)  Tại thời điểm sau khi write(A,t)  A=50, B=200 (A+B=250) - CSDL không nhất quán  Tại thời điểm sau khi write(B,t)  A=50, B=250 (A+B=300) - CSDL nhất quán  Nếu T không bao giờ bắt đầu thực hiện hoặc T được đảm bảo phải hoàn tất thì trạng thái không nhất quán sẽ không xuất hiện 8
  9. Tình huống  Đặt Ti là một giao dịch chuyển 50 USD từ tài khoản A đến tài khoản B. giao dịch này được định nghĩa như sau: Ti: Read(A); A:=A-50; Write(A); Read(B); B:=B+50; Write(B); 9
  10. Tình huống  Giả sử trước khi thực hiện giao dịch Ti, các giá trị của các tài khoản A và B tương ứng là 1000USD và 2000USD. Trong khi thực hiện giao dịch Ti, một lỗi xảy ra (phần cứng, phần mềm,, mất điện, ) ngăn chặn Ti hoàn thành thực hiện giao dịch chuyển khoản. Giả sử lỗi này xảy ra sau khi thao tác Write(A) đã được thực hiện và trước khi thao tác Write(B) được thực hiện.  Trong trường hợp này, giá trị cùa tài khoản A và B được ghi nhận trong CSDL là 950USD và 2000 USD. Hệ thống đã hủy 50USD do lỗi này tong A+B không còn được bảo toàn 10
  11. Tính chất ACID của giao tác (tt)  Tính Nhất quán (Consistency)  Bất kỳ CSDL nào thì mọi ràng buộc tòan vẹn phải thỏa. Tại bất kỳ thời điểm mà mọi RBTV được thỏa gọi là tính nhất quán.  Một giao tác phải biến CSDL từ trạng thái nhất quán này sang trạng thái nhất quán khác không được phá vở trạng thái nhất quán. E1 T E2 (E1nhất quán thì E2 phải nhất quán).  Ví dụ:phái là nam hoặc nữ, nhưng gõ đến phái Enter đi qua mà cho phép thì không còn trạng thái nhất quán. 11
  12. Ví dụ 2 T: Read(A,t); t:=t-50; Write(A,t); Read(B,t); t:=t+50; Write(B,t);  Consistency Tổng A+B là không đổi Nếu CSDL nhất quán trước khi T được thực hiện thì sau khi T hoàn tất CSDL vẫn còn nhất quán 12
  13. Tính chất ACID của giao tác (tt)  Tính Cô lập (Isolation)  Một giao tác không quan tâm đến các giao tác khác xử lý đồng thời với nó  Khi có n giao tác xử lý đồng thời phải làm sao bảo đảm là tôi có tính độc lập của riêng tôi, mà tôi chạy giống như tôi chạy một mình, không biết xung quanh tôi có n người khác đang chạy. Hệ thống làm sao bảo đảm khi có n người chạy 1 lúc hệ thống làm sao bảo đảm n người này chạy một mình. 13
  14. Ví dụ 3 T:Read(A,t); t:=t-50; T’ Write(A,t); Read(B,t); t:=t+50; Write(B,t);  Giả sử có 1 giao tác T’ thực hiện phép toán A+B và chen vào giữa thời gian thực hiện của T  T’ kết thúc: A+B=50+200=250  T kết thúc: A+B=50+250=300  Hệ thống của các giao tác thực hiện đồng thời có trạng thái tương đương với trạng thái hệ thống của các giao tác 14 thực hiện tuần tự theo 1 thứ tự nào đó.
  15.  Như ví dụ trên, khi CSDL ở trạng thái không toàn vẹn trong giao dịch chuyển tiền từ A đến B đang thực hiện, ở đó tài khoản A đã giảm đi nhưng chưa tăng tài khoản B. Nếu một giao dịch thứ hai chạy đồng thời đọc A và B tại thời điểm trung gian này và tính tổng A+B, nó sẽ quan sát thấy một giá trị không đúng đắn.  Hơn nữa, nếu giao dịch thứ hai thực hiện. Việc cập nhật trên A và B và dựa vào những giá trị không đúng đắn mà nó nhận được, CSDL có thể để lại một trạng thái không toàn vẹn sau khi cả hai giao 15 dịch đã hoàn thành
  16. Tính chất ACID của giao tác (tt)  Tính Bền vững (Durability)  Mọi thay đổi mà giao tác thực hiện trên CSDL phải được ghi nhận bền vững T:Read(A,t); t:=t-50; Write(A,t); Read(B,t); t:=t+50; Write(B,t);  Khi T kết thúc thành công  Dữ liệu sẽ không thể nào bị mất bất chấp có sự cố hệ thống xảy ra 16
  17.  Tính bền vững đảm bảo rằng một khi giao dịch được hoàn thành, tât cả các cập nhật trên CSDL là bền vững thậm chí nếu có lỗi hệ thống sau khi giao dịch hoàn thành thực hiện. Giả sử một lỗi hệ thống có thể dẫn đến mất mát dữ liệu trong bộ nhớ chính, nhưng dữ liệu được ghi vào đĩa không bao giờ bị mất. 17
  18. Các thao tác của giao tác  Giả sử CSDL gồm nhiều đơn vị dữ liệu  Một đơn vị dữ liệu (element) Có một giá trị Được truy xuất và sửa đổi bởi các giao tác Quan hệ (relation) - Lớp (class) Khối dữ liệu trên đĩa (block) / trang (page) Bộ (tuple) - Đối tượng (object) 18
  19. Các thao tác của giao tác (tt)  Input(X)  Read(X, t) X t X  Bufffer manager  Input Buffer Disk  Output  Write(X, t)  Transaction  Output(X)  Read  Write X t X 19 Buffer Disk
  20. Ví dụ  Giả sử CSDL có 2 đơn vị dữ liệu A và B với ràng buộc A=B trong mọi trạng thái nhất quán  Giao tác T thực hiện 2 bước  A:=A*2  B:=B*2  Biểu diễn T  Read(A,t) ; t=t*2; Write(A,t);  Read(B,t) ; t=t*2; Write(B,t); 20
  21. Ví dụ (tt) Hành động t Mem A Mem B Disk A Disk B Read(A,t) 8 8 8 8 t:=t*2 16 8 8 8 Write(A,t) 16 16 8 8 Read(B,t) 8 16 8 8 8 t:=t*2 16 16 8 8 8 Write(B,t) 16 16 16 8 8 Output(A) 16 16 16 16 8 Output(B) 16 16 16 16 16 21
  22. Trạng thái của giao tác 22
  23. Trạng thái của giao tác  Active (kích hoạt)  Ngay khi bắt đầu thực hiện thao tác đọc/ghi  Partially committed (hoàn thành bộ phận)  Sau khi lệnh thi hành cuối cùng thực hiện  Failed (thất bại)  Sau khi nhận ra không thể thực hiện các hành động được nữa  Aborted  Sau khi giao tác được quay lui và CSDL được phục hồi về trạng thái trước trạng thái bắt đầu giao dịch  Bắt đầu lại giao tác (nếu có thể)  Hủy giao tác  Committed (hoàn thành) 23  Sau khi mọi hành động hoàn tất thành công
  24. T-SQL đặc trưng của giao tác 24
  25. Các vấn đề truy xuất đồng thời  Vấn đề mất dữ liệu đã cập nhật (Lost Update)  Vấn đề không thể đọc lại được(Unrepeated Read)  Vấn đề dữ liệu chưa hoàn tất (Uncommitted Dependency ) 25
  26. Vấn đề mất dữ liệu đã cập nhật Tình trạng xảy ra khi hai hay nhiều thao tác của các giao tác khác nhau cùng yêu cầu truy cập một mục dữ liệu. Các dữ liệu đã được các thao tác trước cập nhật nhưng lại bị các thao tác sau cập nhật lại làm thay đổi kết quả mong muốn. 26
  27. Vấn đề mất dữ liệu đã cập nhật  Ví dụ: nhà sách còn 500 cuốn sách: Từ lúc T1 nhân viên A yêu cầu mua 400 cuốn sách từ khách hàng X. Cũng từ T1 nhân viên B yêu cầu mua 300 cuốn từ khách hàng Y. A và B đọc dữ liệu thấy 500 cuốn nên đều đồng ý bán. Vào lúc T2 nhân viên A sẽ thực hiện cập nhật số sách từ 500 thành 100. Vào lúc T3 nhân viên B sẽ cập nhật số sách từ 500 thành 200  Như vậy thao tác cập nhật của A không có tác dụng hay dữ liệu của A cập nhật sẽ bị mất vì B cập nhật sau. 27
  28. Vấn đề mất dữ liệu đã cập nhật  Xét 2 giao tác T1 T2 Read(A) Read(A) A:=A+10 A:=A+20 Write(A) Write(A)  Giả sử T1 và T2 được thực hiện đồng thời A=50 T1 T2 t1 Read(A)  Dữ liệu đã cập nhật tại t của T 4 1 t2 Read(A) A:=A+10 bị mất vì đã bị ghi chồng lên ở t3 t4 Write(A) thời điểm t6 t5 A:=A+20 t6 Write(A) 28 A=60 A=70
  29. Vấn đề không thể đọc lại được (Unrepeated Read)  Ví dụ: giả sử nhà sách còn 200 cuốn sách. Vào lúc T1 nhân viên A bán cho khách 150 cuốn, sẽ thực hiện cập nhật sách từ 200 thành 50. (giao dịch chưa hoàn thành chẳng hạn vì việc giao nhận tiền chưa xong). Sau đó lúc T2, B nhận được yêu cầu mua 100 cuốn sách, nếu B đọc được dữ liệu chưa hoàn tất thì B sẽ từ chối bán 100 cuốn sách này. Nếu vào lúc T3 vì lý do nào đó chẳng hạn không đủ tiền khách hàng của A không mua 150 cuốn sách nữa. Giao tác bán hàng của A sẽ không thực hiện nên quay về trạng thái số sách còn lại là 200 Nhưng B từ chối khách hàng. Nếu B không đọc được dữ liệu từ lúc T1 đến T3 thì sẽ như thế nào? 29
  30. Vấn đề dữ liệu chưa hoàn tất (rác) (Uncommitted Dependency )  Giả sử nhân viên C cần tổng hợp 5 dòng dữ liệu 1 2 3 4 5 để làm một bản báo cáo. T1: C đọc và đưa các dòng 1 2 3 4 vào báo cáo. T2: D lại xóa dòng 1 thay bằng dòng 6. T3: C đọc tiếp 5 6 đưa vào báo cáo. Vậy báo cáo này xử lý cả dữ liệu cũ và mới sai 30
  31. Các mức cô lập của Transaction  Các dữ liệu bẩn (dirty data) là một thuật ngữ chung chỉ các dữ liệu được ghi bằng một giao tác nhưng còn chưa được lưu giữ lại (committed). Một dirty read dùng để đọc các dữ liệu bẩn. Điều nguy hiểm của việc đọc các dữ liệu bẩn là ở chỗ một giao tác ghi nó có thể bị bỏ dở. Nếu vậy thì các dữ liệu bẩn sẽ bị đẩy ra khỏi cơ sở dữ liệu và mọi người được phép xử sự như là các dữ liệu đó chưa bao giờ tồn tại. Nếu một giao tác khác nào đó đã đọc các dữ liệu bẩn thì giao tác đó có thể lưu giữ hoặc thực hiện một hành động nào đó phản ánh sự hiểu biết của nó về dữ liệu bẩn. 31
  32. Các mức cô lập của Transaction  Đôi lúc dirty read có ý nghĩa, đôi lúc nó không có ý nghĩa. Lúc khác nó có ý nghĩa rất nhỏ đủ để tạo ý nghĩa về nguy cơ của một dirty read phụ và như vậy làm ngăn cản:  Công việc tốn thời gian của hệ quản trị cơ sở dữ liệu cần để ngăn ngừa dirty read và Mất tính song song gây ra từ sự chờ đợi cho đến khi không có thể có một dirty read. 32
  33. Các mức cô lập của Transaction  Giả sử rằng có các dirty read. Có 3 tài khoản A1, A2, A3 với 100$, 200$ và 300$ tương ứng. Giả sử rằng giao tác T1 thực hiện chương trình P để chuyển 150$ từ A1 đến A2. Cùng một thời gian, giao tác T2 chạy chương trình P để chuyển 250$ từ A2 đến A3. Có khả năng có các dãy sự kiện sau:  1. T2 thực hiện bước 1 và thêm 250$ vào A3 và bây giờ A3 có 550$  2. T1 thực hiện bước 1 và thêm 150$ và A2 và bây giờ A2 có 350$  3. T2 thực hiện kiểm tra của bước 2 và tìm ra rằng A2 có 33 đủ tiền (350$) để cho phép chuyển 250$ từ A2 sang A3.
  34. Các mức cô lập của Transaction  4. T1 thực hiện kiểm tra của bước 2 và tìm ra rằng T1 không có đủ tiền (100$) để cho phép chuyển 150$ từ A1 sang A2.  5. T2 thực hiện bước 2b. Nó trừ đi 250$ khỏi A2 và bây giờ A2 có 100$ và kết thúc.  6. T1 thực hiện bước 2a. Nó trừ 150$ khỏi A2, bây giờ A2 có –50$ và kết thúc. 34
  35. Các mức cô lập của Transaction  Tổng số tiền không thay đổi; trong ba tài khoản vẫn còn 600$. Nhưng bởi vì T2 đọc dữ liệu bẩn ở bước 3 trong 6 bước trên, chúng ta không bảo vệ được việc một tài khoản trở nên âm, đó là mục đích của việc kiểm tra tài khoản thứ nhất để xem tài khoản này có số tiền thích hợp hay không. 35
  36. Lịch thao tác (schedule)  Giới thiệu  Định nghĩa  Lịch tuần tự (Serial schedule)  Lịch khả tuần tự (Serializable schedule) 36
  37. Giới thiệu  Thực hiện tuần tự  Tại một thời điểm, một giao tác chỉ có thể bắt đầu khi giao tác trước nó hoàn tất  Thực hiện đồng thời  Cho phép nhiều giao tác cùng truy xuất dữ liệu  Gây ra nhiều phức tạp về nhất quán dữ liệu  Tuy nhiên có 2 lý do để thực hiện đồng thời:  Tận dụng tài nguyên và thông lượng  Giảm thời gian phản hồi của các giao tác 37
  38. Hai lý do để thực hiện đồng thời - Tận dụng tài nguyên và thông lượng - Một giao tác gồm nhiều bước: hành động I/O trên đĩa, hành động xử lý trên CPU. Do đó hành động I/O trên đĩa và xử lý trên CPU có thể thực hiện song song với nhau. - Trong khi 1 giao tác đang thực hiện đọc/ghi trên đĩa thì giao tác khác thực hiện tính toán trên CPU. - CPU và đĩa có ít thời gian rảnh rỗi. 38
  39. Hai lý do để thực hiện đồng thời - Giảm thời gian phản hồi của các giao tác - Có nhiều giao tác với thời gian thực hiện ngắn dài khác nhau. - Nếu thực hiện tuần tự, có thể 1 giao tác ngắn phải chờ 1 giao tác dài trước trước đó -> trì hoãn. - Nếu các giao tác thực hiện với những dữ liệu khác nhau thì nên thực hiện song song -> chia sẽ chu kỳ của CPU và truy cập đĩa  Khi có nhiều giao tác thực hiện đồng thời, tính nhất quán CSDL có thể bị phá vỡ mặc dù cá nhân mỗi giao tác vẫn thực hiện đúng đắn.Vì vậy cần có khái niệm Lịch thao tác (schedule) để xác định những thực hiện nào đảm bảo tính nhất quán. Bộ phận quản lý các lịch thao tác này gọi là Bộ lập lịch (scheduler). 39
  40. Bộ lập lịch (Scheduler)  Là một thành phần của DBMS có nhiệm vụ lập 1 lịch để thực hiện n giao tác xử lý đồng thời Transaction manager Read/Write request Scheduler Read & Write Buffers 40
  41. Bộ lập lịch (Scheduler) (tt)  Một lịch thao tác S được lập từ n giao tác T1, T2, ,Tn được xử lý đồng thời là 1 thứ tự thực hiện các hành động của n giao tác này  Thứ tự xuất hiện của các thao tác trong lịch phải giống với thứ tự xuất hiện trong giao tác  Có 2 bộ lập lịch  Lịch tuần tự (Serial)  Lịch khả tuần tự (Serializable)  Confict-Serializability  View-Serializability 41
  42. Ví dụ T1 T2 Read(A,t) Read(A,s) t:=t+100 s:=s*2 Write(A,t) Write(A,s) Read(B,t) Read(B,s) t:=t+100 s:=s*2 Write(B,t) Write(B,s)  Giả sử ràng buộc nhất quán trên CSDL là A=B  Từng giao tác thực hiện riêng lẽ thì tính nhất quán sẽ được bảo toàn 42
  43. Lịch tuần tự (Serial schedule)  Một lịch S được gọi là tuần tự nếu các hành động của các giao tác Ti (i=1 n) được thực hiện liên tiếp nhau S T1 T2 T3 Thời gian Tn 43
  44. Lịch tuần tự (tt) T1 T2 A B T1 T2 A B S S 1 25 25 2 25 25 Read(A,t) Read(A,s) t:=t+100 s:=s*2 Write(A,t) 125 Write(A,s) 50 Read(B,t) Read(B,s) t:=t+100 s:=s*2 Write(B,t) 125 Write(B,s) 50 Read(A,s) Read(A,t) s:=s*2 t:=t+100 Write(A,s) 250 Write(A,t) 150 Read(B,s) Read(B,t) s:=s*2 t:=t+100 Write(B,s) 250 Write(B,t) 150 44
  45. Lịch tuần tự (tt) 45
  46. Lịch tuần tự (tt) 46
  47. Lịch tuần tự (tt) 950 2050 855 47 2145
  48. Lịch tuần tự (tt) 48
  49. Lịch tuần tự (tt) 900 2100 850 49 2150
  50. Lịch tuần tự (tt) 50
  51. Lịch tuần tự (tt) 950 855 2050 2145 51
  52. Lịch tuần tự (tt) 900 950 2050 2100 52
  53. Lịch tuần tự (tt) 53
  54. Lịch khả tuần tự (Serializable schedule)  Một lịch S được lập từ n giao tác T1, T2, , Tn xử lý đồng thời được gọi là khả tuần tự nếu nó cho cùng kết quả với 1 lịch tuần tự nào đó được lập từ n giao tác này S T1 T2 T3 Thời gian Tn 54
  55. Lịch khả tuần tự (tt) T T A B S 1 2  Trước S khi thực hiện 3 25 25 3 Read(A,t)  A=B=c t:=t+100  Write(A,t) 125 với c là hằng số Read(A,s)  Sau khi S3 kết thúc s:=s*2 Write(A,s) 250  A=2*(c+100) Read(B,t) t:=t+100  B=2*(c+100) Write(B,t) 125  Trạng thái CSDL nhất Read(B,s) s:=s*2 quán Write(B,s) 250  S3 là khả tuần tự 55
  56. Lịch khả tuần tự (tt) T1 T2 A B S4 25 25  Trước S4 khi thực hiện Read(A,t)  A=B=c t:=t+100 Write(A,t) 125  với c là hằng số Read(A,s) s:=s*2  Sau khi S4 kết thúc Write(A,s) 250  A = 2*(c+100) Read(B,s) s:=s*2  B = 2*c + 100 Write(B,s) 50 Read(B,t)  Trạng thái CSDL không t:=t+100 nhất quán Write(B,t) 150  S4 không khả tuần tự 56
  57. Lịch khả tuần tự (tt) T T A B  Khi S5 kết thúc S 1 2 5 25 25 A và B bằng nhau Read(A,t) t:=t+100 Trạng thái cuối cùng Write(A,t) 125 Read(A,s) nhất quán s:=s*1 Write(A,s) 125  S5 khả tuần tự, có kết Read(B,s) quả giống với lịch tuần s:=s*1 Write(B,s) 25 tự Read(B,t) t:=t+100 T1, T2 Write(B,t) 125 T2, T1 57
  58. Bài tập  Cho A=10; B=20; N=30; M=40 58
  59. Bài tập  Cho A=10; B=20; N=30; M=40  Lịch nào là khả tuần tự? 59
  60. Conflict-Serializability  Ý tưởng  Xét 2 hành động liên tiếp nhau trong 1 lịch thao tác  Nếu thứ tự của chúng được đổi cho nhau  Thì hoạt động của ít nhất 1 giao tác có thể thay đổi T T’ Hành động 1 Hành động 2 Hành động 1’ Hành động 2’ Hành động 3 Hành động 4 Hành động 3’ Hành động 4’ 60
  61. Conflict-Serializability(tt)  Cho lịch S có 2 giao tác Ti và Tj, xét các trường hợp  ri(X) ; rj(Y)  Không bao giờ có xung đột, ngay cả khi X=Y  Cả 2 thao tác không làm thay đổi giá trị của đơn vị dữ liệu X, Y  ri(X) ; wj(Y)  Không xung đột khi X Y  Tj ghi Y sau khi Ti đọc X, giá trị của X không bị thay đổi  Ti đọc X không ảnh hưởng gì đến Tj ghi giá trị của Y  wi(X) ; rj(Y)  Không xung đột khi X Y  wi(X) ; wj(Y) 61  Không xung đột khi X Y
  62. Conflict-Serializability(tt)  Hai hành động xung đột nếu  Thuộc 2 giao tác khác nhau  Truy xuất đến cùng 1 đơn vị dữ liệu  Có ít nhất một hành động ghi (write) không thể hoán vị thứ tự Ti Tj Ti Tj Ti Tj Write(A) Read(A) Write(A) Write(A) Write(A) Read(A) 62
  63. Conflict-Serializability (tt) T T T T T T S 1 2 1 2 S’ 1 2 Read(A) Read(A) Read(A) Write(A) Write(A) Write(A) Read(A) Read(A) Read(B) Write(A) Write(A) Write(B) Read(B) Read(B) Read(A) Write(B) Write(B) Write(A) Read(B) Read(B) Read(B) Write(B) Write(B) Write(B) 63
  64. Conflict-Serializability (tt)  Định nghĩa  S, S’ là những lịch thao tác conflict-equivalent  Nếu S có thể được chuyển thành S’ bằng một chuỗi những hoán vị các thao tác không xung đột  Một lịch thao tác S là conflict-serializable  Nếu S là conflict-equivalent với một lịch thao tác tuần tự nào đó  S conflict-serializable S khả tuần tự  S conflict-serializable  S khả tuần tự ??? 64
  65. Conflict-Serializability (tt)  Xét lại lịch S5 T T A B S 1 2 5 25 25 Read(A,t) t:=t+100 Write(A,t) 125 Serializable Read(A,s) nhưng không s:=s*1 conflict-serializable Write(A,s) 125 Read(B,s) s:=s*1 Write(B,s) 25 Read(B,t) t:=t+100 Write(B,t) 125 65
  66. Conflict-Serializability (tt) 66
  67. Conflict-Serializability (tt) 67
  68. Kiểm tra tính khả tuần tự của một lịch  Nhập: Lịch biểu S cho một tập giao dịch T1,T2, , Tk  Xuất: Khẳng định S có tuần tự hay không?  Nếu có thì đưa ra một lịch biểu tuần tự tương đương với S  Phương pháp: Tạo một đồ thị có hướng G (Precedence graph) 68
  69. Kiểm tra tính khả tuần tự của một lịch (tt)  Xây dựng đồ thị có hướng:  Mỗi giao tác Ti là một nút của đồ thị G.  Nếu có Tj phát ra một yêu cầu Write(A) sau một giao tác Ti đã phát ra yêu cầu Read(A) thì vẽ một cung từ Ti Tj  Nếu có một giá trị Tj phát ra một yêu cầu Read(A) sau một giao tác Ti đã phát sau một yêu cầu Write(A) thì vẽ một cung đi từ Ti Tj  Nếu có một yêu cầu Tj phát ra một yêu cầu Write(A) sau một yêu cầu Ti đã phát ra một yêu cầu Write(A) thì vẽ cung Ti Tj  Nếu G có chu trình S không khả tuần tự 69  Nếu G không có chu trình S conflict-serializable
  70. Lịch biểu tuần tự, khả tuần tự  Lịch biểu tuần tự T1: R(X) T2: W(X) T3: R(X) W(X) W(Y) R(Y) Commit Commit Commit  A) Lịch biểu sau là tuần tự S={W2(X), W2(Y), R2(Z), C2, R1(X), W1(X), C1, R3(X), R3(Y), R3(Z), C3}  B) Lịch biểu sau là khả tuần tự S={W2(X), R1(X), W1(X), C1, R3(X), W2(X), R3(Y), R2(Z),C2, R3(Z), C3} 70
  71. Ví dụ  S1: W2(X),W1(X),R3(X),R1(X),W2(Y),R3(Y),R3(X),R2(X)  Bất khả tuần tự vì đồ thị có chu trình 71
  72. Ví dụ  S1:R2(Z),W2(X),W2(Y),W1(X),R1(X),R3(X),R3(Z),R3(Y)  Khả tuần tự vì đồ thị không có chu trình 72
  73. Bài tập  T T T T2 S T3 S 1 2 3 Read(A) Read(B) 2 3 Write(A) Read(A) Write(B) Write(A)  T1 S T2 Read(B) Write(B) 1 2 73 Lịch có khả tuần tự không?
  74. Bài tập T T T S 1 2 3 Read(A) Read(B) Write(A) Read(B) Read(A) Write(B) Write(A) Write(B) Lịch có khả tuần tự không? 74
  75. Bài tập S T1 T2 T3 T4 Write(A) Read(A) Read(A) Write(A)  Vẽ P(S)  S có conflict-serializable không? 75
  76. Bài tập T T T T S 1 2 3 4 Write(A) Write(C) Read(A) Write(B) Read(C) Write(A) Read(A) Write(D)  Vẽ P(S)  S có conflict-serializable không? 76
  77. View-Serializability  Xét lịch S T T T S 1 2 3 Read(A) Write(A) 1 2 Write(A) Write(A) 3  P(S) có chu trình  S không conflict-serializable 77
  78. View-Serializability (tt)  So sánh lịch S và 1 lịch tuần tự S’ T T T T T T S 1 2 3 S’ 1 2 3 Read(A) Read(A) Write(A) Write(A) Write(A) Write(A) Write(A) Write(A) Không conflict-serializable Serial  Trong S và S’ đều có T1 thực hiện read(A)  T2 và T3 không đọc A  Kết quả của S và S’ giống nhau Giải thích như thế nào đây? 78
  79. View-Serializability (tt)  Ý tưởng  Xét trường hợp T U Write(A) Read(A)  Nhận xét  Sau khi T ghi A xong mà không có giao tác nào đọc giá trị của A  Khi đó, hành động wT(A) có thể chuyển đến 1 vị trí khác trong lịch thao tác mà ở đó cũng không có giao tác nào đọc A  Ta nói  Hành động rU(A) có gốc là giao tác T 79
  80. View-Serializability (tt)  Định nghĩa  S, S’ là những lịch thao tác view-equivalent  1- Nếu trong S có wj(A) rj(A) thì trong S’ cũng có wj(A) rj(A)  2- Nếu trong S có ri(A) là thao tác đọc giá trị ban đầu của A thì trong S’ cũng ri(A) đọc giá trị ban đầu của A  3- Nếu trong S có wi(A) là thao tác ghi giá trị sau cùng lên A thì trong S’ cũng có wi(A) ghi giá trị sau cùng lên A  Một lịch thao tác S là view-serializable  Nếu S là view-equivalent với một lịch thao tác tuần tự nào đó  S view-serializable S conflict-serializable  S view-serializable  S conflict-serializable??? 80
  81. View-Serializability (tt)  S conflict-serializable S view-serializable  Chứng minh  Hoán vị các hành động không xung đột  Không làm ảnh hưởng đến những thao tác đọc  Cũng không làm ảnh hưởng đến trạng thái CSDL 81
  82. View-Serializability (tt)  S view-serializable S conflict-serializable  Trong S có những hành động ghi không có tác dụng (useless)  S = w2(A) w3(A) Không có hành động đọc A S T1 T2 T3 Read(A) Write(A) Write(A) Write(A) 82
  83. View-Serializability (tt) 83
  84. View-Serializability (tt)  Quan sát lịch S thấy các giao dịch T4 và T6 thực hiện các giao tác write (A) mà không thực hiện một lệnh Read (A) nào. Các thao tác này gọi là thao tác mù. Các thao tác ghi mù xuất hiện trong một lịch biểu view- serializability nào đó thì lịch biểu không conflict serializability 84
  85. Các kỹ thuật khóa dữ liệu  Giới thiệu  Kỹ thuật khóa đơn giản  Kỹ thuật khóa đọc ghi  Kỹ thuật khóa 2 pha 85
  86. Giới thiệu  Các giao tác trước khi muốn đọc/viết lên 1 đơn vị dữ liệu phải phát ra 1 yêu cầu xin khóa (lock) đơn vị dữ liệu đó  Lock(A) hay L(A)  Yêu cầu này được bộ phận quản lý khóa xử lý  Nếu yêu cầu được chấp thuận thì giao tác mới được phép đọc/ghi lên đơn vị dữ liệu  Sau khi thao tác xong thì giao tác phải phát ra lệnh giải phóng đơn vị dữ liệu (unlock) 86  Unlock(A) hay u(A)
  87. Kỹ thuật khóa đơn giản  Nếu xuất hiện 2 giao tác tương tranh thì áp dụng cơ chế chờ: một giao tác xử lý hạt dữ liệu A sẽ khóa hạt dữ liệu này cho đến khi hòan tất. Các giao tác còn lại phải chờ cho đến khi hạt dữ liệu này được giải phóng  Trước khi muốn thao tác lên 1 đơn vị dữ liệu A thì phải phát ra 1 yêu cầu xin khóa trên A  Nếu yêu cầu trên khóa A được chấp thuận thì được thao tác trên A (Lock). Sau khi thao tác xong thì phải phải phát ra lệnh giải phóng A (Unlock)  Nếu yêu cầu trên khóa không được chấp thuận thì chờ  Hai kiểu khóa  Khóa đọc (Read lock): chỉ cho phép một giao tác đọc  Khóa ghi (Write lock): cho phép cả hai giao tác đọc và ghi  Bộ phận cấp phát khóa (lock manager) sẽ chỉ cấp phát trên A nếu 87 A tự do
  88. Kỹ thuật khóa đơn giản (tt) Nguyên tắc khó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. Nếu giao tác đã lock trên dvdt thì sau đó phải unlock  Tính hợp lệ Không thể có 2 giao tác đồng thời khóa trên 1 đvdl 88
  89. Kỹ thuật khóa đơn giản (tt) 89
  90. Ví dụ lịch hợp lệ và giao tác đúng T T S 1 2 Lock(A) Read(A,t) t:=t+100 Write(A,t) Unlock(A) Lock(A) Read(A,s) s:=s*2 Write(A,s) Unlock(A) Lock(B) Read(B,s) s:=s*2 Write(B,s) Unlock(B) Lock(B) Read(B,t) t:=t+100 Write(B,t) Unlock(B) 90
  91. Ví dụ  Nếu lịch S hợp lệ thì S có khả tuần tự không? T T A B S 1 2 25 25 Lock(A); Read(A,t) t:=t+100 Write(A,t); Unlock(A) 125 Lock(A); Read(A,s) s:=s*2 Write(A,s); Unlock(A) 250 Lock(B); Read(B,s) s:=s*2 Write(B,s); Unlock(B) 50 Lock(B); Read(B,t) t:=t+100 Write(B,t); Unlock(B) 150 91
  92. Bài tập  Cho biết lịch nào hợp lệ? Giao tác nào là đúng? T1 T2 T3 T1 T2 T3 S1 S2 Lock(A) Lock(A) Lock(B) Read(A) Read(A) Write(B) Write(B) Unlock(A) Lock(B) Unlock(B) Unlock(A) Lock(B) Unlock(B) Read(B) Read(B) Write(B) Write(B) Lock(B) Unlock(B) Read(B) Lock(B) Unlock(B) Read(B) Unlock(B) 92
  93. Bài tập  Cho biết lịch nào hợp lệ? Giao tác nào là đúng? T1 T2 T3 S3 Lock(A) Read(A) Unlock(A) Lock(B) Write(B) Unlock(B) Lock(B) Read(B) Write(B) Unlock(B) Lock(B) Read(B) Unlock(B) 93
  94. Kỹ thuật khóa đơn giản (tt)  Các trường hợp cần tránh  Khóa sống (live lock): khóa nhưng không giải phóng làm cho các giao tác phải chờ vô tận  T1 yêu cầu khóa trên B, T2 yêu cầu khóa trên B  T1 yêu cầu trước nên B được T1 khóa, nhưng T1 không giải phóng B nên T2 không thể khóa B mà phải chờ vô tận  Khóa chết (dead lock): trường hợp 2 hay nhiều giao tác chờ đợi lẫn nhau. Giả sử T1 đang khóa A và chờ B được giải phóng để khóa; trong khi T2 đang khóa B và chờ A được giải phóng để khóa A. Các yêu cầu khóa A,B như vậy dẫn đến sự chờ trở nên vô hạn. 94
  95. Ví dụ Live-Lock  Để giải quyết vấn đề này thì lock Manager phải tinh tế hơn bằng cách ghi nhận thứ tự xin khóa 95
  96. Ví dụ DeadLock  Kỹ thuật ngăn ngừa deadlock  Ép người viết chương trình viết không bao giờ deadLock có thể xảy ra ngăn ngừa deadlock  HQT theo dõi nếu có deadlock sẽ báo cho admin biết để xử lý 96
  97. Giải phát 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?  Dùng thời gian chờ.  Dùng đồ thị chờ  Ngăn ngừa Deadlock  Sắp xếp các đơn vị dữ liệu theo một thứ tự cố định và các giao tác yêu cầu lock trên chúng theo thứ tự này.  Các giao tác chờ lần nhau deadlock. Các transaction 97 chờ theo 1 chiều nhất định ngăn ngừa deadlock.
  98. Đồ thị chờ Khi có trình trạng deadlock xảy ra, hệ thống hủy trình trạng deadlock. Dùng đồ thị chờ để phát hiện deadlock  Cho S là lịch giao 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 Ti phải chờ Tj  Đồ 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. 98
  99. Ví dụ T1 T2 T3 T4 1 L(A); R(A) 2 L(C); R(C) 3 L(B); R(B) 4 L(D); R(D) 5 L(A) 6 L(C) 7  Chờ L(A) 8 L(B)  Chờ  Chờ  Chờ T T T T 1 2 3 4 99
  100. Ví dụ T1 T2 T3 T4 1 L(A); R(A) 2 L(C); R(C) 3 L(B); R(B) 4 L(D); R(D) 5 L(A) 6 L(C) 7 L(A) 8 L(B) T T T T 1 2 3 4 100
  101. Kỹ thuật khóa 2 giai đoạn (2PL)  Qui tắc  (3) Giao tác 2PL S : li(A) ui(A) không có unlock không có lock Đơn vị dữ liệu Thực hiện xong hết tất cả giữ các yêu cầu lock rồi mới lock BOT EOT tiến hành unlock của Ti t Phase lock Phase unlock 101
  102. Kỹ thuật khóa 2 giai đoạn (tt) T3 T1 Lock(B) Lock(A) T2 T Read(B) 4 Read(A) Lock(B) Lock(A) B=B-50 Lock(B) Read(B) Read(A) Write(B) Read(B) Lock(A) Unlock(A) Unlock(B) B:=B+A Read(A) Lock(B) Lock(A) Write(B) Unlock(B) Read(B) Read(A) Unlock(A) A:=A+B Unlock(B) A=A+50 Unlock(B) Write(A) Pritn(A+B) Unlock(A) Write(A) Unlock(A) Thỏa nghi thức khóa 2 giai đoạn Không thỏa nghi thức khóa 2 giai đoạn 102
  103. Ví dụ T T T T S 1 2 S 1 2 Lock(A); Read(A,t) Read(A,t) t:=t+100; Write(A,t) t:=t+100 Lock(B); Unlock(A) Write(A,t) Lock(A); Read(A,s) Read(A,s) s:=s*2; Write(A,s) s:=s*2 Lock(B) Write(A,s) Read(B,t); t:=t+100 Chờ Read(B,t) Write(B,t); Unlock(B) t:=t+100 Lock(B); Ulock(A) Write(B,t) Read(B,t); t:=t*2 Read(B,s) Write(B,t); s:=s*2 Unlock(B) Write(B,s) 103
  104. Ví dụ T T S 1 2 Lock(A) Read(A,t) Lock(B) Read(B,s) t:=t+100 s:=s*2 Write(A,t) Write(B,s) Không xin Lock(B) được lock Lock(A) Không xin  được lock Chờ  Chờ 104
  105. Bài tập T T S 1 2 RL(A) Read(A) UL(A) RL(B) Read(B)  S có khả tuần tự không? UL(B)  WL(A) Giao tác nào không thỏa 2PL? Read(A) A:=A+B Write(A) UL(A) WL(B) Read(B) B:=B+A Write(B) 105 UL(B)
  106. Bài tập T1 T2 T3 T4 RL(A) RL(A) WL(B) UL(A) WL(A)  S có khả tuần tự hay không? UL(B) RL(B)  Giao tác nào không thỏa 2PL? UL(A) RL(B) RL(A) UL(B) WL(C) UL(A) WL(B) UL(B) UL(B) 106 UL(C)
  107. Kỹ thuật khóa đọc ghi Ti Tj Lock(A) Read(A) Unlock(A) Lock(A) Read(A) Unlock(A)  Bộ lập lịch có các hành động  Khóa đọc (Read lock, Shared lock)  RLock(A) hay rl(A)  Khóa ghi (Write lock, Exclusive lock)  WLock(A) hay wl(A)  Giải phóng khóa  Unlock(A) hay u(A) 107
  108. Kỹ thuật khóa đọc ghi (tt)  Cho 1 đơn vị dữ liệu A bất kỳ WLock(A)  Hoặc có 1 khóa ghi duy nhất lên A  Hoặc không có khóa ghi nào lên A RLock(A)  Có thể có nhiều khóa đọc được thiết lập lên A 108
  109. Kỹ thuật khóa đọc ghi (tt)  Giao tác muốn Write(A)  Yêu cầu WLock(A)  WLock(A) sẽ được chấp thuận nếu A tự do  Sẽ không có giao tác nào nhận được WLock(A) hay RLock(A)  Giao tác muốn Read(A)  Yêu cầu RLock(A) hoặc WLock(A)  RLock(A) sẽ được chấp thuận nếu A không đang giữ một WLock nào  Không ngăn chặn các thao tác khác cùng xin Rlock(A)  Các giao tác không cần phải chờ nhau khi đọc A  Sau khi thao tác xong thì giao tác phải giải phóng khóa trên đơn vi dữ liệu A 109  ULock(A)
  110. Kỹ thuật khóa đọc ghi (tt)  Qui tắc  (1) Giao tác đúng đắn Ti : rl(A) r(A) u(A) Ti : wl(A) w(A) u(A)  (2) 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) 110 không có rlj(A)
  111. Bài tập  Trong các giao tác trong lịch trên giao tác nào viết đúng nghi thức khoá hai giai đoạn? 111
  112. Kỹ thuật nhãn thời gian (timestamps)  Giới thiệu  Nhãn thời gian của giao tác  Nhãn thời gian của đơn vị dữ liệu  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 (multiversion) 112
  113. Giới thiệu  Nguyên lý cơ bản của lịch khả tuần tự  Sắp xếp thứ tự các thao tác khi chúng được gọi thực hiện  Kiểm soát các truy xuất tranh chấp trên dữ liệu; phải đảm bảo các truy xuất tôn trọng thứ tự trước sau của giao tác  Chọn một thứ tự thực hiện nào đó cho các giao tác bằng cách gán nhãn thời gian (timestamping)  Mỗi giao tác T sẽ có 1 nhãn, ký hiệu TS(T)  Tại thời điểm giao tác bắt đầu  Thứ tự của các nhãn tăng dần  Giao tác bắt đầu trễ thì sẽ có nhãn thời gian lớn hơn các giao 113 tác bắt đầu sớm
  114. Nhãn thời gian của giao tác 114
  115. Nhãn thời gian của đơn vị dữ liệu 115
  116. Nhãn thời gian toàn phần  Mỗi giao tác T khi phát sinh sẽ được gán 1 nhãn TS(T) ghi nhận lại thời điểm phát sinh của T.  Mỗi đơn vị dữ liệu X cũng có 1 nhãn thời TS(X), nhãn này ghi lại TS(T) của giao tác T đã thao tác read/write thành công sau cùng lên X.  Khi đến lượt giao tác T thao tác trên dữ liệu X, so sánh TS(T) và TS(X). 116
  117. Nhãn thời gian toàn phần (tt) Read(T, X) Write(T, X) If TS(X) <= TS(T) If TS(X) <= TS(T) Read(X); Write(X); //cho phép đọc X //cho phép ghi X TS(X):= TS(T); TS(X):= TS(T); Else Else Abort {T}; Abort {T}; //hủy bỏ T //hủy bỏ T //khởi tạo lại TS //khởi tạo lại TS 117
  118. Ví dụ T1 T2 A B TS(T1)=100)=300 TS(T2)=200 TS(A)=0 TS(B)=0 1 Read(A) TS(A)=100 TS(A) TS(T1) : T1 không đọc được B Abort Khởi tạo lại TS(T1) TS(T2) TS(T1) Lịch khả tuần tự theo thứ tự {T2, T1} 118
  119. Ví dụ  Nhận xét T1 T2 A T1 T2 A TS(T1)=100 TS(T2)=120 TS(A)=0 TS(T1)=100 TS(T2)=120 TS(A)=0 Read(A) TS(A)=100 Read(A) TS(A)=100 Read(A) TS(A)=120 Read(A) TS(A)=120 Write(A) TS(A)=120 Read(A) TS(A)=120 Write(A) Read(A) T1 bị hủy và bắt đầu thực hiện lại T1 bị hủy và bắt đầu thực hiện lại với timestamp mới với timestamp mới Không phân biệt tính chất của thao tác là đọc hay viết T1 vẫn bị hủy và làm lại từ đầu với 1 timestamp mới
  120. Nhãn thời gian riêng phần  Nhãn của đơn vị dữ liệu X được tách ra thành 2  RT(X) - read  Ghi nhận TS(T) gần nhất đọc X thành công  WT(X) - write  Ghi nhận TS(T) gần nhất ghi X thành công 120
  121. Nhãn thời gian riêng phần (tt)  Công việc của bộ lập lịch  Gán nhãn RT(X), WT(X) và C(X)  Kiểm tra thao tác đọc/ghi xuất hiện vào lúc nào  Có xãy ra tình huống  Đọc quá trễ  Ghi quá trễ  Đọc dữ liệu rác (dirty read)  Qui tắc ghi Thomas 121
  122. Nhãn thời gian riêng phần (tt)  Đọc quá trễ U ghi X T đọc X  ST(T) ST(U)  U ghi X trước,T đọc X sau  ST(T) <WT(X)  T không thể đọc X sau U HủyT T bắt đầu U bắt đầu 122
  123. Nhãn thời gian riêng phần (tt)  Ghi quá trễ U đọc X T ghi X  ST(T) ST(U)  U đọc X trước,T ghi X sau  WT(X) < ST(T) < RT(X)  U phải đọc được giá trị X được ghi bởiT T bắt đầu U bắt đầu HủyT 123
  124. Nhãn thời gian riêng phần (tt)  Đọc dữ liệu rác T ghi X U đọc X  ST(T) ST(U)  T ghi X trước, U đọc X sau  Thao tác bình thường  NhưngT hủy  U đọc X sau khiT commit  U đọc X sau khiT abort T bắt đầu U bắt đầu T hủy 124
  125. Nhãn thời gian riêng phần (tt)  Qui tắc ghi Thomas  ST(T) ST(U) U ghi X  U ghi X trước,T ghi X sau T ghi X  ST(T) <WT(X)  T ghi X xong thì không làm được gì  Không có giao tác nào đọc được giá trị X của T (nếu có cũng bị hủy do đọc T bắt đầu U bắt đầu quá trễ)  Các giao tác đọc sau T và U thì mong muốn đọc giá trị X của U Bỏ qua thao tác ghi củaT 125
  126. Nhãn thời gian riêng phần (tt)  Qui tắc ghi Thomas  Nhưng U hủy U ghi X  Giá trị của X được ghi bởi U bị mất  ầ ụ ạ ị ướ đ T ghi X C n khôi ph c l i giá tr X tr c ó  VàT đã kết thúc  X có thể khôi phục từ thao tác ghi củaT  Do qui tắc ghiThomas  Thao tác ghi đã được bỏ qua T bắt đầu U bắt đầu T kết thúc U hủy  Quá trễ để khôi phục X 126
  127. Nhãn thời gian riêng phần (tt)  Qui tắc ghi Thomas U ghi X T ghi X  KhiT muốn ghi  ChoT thử ghi và sẽ gỡ bỏ nếuT hủy  Sao lưu giá trị cũ của X và nhãn WT(X) trước đó T bắt đầu U bắt đầu T kết thúc U hủy 127
  128. Nhãn thời gian riêng phần (tt) If WS(X) <= TS(T) Read(X);//cho phép đọc X Read(T, X) RT(X):= max(RT(X),TS(T)); Else Rollback{T}; //hủy T và khởi tạo lại TS mới If RT(X) <= TS(T) If WT(X) <= TS(T) Write(X);//cho phép ghi X Write(T, X) WT(X):= TS(T); //Else không làm gì cả Else Rollback{T}; //hủy T và khởi tạo lại TS mới 128
  129. Ví dụ T1 T2 A B C RT(A)=0 RT(B)=0 RT(C)=0 TS(T1)=100 TS(T2)=200 WT(A)=0 WT(B)=0 WT(C)=0 WT(A) TS(T1) T1 không ghi lên C được 129 Abort
  130. Ví dụ T1 T2 T3 A B C RT=0 RT=0 RT=0 TS=200 TS=150 TS=175 WT=0 WT=0 WT=0 Read(B) RT=200 WT=0 Read(A) RT=150 WT=0 Read(C) RT=175 WT=0 Write(B) RT=200 WT=200 Write(A) RT=150 WT=200 Write(C) Write(A) Rollback Giá trị của A đã sao lưu bởi T1 T3 không bị rollback và không cần ghi A 130
  131. Ví dụ T1 T2 T3 T4 A RT=0 TS=150 TS=200 TS=175 TS=255 WT=0 Nhận xét Read(A) RT=150 •Thao tác read3(A) làm cho WT=0 giao tác T3 bị hủy Write(A) RT=150 •T3 đọc giá trị của A sẽ WT=150 được ghi đè trong tương lai Read(A) RT=200 bởi T2 WT=150 •Giả sử nếu T3 đọc được giá Write(A) RT=200 trị của A do T1 ghi thì sẽ WT=200 không bị hủy Read(A) Read(A) RT=255 WT=200 131 Rollback
  132. Bài tập  Dùng kỹ thuật timestamp từng phần để điều khiển truy xuất đồng thời của 4 giao tác trên, với timestamp của các giao tác T1, T2, T3, T4 lần lượt là: a) 300, 310, 320, 330 b) 250, 200, 210, 275 132
  133. Bài tập 133
  134. 1) Lịch S có khả tuần tự không? Nếu có thì tương đương với lịch tuần tự nào. 2) Thay Rlock bởi Read, thay Wlock bởi Write, bỏ qua các thao tác Unlock. Dùng kỹ thuật timestamp từng phần để điều khiển việc truy xuất đồng thời của các giao tác biết các timestamp của các giao tác là T1=100, T2=300, T3=200, T4=400, T5=500. 134
  135. Nhãn thời gian nhiều phiên bản  Mỗi đơn vị dữ liệu có thể có nhiều phiên bản cho từng giao tác.  Mỗi phiên bản của 1 đơn vị dữ liệu X có  RT(X)  Ghi nhận lại giao tác sau cùng đọc X thành công  WT(X)  Ghi nhận lại giao tác sau cùng ghi X thành công  Khi giao tác T phát ra yêu cầu thao tác lên X  Tìm 1 phiên bản thích hợp của X  Đảm bảo tính khả tuần tự  Một phiên bản mới của X sẽ được tạo khi hành động ghi X 135 thành công
  136. Thuật tóan 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) Write(T, X) Rollback T//Hủy và khởi tạo TS mới Else Tạo phiên bản Ai+1; Write(Xi+1); RT(Xi+1) = 0;//chưa có ai đọc WT(X ) = TS(T); 136 i+1
  137. Ví dụ T1 T2 T3 T4 A0 A1 A2 RT=0 TS=150 TS=200 TS=175 TS=255 WT=0 Read(A) RT=150 WT=0 Write(A) RT=0 WT=150 Read(A) RT=200 WT=150 Write(A) RT=0 WT=200 Read(A) RT=200 WT=150 Read(A) RT=255 WT=200 137
  138. Ví dụ (tt) T1 T2 A0 A1 A2 B1 RT=0 RT=0 TS=100 TS=200 WT=0 WT=0 Read(A) RT=100 WT=0 Write(A) RT=0 RT=0 WT=200 WT=200 Write(B) RT=0 WT=200 Read(B) RT=100 WT=0 RT=0 Write(A) WT=100 138
  139. Nhãn thời gian nhiều phiên bản (tt)  Nhận xét  Thao tác đọc  Giao tác T chỉ đọc giá trị của phiên bản do T hay những giao tác trước T cập nhật  T không đọc giá trị của các phiên bản do các giao tác sau T cập nhật Thao tác đọc không bị rollback  Thao tác ghi  Thực hiện được bằng cách chèn thêm phiên bản mới  Không thực hiện được thì rollback  Tốn nhiều chi phí tìm kiếm, tốn bộ nhớ  Nên giải phóng các phiên bản quá cũ không còn được các giao tác sử dụng 139
  140. Nhận xét  Khóa & nhãn thời gian  Nếu các giao tác chỉ thực hiện đọc không thôi thì kỹ thuật nhãn thời gian tốt hơn  Ít có tình huống các giao tác cố gắng đọc và ghi cùng 1 đơn vị dữ liệu  Nhưng kỹ thuật khóa sẽ tốt hơn trong những tình huống xãy ra tranh chấp  Kỹ thuật khóa thường hay trì hoãn các giao tác để chờ xin được khóa  Dẫn đến deadlock  Nếu có các giao tác đọc và ghi cùng 1 đơn vị dữ liệu thì việc rollback là thường xuyên hơn 140