Analisis Algoritma Penggantian Halaman Pada Sistem Operasi

Posted by Syaiful Mubarak on 03.11

Ganti halaman dilakukan apabila terjadi page fault. Page fault bukan suatu jenis error yang fatal, page fault terjadi apabila ada halaman yang ingin diakses tetapi halaman tersebut tidak terdapat di dalam memori utama. Page fault pasti terjadi minimal satu kali saat pertama kali halaman itu ingin diakses.
Prinsip ganti halaman adalah sebagai berikut:
  1. Proses meminta halaman tertentu. 
  2. Jika halaman berada di memori, tidak dilakukan ganti halaman.
  3. Jika halaman tidak berada di memori, maka:
    1. Jika ada frame kosong, maka halaman itu di-load ke dalam frame yang kosong tersebut.
    2. Jika tidak ada frame yang kosong, maka pilih halaman yang akan di-swap dengan menggunakan algoritma ganti halaman.
  4. Update tabel halaman dan table memori.
  5. Restart proses.

Berikut Algoritma Penggantian Halaman.

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).
Teknik ini sangat buruk, percobaan menunjukkan algoritma acak menimbulkan rate terjadinya page fault yang sangat tinggi.

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. Pendekatan ini dapat dilakukan dengan simulasi. Tapi simulasi hanya spesifik untuk suatu program. Bila yang terbaik tak dimungkinkan, maka yang perlu dilakukan adalah berusaha mendekatinya. Algoritma penggantian page diusahakan kinerjanya mendekati optimal. Tiap algoritma penggantian page mengumpulkan dan memakai informasi untuk menentukan page yang diganti sehingga mendekati optimal.

3.  Algoritma Penggantian Page LRU

Dikarenakan algoritma optimal sangat sulit dalam pengimplementasiannya, maka dibuatlah algoritma lain yang performance-nya mendekati algoritma optimal dengan sedikit cost yang lebih besar. Algoritma ini mengganti halaman yang paling lama tidak dibutuhkan. Asumsinya, halaman yang sudah lama tidak digunakan sudah tidak dibutuhkan lagi dan kemungkinan besar, halaman yang baru di-load akan digunakan kembali.
Sama seperti algoritma optimal, algoritma LRU tidak mengalami anomali Belady. Algoritma ini memakai linked list untuk mendata halaman mana yang paling lama tidak terpakai. Linked list inilah yang membuat cost membesar, karena harus meng-update linked list tiap saat ada halaman yang di akses. Halaman yang berada dilinked list paling depan adalah halaman yang baru saja digunakan. Semakin lama tidak dipakai, halaman akan berada semakin belakang dan di posisi terakhir adalah halaman yang paling lama tidak digunakan dan siap untuk di-swap.

Algoritma LRU
Algoritma LRU

4.  Algoritma FIFO (First In First Out)
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.

5.  Algoritma Pengantian Page Modifikasi FIFO
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.

6.  Algoritma Penggantian Page NRU
Mekanisme algoritmanya adalah :
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.
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.