Giải bài tập trên lớp của Thày (có cải tiến đề bài 1 chút để hiểu về giải thuật Banker's Algorithm)

Đề bài :
Có 5 tiến trình {P0,P1,P2,P3,P4} và 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). Tại thời điểm T0 :
TT Đang Giữ MAX Hệ Có
ABC ABC ABC
P0 010 753 332
P1 200 322
P2 302 902
P3 211 222
P4 002 433
a) Tìm tất cả các chuỗi an toàn có thể có của hệ thống.
b) Giả xử P1 bây giờ nêu y/cầu mới là (1,0,2) thì xác định xem có nên đáp ứngy/cầu của P1 hay kô? vì sao?

Bài giải
a)
Tính Available = (10,5,7) - (7,2,5) = (3,3,2)
Tính Need = MAX - Allocation
TT Need
ABC
P0 743
P1 122
P2 600
P3 011
P4 431
Tìm chuỗi an toàn :
Work >= Needi Pi Allocation
ABC ABC ABC
332 011 P3 211
543 431 P4 002
545 122 P1 200
745 743 P0 010
755 600 P2 302
=> Chuỗi an toàn = {P3,P4,P1,P0,P2}
Work >= Needi Pi Allocation
ABC ABC ABC
332 011 P3 211
543 431 P4 002
545 122 P1 200
745 600 P2 302
1047 743 P0 010
=> Chuỗi an toàn = {P3,P4,P1,P2,P0}

Work >= Needi Pi Allocation
ABC ABC ABC
332 011 P3 211
543 112 P1 200
743 743 P0 010
753 600 P2 302
1055 431 P4 002
=> Chuỗi an toàn = {P3,P1,P0,P2,P4}
Work >= Needi Pi Allocation
ABC ABC ABC
332 122 P1 200
532 431 P4 002
534 011 P3 211
745 743 P0 010
755 600 P2 302
=> Chuỗi an toàn = {P1,P4,P3,P0,P2}
Work >= Needi Pi Allocation
ABC ABC ABC
332 122 P1 200
532 431 P4 002
534 011 P3 211
745 600 P2 302
1047 743 P0 010
=> Chuỗi an toàn = {P1,P4,P3,P0,P2}
Work >= Needi Pi Allocation
ABC ABC ABC
332 122 P1 200
532 011 P3 211
743 431 P4 002
745 743 P0 010
755 600 P2 302
=> Chuỗi an toàn = {P1,P3,P4,P0,P2}
Work >= Needi Pi Allocation
ABC ABC ABC
332 122 P1 200
532 011 P3 211
743 431 P4 002
745 600 P2 302
1047 743 P0 010
=> Chuỗi an toàn = {P1,P3,P4,P0,P2}
b)P1 y/cầu mới là (1,0,1) thì y/cầu này thoả đk:
- Request1 <= Need1 vì (1,0,1) <= (1,2,2)
- Request1 <= Available vì (1,0,1) <= (3,3,2)
Nên trạng thái mới là :
TT Đang Giữ MAX Hệ Có
ABC ABC ABC
P0 010 753 230
P1 302 322
P2 302 902
P3 211 222
P4 002 433
Tính Need = MAX - Allocation
TT Need
ABC
P0 743
P1 020
P2 600
P3 011
P4 431
Work >= Needi Pi Allocation
ABC ABC ABC
230 020 P1 200
430 011 P3 211
641 431 P4 002
643 600 P2 302
942 743 P0 010 =>tại thời điểm này kô thể cấp phát cho P0 vì (9,4,2) kô >= (7,4,3)

Work >= Needi Pi Allocation
ABC ABC ABC
230 011 P3 211
441 433 P4 002
443 020 P1 010
453
=>tại thời điểm này kô thể cấp phát cho P2 vì (4,5,3) kô >= (6,0,0)
=>tại thời điểm này kô thể cấp phát cho P0 vì (4,5,3) kô >= (7,4,3)

Work >= Needi Pi Allocation
ABC ABC ABC
230 011 P3 211
441 020 P1 010
451 431 P1 002
453
=>tại thời điểm này kô thể cấp phát cho P2 vì (4,5,3) kô >= (6,0,0)
=>tại thời điểm này kô thể cấp phát cho P0 vì (4,5,3) kô >= (7,4,3)

Kết Luận : Tại thời điểm P1 y/cầu mới là (1,0,2) thì hệ thống sẽ rơi vào trạng thái kô an toàn nếu đáp ứng y/cầu của P1, vì vậy sẽ nên đáp ứng y/cầu của P1 để đảm bảo hệ thống vẫn an toàn.
=========
Bài này giải theo ý của mình hiểu nên có chỗ nào sai thì xin chỉ giáo nha các bạn.

Đề bài cùa bạn PhamVanNgo(I11C)
Có 5 tiến trình {P0,P1,P2,P3,P4} và 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). Tại thời điểm T0 :
TT Đang Giữ MAX Hệ Có
ABC ABC ABC
P0 010 753 332
P1 200 322
P2 302 902
P3 211 222
P4 002 433
a) Tìm tất cả các chuỗi an toàn có thể có của hệ thống.
b) Giả xử P1 bây giờ nêu y/cầu mới là (1,0,2) thì xác định xem có nên đáp ứngy/cầu của P1 hay kô? vì sao?

Ta có: Available = (10,5,7) - (7,2,5) = (3,3,2)
Need[i] = Max[i] - Allocation[i]


Tìm các chuỗi an toàn:

...Và còn nhiều chuỗi an toàn khác nữa....
b. Ta thấy, yêu cầu mới (1,0,2) của P1 thoả các điều kiện:
+ Request1 <= Need1 và Request1 <= Available
Vì (1,0,2) <= (1,2,2) và (1,0,2) <= (3,2,2)
+ Trạng thái mới:

....Và có thể còn nhiều chuỗi an toàn khác.....
Do vậy ta có thể cấp thêm cho yêu cầu mới của P1(1,0,2) tại thời điểm này.

Mình cũng hiều sao giài vậy mong các bạn xem giúp.....

Tại câu b: Để làm cho rõ ràng hơn thì ngay sau bước Trạng thái mới
Chúng ta bổ sung thêm:
Need[i] = max[i] -allocation[i]
Cụ thể trường hợp này: Need[1] = max[1] -allocation[1]

	Need
	A	B	C
P0	7	4	3
P1	0	2	0
P2	6	0	0
P3	0	1	1
P4	4	3	1

Còn phần dưới bạn trình bày thì tốt rồi
Mình cũng muốn bổ sung cho bài bạn đầy đủ hơn và rõ ràng, hihi
Chứ mình cũng thấy bạn post nhiều bài hay lắm.
Có gì sai thì bạn góp ý cho mình để tiếp tục hoàn thiện tốt những bài sau nha.