Linux & OSKhi bộ nhớ vật lý đầy mà cần nạp trang mới, OS phải chọn một trang để thay ra:
- FIFO: thay trang được nạp vào sớm nhất. Đơn giản nhưng không quan tâm trang đó còn dùng nhiều hay không.
- LRU (Least Recently Used): thay trang lâu nhất chưa được truy cập, dựa trên nguyên lý locality — trang vừa dùng thường sẽ được dùng lại. Xấp xỉ tốt Optimal nhưng tốn chi phí theo dõi thời điểm truy cập.
- Optimal (OPT/Belady): thay trang sẽ được dùng xa nhất trong tương lai → số page fault tối thiểu. Nhưng cần biết trước tương lai nên chỉ dùng làm mốc so sánh, không cài đặt thực tế.
Belady’s Anomaly: với FIFO, tăng số khung trang (frame) đôi khi lại làm page fault TĂNG thay vì giảm — trái trực giác. LRU và OPT không gặp hiện tượng này vì chúng thuộc lớp stack algorithm.