Page Replacement (Pergantian Page)

Pada pembahasan mengenai Virtual Memory, salah satu keuntungan dari adanya virtual memory adalah meningkatnya derajat multiprogramming, di mana sistem operasi tidak menempatkan semua halaman (page) sebuah proses dalam memori utama, namun memilh beberapa halaman yang penting dan memuat referensi ke page yang lain ke dalam memori utama. Hal ini berarti, apabila hanya terdapat empat puluh frame saja pada memori utama, dan kita memiliki delapan proses yang masing-masing terdiri dari sepuluh proses dan masing-masing proses hanya membutuhkan lima page utama dalam memori utama, maka kedelapan proses dapat secara sekaligus dieksekusi oleh memori. Namun jika tidak menggunakan virtual memori, maka hanya akan ada empat proses saja yang dapat dijalankan pada memori. Sehingga dengan memanfaatkan virtual memori, jumlah proses yang dapat dieksekusi di memori lebih banyak.

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.

1. Mencari lokasi dari halaman yang dicari di disk.

2. Mencari bingkai yang kosong di memori fisik:

a. Jika ada bingkai yang kosong, maka gunakan bingkai tersebut.

b. Jika tidak ada bingkai yang kosong, gunakan algoritma ganti halaman untuk memilih bingkai "korban"

c. Pindahkan bingkai "korban" tersebut ke disk dan sesuaikan tabel halaman.

3. Masukkan halaman yang berasal dari disk tersebut ke dalam bingkai yang baru dikosongkan tersebut. Sesuaikan tabel halaman.

4. Lanjutkan proses yang telah diinterupsi.

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. Berikut ini adalah gambar proses terjadinya pergantian page.