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] Bất thường Belady với FIFO

    Bất thường Belady (Belady's Anomaly) là hiện tượng: với thuật toán FIFO, việc TĂNG số khung trang đôi khi lại làm TĂNG số page fault.

    Cho một chuỗi tham chiếu và hai số khung F1 < F2. Hãy:

    1. Mô phỏng FIFO với F1 khung, đếm số fault a.
    2. Mô phỏng FIFO với F2 khung, đếm số fault b.

    FIFO: khi miss và bộ nhớ đầy, thay trang được nạp vào sớm nhất (hàng đợi FIFO theo thứ tự nạp). Hit không đổi thứ tự.

    In ra ba giá trị cách nhau dấu cách: a, b, và 1 nếu xảy ra bất thường Belady (b > a) hoặc 0 nếu không.

    Ví dụ chuỗi cổ điển 1 2 3 4 1 2 5 1 2 3 4 5 với F1=3, F2=4 cho a=9, b=10 → có bất thường (in 9 10 1).

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

      Dòng đầu: F1 F2 M (F1 < F2, M là độ dài chuỗi). Dòng tiếp: M số chuỗi tham chiếu.

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

      1 ≤ F1 < F2 ≤ 1000; 1 ≤ M ≤ 100000.

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

      Ba số: số fault với F1, số fault với F2, và 1/0 cho biết có/không bất thường Belady.

    Ví dụ:

    Đầu vào:

    3 4 12
1 2 3 4 1 2 5 1 2 3 4 5

    Đầu ra:

    9 10 1

    Giải thích:

    FIFO với 3 khung cho 9 fault; với 4 khung cho 10 fault. Vì 10>9 nên xảy ra bất thường Belady => in 9 10 1.

    Đang tải editor...