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] Optimal vs LRU — khoảng cách page fault

    Optimal vs LRU — khoảng cách số page fault

    So sánh hai thuật toán thay trang trên cùng chuỗi tham chiếu với f frame:

    • OPT (Optimal): khi đầy, loại trang sẽ được dùng xa nhất trong tương lai; trang không còn được dùng lại coi như khoảng cách vô hạn. Nếu hai trang cùng khoảng cách (cùng không dùng lại), chọn trang có số hiệu nhỏ hơn.
    • LRU: loại trang lâu nhất chưa được dùng (last-used nhỏ nhất).

    Thuật toán

    • Chạy độc lập OPT và LRU, đếm page fault mỗi bên.
    • In fault_OPT fault_LRU (LRU - OPT). Hiệu này không âm vì OPT là tối ưu.

    Ví dụ

    f=2, chuỗi 1 2 3 1. LRU: nạp 1,2 (2 fault); 3 loại 1 (fault); 1 loại 2 (fault) → 4. OPT: nạp 1,2; gặp 3 loại 2 (vì 2 không dùng lại) → 1 còn trong frame nên hit → 3 fault. In 3 4 1.

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

      Dòng 1: f. Dòng 2: m. Dòng 3: m số hiệu trang.

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

      1 ≤ f ≤ 50; 1 ≤ m ≤ 2000; 0 ≤ số_trang ≤ 10^4.

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

      fault_OPT fault_LRU hiệu (hiệu = LRU − OPT).

    Ví dụ:

    Đầu vào:

    2
4
1 2 3 1

    Đầu ra:

    3 4 1

    Giải thích:

    LRU: 1,2 fault; 3 loại 1; 1 loại 2 → 4 fault. OPT: 1,2 fault; 3 loại 2 (2 không dùng lại) → 1 hit. OPT=3. In `3 4 1`.

    Đang tải editor...