Page Fault yaitu suatu operasi yang muncul pada sebuah komputer yang disertai dengan memori virtual (virtual Memory), atau mampu dikatakan sebuah proses yang memungkinkan episode hard disk untuk menambah memori fisik (Physical Memory) komputer. Kebanyakan page fault terjadi ketika sebuah sebuah aktivitas mencoba mengakses gosip yang telah ditempatkan ke dalam file virtual memory pada hard disk. Hal ini merupakan sebuah fungsi normal virtual memmory. Kemudian komputer akan merespon dengan memuat gosip yang sesuai ke dalam physical memory. Tipe page fault yang lebih teknis lagi berafiliasi dengan Crash dan error pada komputer yang mampu muncul ketika aktivitas mencari gosip yang tidak ada atau dilindungi. Hal ini mampu disebabkan oleh hardware yang bermasalah atau software yang corrupt atau kurang sempurna. Refferensi: Gicara.com
Jadi, Pada dikala terjadinya page fault berarti harus diputuskan page frame di memori fisik yang harus diganti. Kinerja sistem akan baik jikalau page yang diganti dipilih yang tidak akan digunakan di masa yang akan datang. Jika page yang diganti akan kembali digunakan maka page akan dikembalikan secepatnya yang berarti terjadi page fault berulang kali. Banyaknya page fault menghasilkan banyak overheard.
Terdapat beberapa algoritma page replacement, setiap sistem operasi mempunyai denah yang unik. Algoritma page replacement secara umum diinginkan yang mempunyai rata-rata page fault terendah. Algoritma page replacement di antaranya adalah:
- Algoritma page replacement Acak
- Algoritma page replacement FIFO
- Algoritma page replacement Optimal
- Algoritma page replacement NRU
- Algoritma page replacement LRU
- Algoritma page replacement Second Chance Page
- Algoritma page replacement Clock
Mari kita bahas satu per-satu Algoritma Page Replacement di atas.
1. Algoritma Page Replacement Acak
Dari segi mekanisme algoritma tersebut, setiap akan timbul page fault, page yang diganti dengan pilihan secara acak. Untuk segi tekniknya sendiri pun algoritma ini tidak perlu menggunakan gosip dalam menentukan page yang diganti, di dalam memory utama itu sendiri pun sudah mempunyai bobot yang sama untuk dipilih, karena teknik ini dapat dipakai untuk memilih page sembarang. Termasuk page yang sudah dipilih dengan benar-benar / page yang tidak seharusnya diganti.
 |
| Contoh gambar algoritma page replacement acak |
2. Algoritma Page Replacement FIFO (First In - First Out)
Inti dari algoritma ini yaitu simple / paling sederhana karena prinsipnya sama ibarat prinsip antrian tak berprioritas. Page yang masuk terlebih dahulu maka page tersebut akan keluar duluan juga. Untuk algoritma ini menggunakan structure data stack. Makara cara kerjanya yaitu dimana ketika tidak ada frame yang kosong dikala terjadi page fault maka korban yang dipilih yaitu frame dengan stack paling bawah ibarat hal nya halaman yang sudah lama tersimpan didalam memory maka dari itu algoritma ini juga mampu memindahkan page yang sering digunakan.
 |
| Contoh gambar page replacement FIFO |
Dulu algoritma ini di anggap cukup mengatasi pergantian page hingga pada tahun 70-an, pada dikala itu juga Belady menemukan keganjalan pada algoritma ini dan dikenal dengan anomali Belady. Anomali Belady itu sendiri ialah keadaan dimana page fault rate meningkat seiring dengan pertambahannya jumlah frame.
 |
| Contoh gambar anomali Belady pada algoritma FIFO |
3. Algoritma Page Replacement Optimal
Pengertian dari algoritma ini sendiri yaitu algoritma yang page nya paling optimal. Untuk prinsip dari algoritma ini sangat efisien sekali karena hanya mengganti halaman yang sudah tidak terpakai lagi dalam jangka waktu lama sehingga page fault yang terjadi akan berkurang dan terbebas dari anomali Belady Selain itu juga page fault dari algoritma ini memiliki rate paling tinggi dari algoritma lainnya dari semua kasus, akan tetapi belum mampu disebut tepat karena sulit untuk dimengerti dan dari segi system pun belum tentu mampu mengetahui page untuk berikutnya tetapi dapat disimulasikan hanya untuk suatu program. Untuk intinya gunakanlah hingga mendekati page optimal semoga mampu memanfaatkannya.
 |
| Contoh gambar page replacement optimal |
4. Algoritma Page Replacement NRU (Not Recently Used)
Untuk mekanisme dari algoritma ini diberi dua bit untuk mencatat status page, diantaranya bit M dan R yaitu :
Bit M : Page yang telah dimodifikasi
Bit M = 0 berarti tidak dimodif
Bit M = 1 berarti sudah dimodif
Bit R : Page yang sedang dipacu / referenced
Bit R = 1 berarti sedang di acu
Bit R = 0 berarti tidak sedang di acu
Adanya dua bit di atas maka akan dapat dikelompokkan menjadi 4 kelas page, yaitu :
Kelas 0 => Tidak sedang di acu / belum di modif (R=0, M=0)
Kelas 1 => Tidak sedang di acu / telah di modif (R=0, M=1)
Kelas 2 => Sedang di acu / belum di modif (R=1, M=0)
Kelas 3 => Sedang di acu / telah di modif (R=1, M=1)
Jadi, apabila algoritma ini diasumsikan kelas-kelas bernomor lebih rendah gres akan digunakan kembali dalam relatif jangka waktu lama. Intinya algoritma ini mudah dipahami dan dikembangkan karena sangat efisien walaupun tak banyak langkah dalam pemilihan page dan kelemahannya juga tidak optimal tapi dalam kondisi normal yang memadai.
5. Algoritma Page Replacement LRU (Least Recently Used)
Dikarenakan algoritma optimal sangat sulit dalam pengimplementasiannya, maka dibuatlah algoritma lain yang performance-nya mendekati algoritma optimal dengan sedikit cost yang lebih besar. Sama ibarat 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 dikala ada halaman yang di akses.
 |
| Contoh gambar page replacement LRU |
6. Algoritma Page Replacement Second Chance Page
Algoritma second chance merupakan hasil modifikasi dari algoritma FIFO yang disempurnakan lagi. Algoritma ini menggunakan suplemen berupa reference bit yang nilainya 0 atau 1. Jika dalam FIFO menggunakan stack, maka second chance menggunakan circular queue. Halaman yang gres di-load atau gres digunakan akan diberikan nilai 1 pada reference bit-nya. Halaman yang reference bit-nya bernilai 1 tidak akan eksklusif diganti walaupun ia berada di antrian paling bawah (berbeda dengan FIFO).
Urutan langkah kerja algoritma second chance yaitu 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 dikala razia reference bit-nya akan diset menjadi 0.
 |
| Contoh gambar algoritma page replacement SCP |
7. Algoritma Page Replacement Clock
Algoritma Clock merupakan hasil modifikasi dari algoritma FIFO yang kedua dan juga merupakan model lain dari algoritma page replacement second chance page, namun dalam implementasinya menggunakan 'circular queue' dengan page berbentuk lingkaran.
Jika :
Nilai bit = 0, ganti page
Nilai bit = 1
- Ubah nilai bit = 0
- Pointer bergerak ke page berikutnya searah jarum jam.
Untuk melihat ringkasan ini semua, Anda mampu unduh e-book / file pdf di bawah ini. Khususnya untuk Algoritma Clock.
Overall, Terima kasih kepada blog Operating System yang menunjukkan materi pembelajaran yang mudah dicerna bagi kami yang gres mulai berguru perihal Algoritma Page Replacement.
Dan terima kasih juga untuk penjelasan singkat yang saya peroleh dari Journal Amikom.
Thanks to: http://ocw.ui.ac.id/ untuk ebook / ringkasan materi-nya!
Tanpa adanya blog di atas, rangkuman materi ini tidak mungkin pernah ada. Sekali lagi saya ucapkan terima kasih banyak dan saya sangat mengapresiasi kalian semua yang telah mau membuatkan kepada sesama untuk mencerdaskan generasi bangsa! ;)
Regards,
0 comments
Post a Comment