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

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 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 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