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 LFU (ít dùng nhất)

    Mô phỏng thuật toán thay trang LFU (Least Frequently Used) với F khung trang.

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

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

    1. Nếu trang đã có (hit): tăng bộ đếm của nó thêm 1.
    2. Nếu chưa có (miss → fault):
      • Nếu còn khung trống: nạp vào, đặt bộ đếm = 1.
      • Nếu đầy: chọn trang có bộ đếm nhỏ nhất để thay. Nếu nhiều trang cùng bộ đếm nhỏ nhất, thay trang được nạp vào sớm nhất (FIFO làm tie-break). Trang mới có 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, cnt: trang1=2,trang2=1 -> thay trang2 (nhỏ nhất). 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: cnt trang1=2,trang2=1 -> thay trang2. Tổng 3 fault.

    Đang tải editor...