Thuật toán thay trang tối ưu (OPT, Belady) loại bỏ trang sẽ không được dùng trong thời gian lâu nhất ở tương lai. Đây là chuẩn lý thuyết tối thiểu hóa page fault.
Cho số khung F và chuỗi tham chiếu, mô phỏng OPT và đếm page fault. Khi cần loại trang, nếu có trang nào không còn xuất hiện trong tương lai thì loại trang đó trước (ngược lại chọn trang có lần dùng tiếp theo xa nhất).
Ví dụ I/O:
Input:
3
7 0 1 2 0 3 0 4
Output: 6
Dòng 1: số khung F. Dòng 2: chuỗi tham chiếu trang.
1 ≤ F ≤ 100; 1 ≤ độ dài chuỗi ≤ 2000.
Một dòng: tổng page fault tối thiểu (OPT).
Ví dụ:
Đầu vào:
3
7 0 1 2 0 3 0 4
Đầu ra:
6
Giải thích:
Đang tải editor...