Dikarenakan algoritma optimal sangat
sulit dalam pengimplementasikannya, maka dibuatlah algoritma lain yang
performance-nya mendekati algoritma optimal dengan sedikit cost yang
lebih besar. Algoritma in 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 ini lah yang membuat cost membesar, karena harus meng-update linked list paling depan adalah halaman yang baru saja digunakan. Semakin lama tidak dipakai, halaman akan berada semakin belakang dan diposisi terakhir adalah halaman yang paling lama tidak digunakan dan siap untuk di-swap.
contoh dari gambar Algoritma LRU
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 ini lah yang membuat cost membesar, karena harus meng-update linked list paling depan adalah halaman yang baru saja digunakan. Semakin lama tidak dipakai, halaman akan berada semakin belakang dan diposisi terakhir adalah halaman yang paling lama tidak digunakan dan siap untuk di-swap.
contoh dari gambar Algoritma LRU
Tidak ada komentar:
Posting Komentar