Bài giảng Hệ điều hành - Chương 4: Deadlock

Nội dung text: Bài giảng Hệ điều hành - Chương 4: Deadlock

1. RAG và deadlock (tt) ❑ RAG không chứa chu trình không có deadlock ❑ RAG chứa một (hay nhiều) chu trình – Nếu mỗi loại tài nguyên chỉ có một thực thể deadlock – Nếu mỗi loại tài nguyên có nhiều thực thể có thể xảy ra deadlock Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 4.11
2. Các phương pháp giải quyết deadlock (1) Ba phương pháp 1) Bảo đảm rằng hệ thống không rơi vào tình trạng deadlock bằng cách ngăn (preventing) hoặc tránh (avoiding) deadlock. Khác biệt – Ngăn deadlock: không cho phép (ít nhất) một trong 4 điều kiện cần cho deadlock – Tránh deadlock: các quá trình cần cung cấp thông tin về tài nguyên nó cần để hệ thống cấp phát tài nguyên một cách thích hợp Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 4.12
3. Các phương pháp giải quyết deadlock (2) 2) Cho phép hệ thống vào trạng thái deadlock, nhưng sau đó phát hiện deadlock và phục hồi hệ thống. 3) Bỏ qua mọi vấn đề, xem như deadlock không bao giờ xảy ra trong hệ thống. ☺Khá nhiều hệ điều hành sử dụng phương pháp này. – Deadlock không được phát hiện, dẫn đến việc giảm hiệu suất của hệ thống. Cuối cùng, hệ thống có thể ngưng hoạt động và phải được khởi động lại. Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 4.13
4. Ngăn deadlock Ngăn deadlock bằng cách ngăn một trong 4 điều kiện cần của deadlock 1. Ngăn mutual exclusion – đối với nonsharable resource (vd: printer): không làm được – đối với sharable resource (vd: read-only file): không cần thiết Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 4.14
5. Ngăn deadlock (tt) 2. Ngăn Hold and Wait – Cách 1: mỗi process yêu cầu toàn bộ tài nguyên cần thiết một lần. Nếu có đủ tài nguyên thì hệ thống sẽ cấp phát, nếu không đủ tài nguyên thì process sẽ bị blocked. – Cách 2: khi yêu cầu tài nguyên, process không đang giữ bất kỳ tài nguyên nào. Nếu đang giữ thì phải trả lại trước khi yêu cầu. – Ví dụ để so sánh hai cách trên: một quá trình copy dữ liệu từ tape drive sang disk file, sắp xếp disk file, rồi in kết quả ra printer. – Khuyết điểm của các cách trên: ▪ Hiệu suất sử dụng tài nguyên (resource utilization) thấp ▪ Quá trình có thể bị starvation Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 4.15
6. Ngăn deadlock (tt) 3. Ngăn No Preemption: nếu process A có giữ tài nguyên và đang yêu cầu tài nguyên khác nhưng tài nguyên này chưa cấp phát ngay được thì – Cách 1: Hệ thống lấy lại mọi tài nguyên mà A đang giữ ▪ A phải bắt đầu lại từ đầu. – Cách 2: Hệ thống sẽ xem tài nguyên mà A yêu cầu ▪ Nếu tài nguyên được giữ bởi một process khác đang đợi thêm tài nguyên, tài nguyên này được hệ thống lấy lại và cấp phát cho A. ▪ Nếu tài nguyên được giữ bởi process không đợi tài nguyên, A phải đợi và tài nguyên của A bị lấy lại. Tuy nhiên hệ thống chỉ lấy lại các tài nguyên mà process khác yêu cầu. Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 4.16
7. Ngăn deadlock (tt) 4. Ngăn Circular Wait: tập các loại tài nguyên trong hệ thống được gán một thứ tự hoàn toàn. – Ví dụ: F(tape drive) = 1, F(disk drive) = 5, F(printer) = 12 ▪ F là hàm định nghĩa thứ tự trên tập các loại tài nguyên. Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 4.17
8. Ngăn deadlock (tt) 4. Ngăn Circular Wait (tt) – Cách 1: mỗi process yêu cầu thực thể của tài nguyên theo thứ tự tăng dần (định nghĩa bởi hàm F) của loại tài nguyên. Ví dụ ▪ Chuỗi yêu cầu thực thể hợp lệ: tape drive → disk drive → printer ▪ Chuỗi yêu cầu thực thể không hợp lệ: disk drive → tape drive – Cách 2: Khi một process yêu cầu một thực thể của loại tài nguyên Rj thì nó phải trả lại các tài nguyên Ri với F(Ri) > F(Rj). R – “Chứng minh” cho cách 1: phản chứng 1 P P2 ▪ F(R4) < F(R1) 1 ▪ F(R1) < F(R2) ▪ F(R2) < F(R3) R4 R2 ▪ F(R3) < F(R4) Vậy F(R4) < F(R4), mâu thuẩn! R3 P4 P3 Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 4.18
9. Deadlock avoidance ❑ Deadlock prevention sử dụng tài nguyên không hiệu quả. ❑ Deadlock avoidance vẫn đảm bảo hiệu suất sử dụng tài nguyên tối đa đến mức có thể. ❑ Yêu cầu mỗi process khai báo số lượng tài nguyên tối đa cần để thực hiện công việc ❑ Giải thuật deadlock-avoidance sẽ kiểm tra trạng thái cấp phát tài nguyên (resource-allocation state) để bảo đảm hệ thống không rơi vào deadlock. Trạng thái cấp phát tài nguyên được định nghĩa dựa trên số tài nguyên còn lại, số tài nguyên đã được cấp phát và yêu cầu tối đa của các process. Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 4.19
10. Trạng thái safe và unsafe ❑ Một trạng thái của hệ thống được gọi là an toàn (safe) nếu tồn tại một chuỗi an toàn (safe sequence). Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 4.20
11. Chuỗi an toàn ❑ Một chuỗi quá trình P1, P2, , Pn  là một chuỗi an toàn nếu – Với mọi i = 1, ,n, yêu cầu tối đa về tài nguyên của Pi có thể được thỏa bởi ▪ tài nguyên mà hệ thống đang có sẵn sàng (available) ▪ cùng với tài nguyên mà tất cả Pj , j < i, đang giữ. ❑ Một trạng thái của hệ thống được gọi là không an toàn (unsafe) nếu không tồn tại một chuỗi an toàn. Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 4.21
12. Chuỗi an toàn (tt) Ví dụ: Hệ thống có 12 tape drives và 3 quá trình P0, P1, P2 ❑ Tại thời điểm t0 , giả sử hệ thống còn 3 tape drive sẵn sàng. cần tối đa đang giữ P0 10 5 P1 4 2 P2 9 2 – Chuỗi P1, P0, P2  là chuỗi an toàn hệ thống là an toàn Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 4.22
13. Chuỗi an toàn (tt) ❑ Giả sử tại thời điểm t1, P2 yêu cầu và được cấp phát 1 tape drive – còn 2 tape drive sẵn sàng cần tối đa đang giữ P0 10 5 P1 4 2 P2 9 3 Hệ thống trở nên không an toàn. Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 4.23
14. ❑ Ý tưởng cho giải pháp tránh deadlock: Khi một process yêu cầu một tài nguyên đang sẵn sàng, hệ thống sẽ kiểm tra: nếu việc cấp phát này không dẫn đến tình trạng unsafe thì sẽ cấp phát ngay. Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 4.24
15. Trạng thái safe/unsafe và deadlock ❑ Nếu hệ thống đang ở trạng thái safe không deadlock. ❑ Nếu hệ thống đang ở trạng thái unsafe có thể dẫn đến deadlock. ❑ Tránh deadlock bằng cách cấp phát tài nguyên sao cho hệ thống không đi đến trạng thái unsafe. deadlock unsafe safe Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 4.25
16. Giải thuật banker ❑ Áp dụng cho hệ thống cấp phát tài nguyên trong đó mỗi loại tài nguyên có thể có nhiều instance. ❑ Bắt chước nghiệp vụ ngân hàng (banking) ❑ Điều kiện – Mỗi process phải khai báo số lượng thực thể (instance) tối đa của mỗi loại tài nguyên mà nó cần – Khi process yêu cầu tài nguyên thì có thể phải đợi mặc dù tài nguyên được yêu cầu đang có sẵn – Khi process đã có được đầy đủ tài nguyên thì phải hoàn trả trong một khoảng thời gian hữu hạn nào đó. Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 4.26
17. Giải thuật banker (tt) n: số process, m: số loại tài nguyên Các cấu trúc dữ liệu Available: vector độ dài m Available[ j ] = k loại tài nguyên Rj có k instance sẵn sàng Max: ma trận n m Max[ i, j ] = k quá trình Pi yêu cầu tối đa k instance của loại tài nguyên Rj Allocation: ma trận n m Allocation[i, j ] = k Pi đã được cấp phát k instance của Rj Need: ma trận n m Need[i, j] = k Pi có thể yêu cầu thêm k instance của Rj Nhận xét: Need[i, j ] = Max[i, j ] – Allocation[i, j ] Ký hiệu Y X Y[i] X[i], ví dụ (0, 3, 2, 1) (1, 7, 3, 2) Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 4.27
18. Giải thuật kiểm tra trạng thái an toàn Tìm một chuỗi an toàn 1. Gọi Work và Finish là hai vector độ dài là m và n. Khởi tạo Work := Available Finish[ i ] := false, i = 1, , n 2. Tìm i thỏa (a) Finish[ i ] = false (b) Needi Work (hàng thứ i của Need) Nếu không tồn tại i như vậy, đến bước 4. 3. Work := Work + Allocationi Finish[ i ] := true quay về bước 2. 4. Nếu Finish[ i ] = true, i = 1, , n, thì hệ thống đang ở trạng thái safe Thời gian chạy của giải thuật là O(m·n2) Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 4.28
19. Giải thuật cấp phát tài nguyên Gọi Requesti (độ dài m) là request vector của process Pi . Requesti [ j ] = k Pi cần k instance của tài nguyên Rj . 1. Nếu Requesti Needi thì đến bước 2. Nếu không, báo lỗi vì process đã vượt yêu cầu tối đa. 2. Nếu Requesti Available thì qua bước 3. Nếu không, Pi phải chờ vì tài nguyên không còn đủ để cấp phát. Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 4.29
20. Giải thuật cấp phát tài nguyên (tt) 3. Giả định cấp phát tài nguyên đáp ứng yêu cầu của Pi bằng cách cập nhật trạng thái hệ thống như sau: Available := Available – Requesti Allocationi := Allocationi + Requesti Needi := Needi – Requesti Áp dụng giải thuật kiểm tra trạng thái an toàn lên trạng thái trên ▪ Nếu trạng thái là safe thì tài nguyên được cấp thực sự cho Pi . ▪ Nếu trạng thái là unsafe thì Pi phải đợi, và phục hồi trạng thái: Available := Available + Requesti Allocationi := Allocationi - Requesti Needi := Needi + Requesti Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 4.30
21. Giải thuật kiểm tra trạng thái an toàn – Ví dụ ❑ Có 5 process P0 , , P4 ❑ Có 3 loại tài nguyên: A (có 10 instance), B (5 instance) và C (7 instance). ❑ Trạng thái cấp phát tài nguyên của hệ thống tại thời điểm T0 Allocation Max Available Need A B C A B C A B C A B C P0 0 1 0 7 5 3 3 3 2 7 4 3  P1 2 0 0 3 2 2 1 2 2  P2 3 0 2 9 0 2 6 0 0  P3 2 1 1 2 2 2 0 1 1  P4 0 0 2 4 3 3 4 3 1  Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 4.31
22. GT kiểm tra trạng thái an toàn – Vd (tt) Dùng giải thuật kiểm tra trạng thái, tìm được một chuỗi an toàn là P1, P3, P4, P2, P0 : Allocation Need Work A B C A B C A B C P0 0 1 0 7 4 3 3 3 2 P 2 0 0 1 2 2 1 5 3 2 P2 3 0 2 6 0 0 7 4 3 P3 2 1 1 0 1 1 P4 0 0 2 4 3 1 7 4 5 10 4 7 10 5 7 Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 4.32
23. GT cấp phát tài nguyên – Ví dụ ❑ Yêu cầu (1, 0, 2) của P1 có thỏa được không? – Kiểm tra điều kiện Request1 Available: ▪ (1, 0, 2) (3, 3, 2) là đúng – Giả sử đáp ứng yêu cầu, kiểm tra trạng thái mới có phải là safe hay không: Allocation Need Available A B C A B C A B C P0 0 1 0 7 4 3 2 3 0 P1 3 0 2 0 2 0 P2 3 0 2 6 0 0 P3 2 1 1 0 1 1 P4 0 0 2 4 3 1 – Trạng thái mới là safe (chuỗi an toàn là P1, P3, P4, P0, P2 ), vậy có thể cấp phát tài nguyên cho P1. Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 4.33
24. GT cấp phát tài nguyên – Ví dụ (tt) ❑ P4 yêu cầu (3, 3, 0) hoặc P0 yêu cầu (0, 2, 0) thì có thỏa mãn được hay không? Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 4.34
25. Phát hiện deadlock ❑ Chấp nhận xảy ra deadlock trong hệ thống, kiểm tra trạng thái hệ thống bằng giải thuật phát hiện deadlock. Nếu có deadlock thì tiến hành phục hồi hệ thống ❑ Các giải thuật phát hiện deadlock thường sử dụng RAG. ❑ Giải thuật phát hiện deadlock được thiết kế cho mỗi trường hợp sau 1. Mỗi loại tài nguyên chỉ có một thực thể 2. Mỗi loại tài nguyên có thể có nhiều thực thể Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 4.35
26. Mỗi loại tài nguyên chỉ có một thực thể ❑ Sử dụng wait-for graph – Wait-for graph được dẫn xuất từ RAG bằng cách bỏ các node biểu diễn tài nguyên và ghép các cạnh tương ứng: ▪ Có cạnh từ Pi đến Pj Pi đang chờ tài nguyên từ Pj P5 P5 R1 R3 R4 P1 P2 P3 P1 P2 P3 R P R 2 4 5 P4 ❑ Gọi định kỳ một giải thuật kiểm tra có tồn tại chu trình trong wait-for graph hay không. Giải thuật phát hiện chu trình có thời gian chạy là O(n 2), với n là số đỉnh của graph. Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 4.36
27. Mỗi loại tài nguyên có nhiều thực thể ❑ Phương pháp dùng wait-for graph không áp dụng được cho trường hợp mỗi loại tài nguyên có nhiều instance. ❑ Giải thuật phát hiện deadlock trường hợp mỗi loại tài nguyên có nhiều instance: các cấu trúc dữ liệu Available: vector độ dài m số instance sẵn sàng của mỗi loại tài nguyên Allocation: ma trận n m số instance của mỗi loại tài nguyên đã cấp phát cho mỗi process Request: ma trận n m yêu cầu hiện tại của mỗi process. Request [i, j ] = k Pi đang yêu cầu thêm k instance của Rj Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 4.37
28. Giải thuật phát hiện deadlock 1. Các biến Work và Finish là vector kích thước m và n. Khởi tạo: Work := Available i = 1, 2, , n, nếu Allocationi 0 thì Finish[ i ] := false còn không thì Finish[ i ] := true 2. Tìm i thỏa mãn: Finish[ i ] := false và thời gian chạy Requesti Work của giải thuật Nếu không tồn tại i như thế, đến bước 4. O(m·n2) 3. Work := Work + Allocationi Finish[ i ] := true quay về bước 2. 4. Nếu tồn tại i với Finish[ i ] = false, thì hệ thống đang ở trạng thái deadlock. Hơn thế nữa, nếu Finish[ i ] = false thì Pi bị deadlocked. Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 4.38
29. Giải thuật phát hiện deadlock (tt) ❑ Nhận xét: – Khi giải thuật phát hiện deadlock không thấy hệ thống đang deadlock, chưa chắc trong tương lai hệ thống vẫn không deadlock. Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 4.39
30. Giải thuật phát hiện deadlock – Ví dụ ❑ Hệ thống có 5 quá trình P0 , , P4 3 loại tài nguyên: A (7 instance), B (2 instance), C (6 instance). Allocation Request Available A B C A B C A B C P0 0 1 0 0 0 0 0 0 0 P1 2 0 0 2 0 2 P2 3 0 3 0 0 0 P3 2 1 1 1 0 0 P4 0 0 2 0 0 2 Chạy giải thuật, tìm được chuỗi P0, P2, P3, P1, P4  với Finish[ i ] = true, i = 1, , n, vậy hệ thống không bị deadlocked. Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 4.40
31. Giải thuật phát hiện deadlock – Ví dụ (tt) ❑ P2 yêu cầu thêm một instance của C. Ma trận Request như sau: Request A B C P0 0 0 0 P1 2 0 2 P2 0 0 1 P3 1 0 0 P4 0 0 2 – Trạng thái của hệ thống là gì (safe, unsafe, deadlock)? ▪ Có thể thu hồi tài nguyên đang giữ bởi process P0 nhưng vẫn không đủ đáp ứng yêu cầu của các process khác. Vậy tồn tại deadlock, bao gồm các process P1, P2, P3, và P4 . Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 4.41
32. Phục hồi khỏi deadlock ❑ Các giải pháp khi phát hiện deadlock – báo người vận hành (operator), người này sẽ xử lý tiếp hoặc – hệ thống tự động phục hồi bằng cách phá deadlock: ▪ Giải pháp chấm dứt quá trình hoặc ▪ Giải pháp lấy lại tài nguyên Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 4.42
33. Phục hồi khỏi deadlock: Chấm dứt quá trình ❑ Phục hồi hệ thống khỏi deadlock bằng cách – Chấm dứt tất cả process bị deadlocked, hoặc – Chấm dứt lần lượt từng process cho đến khi không còn deadlock ▪ Sử dụng giải thuật phát hiện deadlock để xác định còn deadlock hay không ❑ Dựa trên yếu tố nào để chọn process cần được chấm dứt? – Độ ưu tiên của process – Thời gian đã thực thi của process và thời gian còn lại – Loại tài nguyên mà process đã sử dụng – Tài nguyên mà process cần thêm để hoàn tất công việc – Số lượng process cần được chấm dứt – Process là interactive process hay batch process Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 4.43
34. Phục hồi khỏi deadlock: Lấy lại tài nguyên ❑ Lần lượt lấy lại tài nguyên từ các process, cấp phát chúng cho process khác cho đến khi không còn deadlock nữa. ❑ Các vấn đề khi thu hồi tài nguyên: – Chọn “nạn nhân”: chọn tài nguyên và process nào (có thể dựa trên số tài nguyên sở hữu, thời gian CPU đã tiêu tốn, )? – Rollback: rollback process bị lấy lại tài nguyên trở về trạng thái safe, rồi tiếp tục process từ trạng thái đó. Do đó hệ thống cần lưu giữ một số thông tin về trạng thái các process đang thực thi. – Starvation: để tránh starvation, phải bảo đảm không có process nào mà luôn bị lấy lại tài nguyên mỗi khi phục hồi khỏi deadlock. Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 4.44