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

(cid:122) Quay lui dây chuyền (cascading rollback) (cid:122) Lịch khả phục hồi (recoverable schedule) (cid:122) Deadlock

(cid:122) Phát hiện (detection) (cid:122) Ngăn ngừa (prevention)

Những vấn đề khác trong điều khiển đồng thời

Ví dụ

Những vấn đề khác trong điều khiển đồng thời

A B T1 T2 S 25 25 Lock(A); Read(A,t) 125 t:=t+100; Write(A,t) Lock(B); Unlock(A) Lock(A); Read(A,s) 250 s:=s*2; Write(A,s) Lock(B) Read(B,t); t:=t+100 Chờ 125 Write(B,t); Unlock(B) Lock(B); Ulock(A) Read(B,t); t:=t*2 250 Write(B,t); Unlock(B)

1

Ví dụ (tt)

A B T1 T2 S 25 25 Lock(A); Read(A,t) 125 t:=t+100; Write(A,t) Lock(B); Unlock(A) Lock(A); Read(A,s) 250 s:=s*2; Write(A,s) Lock(B) Read(B,t); Chờ Abort; Unlock(B); Lock(B); Ulock(A) Read(B,t); t:=t*2 50 Write(B,t); Unlock(B)

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

Ví dụ (tt)

T1 T2 T3 S 200 150 175 A RT=0 WT=0 C RT=0 WT=0 B RT=0 WT=0 Write(B) RT=0 WT=150 RT=200 Read(B) WT=150 Read(A) RT=150 WT=0 Read(C) RT=175 WT=0

Write(C) Abort RT=0 WT=0

→ Phục hồi giá trị của B

Những vấn đề khác trong điều khiển đồng thời

Write(A) RT=150 WT=175

Quay lui dây chuyền

T4

T1

T2

T3

. . .

. . . . . .

r(A)

. . . . . . . . .

. . . .

w(A) . . . . . . abort

abort

r(A) . . .

abort

Những vấn đề khác trong điều khiển đồng thời

2

Lịch khả phục hồi

Tj

Ti

. . .

. . . . . .

r(A) commit

w(A) . . . . . . abort

(cid:122) Xét mỗi cặp Ti và Tj sao cho (cid:122) Tj đọc dữ liệu sau khi Ti ghi (cid:122) Ti phải được hoàn tất (commit) trước khi Tj hoàn tất

Những vấn đề khác trong điều khiển đồng thời

(cid:122) Ký hiệu ci: giao tác thứ i hoàn tất

Lịch khả phục hồi (tt)

S1 : w1(A); w1(B); w2(A); r2(B); c1; c2;

T2 đọc B sau T1 ghi B

T1 hoàn tất 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

Lịch khả phục hồi (tt)

S2 : w2(A); w1(B); w1(A); r2(B); c1; c2;

T1 ghi B trước T2 đọc B sau

T1 hoàn tất 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

3

Lịch khả phục hồi (tt)

S3 : w1(A); w1(B); w2(A); r2(B); c2; c1;

T1 ghi B trước T2 đọc B sau

T2 hoàn tất 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

Lịch khả phục hồi (tt)

(cid:122) Nhận xét

(cid:122) Muốn khôi phục đôi khi cần quay lui dây chuyền (cid:122) Nhưng quay lui dây chuyền không thể xãy ra

→ 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

(cid:122) Tốn nhiều chi phí

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

4

Lịch không quay lui dây chuyền (tt)

(cid:122) Khả phục hồi

S1 : w1(A); w1(B); w2(A); r2(B); c1; c2;

(cid:122) Ngăn ngừa quay lui dây chuyền

S1 : w1(A); w1(B); w2(A); c1; r2(B); c2;

(cid:122) → 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

Nội dung chi tiết

(cid:122) Quay lui dây chuyền (cascading rollback) (cid:122) Lịch khả phục hồi (recoverable schedule) (cid:122) Deadlock

(cid:122) Phát hiện (detection) (cid:122) Ngăn ngừa (prevention)

Những vấn đề khác trong điều khiển đồng thời

Deadlock

(cid:122) Nhắc lại 2 tình huống

Những vấn đề khác trong điều khiển đồng thời

T1 T2 T1 T2 S S RLock(A) Lock(A) Read(A) Read(A) RLock(A) Lock(B) Read(A) Read(B) WLock(A) Write(A) WLock(A) Write(B) ↓ ↓ Chờ Lock(B) Chờ Lock(A) ↓ Chờ ↓ Chờ Nâng cấp khóa Qui tắc khóa 2PL

5

Deadlock (tt)

(cid:122) Hệ thống rơi vào trạng thái deadlock khi

(cid:122) 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

(cid:122) 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

Giải quyết Deadlock

(cid:122) Phát hiện

(cid:122) 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 (cid:122) Chọn 1 giao tác để rollback

(cid:122) Phương pháp

(cid:122) Ngăn ngừa

(cid:122) Quản lý các giao tác sao cho không bao giờ có deadlock (cid:122) Phương pháp

(cid:122) Đồ thị chờ (wait-for graph)

Những vấn đề khác trong điều khiển đồng thời

(cid:122) Sắp thứ tự tài nguyên (resource ordering) (cid:122) Timeout (cid:122) Wait-die (cid:122) Wound-wait

Đồ thị chờ

(cid:122) Đồ thị gồm

(cid:122) Đỉnh là các giao tác đang giữ khóa hoặc đang chờ khóa (cid:122) Cung đi từ đỉnh T sang U khi

(cid:122) Nếu đồ thị chờ không có chu trình

(cid:122) Các giao tác có thể hoàn tất

(cid:122) Ngược lại

(cid:122) 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

(cid:122) U đang giữ khóa trên đơn vị dữ liệu A (cid:122) T đang chờ khóa trên A (cid:122) T không thể khóa đơn vị dữ liệu A nếu U không giải phóng khóa

6

Ví dụ

T2 T3 T4 1 T1 L(A); R(A) 2 L(C); R(C) 3 L(B); R(B) 4 L(D); R(D) L(A) 5 L(C) 6 ↓ Chờ L(A) 7 ↓ Chờ L(B) 8 ↓ Chờ ↓ Chờ

Những vấn đề khác trong điều khiển đồng thời

T1 T2 T3 T4

Ví dụ (tt)

T2 T3 T4 1 T1 L(A); R(A) 2 L(C); R(C) 3 L(B); R(B) 4 L(D); R(D) L(A) 5 L(C) 6 L(A) 7 L(B) 8

Những vấn đề khác trong điều khiển đồng thời

T2 T3 T4 T1

Sắp thứ tự tài nguyên

(cid:122) Áp đặt một thứ tự nào đó lên các đơn vị dữ liệu (cid:122) 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

(cid:122) Thì không có deadlock xãy ra trong khi chờ đợi

(cid:122) Chứng minh

(cid:122) Bài tập về nhà

Những vấn đề khác trong điều khiển đồng thời

7

Ví dụ

(cid:122) Giả sử các đơn vị dữ liệu được sắp thứ tự theo

alphabet

l(A); r(A); l(B); w(B); u(A); u(B);

T1 :

l(C); r(C); l(A); w(A); u(C); u(A);

T2 :

l(B); r(B); l(C); w(C); u(B); u(C);

T3 :

l(D); r(D); l(A); w(A); u(D); u(A);

T4 :

Những vấn đề khác trong điều khiển đồng thời

Ví dụ (tt)

l(A); r(A); l(B); w(B); u(A); u(B);

T1 :

l(A); l(C); r(C); w(A); u(C); u(A);

T2 :

l(B); r(B); l(C); w(C); u(B); u(C);

T3 :

l(A); l(D); r(D); w(A); u(D); u(A);

T4 :

Những vấn đề khác trong điều khiển đồng thời

Ví dụ (tt)

Những vấn đề khác trong điều khiển đồng thời

T3 T4 T2 T1 L(A); R(A) 1 2 3 L(B); R(B) L(A) ↓ Chờ 4 L(C); W(C) 5 L(A) ↓ Chờ U(B); U(C) 6 L(B); R(B) 7 U(A); U(B) 8 L(A); L(C) 9 R(A); W(C) 10 U(C); U(A) 11 L(A); L(D) 12 R(D); W(A) 13 U(D); U(A) 14

8

Timeout

(cid:122) Giới hạn các giao tác chỉ được thực hiện trong 1

khoảng thời gian nào đó

(cid:122) Nếu giao tác vượt quá thời gian này (cid:122) Thì giao tác phải bị rollback

Những vấn đề khác trong điều khiển đồng thời

Wait-die

(cid:122) 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)

(cid:122) Xét 2 giao tác T và U

(cid:122) U đang giữ khóa trên đơn vị dữ liệu A (cid:122) T muốn khóa đơn vị dữ liệu A

T U

(cid:122) T sẽ chờ-wait U khi ts(T) < ts(U) (cid:122) Ngược lại T sẽ bị hủy-die và bắt đầu làm lại ở 1 thời điểm khác

Những vấn đề khác trong điều khiển đồng thời

T U

Ví dụ

Những vấn đề khác trong điều khiển đồng thời

T3 T4 T2 T1 L(A); R(A) 1 2 3 L(B); R(B) L(A) ↓ Dies 4 L(C); W(C) 5 L(A) ↓ Dies U(B); U(C) 6 L(B); R(B) 7 U(A); U(B) 8

9

Ví dụ (tt)

(cid:122) T2 bắt đầu trước T4 T2

Những vấn đề khác trong điều khiển đồng thời

T3 T4 T1 L(A); R(A) 1 2 3 L(B); R(B) L(A) ↓ Dies 4 5 L(C); W(C) L(A) ↓ Dies 6 U(B); U(C) 7 L(B); R(B) 8 U(A); U(B) L(A); L(C) 9 10 R(A); W(C) 11 L(A) ↓ Dies U(C); U(A) 12 L(A); L(D) 13 14 R(D); W(A) U(D); U(A) 15

Ví dụ (tt)

(cid:122) T4 bắt đầu trước T2 T2

Những vấn đề khác trong điều khiển đồng thời

T3 T4 T1 L(A); R(A) 1 2 3 L(B); R(B) L(A) ↓ Dies 4 5 L(C); W(C) L(A) ↓ Dies 6 U(B); U(C) 7 L(B); R(B) 8 U(A); U(B) L(A); L(D) 9 L(A) 10 R(D); W(A) 11 ↓ Waits U(D); U(A) 12 L(A); L(C) 13 R(A); W(C) 14 U(C); U(A) 15

Wound-wait

(cid:122) 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)

(cid:122) Xét 2 giao tác T và U

(cid:122) U đang giữ khóa trên đơn vị dữ liệu A (cid:122) T muốn khóa đơn vị dữ liệu A

(cid:122) T buộc U rollback và trao khóa

lại cho T-wound khi ts(T) < ts(U) (cid:122) Ngoại lệ: nếu U đã kết thúc và giải phóng khóa, U sẽ không rollback

(cid:122) 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

T U

10

Ví dụ

Những vấn đề khác trong điều khiển đồng thời

T2 T3 T4 T1 L(A); R(A) 1 2 3 L(B); R(B) L(A) ↓ Waits 4 L(B); R(B) 5 L(A) ↓ Waits ↓ Wound U(A); U(B) 6 L(A); L(C) 7 R(A); W(C) 8 U(C); U(A) 9 L(A); L(D) 10 R(D); W(A) 11 U(D); U(A) 12 L(B); R(B) 13 14 L(C); W(C) 15 U(B); U(C)

Nhận xét

(cid:122) Timeout

(cid:122) Đơn giản (cid:122) Khó chọn được khoảng thời gian timeout thích hợp (cid:122) Có hiện tượng starvation

(cid:122) Resource ordering (cid:122) Không thực tế (cid:122) Chờ đợi nhiều → tiềm ẩn của deadlock

Những vấn đề khác trong điều khiển đồng thời

(cid:122) Giao tác lập đi lập lại quá trình: bắt đầu, deadlock, rollback

Nhận xét (tt)

(cid:122) Wait-die và Wound-wait (cid:122) Không có starvation (cid:122) Wound-wait ít rollback các giao tác hơn wait-die (cid:122) Dễ cài đặt hơn wait-for graph (cid:122) Có thể rollback những giao tác không gây ra deadlock

(cid:122) Wait-for graph

(cid:122) Nếu đồ thị quá lớn sẽ tốn nhiều thời gian phân tích (cid:122) Rất phức tạp khi CSDL phân tán (cid:122) Giảm tối thiểu rollback các giao tác

Những vấn đề khác trong điều khiển đồng thời

(cid:122) Chỉ rollback 1 trong những giao tác gây ra deadlock