Algoritma Penggantian Page LRU

Dikarenakan Algoritma Optimal sangat sulit dalam pengimplementasiaannya, maka dibuatlah algoritma lain yang performancenya mendekati algoritma optimal dengan sedikit cost yang lebih besar. Algoritma ini menganti halaman yang sudah lama tidak digunakan sudah tidak dibutuhkan lagi dan kemungkinan besar halamann yang baru di load akan digunakan kembali.

Sama seperti algoritma optimal, algoritma LRU (Least Recently Used) 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 halaman yang di akses. Halaman yang berada di linked list paling depan adalah halaman yang baru saja digunakan. Semakin lama tidak dipakai, halaman akan berada semakin belakang dan di posisi terakhir adalah halaman yang paling lama tidak digunakan dan siap untuk di-swap.

Implementasi Algoritma LRU

Ada beberapa cara untuk mengimplementasikan algoritma LRU. Tetapi, yang cukup terkenal ada 2, yaitu counter dan stack. Contoh algoritma di atas menggunakan stack.

 

• 
  
  Counter. Cara ini dilakukan dengan menggunakan counter atau logical clock. Setiap halaman memiliki nilai yang pada awalnya diinisialisasi dengan 0. Ketika mengakses ke suatu halaman baru, nilai pada clock di halaman tersebut akan bertambah 1. Semakin sering halaman itu diakses, semakin besar pula nilai counter-nya dan sebaliknya. Untuk melakukan hal itu dibutuhkan extra write ke memori. Selain berisi halaman-halaman yang sedang di-load, memori juga berisi tentang counter masing-masing halaman. Halaman yang diganti adalah halaman yang memiliki nilai clock terkecil, yaitu halaman yang paling jarang diakses. Kekurangan dari cara ini adalah memerlukan dukungan tambahan counter pada hardware.

• Stack. Cara ini dilakukan dengan menggunakan stack yang menandakan halaman-halaman yang berada di memori. Setiap kali suatu halaman diakses, akan diletakkan di bagian paling atas stack. Apabila ada halaman yang perlu diganti, maka halaman yang berada di bagian paling bawah stack akan diganti sehingga setiap kali halaman baru diakses tidak perlu mencari kembali halaman yang akan diganti. Dibandingkan pengimplementasian dengan counter, cost untuk mengimplementasikan algoritma LRU dengan menggunakan stack akan lebih mahal karena seluruh isi stack harus di-update setiap kali mengakses halaman, sedangkan dengan counter, yang dirubah hanya counter halaman yang sedang diakses, tidak perlu mengubah counter dari semua halaman yang ada.