Chương 2: Những vấn đề khác trong điều kiển đồng thời

Chia sẻ: Lê Trinh | Ngày: | Loại File: PDF | Số trang:12

Thêm vào BST

Báo xấu

72
lượt xem 8
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tham khảo bài thuyết trình 'chương 2: những vấn đề khác trong điều kiển đồng thời', công nghệ thông tin, cơ sở dữ liệu phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Chương 2: Những vấn đề khác trong điều kiển đồng thời

Chương 2 Những vấn đề khác trong điều kiển đồng thời Nội dung chi tiết z Quay lui dây chuyền (cascading rollback) z Lịch khả phục hồi (recoverable schedule) z Deadlock z Phát hiện (detection) z Ngăn ngừa (prevention) Những vấn đề khác trong điều khiển đồng thời 2 Ví dụ T1 T2 A B S 25 25 Lock(A); Read(A,t) t:=t+100; Write(A,t) 125 Lock(B); Unlock(A) Lock(A); Read(A,s) s:=s*2; Write(A,s) 250 Lock(B) Read(B,t); t:=t+100 Chờ Write(B,t); Unlock(B) 125 Lock(B); Ulock(A) Read(B,t); t:=t*2 Write(B,t); Unlock(B) 250 Những vấn đề khác trong điều khiển đồng thời 3 1
Ví dụ (tt) T1 T2 A B S 25 25 Lock(A); Read(A,t) t:=t+100; Write(A,t) 125 Lock(B); Unlock(A) Lock(A); Read(A,s) s:=s*2; Write(A,s) 250 Lock(B) Read(B,t); Chờ Abort; Unlock(B); Lock(B); Ulock(A) Read(B,t); t:=t*2 Write(B,t); Unlock(B) 50 Tính nhất quán bị vi phạm → T2 cũng phải rollback Những vấn đề khác trong điều khiển đồng thời 4 Ví dụ (tt) T1 T2 T3 A B C S RT=0 RT=0 RT=0 200 150 175 WT=0 WT=0 WT=0 RT=0 Write(B) WT=150 RT=200 Read(B) WT=150 RT=150 Read(A) WT=0 RT=175 Read(C) WT=0 Write(C) RT=0 → Phục hồi Abort WT=0 giá trị của B RT=150 Write(A) WT=175 Những vấn đề khác trong điều khiển đồng thời 5 Quay lui dây chuyền T1 T2 T3 T4 . . . . . . . . . . . . . . w(A) . . . . . . . r(A) . . . . . . . . . r(A) abort . . . abort . abort Những vấn đề khác trong điều khiển đồng thời 6 2
Lịch khả phục hồi Ti Tj . . . . . . . w(A) . . . . r(A) . . commit . . abort z Xét mỗi cặp Ti và Tj sao cho z Tj đọc dữ liệu sau khi Ti ghi z Ti phải được hoàn tất (commit) trước khi Tj hoàn tất z Ký hiệu ci: giao tác thứ i hoàn tất Những vấn đề khác trong điều khiển đồng thời 7 Lịch khả phục hồi (tt) S1 : w1(A); w 1(B); w2(A); r2(B); c1; c2; T2 đọc B sau T1 hoàn tất T1 ghi B trước T2 S1 tuần tự và khả phục hồi Những vấn đề khác trong điều khiển đồng thời 8 Lịch khả phục hồi (tt) S2 : w2(A); w 1(B); w1(A); r2(B); c1; c2; T1 ghi B trước T1 hoàn tất T2 đọc B sau trước T2 S2 không khả tuần tự nhưng khả phục hồi Những vấn đề khác trong điều khiển đồng thời 9 3
Lịch khả phục hồi (tt) S3 : w1(A); w 1(B); w2(A); r2(B); c2; c1; T1 ghi B trước T2 hoàn tất T2 đọc B sau trước T1 S3 khả tuần tự nhưng không khả phục hồi Những vấn đề khác trong điều khiển đồng thời 10 Lịch khả phục hồi (tt) z Nhận xét z Muốn khôi phục đôi khi cần quay lui dây chuyền z Nhưng quay lui dây chuyền không thể xãy ra z Tốn nhiều chi phí → Lịch không quay lui dây chuyền (cascadeless schedule) Những vấn đề khác trong điều khiển đồng thời 11 Lịch không quay lui dây chuyền Ti Tj . . . . . . . w(A) . . commit . . r(A) Các giao tác chỉ đọc những giá trị đã được hoàn tất Những vấn đề khác trong điều khiển đồng thời 12 4
Lịch không quay lui dây chuyền (tt) z Khả phục hồi S1 : w1(A); w 1(B); w2(A); r2(B); c1; c2; z Ngăn ngừa quay lui dây chuyền S1 : w1(A); w 1(B); w2(A); c1; r2(B); c2; z → Các lịch ngăn ngừa quay lui dây chuyền đều khả phục hồi Những vấn đề khác trong điều khiển đồng thời 13 Nội dung chi tiết z Quay lui dây chuyền (cascading rollback) z Lịch khả phục hồi (recoverable schedule) z Deadlock z Phát hiện (detection) z Ngăn ngừa (prevention) Những vấn đề khác trong điều khiển đồng thời 14 Deadlock z Nhắc lại 2 tình huống T1 T2 T1 T2 S S Lock(A) RLock(A) Read(A) Read(A) Lock(B) RLock(A) Read(B) Read(A) Write(A) WLock(A) Write(B) ↓ WLock(A) Lock(B) Chờ ↓ Chờ ↓ Lock(A) Chờ ↓ Chờ Nâng cấp khóa Qui tắc khóa 2PL Những vấn đề khác trong điều khiển đồng thời 15 5
Deadlock (tt) z Hệ thống rơi vào trạng thái deadlock khi z Các giao tác phải chờ đợi lẫn nhau để được thao tác lên các đơn vị dữ liệu bị khóa bởi chúng z Và không một giao tác nào có thể thực hiện tiếp công việc của mình Những vấn đề khác trong điều khiển đồng thời 16 Giải quyết Deadlock z Phát hiện z Cho phép trạng thái deadlock xãy ra và sau đó cố gắng khôi phục lại hệ thống z Chọn 1 giao tác để rollback z Phương pháp z Đồ thị chờ (wait-for graph) z Ngăn ngừa z Quản lý các giao tác sao cho không bao giờ có deadlock z Phương pháp z Sắp thứ tự tài nguyên (resource ordering) z Timeout z Wait-die z Wound-wait Những vấn đề khác trong điều khiển đồng thời 17 Đồ thị chờ z Đồ thị gồm z Đỉnh là các giao tác đang giữ khóa hoặc đang chờ khóa z Cung đi từ đỉnh T sang U khi z U đang giữ khóa trên đơn vị dữ liệu A z T đang chờ khóa trên A z T không thể khóa đơn vị dữ liệu A nếu U không giải phóng khóa z Nếu đồ thị chờ không có chu trình z Các giao tác có thể hoàn tất z Ngược lại z Không một giao tác nào trong chu trình có thể tiếp tục thực hiện → deadlock Những vấn đề khác trong điều khiển đồng thời 18 6
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) Chờ 7 ↓ L(A) Chờ 8 L(B) ↓ Chờ ↓ Chờ T1 T2 T3 T4 Những vấn đề khác trong điều khiển đồng thời 19 Ví dụ (tt) 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) T1 T2 T3 T4 Những vấn đề khác trong điều khiển đồng thời 20 Sắp thứ tự tài nguyên z Áp đặt một thứ tự nào đó lên các đơn vị dữ liệu z Nếu các giao tác thực hiện khóa những đơn vị dữ liệu theo thứ tự này z Thì không có deadlock xãy ra trong khi chờ đợi z Chứng minh z Bài tập về nhà Những vấn đề khác trong điều khiển đồng thời 21 7
Ví dụ z Giả sử các đơn vị dữ liệu được sắp thứ tự theo alphabet T1 : l(A); r(A); l(B); w(B); u(A); u(B); T2 : l(C); r(C); l(A); w(A); u(C); u(A); T3 : l(B); r(B); l(C); w(C); u(B); u(C); T4 : l(D); r(D); l(A); w(A); u(D); u(A); Những vấn đề khác trong điều khiển đồng thời 22 Ví dụ (tt) T1 : l(A); r(A); l(B); w(B); u(A); u(B); T2 : l(A); l(C); r(C); w(A); u(C); u(A); T3 : l(B); r(B); l(C); w(C); u(B); u(C); T4 : l(A); l(D); r(D); w(A); u(D); u(A); Những vấn đề khác trong điều khiển đồng thời 23 Ví dụ (tt) T1 T2 T3 T4 1 L(A); R(A) 2 L(A) 3 ↓ L(B); R(B) Chờ 4 L(A) 5 L(C); W(C) ↓ Chờ 6 U(B); U(C) 7 L(B); R(B) 8 U(A); U(B) 9 L(A); L(C) 10 R(A); W(C) 11 U(C); U(A) 12 L(A); L(D) 13 R(D); W(A) 14 U(D); U(A) Những vấn đề khác trong điều khiển đồng thời 24 8
Timeout z Giới hạn các giao tác chỉ được thực hiện trong 1 khoảng thời gian nào đó z Nếu giao tác vượt quá thời gian này z Thì giao tác phải bị rollback Những vấn đề khác trong điều khiển đồng thời 25 Wait-die z Mỗi giao tác sẽ được gán một nhãn ghi nhận thứ tự xuất hiện, kí hiệu: ts(T) z Xét 2 giao tác T và U z U đang giữ khóa trên đơn vị dữ liệu A z T muốn khóa đơn vị dữ liệu A z T sẽ chờ-wait U khi ts(T) < ts(U) T U z Ngược lại T sẽ bị hủy-die và bắt đầu làm lại ở 1 thời T U điểm khác Những vấn đề khác trong điều khiển đồng thời 26 Ví dụ T1 T2 T3 T4 1 L(A); R(A) 2 L(A) 3 ↓ L(B); R(B) Dies 4 L(A) 5 L(C); W(C) ↓ Dies 6 U(B); U(C) 7 L(B); R(B) 8 U(A); U(B) Những vấn đề khác trong điều khiển đồng thời 27 9
Ví dụ (tt) z T2 bắt đầu trước T4 T1 T2 T3 T4 1 L(A); R(A) 2 L(A) 3 ↓ L(B); R(B) Dies 4 L(A) 5 L(C); W(C) ↓ Dies 6 U(B); U(C) 7 L(B); R(B) 8 U(A); U(B) 9 L(A); L(C) 10 L(A) 11 R(A); W(C) ↓ Dies 12 U(C); U(A) 13 L(A); L(D) 14 R(D); W(A) 15 U(D); U(A) Những vấn đề khác trong điều khiển đồng thời 28 Ví dụ (tt) z T4 bắt đầu trước T2 T1 T2 T3 T4 1 L(A); R(A) 2 L(A) 3 ↓ L(B); R(B) Dies 4 L(A) 5 L(C); W(C) ↓ Dies 6 U(B); U(C) 7 L(B); R(B) 8 U(A); U(B) 9 L(A); L(D) 10 L(A) 11 ↓ R(D); W(A) Waits 12 U(D); U(A) 13 L(A); L(C) 14 R(A); W(C) 15 U(C); U(A) Những vấn đề khác trong điều khiển đồng thời 29 Wound-wait z Mỗi giao tác sẽ được gán một nhãn ghi nhận thứ tự xuất hiện, kí hiệu: ts(T) z Xét 2 giao tác T và U z U đang giữ khóa trên đơn vị dữ liệu A z T muốn khóa đơn vị dữ liệu A z T buộc U rollback và trao khóa lại cho T-wound khi ts(T) < ts(U) T U z Ngoại lệ: nếu U đã kết thúc và giải phóng khóa, U sẽ không rollback z Ngược lại T sẽ chờ-wait U T U Những vấn đề khác trong điều khiển đồng thời 30 10
Ví dụ T1 T2 T3 T4 1 L(A); R(A) 2 L(A) 3 ↓ L(B); R(B) Waits 4 L(A) 5 L(B); R(B) ↓ ↓ Waits 6 U(A); U(B) Wound 7 L(A); L(C) 8 R(A); W(C) 9 U(C); U(A) 10 L(A); L(D) 11 R(D); W(A) 12 U(D); U(A) 13 L(B); R(B) 14 L(C); W(C) 15 U(B); U(C) Những vấn đề khác trong điều khiển đồng thời 31 Nhận xét z Timeout z Đơn giản z Khó chọn được khoảng thời gian timeout thích hợp z Có hiện tượng starvation z Giao tác lập đi lập lại quá trình: bắt đầu, deadlock, rollback z Resource ordering z Không thực tế z Chờ đợi nhiều → tiềm ẩn của deadlock Những vấn đề khác trong điều khiển đồng thời 32 Nhận xét (tt) z Wait-die và Wound-wait z Không có starvation z Wound-wait ít rollback các giao tác hơn wait-die z Dễ cài đặt hơn wait-for graph z Có thể rollback những giao tác không gây ra deadlock z Wait-for graph z Nếu đồ thị quá lớn sẽ tốn nhiều thời gian phân tích z Rất phức tạp khi CSDL phân tán z Giảm tối thiểu rollback các giao tác z Chỉ rollback 1 trong những giao tác gây ra deadlock Những vấn đề khác trong điều khiển đồng thời 33 11
Những vấn đề khác trong điều khiển đồng thời 34 12