Giải thích thuật giải Nhà băng Dữ liệu : – có 5 tiến trình : P0,……,P4 (Ví dụ là : 5 công ty khác nhau cần vay ) – 3 loại tài nguyên : A(10 phiên bản), B(5 phiên bản), C(7 phiên bản) \=>Đây là các loại tiền mà nhà băng có. – Tại thời điểm To: Allocation Max Available A B C A B C A B C Po 0 1 0 7 5 3 3 3 2 P1 2 0 0 3 2 2 P2 3 0 2 9 0 2 P3 2 1 1 2 2 2 P4 0 0 2 4 3 3 Tổng loại tiền mà các công ty có (Cộng theo cột từ trên xuống của Allocation) Tổng :7 2 5 Chú ý : – Allocation tổng số các loại tiền mà các công ty đang có – Max : Tổng các loại tiền (tối đa ) mà các công ty có thể có – Hệ có : Available = ( 10 ,5 ,7 ) – ( 7, 2 ,5 ) = ( 3 ,3 ,2 ) Ta có : Need = Max – Allocation \=>Số loại tiền tối đa mà các công ty có thể vay thêm. Ta có ma trận sau : Need A B C P0 7 4 3 (7,5,3) – (0,1,0) P1 1 2 2 (3,2,2) – (2,0,0) P2 6 0 0 (9,0,2) – (3,0,2) P3 0 1 1 (2,2,2) – (2,1,1) P4 4 3 1 (4,3,3) – (0,0,2) Giả sử tại thời điểm To công ty : Ta phải kiểm tra tổng số các loại tiền mà công ty cần : Need <= Work : hệ số các loại tiền có trong nhà băng. Trong thời điểm này thì chỉ có P1,P3 là thỏa điều kiện được vay trước. Giả sử P1 vay trước : Ta có bảng sau đảm bảo số tiền vay không vượt qua số tiền nhà băng cần có. Work Need(i) P(i) Allocation A B C A B C A B C 3 2 2 1 2 2 P1 2 0 0 Số tiền ít nhất nhà băng cần có cho P1 vay là (3,2,2) Vậy hệ số tiền mà nhà băng có ít nhẩt cho công ty tiếp theo vay là: Work = (3,2,2)+(2,0,0) = (5,3,2) Ta xét hệ số các loại tiền Need <=Work. Trong trường hợp này thì P1 và P4 có thể vay.Giả sử P3 vay.Và làm các bước tương tự cho các công ty còn lại ta có bảng sau Work Need(i) P(i) Allocation A B C A B C A B C 3 2 2 1 2 2 P1 2 0 0 5 3 2 0 1 1 P3 2 1 1 7 4 3 4 3 1 P4 0 0 2 7 4 5 6 0 0 P2 3 0 2 10 4 7 7 4 3 P0 0 1 0 Chú ý : Hệ số các loại tiền của nhà băng cần có để cho vay (10,4,7) <= (10,5,7) các tài nguyên ban đầu Như vậy : Ở thời điểm To hệ thống nhà băng trong trạng thái an toàn vì tồn tại chuỗi an toàn : < P1 ,P3 ,P4 ,P2 ,P0 > P1 muốn tăng tiền vay (1,0,2) thì phải thỏa điều kiện: 1 – Request (yêu cầu) <= Need vì (1,0,2) <= (1,2,2) // Thỏa điều kiện 2- Request (yêu cầu) <= Available vì (1,0,2) <= (3,3,2) // Thỏa điều kiện Ta lại làm lại từ đầu và xét trạng thái mới Ta có: Bảng Max sẽ được thay bằng bảng Need (Vì Need đã là giá trị lớn nhất để có thể tồn tại chuổi an toàn). Allocation của P1 sẽ đổi do cộng đồn giá trị Allocation ban đầu với giá trị Allocation mới: (2,0,0) + (1,0,2) = (3,0,2) Need của P1 cũng thay đổi do điều kiện xét ta có: Need (P1)[mới] = Need(P1)[cũ] – Request = (1,2,2) – (1,0,2) = (0,2,0) Available cũng thay đổi do: Available (mới) = Available (củ) – Request = (3,3,2,) – (1,0,2) = (2,3,0) Allocation Need Available A B C A B C A B C Po 0 1 0 7 4 3 2 3 0 P1 3 0 2 0 2 0 P2 3 0 2 6 0 0 P3 2 1 1 0 1 1 P4 0 0 2 4 3 1 Work Need(i) P(i) Allocation A B C A B C A B C 2 3 0 0 2 0 P1 3 0 2 5 3 2 0 1 1 P3 2 1 1 7 4 3 4 3 1 P4 0 0 2 7 4 5 6 0 0 P2 3 0 2 104 7 7 4 3 P0 0 1 0 Chú ý : Hệ số các loại tiền của nhà băng cần có để cho vay (10,4,7) <= (10,5,7) các tài nguyên ban đầu Như vậy : Ở thời điểm To hệ thống nhà băng trong trạng thái an toàn vì tồn tại chuỗi an toàn : < P1 ,P3 ,P4 ,P2 ,P0 > Các bạn chú ý là việc tìm chuỗi trên ko chỉ có tính duy nhất nhé 😉  c)P1 yêu cầu thêm (0,4,2,0) Yêu cầu này thỏa các điều kiện 1.Request1 <= Need1 vì (0,4,2,0)<=(0,7,5,0) 2.Request1 <= Available vì (0,4,2,0)<=(1,5,2,0) ở câu c available mới là (1,1,0,0) vì (1,5,2,0)-(0,4,2,0) Đề thi HDH http://www.mediafire.com/?65ubfdykrs6kbpe Câu hỏi ôn tập HDH http://www.mediafire.com/?wfmbza4gmdt7q6l Bài tập điều phối : http://www.mediafire.com/?tvsky2a7m9nnqci ôn thi HDH http://www.mediafire.com/?tvsky2a7m9nnqci Bài tập trên tailieu.vn/ Bác nào có tài khoản tải về up mediafire cho a em nào =)) http://tailieu.vn/xem-tai-lieu/mot-so-bai-tap-he-dieu-hanh-can-chu-y.314758.html |
