Pada pembahasan mengenai masalah page-fault, diasumsikan bahwa setiap halaman minimal mengalami satu kali page fault, yaitu pada saat diakses pertama kali. Akan tetapi, tidak semua halaman tersebut akan digunakan oleh suatu proses. Jika terdapat sebuah proses yang memiliki sepuluh halaman, dan hanya menggunakan setengah di antaranya, yaitu lima halaman, maka demand paging menyimpan kelima proses yang tidak dibutuhkan tersebut agar tidak diakses oleh M/K. Dengan begitu, kita dapat meningkatkan degree of multiprogramming, yaitu dengan menjalankan proses dua kali lebih banyak. Jika kita memiliki empat puluh bingkai, kita dapat menjalankan delapan proses. Bandingkan dengan jika kesepuluh halaman tersebut dipanggil, maka hanya dapat dijalankan maksimum empat proses.

Jika kita meningkatkan degree of multiprogramming, yaitu dengan menjalankan proses lebih banyak, maka dapat terjadi over-allocating memory. Misalnya kita menjalankan enam proses yang masing-masing memiliki sepuluh halaman dan seluruhnya dipanggil (di-load) ke memori, maka akan dibutuhkan 60 bingkai, padahal yang tersedia hanya empat puluh bingkai. Over-allocating memory juga dapat terjadi jika terdapat page fault, yaitu pada saat sistem operasi mendapatkan halaman yang dicari pada disk kemudian membawanya ke memori fisik tetapi tidak terdapat bingkai yang kosong pada memori fisik tersebut.

Sistem operasi memiliki dua cara untuk menangani masalah ini. Yang pertama dengan men-terminasi proses yang sedang mengakses halaman tersebut. Akan tetapi, cara ini tidak dapat dilakukan karena demand paging merupakan usaha sistem operasi untuk meningkatkan utilisasi komputer dan throughput-nya.

Cara yang kedua yaitu dengan penggantian halaman (page replacement). Sistem operasi dapat memindahkan suatu proses dari memori fisik, lalu menghapus semua bingkai yang semula digunakannya, dan mengurangi level of multiprogramming (dengan mengurangi jumlah proses yang berjalan).

Prinsip kerja penggantian halaman adalah sebagai berikut. "Jika tidak ada bingkai yang kosong, maka dicari (dengan suatu algoritma ganti halaman) salah satu bingkai yang sedang tidak digunakan dan kemudian dikosongkar. Suatu bingkai dapat dikosongkan dengan memindahkan isinya ke dalam ruang pemindahan kemudian mengubah semua tabel halaman hingga mengindikasikan bahwa halaman yang dipindah tersebut sudah tidak berada di memori fisik. Lalu bingkai yang telah kosong tersebut dapat digunakan oleh halaman yang akan ditempatkan di memori fisik".

Dengan memodifikasi urutan penanganan page fault, maka dapat dijabarkan urutan proses page replacement sebagai berikut.

Dari penjelasan di atas, maka dapat disimpulkan bahwa jika tidak terdapat bingkai yang kosong maka terdapat dua transfer halaman (yang keluar dan masuk memori fisik). Hal ini tentu saja menambah waktu dalam penanganan page fault dan sceara otomatis menambah effective access time.

Hal tersebut dapat diselesaikan dengan menggunakan bit modifikasi (modify bit/dirty bit ). Setiap halaman atau bingkai memiliki bit modifikasi yang sesuai pada perangkat keras. Bit modifikasi untuk sebuah halaman diatur oleh perangkat keras pada saat suatu byte atau word dituliskan ke halaman tersebut, yang menunjukan bahwa halaman tersebut telah dimodifikasi. Waktu suatu halaman dipilih untuk dipindahkan dari memori fisik ke disk, diperiksa terlebih dahulu bit modifikasinya di disk. Jika bit modifikasinya ada, maka halaman tersebut harus ditulis ke disk. Namun, apabila bit modifikasinya belum ada di disk, maka halaman tersebut belum dimodifikasi karena halaman tersebut masih berada di memori utama. Oleh karena itu, jika salinan dari halaman tersebut masih terdapat di disk (belum ditimpa oleh halaman lain) maka penulisan halaman dari memori utama ke disk tidak diperlukan. Hal ini juga berlaku pada halaman read-only, yaitu halaman yang tidak dapat dimodifikasi. Sehingga waktu yang diperlukan untuk penanganan page fault dapat berkurang dengan cukup signifikan karena berkurangnya waktu M/K dari dan ke disk.

Gambar 5.6. Page Replacement