ALGORITMA PENGGANTIAN PAGE LRU

LRU sendiri merupakan kepanjangan dari Least Recently Used

Algoritma Penggantian Page LRU merupakan algoritma penggantian isi chache, yaitu apabila chache penuh dan diperlukan penyimpanan entri baru, maka entri yang paling jarang digunakan akan dihapus dan diganti dengan entri baru.

Ada beberapa cara untuk mengimplementasikan algoritma LRU, tetapi yang cukup terkenal ada 2 yaitu, Counter dan Stack.

1. Dengan cara 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 dihalaman tersebut bertambah 1.

2. Dengan cara Stack

Cara ini dilakukan dengan menggunakan stack yang menandakan halaman-halaman yang berada dimemori. setiap kali suatu halaman diakses, akan diletakan dibagian paling atas stack. Apabila ada halaman yang perlu diganti, maka halaman yang berada dibagian paling bawah stack akan diganti sehingga setiap kali halam baru akan diakses tidak perlu mencari kembali halaman yang akan diganti.

ALGORITMA PENGGANTIAN PAGE MODIFIKASI FIFO

Kelemahan FIFO yang jelas adalah algoritma dapat memilih memindahkan page yang sering di gunakan yang lama berada di memeori.kemungkinan ini dapat di hindari dengan hanya memindahkan page tidak di acu.page di tambah bit R mencatat apakah page di acu atau tidak,bit R bernilai 1 bila di acu dan bernilai 0 bila tidak di acu.

Variasi dari FIFO antara lain :

1. Algoritma Penggantian page kesempatan kedua

Mekanisme algoritma :

- Saat terjadi page fault,algoritma memilih page elemen terdepan di ganti bila bit R bernilai 0

2.  Algoritma penggantian clock page

Mekanisme algoritma :

-  Bila bit R berniali 1, maka bit page terdepan senarai diseret menjadi 0 dan di letekan di ujung belakang senarai. Mekanisme ini kembali di terapkan ke elemen erikutnya.

ALGORITMA PENGGANTIAN PAGE FIFO

Algoritma ini adalah algoritma yang paling sederhana. Prinsip dari algoritma ini adalah seperti prinsip antrian (antrian tak berprioritas), halaman yang masuk lebih dulu maka akan keluar lebih dulu juga. Algoritma ini menggunakan struktur data stack. Apabila tidak ada frame kosong saat terjadi page fault, maka korban yang dipilih adalah frame yang berada di stack paling bawah, yaitu halaman yang berada paling lama berada di memori. Dengan hanya informasi mengenai lama berada di memori, maka algoritma ini dapat memindahkan page yang sering digunakan. Boleh jadi page itu berada terus di memori karena selalu digunakan. Page itu karena mengikuti pola antrian berdasar lamanya berada di memori menjadi elemen terdepan, diganti, dan segera harus masuk kembali ke memori sehingga terjadi page fault kembali.

ALGORITMA PENGGANTIAN PAGE NRU

Pada algoritma ini, page diberi dua bit mencatat status page, bit R dan M, yaitu :

- Bit R   : referenced (menyatakan page sedang diacu)

- Bit R = 1 berarti sedang diacu

- Bit R = 0 berarti tidak sedang diacu

- Bit M  : modified (menyatakan page telah dimodifikasi)

- Bit M = 1 berarti dimodifikasi

- Bit M = 0 berarti tidak dimodifikasi

Dengan 2 bit, maka page-page dikelompokkan menjadi 4 kelas page, yaitu

- Kelas 0 : Tidak sedang diacu, belum dimodifikasi (R=0, M=0)

- Kelas 1 : Tidak sedang diacu, telah dimodifikasi (R=0, M=1)

- Kelas 2 : Sedang diacu, belum dimodifikasi (R=1, M=0)

- Kelas 3 : Sedang diacu, telah dimodifikasi (R=1, M=1)

Memilih mengganti page kelas bernomor terendah (bila terdapat page-page di kelas itu) secara acak. Bila kelas tersebut kosong maka dipilih page di kelas lebih tinggi, dan seterusnya.

Algoritma ini mengasumsikan kelas-kelas bernomor lebih rendah akan baru akan digunakan kembali dalam waktu relatif lama.

Algoritma ini mudah dipahami dan diimplementasikan. Implementasi algoritma ini sangat efisien karena tak banyak langkah dalam pemilihan page. Algoritma ini memang tidak optimal, tapi dalam kondisi-kondisi normal telah memadai.

ALGORITMA PENGGANTIAN PAGEOPTIMAL

Algoritma ini adalah algoritma yang paling optimal sesuai dengan nama_nya. Prinsip dari algoritma ini adalah mengganti halaman yang tidak akan terpakai lagi dalam waktu lama. Sehingga untuk efesiensi pergantian halaman meningkat (page fault yang terjadi berkurang) dan terbebas dari anomali belady. Strategi ini akan menghasilkan page-fault paling sedikit. Algoritma ini memiliki page fault rate paling rendah diantara semua algoritma disemua kasus. Akan tetapi, optimal belum berarti sempurna karena algoritma ini ternyata sangat sulit untuk diterapkan. System tidak dapat mengetahui halaman-halaman mana saja yang akan digunakan berikut_nya. Pendekatan ini dapat dilakukan dengan simulasi. Tapi simulasi hanya spesifik untuk suatu program. Bila yang terbaik tak dimungkinkan, maka yang perlu dilakukan adalah berusaha mendekati nya. Algoritma penggantian page diusahakan kinerja nya mendekati optimal. Tiap algoritma penggantian page mengumpulkan dan memakai informasi untuk menentukan page yang diganti sehingga mendekati optimal.

ANALISIS ALGORITMA PENGGANTIAN PAGE

Algoritma penggantian page acak ( algoritma random) memiliki fungsi mengeluarkan page untuk memberikan tempat yang baru dengan ditentukan secara acak tanpa kriteria tertentu. Dalam penggunaannya ia tidak memakai informasi apapun dalam menentukan page yang diganti. Kekurangan dari algoritma page acak ini sendiri ialah bisa menimbulkan rate terjadinya page error yang sering akan terjadi.