Bai tap ve thuat giai nha bang

Một hệ thống có 5 tiến trình với tình trạng tài nguyên như sau:
Process Allocation Max Available
A B C D A B C D A B C D
P0 0 0 1 2 0 0 1 2 1 5 2 0
P1 1 0 0 0 1 7 5 0
P2 1 3 5 4 2 3 5 6
P3 0 6 3 2 0 6 5 2
P4 0 0 1 4 0 6 5 6
Dùng Thuật giải Nhà băng để xác định:
a. Nội dung của ma trận Need.
b. Trạng thái này có an toàn không?
c. Nếu P1 nêu yêu cầu (0, 4, 2, 0), có thể đáp ứng ngay được không?
Giải:
a. Xét tại thời điểm T0 mà 5 tiến trình được cấp phát như đề bài ta có:
Need[i] = Max[i] – Allocation[i]
Process Need
A B C D
P0 0 0 0 0
P1 0 7 5 0
P2 1 0 0 2
P3 0 0 2 0
P4 0 6 4 2
b. Tìm chuỗi an toàn:
Work >= Need[i] P[i] Allocation[i]
A B C D A B C D A B C D
1 5 2 0 0 0 0 0 P0 0 0 1 2
1 5 3 2 1 0 0 2 P2 1 3 5 4
2 8 8 6 0 0 2 0 P3 0 6 3 2
2 14 11 8 0 6 4 2 P4 0 0 1 4
2 14 12 12 0 7 5 0 P1 1 0 0 0
Vậy tại thời điểm T0 tồn tại chuỗi an toàn {P0, P2, P3, P4, P1}. Suy ra, hệ thống tại thời điểm T0 ở trạng thái an toàn.
c. Ta thấy, yêu cầu thêm (0, 4, 2, 0) của P1 thoả điều kiện Request1  Need1, và thoả điều kiện: Request1  Available. Giả sử ta cấp phát theo yêu cầu của P1 thì vẫn tồn tại chuỗi an toàn. Do vậy, ta hoàn toàn có thể cấp phát thêm (0, 4, 2, 0) cho P1 được.