CÙNG ÔN BÀI TẬP HỆ ĐIỀU HANH NHA CÁC BẠN

Thuật giải Nhà băng
Câu 1:
Một hệ thống có 3 ổ băng từ và 3 tiến trình P1, P2, P3 với trạng thái cấp phát tài nguyên ở thời điểm Ti thể hiện bằng véc-tơ Allocation = (1, 0, 1) và Max = (1, 2, 2):
Dùng thuật giải nhà băng để:
a. Chứng minh trạng thái này an toàn. (1 điểm)
b. Xác định có nên đáp ứng hay không yêu cầu xin thêm 1 ổ nữa của của P3 ? (1 điểm)


đây là đề bài chúng ta cùng giải nha.

Trước khi giải bài này,cta cùng ôn lại ví dụ trong bài giảng của Thầy trước nha các bạn:
Ví dụ: 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:
Tài nguyên đang giữ(Allocation) |Tài nguyên cực đại được vay( Max) | Hệ có (Available)-tài nguyên còn
... 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 Allocation=7 2 5 (Cộng theo cột Allocation từ trên xuống )
Đây là tổng loại tiền mà các cty đang vay

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)

Work Need(i) P(i) Allocation
A B C A B C A B C
3 3 2 1 2 2 P1 2 0 0
Số tiền nhà băng cho P1 vay lúc này là (1,2,2) và nhà băng còn (2,1,0)
khi này P1 sẽ bị thu hồi (vì đã vay max rồi)=> chuyển về cho Work.
Vậy Số tiền mà nhà băng có ít nhẩt cho công ty tiếp theo vay là:
Work = (3,3,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 3 2 | 1 2 2 |. P1 |2 1 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 >

Va day la bai giai(minh ko chac chan la dung???)

a. Chứng minh trạng thái này an toàn.
Ta có:
Available = 3-2=1
Need = Max- Allocation

Ta có Need của các Tiến trình có thể cấp thêm:
P1: 1-1=0
P2: 2-0=2
P3: 2-1=1
Xét tại thời điểm Ti với đk:Work >= Need[i]

Work------Need[i]------P[i]------Allocation[i]
1-------------0------------ P1-----------1
2-------------2-------------P2-----------0
2-------------1-------------P3-----------1
3

Tại thời điểm Ti,trạng thái là an toàn vì tồn tại chuổi an toàn < p1, p2, p3 >

b. Xác định có nên đáp ứng hay không nếu yêu cầu xin thêm 1 ổ nữa của P3
Với y/c xin thêm 1 ổ nữa của P3,ta có: đặt x=1
Để có thể cấp thêm x phải thỏa các điều kiện sau:
i) x<=Need (Ta có x=1<=Need[3]=1) => Thỏa dk
ii) x<=Available (Ta có x=1 <= Available=1)=> Thỏa đk

Khi đó:
Work------Need[i]------P[i]------Allocation[i]
0--------------0------------P1-----------1
1-------------0-------------P3------------2
3-------------2-------------P2------------0
3
=>Tồn tại chuỗi an toàn(P1,P2,P3) do đó đủ để cấp thêm 1 ổ nữa cho P3.

Mình có đáp án câu a giống bạn, còn câu b thì mình thật sự chưa nắm rõ lắm.

09H1010040_PhuongHuy đã viết:Mình có đáp án câu a giống bạn, còn câu b thì mình thật sự chưa nắm rõ lắm.

sori,vi bai lam sai,minh moi update lai!neu Huy co dap an cau a giong minh,như vay la sai giong nhau roi ,H xem lai nha!

Thiệt tình là dạng bài Thuật giải nhà băng này H hay lộn quá. Cám ơn bạn vophatdat nhiều nha.