Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Hệ điều hành] Thay trang MFU (dùng nhiều nhất)

    Mô phỏng thuật toán thay trang MFU (Most Frequently Used) với F khung trang. MFU dựa trên lập luận: trang có bộ đếm nhỏ nhất có lẽ vừa được nạp và sẽ còn dùng, nên thay trang dùng NHIỀU nhất.

    Mỗi trang có bộ đếm tần suất (số lần truy cập kể từ khi nạp).

    Thuật toán cho mỗi trang:

    1. Hit: tăng bộ đếm thêm 1.
    2. Miss (fault):
      • Còn khung trống: nạp, bộ đếm = 1.
      • Đầy: chọn trang có bộ đếm LỚN nhất để thay. Nếu nhiều trang cùng bộ đếm lớn nhất, thay trang nạp vào sớm nhất. Trang mới bộ đếm = 1.

    In ra tổng số page fault.

    Ví dụ: F=2, chuỗi 1 1 2 3. 1 fault(cnt1)->1 hit(cnt2)->2 fault(cnt1)->3 miss đầy: trang1 cnt=2 lớn nhất -> thay trang1. Tổng 3 fault.

    • Định dạng đầu vào:

      Dòng đầu: F M. Dòng tiếp: M số chuỗi tham chiếu.

    • Ràng buộc đầu vào:

      1 ≤ F ≤ 1000; 1 ≤ M ≤ 100000; số hiệu trang ≥ 0.

    • Định dạng đầu ra:

      Một số nguyên: tổng số page fault.

    Ví dụ:

    Đầu vào:

    2 4
1 1 2 3

    Đầu ra:

    3

    Giải thích:

    1 fault(cnt1); 1 hit(cnt2); 2 fault(cnt1); 3 miss đầy: trang1 cnt=2 lớn nhất bị thay. Tổng 3 fault.

    Đang tải editor...