[Help]Tìm Số Page Fault Tối Thiểu ,Tối Đa Môn Hệ Điều Hành

[11520207]

Anh em nào vào giúp mình giải bài tập này với, hix:hungry:

Giả sử có một chuỗi truy xuất bộ nhớ có chiều dài p với n số hiệu trang khác nhau xuất hiện trong chuỗi. Giả sử hệ thống sử dụng m khung trang ( khởi động trống). Với một thuật toán thay thế trang bất kỳ :
	– Cho biết số lượng tối thiểu các lỗi trang xảy ra ? (1 điểm)
	– Cho biết số lượng tối đa các lỗi trang xảy ra khi m=1 và khi m>=n? (1 điểm)

[11520444]

Theo mình biết thì trong các giải thuật thì giải thuật OPT có số lượng page fault ít nhất ( nếu câu này thì mình làm theo giải thuật OPT tìm số page fault ).
Còn tối đa thì là FIFO rồi.
Đây là hình so sánh các giải thuật thay thế trang.HĐH.jpg
Mọi người xem đúng ko giải quyết với. Tại loanh quoanh trên mạng tìm được cái hình đó

[11520317]

Theo mình biết thì trong các giải thuật thì giải thuật OPT có số lượng page fault ít nhất ( nếu câu này thì mình làm theo giải thuật OPT tìm số page fault ).
Còn tối đa thì là FIFO rồi.
Đây là hình so sánh các giải thuật thay thế trang.[ATTACH=CONFIG]6229[/ATTACH]
Mọi người xem đúng ko giải quyết với. Tại loanh quoanh trên mạng tìm được cái hình đó

Đã có dữ liệu cho các trang thay thế đâu... Vấn đề đặt ra là làm thế nào ? Mà đề chỉ cho m, n, p thôi mà.
Cái này không cần dựa vào giải thuật nào hết, mà chỉ ra được trong các "xác xuất" có thể xảy ra, chỉ ra được thằng nào xấu nhất và thằng nào tốt nhất.
Nói đơn giản kết quả sẽ là 2 biểu thức có mối tương quan liên hệ giữa 3 giá trị p, m, n.

[11520086]

Nếu có m khung thì theo mình nghĩ là tối thiểu m lỗi trang (Chỉ là suy nghĩ)

[11520537]

Nếu có m khung thì theo mình nghĩ là tối thiểu m lỗi trang (Chỉ là suy nghĩ)

một suy nghĩ không logic tẹo nào.

[11520268]

Đang suy nghĩ câu này,cái này chắc chắn là phải tính đến việc số lần xuất hiện trung bình của 1 số hiệu trang,nhưng mà chưa biết hướng giải quyết ra làm sao(số lần xuất hiện trung bình của 1 số hiệu trang là p/n)

[11520537]

mình nghĩ thế này, với bất kỳ m, vì lúc đầu các khung trang trống, nên trong m lần thế trang đầu tiên thì kết quả tệ nhất là m lỗi trang (cái này chuẩn không cần chỉnh),
mà chuỗi tham khảo trang dài p cộng với điều kiện siêu xấu là n số hiệu trang khác nhau phân bố quá xâu thì kết quả tệ nhất là p, không thể quá p được (cái này cũng chuẩn không phải chỉnh), từ đó ta kết luận được, số lỗi trang cực đại là p.
trong trường hợp êm thấm nhất với m lần tham khảo trang đầu tiên có số lỗi trang là 1 (vì bao giờ bắt đầu cũng lỗi với các khung trang trống), tiếp theo ta thấy có n số hiệu trang khác nhau nên không thể tránh khỏi n lần lỗi trang, mà nếu trong m lần tham khảo đầu tiên muốn có lỗi trang là 1 thì m số hiệu trang đầu tiên phải giống nhau và còn n-1 số hiệu trang khác nên kết luận số lỗi trang cực tiêu là n. chấm dứt câu a trong niềm hân hoan tột độ.
bước sang câu b với niềm tin mãnh liệt hơn vì biết trước m.
nếu m =1 thì số lỗi trang tệ nhất vẫn là p, vì sao? nếu không có hai số hiệu trang giống nhau lien tiếp thì p lần lỗi trang chứ sao, chốt ngay lỗi trang cực đại là p, khi mọi chuyện êm thấm hơn với tối đa cực đại các số hiệu trang giống nhau đứng lien tiếp nhau nhưng vẫn không tránh khỏi có n số hiệu trang khác nhau nên chốt ngay cực tiểu là n.
nếu m >= n thì số lỗi trang tệ nhất sẽ giảm xuống n, vì đầu tiên không tránh khỏi lỗi trang đầu tiên nhưng tiếp tục tệ quá có n số hiệu trang khác nhau (kể cả cái đầu tiên) lien tiếp thì tối đa sẽ là n lỗi trang, và khi có được n số hiệu trang này rồi thì không lo lỗi nữa vì đã ăn đủ n số hiệu trang khác rồi. Và còn một cái nữa là số lỗi trang cực tiểu, khi đó cũng sẽ không tránh được n số hiệu trang khác nhau nên cực tiểu vẫn sẽ là n.

chốt hạ:
câu a: cực tiểu n, cực đại p
câu b: m = 1: cực tiểu n, cực đại p
m>=n: cực tiểu n, cực đại n

đó là bài làm nháp của mình, không biết đúng hay sai, ai phát hiện lỗi nào thì cùng sửa nha.

[11520444]

Đã có dữ liệu cho các trang thay thế đâu... Vấn đề đặt ra là làm thế nào ? Mà đề chỉ cho m, n, p thôi mà.
Cái này không cần dựa vào giải thuật nào hết, mà chỉ ra được trong các "xác xuất" có thể xảy ra, chỉ ra được thằng nào xấu nhất và thằng nào tốt nhất.
Nói đơn giản kết quả sẽ là 2 biểu thức có mối tương quan liên hệ giữa 3 giá trị p, m, n.

Đọc chưa kĩ đề.

[11520481]

mình có cùng đáp án với Trần Đại Dương

[11520537]

mình có cùng đáp án với Trần Đại Dương

đã có một thằng đồng phạm!

[11520327]

một suy nghĩ không logic tẹo nào.

không logic chỗ nào? nói người ta sai thì cũng phải chỉ ra sai ở đâu chứ!

[11520289]

đã có một thằng đồng phạm!

Bác Dương thâm wa ! :funny:
Vậy cho em ké 1 vé đồng phạm vậy :brick::brick:

[11520207]

Thank mấy bác nhiều :salute:. Em đã "thông "

[11520126]

Đề thi ra ngay câu này mới ghê chứ :dreaming:

[11520537]

ca 1 trúng ngay câu này, hy vọng các bạn lấy trọn điểm câu này.