Algoritma Penggantian Page

1. Algoritma Penggantian Page Acak

Mekanisme algoritma,Setiap terjadi page fault, page yang diganti dipilih secara acak.

Teknik ini tidak memakai informasi apapun dalam menentukan page yang diganti. Semua page di memori utama mempunyai bobot sama untuk dipilih. Teknik ini dapat memilih sembarang page, termasuk page yang sedang diacu (page yang seharusnya tidak diganti, pilihan terburuk).

     2. Algoritma Penggantian Page Optimal 

Algoritma ini adalah algoritma yang paling optimal sesuai namanya. Prinsip dari algoritma ini adalah mengganti halaman yang tidak akan terpakai lagi dalam waktu lama, sehingga efisiensi pergantian halaman meningkat (page fault yang terjadi berkurang) dan terbebas dari anomali Belady. Strategi ini akan menghasilkan jumlah page-fault paling sedikit. Algoritma ini memiliki page fault rate paling rendah di antara semua algoritma di semua kasus. Akan tetapi, optimal belum berarti sempurna karena algoritma ini ternyata sangat sulit untuk diterapkan. Sistem tidak dapat mengetahui halaman-halaman mana saja yang akan digunakan berikutnya.
   
    3. Algoritma Penggantian Page NRU 

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.

Mekanisme algoritmanya

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.

    4. Algoritma Penggantian Page FIFO

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