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] Đếm page fault thuật toán Optimal (OPT)

    Mô phỏng thuật toán thay trang Optimal (OPT / Belady) và đếm số page fault.

    Khi khung đầy và xảy ra fault, loại trang sẽ được dùng xa nhất trong tương lai — nếu một trang trong khung không còn được dùng nữa thì loại nó ngay (ưu tiên trang gặp đầu tiên trong khung theo thứ tự nạp khi có nhiều trang không dùng lại).

    Thuật toán: với mỗi page fault và khung đầy, với mỗi trang f đang ở trong khung, tìm vị trí xuất hiện kế tiếp của f trong phần còn lại của chuỗi. Trang có vị trí kế tiếp xa nhất (hoặc không xuất hiện) là nạn nhân. (Khi duyệt khung theo thứ tự nạp, trang không-xuất-hiện-lại đầu tiên được chọn ngay.)

    Ví dụ: cap=3, chuỗi 7 0 1 2 0 3 0 4. Số page fault OPT = 6.

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

      Dòng đầu: cap m. Dòng sau: m số — chuỗi tham chiếu trang.

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

      1 ≤ cap ≤ 50; 1 ≤ m ≤ 5000; 0 ≤ trang ≤ 1000000.

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

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

    Ví dụ:

    Đầu vào:

    3 8
7 0 1 2 0 3 0 4

    Đầu ra:

    6

    Giải thích:

    cap=3. 7,0,1 fault→[7,0,1]. 2 fault: tương lai 0 còn dùng (idx4), 1 và 7 không dùng lại → loại 7 (gặp đầu tiên trong khung)→[0,1,2]. 0 hit. 3 fault: trong {0,1,2} chỉ 0 còn dùng (idx6), 1 và 2 không → loại 1→[0,2,3]. 0 hit. 4 fault: 0,2,3 đều không dùng lại → loại 0 (đầu khung)→[2,3,4]. Tổng fault OPT = 6 (các bài fault: 7,0,1,2,3,4).

    Đang tải editor...