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

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