Giải thuật Nhà băng (Banker's Algorithm)

Giành cho những ai không đi học lý thuyết ngày 22/11/2010

Ví dụ Giải thuật Nhà băng
Một hệ thống có 5 tiến trình {P0, P1, P2, P3, P4} và 3 tài nguyên A(10 phiên bản), B(5 phiên bản), C(7 phiên bản).
Giả sử ở thời điểm T0:

a) Chứng minh hệ thống tồn tại chuỗi an toàn?
b) Tìm chuỗi an toàn?

Giải:

- Hệ có Available = (10,5,7) - (7,2,5) = (3,3,2)
Trong đó:
(10,5,7): 3 tài nguyên của đề bài
(7,2,5) = (P0A+P1A+P2A+P3A+P4A, P0B+P1B+P2B+P3B+P4B, P0C+P1C+P2C+P3C+P4C)
- Ma trận Need = Max - Allocation:

- Tìm chuỗi an toàn:

Giải thích:
(1): hệ có; Need[i]: tìm giá trị thích hợp trong ma trận Need sao cho Work >= Need; Allocation[i] chiếu vô đề bài lấy giá trị.
(2) = Work(1) + Allocation[i] = (3,3,2) + (2,0,0) = (5,3,2)
(3) = Work(2) + Allocation[i] = (5,3,2) + (2,1,1) = (7,4,3)
(4),(5): tương tự
- Hệ thống trong trạng thái an toàn vì tồn tại chuỗi an toàn {P1, P3, P4, P2, P0} (đpcm !)

Nếu có sai sót xin mọi người đóng góp ý kiến nha.

Hình ảnh rõ ràng, bài của bạn dễ đọc hơn bài của lớp phó I92c, nhưng mình nghĩ bạn nên ghi rõ ràng là :
Work2= Work1 + Allocation1
........
Work(n)= Work (n-1) + Allocation(n-1)
Chứ bạn ghi như vầy : (2)= Work1 + Allocation1 mình nghĩ không đúng và có thể sẽ bị Thầy trừ điểm

mình thử 1 trật tự khác, thấy cũng đúng, và còn vài trường hợp nữa cũng tương tự




Hệ thống trong trạng thái an toàn vì tồn tại chuỗi an toàn {P3, P1, P0, P4, P2}

Bài này mình cũng tìm ra được một chuỗi an toàn khác(P3 p4 p1 p0 p2) và đã post lên,bạn ghé qua xem thử,thanks các bạn

minhtrieu_i92c đã viết:Hình ảnh rõ ràng, bài của bạn dễ đọc hơn bài của lớp phó I92c, nhưng mình nghĩ bạn nên ghi rõ ràng là :
Work2= Work1 + Allocation1
........
Work(n)= Work (n-1) + Allocation(n-1)
Chứ bạn ghi như vầy : (2)= Work1 + Allocation1 mình nghĩ không đúng và có thể sẽ bị Thầy trừ điểm

Uh, đúng rùi, bạn góp ý rất chính xác, để mình sửa lại sau nhé.
Cảm ơn bạn nhiều !