tailieunhanh - Bài tập Tắc nghẽn

Nội dung của tài liệu trình bày một số thuật ngữ về Max, Allocation, Available, Need, số tài nguyên từng loại và 8 bài tập về các loại tài nguyên, các thông số, tiến trình và giải thuật, yêu cầu cấp phát tài nguyên và thực hiện yêu cầu cấp phát tài nguyên, tính số tài nguyên, trạng thái hệ thống và trạng thái an toàn của hệ thống có kèm theo lời giải. | Bài tập Tắc nghẽn Một số thuật ngữ: • Max: Yêu cầu ban đầu (ma trận mxn, với m là số dòng - ứng với số lượng tiến trình, n là cột - ứng với số lượng tài nguyên). Trong một số tài liệu, người ta thường dùng từ Request thay cho Max. • Allocation: Đã cấp phát (ma trận mxn) • Available: Tài nguyên còn lại (ma trận 1xn) • Need: Nhu cầu còn lại (ma trận mxn, xác định như sau: Need[i,j] = Max[i,j] – Allocation[i,j]) • Số tài nguyên từng loại: Allocation[j] + Available[j] Bài 1. Một hệ thống có 3 loại tài nguyên (A, B, C) và 5 tiến trình (P0, P1, P2, P3, P4) kèm theo các thông số được mô tả trong bảng sau. Allocation Max Available A B C A B C A B C P0 3 0 1 10 7 4 3 2 1 8 5 3 P1 P2 2 1 3 6 3 4 6 2 2 P3 0 3 0 9 6 3 P4 1 1 2 7 4 5 Tiến trình P1 yêu cầu tài nguyên là (2, 0, 1). Sử dụng giải thuật Banker, cho biết có thể thực hiện yêu cầu cấp phát tài nguyên này hay không? GIẢI Bước 1: Kiểm tra Request False Với P1: 3 3 1 False Với P2: 4 2 1 True => Thu hồi tài nguyên Work = Work + Allocation (P2)= (4, 2, 1) + (2, 1, 3) = (6, 3, 4) => Xét lại vòng lặp Với P0: 7 7 3 False Với P1: 3 3 1 True => Thu hồi tài nguyên Work = Work + Allocation (P1)=(6, 3, 4) + (5, 2, 2) = (11, 5, 6) => Xét lại vòng lập Với P0: 7 7 3 False Với P3: 9 3 3 True => Thu hồi tài nguyên Work = Work + Allocation (P3)=11 5 6 + 0 3 0 = 11 8 6 => Xét lại vòng lập Với P0: 7 7 3 True => Thu hồi tài nguyên Work = Work + Allocation (P0)=11 8 6 + 3 0 1 = 14 8 7 => Xét lại vòng lập Với P4: 6 3 3 True => Thu hồi tài nguyên Work = Work + Allocation (P4)=14 8 7 + 1 1 2 = 15 9 9 Tìm thấy chuỗi cấp phát an toàn {P2, P1, P3, P0, P4} nên có thể thực hiện cấp phát tài nguyên cho P1 được. Bài 2. Một hệ thống có 3 loại tài nguyên (A, B, C) và 4 tiến trình (P0, P1, P2, P3, P4) kèm theo các thông số được mô tả trong bảng sau. Allocation Max Available A B C A B C A B C P0 3 0 1 10 7 4 P1 3 2 1 8 5 3 6 2 2 P2 2 1 3 6 3 4 P3 0 3 0 9 6 3 P4 1 1 2 7 4 5 Tiến trình P1 yêu cầu tài nguyên là (1, 1, 0). Sử dụng giải thuật Banker, cho .