Dikarenakan algoritma optimal sangat sulit dalam pengimplementasiannya, maka dibuatlah algoritma lain yang
performance-nya mendekati algoritma optimal dengan sedikit
cost yang lebih besar. Algoritma ini mengganti halaman yang paling lama tidak dibutuhkan. Asumsinya, halaman yang sudah lama tidak digunakan sudah tidak dibutuhkan lagi dan kemungkinan besar, halaman yang baru di-
load akan digunakan kembali.
Sama seperti algoritma optimal, algoritma LRU tidak mengalami anomali Belady. Algoritma ini memakai
linked list untuk mendata halaman mana yang paling lama tidak terpakai.
Linked list inilah yang membuat
cost membesar, karena harus meng-
update linked list tiap saat ada