Analisis Algoritma penggantian page

      I.        Algoritma penggantian page acak

Mekanisme algoritma :

Setiap terjadi page fault,page yang di ganti di pilih secara acak.

Teknik ini tidak memakai informasi apapun dalam menentukan page yang di ganti,semua page di memori utama mempunyai bobot sama untuk di pilih.teknik ini memiliki sembarang page,termasuk page yang sedang di acu,teknik ini sangat buruk,percobaan menunjukkan algoritma acak menimbulkan rate terjadinya page fault yang sangat tinggi.

    II.        Algoritma pengganti page optimal

Mekanisme algoritma

Dasar Algoritma ini adalah memiliki page yang berpeluang di pakai kembali di masa datang yang paling kecil.

Pendekatan ini dapat dilakukan dengan simulasi,tapi hanya spesifik suatu program.bila yang terbaik tidak di mungkinkan,maka yang perlu di lakukan adalah berusaha mendekatinya.algoritma pengganti page mengumpulkan dan memakai informasi untuk menentukan page yang di ganti sehingga mendekati optimal.

Algoritma pengganti page optimal penting untuk kajian teoretis,sebagai pembanding bagi algoritma-algoritma yang lain.

Ilustrasi gambar :

   III.        Algoritma pengganti page NRU

Mekanisme algoritma

Pada algoritma ini,page di beri dua bit mencatat setatus page,bit R dan M, yaitu:

Bit R    : referenced(menyatakan page sedang di acu)

Bit R    = 1 berati sedang di acu

            = 0 berati tidak sedang di acu

Bit M    : modified (menyatakan page telah di modifikasi)

Bit M    = 1 berati di modifikasi

            = 0 berati tidak di modifikasi

Dengan 2 bit,maka page-page di kelompokan menjadi 4 kelas page yaitu:

Kelas 0            : tidak sedang di acu,belum di modifikasi (R=0,M=0)

Kelas 1            : tidak sedang di acu,telah di modifikasi (R=0,M=1)

Kelas 2            : sedang di acu,belum di modifikasi (R=1,M=0)

Kelas 3            : sedang di acu,telah di modifikasi (R=1,M=1)

Ø  Memilih mengganti page kelas bernomor terendah secara acak

Ø  Bila kelas tersebut kosong maka di pilih page di kelas yang lebih tingggi,dan seterusnya.

  IV.        Algoritma pengganti page FIFO

Mekanisme algoritma

Algoritma ini memerlukan pengelolaan senari page di memeori,elemen terdepan senari adalah page tertua dan ujung belakang adalah page paling akhir datang. 
  Bila terjadi page fault,page elemen terdepan(page tertua) di ganti dan page baru di tambahkan di ujung belakang senari.Algoritma FIFO murni jarang digunakan,tetapi di kombinasikan(modif)

Ilustrasi gambar :

    V.        Algoritma penggantian Modifikasi dari 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

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

  VI.        Algoritma penggantian page LRU

Mekanisme algoritma

Algoritma LRU adalah ketika terjadi page fault maka memindahkan page yang tidak di gunakan paling lama.

Masalah

Sangat mahal

Kemahalan disebabkan harus mengelola senarai informasi seluruh page di memori.senarai harus terurut berdasarkan kemutkhiran penggunaan.senarai harus di perbaharui setiap terjadi pengacuan memori.begitu terjadi pengacuan memori,harus di lakukan operasi menemukan page di senarai.di pindahkan sebagai terdepan yaitu paling akhir di acu.

Ilustrasi gambar :