Bài giảng Kỹ thuật Máy tính - Chương 8: Tắc nghẽn - Nguyễn Thanh Sơn

Nội dung text: Bài giảng Kỹ thuật Máy tính - Chương 8: Tắc nghẽn - Nguyễn Thanh Sơn

1. Nội dung  Mô hình hệ thống  Đồ thị phân bổ tài nguyên (RAG)  Phương pháp giải quyết nghẽn  Chống (Ngăn) nghẽn  Tránh (avoidance) nghẽn  Phát hiện nghẽn  Phục hồi nghẽn BK TP.HCM Khoa Khoa học & Kỹ thuật Máy tính 2
2. Tắc nghẽn trong hệ thống  Tình huống: một tập các process bị blocked, mỗi process giữ tài nguyên và đang chờ tài nguyên mà process khác trong tập đang giữ.  Ví dụ 1  Giả sử hệ thống có một printer và một DVD drive. Quá trình P1 đang giữ DVD drive, quá trình P2 đang giữ printer. Bây giờ P1 yêu cầu printer, và P2 yêu cầu DVD drive BK TP.HCM Khoa Khoa học & Kỹ thuật Máy tính 4
3. Điều kiện cần để xảy ra nghẽn Bốn điều kiện cần (necessary conditions) 1. Mutual exclusion: ít nhất một tài nguyên được giữ theo nonsharable mode (ví dụ: printer; ví dụ sharable resource: read-only file). 2. Hold and wait: một process đang giữ ít nhất một tài nguyên và đợi thêm tài nguyên do quá trình khác đang giữ. 3. No preemption: (= no resource preemption) không lấy lại tài nguyên đã cấp phát cho process, ngoại trừ khi process tự hoàn trả nó. 4. Circular wait: tồn tại một tập {P0, ,Pn} các quá trình đang đợi sao cho P0 đợi một tài nguyên mà P1 đang giữ P1 đợi một tài nguyên mà P2 đang giữ Pn đợi một tài nguyên mà P0 đang giữ BK TP.HCM Khoa Khoa học & Kỹ thuật Máy tính 6
4. Resource Allocation Graph (tt.) Ký hiệu  Process: Pi R j  Loại tài nguyên với 4 thực thể: Rj P  Pi yêu cầu một thực thể của Rj : i Rj  Pi đang giữ một thực thể của Rj : Pi BK TP.HCM Khoa Khoa học & Kỹ thuật Máy tính 8
5. Ví dụ về RAG (tt.) R1 R3 P1 P2 P3 Deadlock xảy ra! BK R2 R4 TP.HCM Khoa Khoa học & Kỹ thuật Máy tính 10
6. 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 BK TP.HCM Khoa Khoa học & Kỹ thuật Máy tính 12
7. Deadlock: Cch giải quyết (tt.) 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. BK TP.HCM Khoa Khoa học & Kỹ thuật Máy tính 14
8. 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.  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 BK TP.HCM Khoa Khoa học & Kỹ thuật Máy tính 16
9. 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. BK TP.HCM Khoa Khoa học & Kỹ thuật Máy tính 18
10. Trnh (avoidance) Nghẽn  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ẽ điều khiển 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.  Traïng thaùi caáp phaùt taøi nguyeân ñöôïc ñònh nghóa döïa treân soá taøi nguyeân coøn laïi, soá taøi nguyeân ñaõ ñöôïc caáp phaùt vaø yeâu caàu toái ña cuûa caùc process. BK TP.HCM Khoa Khoa học & Kỹ thuật Máy tính 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. BK TP.HCM Khoa Khoa học & Kỹ thuật Máy tính 22
12. 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  coøn 2 tape drive saün saøng cần tối đa đang giữ P 10 5 0 P1 4 2 P2 9 3  Hệ thống trở nên không an toàn. BK TP.HCM Khoa Khoa học & Kỹ thuật Máy tính 24
13. Safe/unsafe và deadlock (tt.)  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 Neáu heä thoáng ñang ôû traïng thaùi safe khoâng deadlock. deadlock unsafe safe BK TP.HCM Khoa Khoa học & Kỹ thuật Máy tính 26
14. Thực hiện Giải thuật 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) BK TP.HCM Khoa Khoa học & Kỹ thuật Máy tính 28
15. Thực hiện Giải thuật (tt.)  5 process P0 , , P4  3 loại tài nguyên: A, gồm 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  P 3 0 2 9 0 2 6 0 0 2  P3 2 1 1 2 2 2 0 1 1  P4 0 0 2 4 3 3 4 3 1  BK TP.HCM Khoa Khoa học & Kỹ thuật Máy tính 30
16. 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. BK TP.HCM Khoa Khoa học & Kỹ thuật Máy tính 32
17. Giải thuật cấp phát tài nguyên (tt.)  (tiếp ví dụ) Yêu cầu (1, 0, 2) của P1 có thỏa đượckhô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 P 3 0 2 0 2 0 1 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, với 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. BK TP.HCM Khoa Khoa học & Kỹ thuật Máy tính 34
18. 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  Mỗi loại tài nguyên chỉ có một thực thể  Mỗi loại tài nguyên có thể có nhiều thực thể BK TP.HCM Khoa Khoa học & Kỹ thuật Máy tính 36
19. 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ả thiết: sau khi được đáp ứng yêu cầu tài nguyên, process sẽ hoàn tất và trả lại tất cả tài nguyên giải thuật optimistic!  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 BK TP.HCM Khoa Khoa học & Kỹ thuật Máy tính 38
20. 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. BK TP.HCM Khoa Khoa học & Kỹ thuật Máy tính 40
21. Giải thuật phát hiện deadlock (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 . BK TP.HCM Khoa Khoa học & Kỹ thuật Máy tính 42
22. 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 BK TP.HCM Khoa Khoa học & Kỹ thuật Máy tính 44
23. Kết luận  Định nghĩa  Điều kiện cần để Deadlock xảy ra  Cc giải php BK TP.HCM