Thắc mắc về cách tìm chuỗi an toàn trong thuật giải nhà băng

TranKimKhoa(102c) 6/5/2011, 08:48

Em xin lấy ví dụ điển hình là bài tập thầy giảng trên lớp về cách tìm chuỗi an toàn trong thuật giải nhà băng, theo phương pháp bản quyền của thầy, em nhận thấy muốn tìm được chuỗi an toàn của 5 tiến trình P0, P1, P2, P3, P4, P5, ta phải hoán vị các vị trí của 5 tiến trình này với nhau cho đến khi ra được chuỗi an toàn, có nghĩa là phải xét ít hơn hoặc bằng 5! = 120 trường hợp. Giả sử bài toán chỉ có 1 chuỗi an toàn, nếu hên thì trong 10 lần xét đầu tiên ra, còn xui thì... có thể 100 hoặc hơn.

Không biết suy nghĩ của em có đúng không, mong thầy và các bạn giúp đỡ thêm. Giả sử điều em nói là đúng thì khi ra thi nhỡ thầy cho 5 hoặc 6 tiến trình thì làm sao đủ thời gian để làm Razz

Admin
- Không cần phải quá "rắc rối" như vậy. Hãy tư duy thực tế hơn ! Mọi việc đơn giản nhưng lại cho là phức tạp.
- Mà "Lý thuyết" vậy vẫn sai đấy: Độ phức tạp chỉ có O(n²) thôi, với n là tổng số tiến trình, lấy đâu ra tới n!.

vongocminhhoang (102C) 6/5/2011, 08:54

chắc là như vậy rồi đó. nếu như tìm được 1 chuỗi an toan rồi thì break; để làm tiếp câu tiếp theo không thôi hết giờ Very Happy

. nếu mà xui gặp bài nào không có chuỗi an toàn, thì khi đó phải tìm hết n! (với n là số tiến trình) trường hợp rồi mới kết luận được là không có chuỗi an toàn Sad

BuiThiLanChi (102C) 6/5/2011, 09:00

nhưng đề thi thầy ra có 3 tiến trình thôi, chắc cũng ko sao đâu

nguyenphicuong (i92c) 6/5/2011, 09:18

TranKimKhoa(102c) đã viết:Em xin lấy ví dụ điển hình là bài tập thầy giảng trên lớp về cách tìm chuỗi an toàn trong thuật giải nhà băng, theo phương pháp bản quyền của thầy, em nhận thấy muốn tìm được chuỗi an toàn của 5 tiến trình P0, P1, P2, P3, P4, P5, ta phải hoán vị các vị trí của 5 tiến trình này với nhau cho đến khi ra được chuỗi an toàn, có nghĩa là phải xét ít hơn hoặc bằng 5! = 120 trường hợp. Giả sử bài toán chỉ có 1 chuỗi an toàn, nếu hên thì trong 10 lần xét đầu tiên ra, còn xui thì... có thể 100 hoặc hơn.

Không biết suy nghĩ của em có đúng không, mong thầy và các bạn giúp đỡ thêm. Giả sử điều em nói là đúng thì khi ra thi nhỡ thầy cho 5 hoặc 6 tiến trình thì làm sao đủ thời gian để làm

Suy nghĩ của bạn rất là hay, nhưng theo mình nghĩ đề thi chỉ có khoảng 3 tiến trình và sẽ có chuỗi an toàn. Thầy ra đề thi để kiểm tra kiến thức căn bản của tụi mình, chứ không phải để thách đố chúng ta. Hơn nữa thời gian làm bài cũng không nhiều, mình nghĩ thầy hiểu điều đó và sẽ ra đề phù hợp để chúng ta có thể hoàn thành tốt bài làm.

LuuDucPhu (102C) 6/5/2011, 09:35

Mình nghĩ không cần xét nhiều đến thế đâu, cứ làm đúng thuật giải đó là WORK luôn luôn >= NEEDi nếu không tìm được Need nào trong tập tiến trình thì hệ thống không an toàn còn nếu thỏa hết thì thì tồn tại chuỗi an toàn, chuỗi an toàn thì chỉ cần 1 là đủ rồi Smile

vunhattien(102c) 6/5/2011, 09:40

Nếu thầy ra đề như chủ topic thắc mắc thì ai cũng ngỏe hết ko riêng chủ topic, yên tâm nhe'

trantanphat102C 6/5/2011, 09:49

Ví dụ nhiều vậy chứ đề thi có ít thôi. Mình học phần này trước rồi cách của thầy hay nhưng hơi khó hiểu. Phần mền của thầy giới thiệu rất hay.

nguyenminhduong(102c) 6/5/2011, 11:10

TranKimKhoa(102c) đã viết:Em xin lấy ví dụ điển hình là bài tập thầy giảng trên lớp về cách tìm chuỗi an toàn trong thuật giải nhà băng, theo phương pháp bản quyền của thầy, em nhận thấy muốn tìm được chuỗi an toàn của 5 tiến trình P0, P1, P2, P3, P4, P5, ta phải hoán vị các vị trí của 5 tiến trình này với nhau cho đến khi ra được chuỗi an toàn, có nghĩa là phải xét ít hơn hoặc bằng 5! = 120 trường hợp. Giả sử bài toán chỉ có 1 chuỗi an toàn, nếu hên thì trong 10 lần xét đầu tiên ra, còn xui thì... có thể 100 hoặc hơn.

Không biết suy nghĩ của em có đúng không, mong thầy và các bạn giúp đỡ thêm. Giả sử điều em nói là đúng thì khi ra thi nhỡ thầy cho 5 hoặc 6 tiến trình thì làm sao đủ thời gian để làm

Bạn nghĩ hơi cao xa rồi đó. Theo phương pháp của thầy, ta sắp xếp lại thứ tự của các tiến trình theo điều kiện (Work >=Need) hẳn hoi, thì ngay trong lần đầu tiên đã có chuỗi an toàn hoặc không có. Và chỉ cần một chuỗi thôi.
Nữa là chắc thầy không có ra nhiều tiến trình quá đâu,hehe.

bigcat 6/5/2011, 11:27

Chào bạn Trần Kim Khoa,

Bạn lo lắng phải tìm n! chuỗi khi có n tiến trình là không cấn thiết, đó là trường hợp ta vét cạn khi lập trình, mà giả sử khi lập trình thì ta cũng chặn, không cho vét cạn, mất thời gian, mặc dù việc tính tóan khi lập trình là “chuyện nhỏ” với CPU rồi phải không! Vì rõ ràng, chuỗi an tòan phải là tập hợp n tiến trình sao cho hệ không deadlock. Giả sử ta có P1,P2….Pn tiến trình, ta xét P1,P?,P?....Pn ( P1 đứng đầu chuỗi), nếu P1 không thỏa hệ an tòan => Lọai trường hợp P1 đứng đầu ra…. Nên giả sử thầy cho 5 tiến trình và cho tìm nhiều hơn 1 chuỗi an tòan thì không đáng ngại đâu. Mình chia sẻ cách này, nếu bạn cải biên tốt thì share lại nhé ^.^.
Như chúng ta đã biết,
1/ chuỗi an tòan có nhiều chuỗi, nghiã là thứ tự các tiến trình trong chuỗi an tòan khác nhau.
2/ Tiến trình nào thực hiện xong sẽ trả lại tài nguyên.
3/ Tiến trình nào muốn xong thì lượng tài nguyên đang rảnh phải đủ cung cấp cho tiến trình.

Dựa vào 03 đặc điểm trên, ta có thể nhanh chóng tìm ra chuỗi an tòan bằng cách nhìn số luợng tài nguyên của mỗi tiến trình đang cần và so sánh với số tài nguyên đang rảnh của hệ , khi đó ta chọn tiến trình nào ĐÃ ĐUỢC CẤP TÀI NGUYÊN NHIỀU NHẤT, mà SỐ LƯỢNG TÀI NGUYÊN ĐANG RẢNH ĐỦ CUNG CẤP CHO TIẾN TRÌNH NÀY (khi đó nó sẽ TRả LạI NHIềU TÀI NGUYÊN, do nó đã xong việc), từ đó số luợng tài nguyên rảnh sẽ tăng cao để cung cấp cho các tiến trình còn lại và dễ dàng tìm ra chuỗi an tòan.

Big Cat - Phạm Xuân Trinh

NguyenTuanDuy(83C) 6/5/2011, 13:35

Mình thấy kinh nghiệm tìm chuỗi an toàn theo tiến trình nào có Need nhỏ nhất thì cho nó lên trước. VD như P1 cần 5, P2 cần 3 và P3 cần 2 thì xét chuỗi an toàn theo P3,P2,P1 trước tiên rồi xét tới các chuỗi khác. ai có cách nào tìm nhanh thì Post bài lên cho A/e tham khảo với nha ? Thanks trước cái

NguyenManhTuan(102C) 6/5/2011, 15:27

NguyenTuanDuy(83C) đã viết:Mình thấy kinh nghiệm tìm chuỗi an toàn theo tiến trình nào có Need nhỏ nhất thì cho nó lên trước. VD như P1 cần 5, P2 cần 3 và P3 cần 2 thì xét chuỗi an toàn theo P3,P2,P1 trước tiên rồi xét tới các chuỗi khác. ai có cách nào tìm nhanh thì Post bài lên cho A/e tham khảo với nha ? Thanks trước cái

Mình thấy cách này là oke rồi, cứ lấy cái Needi nào đủ tiêu chuẩn thì lần lượt cho vô, nếu tồn tại chuỗi an toàn, thế nào những cái Needi sau cũng được đáp ứng, vì những cái Avaluble sau được cộng dồn từ những cái Needi trước.

TonThatTrong_102C 6/5/2011, 16:18

Theo mình thấy thì chắc thầy chỉ cho những con số nhỏ nên việc xác định có tìm được chuỗi an toàn hay không thì với người tinh mắt thì chỉ cần nhìn các con số đã tính ra ở trên thì ta đã có thể xác định được có chuỗi an toàn hay không rồi. Nên mình nghĩ vấn đề có hay không chuỗi an toàn không phải là chuyện lớn nếu đã làm đúng các bước trước đó.

levantrung102 (102C) 7/5/2011, 01:23

Đúng vậy, chỉ cần làm theo các bước như trong "bản quyền" của thầy, đặt 2 ngón tay vào và tính, xét hệ có không quá 3 tiến trình làm nhiều lần cái đã để mà mình làm tốt bài thi trước, vì thầy nói chỉ cho thi hệ có 1 tiến trình thôi mà.
Bạn làm mình muốn tìm tài liệu nghiên cứu quá đi! study

Admin
- Sao lại cho thi chỉ có 1 tiến trình ? Có một thì tranh chấp với ai ?
- Em lẫn với ràng buộc: Có thể cho thi với 1 loại tài nguyên thôi, còn với nhiều loại như A (ví dụ USD), B (EURO) và C (JPY) thì khó hơn chút.

Sponsored content

Thắc mắc về cách tìm chuỗi an toàn trong thuật giải nhà băng