Macam - macam Algoritma Page Replacement

Selamat Pagi, kali ini saya akan coba untuk menerangkan berbagai macam Algoritma Page Replacement. Sebelum kita membahas tentang Algoritma Page Replacement, pertama - tama kita harus mengerti dulu apa itu Page Fault?

Page Fault adalah suatu operasi yang muncul pada sebuah komputer yang disertai dengan memori virtual (virtual Memory), atau bisa dikatakan sebuah proses yang memungkinkan bagian hard disk untuk menambah memori fisik (Physical Memory) komputer. Kebanyakan page fault terjadi ketika sebuah sebuah program mencoba mengakses informasi 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 informasi yang sesuai ke dalam physical memory. Tipe page fault yang lebih teknis lagi berhubungan dengan Crash dan error pada komputer yang bisa muncul ketika program mencari informasi yang tidak ada atau dilindungi. Hal ini bisa disebabkan oleh hardware yang bermasalah atau software yang corrupt atau kurang sempurna. Refferensi: Gicara.com

Jadi, Pada saat terjadinya page fault berarti harus diputuskan page frame di memori fisik yang harus diganti. Kinerja sistem akan baik jika 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 skema yang unik. Algoritma page replacement secara umum diinginkan yang mempunyai rata-rata page fault terendah. Algoritma page replacement di antaranya adalah:

1. Algoritma page replacement Acak
2. Algoritma page replacement FIFO
3. Algoritma page replacement Optimal
4. Algoritma page replacement NRU
5. Algoritma page replacement LRU
6. Algoritma page replacement Second Chance Page
7. 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 informasi 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 adalah simple / paling sederhana karena prinsipnya sama seperti prinsip antrian tak berprioritas. Page yang masuk terlebih dahulu maka page tersebut akan keluar duluan juga. Untuk algoritma ini menggunakan structure data stack. Jadi cara kerjanya yaitu dimana ketika tidak ada frame yang kosong saat terjadi page fault maka korban yang dipilih adalah frame dengan stack paling bawah seperti hal nya halaman yang sudah lama tersimpan didalam memory maka dari itu algoritma ini juga bisa memindahkan page yang sering digunakan.

Contoh gambar page replacement FIFO

Dulu algoritma ini di anggap cukup mengatasi pergantian page sampai pada tahun 70-an, pada saat 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 bisa disebut sempurna karena sulit untuk dimengerti dan dari segi system pun belum tentu bisa mengetahui page untuk berikutnya tetapi dapat disimulasikan hanya untuk suatu program. Untuk intinya gunakanlah hingga mendekati page optimal agar bisa 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 baru 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 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.

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

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 bisa download e-book / file pdf di bawah ini. Khususnya untuk Algoritma Clock.

Overall, Terima kasih kepada blog Operating System yang memberikan materi pembelajaran yang mudah dicerna bagi kami yang baru mulai belajar tentang Algoritma Page Replacement.

http://selaluwanien.wordpress.com/2012/01/03/pengertian-tentang-algoritma-algoritma-penggantian-halaman/

Dan terima kasih juga untuk penjelasan singkat yang saya peroleh dari Journal Amikom.

http://journal.amikom.ac.id/index.php/KIDA/article/view/3135#

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 berbagi kepada sesama untuk mencerdaskan generasi bangsa! ;)

Regards,