Implementasi LRU

Implementasi LRU

Implementasi 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.
sumber

Implementasi LRU
Oleh Annas Bawika pada 20 mei 2012.
Implementasi LRU semoga membantu. Rating: 5

Deskripsi: Berbagi itu baik ~ Annas bawika Rating: 5