BÀI TOÁN DÙNG THUẬT GIẢI NHÀ BĂNG ĐỂ XÁC ĐỊNH TRẠNG THÁI CÓ AN TOÀN?

Một hệ thống có 12 ổ băng từ và 3 tiến trình với bảng cấp phát tài nguyên như sau:

Tiến trình	Đã được cấp phát(số ổ băng)	Tối đa cần(số ổ băng)
P1	5	10
P2	2	4
P3	2	9

Dùng thuật giải Nhà Băng để xác định trạng thái này có an toàn hay không?

Ta có
- Available=12-(5+2+2)=3
- Need=Max-Allocation

P[i]	Allocation	Max	Need	Available
P1	5	10	5	3
P2	2	4	2
P3	2	9	7

Xét tại thời điểm Ti

Work >=	Need[i]	P[i]	Allocation[i]
3	2	P2	2
5	5	P1	5
10	7	P3	2

Vậy tồn tại chuỗi an toàn<P2, P1, P3>.Suy ra trạng thái hệ thống ở thời điểm Ti là an toàn

^^ ông up trể hơn tôi và không có giải thích !! sao các bạn hiểu

Admin
- Nhưng bạn Kim Giáp biết "vẽ" bảng (dễ hình dung hơn), còn em không biết vẽ (chỉ biết thủ công bằng từng ký tự "rời rạc"), tuy "từ ngữ" của em có hơn (tốt).
- Nên học ngay cách tạo bảng và đưa hình lên ! Nhiều khi, hình+bảng mang nhiều thông tin và giúp người xem dễ nắm bắt hơn. Cần cả hai: Từ ngữ và Hình+Bảng.
- Bạn Kim Giáp dùng từ có vẻ chính xác hơn em (chắc rút được kinh nghiệm từ chuyện "Mục quản lớp").

luonghuytai(I92C) đã viết:^^ ông up trể hơn tôi và không có giải thích !! sao các bạn hiểu

Các bạn trong lớp nhìn mấy cái hình đó sẽ hiểu liền.Nếu không hiểu cho nào cho ý kiến, mình sẽ Giải thích.

Lop truong va lop pho dung la cham chi that, vua hoc tren lop ve onl minh da thay bai of 2 ban, can bo lop minh that xung dang de moi nguoi tin tuong hen, minh nghi diem dien dan of 2 ban la tot roi nhung 2 ban van tim hiu va chia se, cam on 2 ban rat nhiu, nhat la lop pho, minh thay ban noi hoi nhieu nhung nhin chung ban rat nhiet tinh, xong xao, nhung fan noi dung minh chua nam bat het minh deu co the nam bat lai qua fan post bai cung nhu qua mail, bai nay lop truong post len hoi ngan gon, neu dien giai them 1 chut nua se de hieu hon , thanks!

Admin
- Cả 2 bạn đều hay. Mỗi người có mặt mạnh-mặt yếu, nên bổ sung được cho nhau.
- Năm nay, thày hài lòng ở 2 bạn phụ trách lớp này.
- Em cần biết và chịu khó gõ dấu vào !

minhtrieu_i92c đã viết:Lop truong va lop pho dung la cham chi that, vua hoc tren lop ve onl minh da thay bai of 2 ban, can bo lop minh that xung dang de moi nguoi tin tuong hen, minh nghi diem dien dan of 2 ban la tot roi nhung 2 ban van tim hiu va chia se, cam on 2 ban rat nhiu, nhat la lop pho, minh thay ban noi hoi nhieu nhung nhin chung ban rat nhiet tinh, xong xao, nhung fan noi dung minh chua nam bat het minh deu co the nam bat lai qua fan post bai cung nhu qua mail, bai nay lop truong post len hoi ngan gon, neu dien giai them 1 chut nua se de hieu hon , thanks!

Minh Triều không hiểu chỗ nào trên bài tập này để mình giải thích.Bạn cứ hỏi cho chưa hiểu, mình giải thích nếu không được thì còn các bạn khác nữa sẽ hỗ trợ giải thích cho bạn, còn đến mức không thể thì Thày sẽ giải thích dùm.

kimgiap(i92c) đã viết:

minhtrieu_i92c đã viết:Lop truong va lop pho dung la cham chi that, vua hoc tren lop ve onl minh da thay bai of 2 ban, can bo lop minh that xung dang de moi nguoi tin tuong hen, minh nghi diem dien dan of 2 ban la tot roi nhung 2 ban van tim hiu va chia se, cam on 2 ban rat nhiu, nhat la lop pho, minh thay ban noi hoi nhieu nhung nhin chung ban rat nhiet tinh, xong xao, nhung fan noi dung minh chua nam bat het minh deu co the nam bat lai qua fan post bai cung nhu qua mail, bai nay lop truong post len hoi ngan gon, neu dien giai them 1 chut nua se de hieu hon , thanks!

Minh Triều không hiểu chỗ nào trên bài tập này để mình giải thích.Bạn cứ hỏi cho chưa hiểu, mình giải thích nếu không được thì còn các bạn khác nữa sẽ hỗ trợ giải thích cho bạn, còn đến mức không thể thì Thày sẽ giải thích dùm.

Đầu tiên cáo lỗi với lớp trưởng nha,vì bài này post lên lúc chưa đọc nhắc nhở của lớp trưởng nên vẫn chưa có gõ tiếng Việt có dấu,phần này mình nắm bài trên lớp rồi, ý mình muốn nói là giải thích cho rõ ràng hơn thôi, vì bài này chỉ có 1 loại tài nguyên.Thêm nữa mình muốn biết nếu mình bắt đầu từ P2 hoặc P3 thì sao?
Với lại hồi nãy trên lớp mình có nghe thầy nói có thể tìm những chuỗi an toàn khác cũng được, vậy co phải là bắt đầu từ 1 tiến trình khác P1 (hoặc P0) hay không?hay làm cách khác, bạn nào giải thích đi, mình nghĩ thắc mắc này không của riêng mình.

minhtrieu_i92c đã viết:

kimgiap(i92c) đã viết:

minhtrieu_i92c đã viết:Lop truong va lop pho dung la cham chi that, vua hoc tren lop ve onl minh da thay bai of 2 ban, can bo lop minh that xung dang de moi nguoi tin tuong hen, minh nghi diem dien dan of 2 ban la tot roi nhung 2 ban van tim hiu va chia se, cam on 2 ban rat nhiu, nhat la lop pho, minh thay ban noi hoi nhieu nhung nhin chung ban rat nhiet tinh, xong xao, nhung fan noi dung minh chua nam bat het minh deu co the nam bat lai qua fan post bai cung nhu qua mail, bai nay lop truong post len hoi ngan gon, neu dien giai them 1 chut nua se de hieu hon , thanks!

Minh Triều không hiểu chỗ nào trên bài tập này để mình giải thích.Bạn cứ hỏi cho chưa hiểu, mình giải thích nếu không được thì còn các bạn khác nữa sẽ hỗ trợ giải thích cho bạn, còn đến mức không thể thì Thày sẽ giải thích dùm.

Đầu tiên cáo lỗi với lớp trưởng nha,vì bài này post lên lúc chưa đọc nhắc nhở của lớp trưởng nên vẫn chưa có gõ tiếng Việt có dấu,phần này mình nắm bài trên lớp rồi, ý mình muốn nói là giải thích cho rõ ràng hơn thôi, vì bài này chỉ có 1 loại tài nguyên.Thêm nữa mình muốn biết nếu mình bắt đầu từ P2 hoặc P3 thì sao?
Với lại hồi nãy trên lớp mình có nghe thầy nói có thể tìm những chuỗi an toàn khác cũng được, vậy co phải là bắt đầu từ 1 tiến trình khác P1 (hoặc P0) hay không?hay làm cách khác, bạn nào giải thích đi, mình nghĩ thắc mắc này không của riêng mình.

- Work>=Need So sánh giá trị Work và Need nếu không thỏa điều kiện này thì tạm thời bỏ qua tiến trình đang xét để xét tiếp đến tiến trình kế tiếp cho đến khi nào thỏa sẽ thực hiện.
Thêm nữa mình muốn biết nếu mình bắt đầu từ P2 hoặc P3 thì sao? Nên bắt đầu từ P2 thì được còn P3 không thỏa điều kiện Work>=Need.

Mình xin trả lời câu hỏi của bạn Triều về: " Thêm nữa mình muốn biết nếu mình bắt đầu từ P2 hoặc P3 thì sao?
Với lại hồi nãy trên lớp mình có nghe thầy nói có thể tìm những chuỗi an toàn khác cũng được, vậy co phải là bắt đầu từ 1 tiến trình khác P1 (hoặc P0) hay không?hay làm cách khác, bạn nào giải thích đi, mình nghĩ thắc mắc này không của riêng mình."

Trong trường hợp của bài tập này thì không thể bắt đầu từ P1 hay P3 trước được. Vì Work=3 không thỏa điều kiện >= Need[1]=5 và Need[3]=7, trong khi đó Need[2]=2, thỏa điều kiện (MinhTrieu xem kỹ trong bảng trạng thái KimGiap post ở trên). Chính vì vậy mình sẽ bắt đầu từ P2 trước.
Trên lớp thầy nói có thể bắt đầu từ 1 tiến trình khác là đúng, nhưng trong bài tập này thì chỉ có P2 thỏa điều kiện để bắt đầu cho ra 1 chuỗi an toàn.

oke thanks G nhiều nhé, mấy giải thuật này cần vẽ hình dễ nhìn

Đọc xong những bài post của các bạn về bài học tối qua Thầy giảng trên lớp,mình thấy mâu thuẫn giũa các bạn cũng không có gì phải quan tâm nhiều.Quan trọng là chúng mình cùng hiểu rõ bài học hôm qua của Thầy và giải các bài tập về Thuật giải Nhà băng thật nhuần nhuyễn để sau này áp dụng vào công việc của mình như Thầy đã nói về tầm quan trọng và cái thú vị của nó.Chúc các bạn học tốt nha.

Bổ sung câu b cho bài tập này:
b.) Xác định có nên đáp ứng hay không yêu cầu xin thêm 1 ổ nữa của P3?
Giải:
Yêu cầu này thỏa các điều kiện:
1. Request[3] <= Need[3] vì 1 <= 7
2. Request[3] <= Available[3] vì 1 <= 3

Ta có trạng thái mới:



Xét tại thời điểm Ti



Ta thấy Need[1] = 5 và Need[2] = 6 trong khi Work =4 => Không thỏa mãn điều kiện Work >= Need => Không tìm thấy chuỗi an toàn.

Vậy không nên đáp ứng yêu cầu xin thêm 1 ổ nữa của P3 vì hệ sẽ chuyển sang trạng thái không an toàn do không tồn tại chuỗi an toàn.

kimgiap(i92c) đã viết:Một hệ thống có 12 ổ băng từ và 3 tiến trình với bảng cấp phát tài nguyên như sau:

Tiến trình	Đã được cấp phát(số ổ băng)	Tối đa cần(số ổ băng)
P1	5	10
P2	2	4
P3	2	9

Dùng thuật giải Nhà Băng để xác định trạng thái này có an toàn hay không?

Ta có
- Available=12-(5+2+2)=3
- Need=Max-Allocation

P[i]	Allocation	Max	Need	Available
P1	5	10	5	3
P2	2	4	2
P3	2	9	7

Xét tại thời điểm Ti

Work >=	Need[i]	P[i]	Allocation[i]
3	2	P2	2
5	5	P1	5
10	7	P3	2

Vậy tồn tại chuỗi an toàn<P2, P1, P3>.Suy ra trạng thái hệ thống ở thời điểm Ti là an toàn

hôm này mình cũng đang chuẩn bị định đưa bài tập thuật giải nhà bằng lên,mà thấy bạn giải hay mà chính xác quả,thấy cách trình bày dễ hiểu hiểu nữa ,cảm ơn bạn nhiều đã đưa bài lên cho các bạn tham khảo nha

Mình cũng định lúc rảnh sẽ post bài giải lên nhưng thấy Giáp và các bạn đã làm rất là chuẩn rồi .....nên không dám múa rìu wa mắt thợ nữa......Mong rằng lớp ta luôn tích cực phát huy tinh thần học tập này......Để toàn thể các bạn có thể hiểu và hoàn thành tốt các kiến thức mà Thầy đã truyền đạt......^_^