Algoritma-algoritma Penggantian Page (Lanjutan)

Sebelumnya saya sudah menjelaskan 3 algoritma penggantian page (baca disini). Selanjutnya ini adalah 3 algoritma penggantian page selain dari yang saya bahas sebelumya.

4. Algoritma penggantian page FIFO (First In, First Out)

Mekanisme Algoritma ini: Algoritma ini memerlukan pengelolaan senarai page di memori. Elemen terdepan senarai adalah page tertua dan ujung belakang adalah page paling akhir datang.

Bila terjadi page fault, page elementerdepan (page tertua) diganti dan page baru diambahkan diujung belakang senarai.

Dengan hanya informasi mengenai lama berada dimemori, maka algoritma ini dapat memindahkan page yang sering digunakan. Boleh jadi page itu berada terus dimemori karena selalu digunakan. Page itu karena mengikuti pola antrian berdasar lamanya berada dimemori menjadi elemen terdepan, diganti, dan segera harus masuk kembali ke memori sehingga terjadi page fault kembali.

Algoritma FIFO murni jarang digunakan, tetapi dikombinasikan (modifikasi).

5. Algoritma penggantian page modifikasi dari algoritma FIFO

Kelemahan FIFO yang jelas adalah algoritma dapat memilih memindahkan page yang sering digunakan yang lama berada dimemori. Kemungkinan ini dapat dihindari dengan hanya memindahkan page tidak diacu. Page ditambah bit R mencatat apakah page diacu atau tidak. Bit R bernilai 1 bila diacu dan bernilai 0 bila tidak diacu.

Variasi dari FIFO antara lain:

• Algoritma penggantian page kesempatan kedua (secong chance page replacement algorithm)
• Algoritma penggantian clock page (clock page replacement algorithm)

 Algoritma penggantian page kesempatan kedua

Mekanisme algoritma: 

• Saat terjadi page fault, algoritma memilih page elemen terdepan diganti bila bit R bernilai 0 

• Bila bit R bernilai 1, maka bit page terdepan senarai direset menjadi 0 dan diletakkan keujung belakang senarai. Mekanisme ini kembali diterapkan ke elemen berikutnya.

Algoritma penggantian Clock Page

Algoritma penggantian page kesempatan kedua merupakan Algoritma yang memadai tapi tidak efisien karena memindahkan page-page disenarainya. Algoritma penggantian clock page merupakan perbaikan algoritma pertama.

Mekanisme Algoritma:

• Pada Algoritma ini semua page merupakan senarai melingkar membentuk pola jam. Terdapat penunjuk (pointer) ke page tertua.

Ketika terjadi page fault, page yang ditunjuk diperiksa.

• Jika bit R bernilai 0, maka page diganti. Page baru ditempatkan ditempat page diganti, dan penunjuk dimajukan satu posisi ke page berikutnya. 
• Jika bit R bernilai 1, maka bit R direset menjadi 0, dan penunjuk dimajukan satu posisi. Seterusnya sampai menemui page dengan bit R bernilai 0.

Kedua algoritma adalah sama, hanya berbeda dalam implementasi, yaitu:

• Algoritma penggantian page kesempatan kedua menggunakan senarai lurus tidak sirkular.
• Algoritma penggantian clock page menggunakan senarai sirkular.

6. Algoritma penggantian page LRU (Least Recently Used)

Berdasar observasi, page-page pada beberapa instruksi terakhir berkemungkinan besar akan dipakai kembali. Page-page yang lama tidak digunakan akan tetap tidak digunakan dalam waktu lama.

Mekanisme Algoritma: Algoritma LRU adalah ketika terjadi page fault maka memindahkan page yang tidak digunakan paling lama.

Masalah: sangat mahal

Kemahalan disebabkan harus mengelola senarai informasi seluruh page di memori. Senarai harus terurut berdasar kemuktahiran penggunaan. Senarai harus diperbarui setiap terjadi pengacuan memori. Begitu terjadi pengacauan memori, harus dilaksanakan operasi menemukan page di senarai, dipindahkan sebagai terdepan yaitu paling muktahir diacu. Mekanisme ini memerlukan waktu yang sangat banyak.

Sumber: DR. Bambang Hariyanto, Sistem Operasi.