LRU
Least Recently Used (LRU) algorithm dalam OS adalah strategi manajemen memori yang digunakan oleh sistem operasi untuk menentukan halaman mana yang harus diganti (di-swap out) dari memori fisik ke penyimpanan sekunder (seperti hard disk) ketika terjadi page fault. Tujuannya adalah untuk menjaga halaman yang paling sering dan paling baru diakses tetap berada di memori utama, karena diasumsikan halaman tersebut akan dibutuhkan lagi dalam waktu dekat.
Cara Kerja dalam Konteks OS
Ketika sebuah proses membutuhkan data atau instruksi yang tidak ada di memori fisik (disebut page fault), OS harus memuat halaman tersebut dari disk. Jika memori fisik sudah penuh, OS perlu membuat ruang dengan mengganti halaman lain. Di sinilah algoritma LRU berperan.
Identifikasi Halaman: Algoritma ini melacak waktu akses terakhir untuk setiap halaman di memori. Halaman yang paling lama tidak diakses adalah kandidat terbaik untuk diganti.
Mekanisme Pelacakan: Secara teoritis, setiap halaman memiliki timestamp yang diperbarui setiap kali diakses. Namun, implementasi ini sangat mahal secara komputasi karena setiap akses memori akan memicu pembaruan timestamp.
Implementasi Praktis: Karena implementasi "sempurna" terlalu mahal, sistem operasi menggunakan berbagai skema perkiraan (approximation schemes) untuk mendekati perilaku LRU:
Menggunakan Counter: Setiap halaman memiliki sebuah counter. Ketika sebuah halaman diakses, counternya diperbarui. OS akan memilih halaman dengan nilai counter terendah untuk diganti.
Using Stacks: Mirip dengan contoh software engineer sebelumnya, OS bisa menggunakan stack untuk melacak urutan penggunaan. Halaman yang diakses dipindahkan ke bagian atas stack. Halaman di bagian bawah stack adalah yang paling lama tidak diakses.
Clock Algorithm (Second Chance): Ini adalah salah satu pendekatan LRU yang paling populer dan praktis. Setiap halaman memiliki sebuah "use bit" atau "reference bit" yang diset menjadi 1 saat halaman tersebut diakses. Ketika OS perlu mengganti halaman, ia memindai halaman-halaman dalam memori (seperti jarum jam). Jika "use bit" halaman adalah 1, OS mengesetnya menjadi 0 dan memberikannya "kesempatan kedua." Jika "use bit" adalah 0, berarti halaman tersebut belum diakses sejak pemindaian terakhir, dan halaman ini akan dipilih untuk diganti.
Kelebihan dan Kekurangan
Kelebihan: LRU umumnya sangat efektif dan menghasilkan tingkat hit cache yang tinggi (jumlah permintaan memori yang dapat dilayani dari cache) dan tingkat miss yang rendah (jumlah page fault). Ini karena LRU memanfaatkan prinsip lokalitas temporal dengan baik, sehingga kinerja sistem secara keseluruhan meningkat.
Kekurangan: Implementasi LRU yang sempurna sangat sulit dan mahal secara overhead, baik dari segi waktu CPU maupun memori. Oleh karena itu, sebagian besar sistem operasi menggunakan pendekatan atau aproksimasi dari LRU, seperti Clock Algorithm, yang memberikan kinerja yang baik dengan overhead yang lebih rendah.
Last updated