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

Pada awalnya, algoritma ini dianggap cukup mengatasi masalah tentang pergantian halaman, sampai pada tahun 70-an, Belady menemukan keanehan pada algoritma ini yang dikenal kemudian dengan anomali Belady. Anomali Belady adalah keadaan di mana page fault rate meningkat seiring dengan pertambahan jumlah frame , seperti yang bisa dilihat pada contoh di bawah ini.

Ketika jumlah frame ditambah dari 3 frame menjadi 4 frame, jumlah page fault yang terjadi malah bertambah (dari 14 page fault menjadi 15 page fault ). Hal ini biasanya terjadi pada kasus yang menginginkan halaman yang baru saja di-swap-out sebelumnya. Oleh karena itu, dicarilah algoritma lain yang mampu lebih baik dalam penanganan pergantian halaman seperti yang akan dibahas berikut ini.

Algoritma Page Modifikasi FIFO

Algoritma FIFO murni jarang digunakan, tetapi dikombinasikan (modifikasi).
Kelemahan FIFO yang jelas adalah algoritma dapat memilih memindahkan page yang sering digunakan yang lama berada di memori. 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 (second chance page replacement algorithm)

• Algoritma penggantian clock page (clock page replacement algorithm)

Algoritma yang pertama adalah algoritma second chance. Algoritma second chance berdasarkan pada algoritma FIFO yang disempurnakan. Algoritma ini menggunakan tambahan berupa reference bit yang nilainya 0 atau 1. Jika dalam FIFO menggunakan stack , maka second chance menggunakan circular queue . Halaman yang baru di-load atau baru digunakan akan diberikan nilai 1 pada reference bit-nya. Halaman yang reference bit-nya bernilai 1 tidak akan langsung diganti walaupun dia berada di antrian paling bawah (berbeda dengan FIFO).

• Urutan langkah kerja algoritma second chance adalah sebagai berikut:Apabila terjadi page fault dan tidak ada frame yang kosong, maka akan dilakukan razia (pencarian korban) halaman yang reference bit-nya bernilai 0 dimulai dari bawah antrian (seperti FIFO).

• Setiap halaman yang tidak di- swap (karena reference bit-nya bernilai 1), setiap dilewati saat razia reference bit-nya akan diset menjadi 0.