1. Algoritma Penggantian Page 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 usah perlu menggunakan informasi dalam menentukan page yang diganti, didalam memory utama itu sendiri 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.
2. Algoritma Penggantian Page 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 tidak belum bias disebut sempurna karena sulit untuk di mengerti dan dari segi system pun belum tentu bisa mengetahui page untuk berikutnya tetapi dapat di simulasikan hanya untuk suatu program. Untuk intinya gunakanlah hingga mendekati page optimal agar bisa memanfaatkannya.
Setiap page diberi label untuk menandai berapa intruksi lagi baru dia gunakan. Page dengan label tertinggi (waktu dari sekarang sampai pemakaian berikutnya paling lama) yang akan dikeluarkan.
3. Algoritma Penggantian Page NRU (Not-Recently Used)
Setiap page diberi status bit R (referenced) dan M (modified).
Bit bernilai 0 jika page belum direferensi/dimodifikasi, dan 1 jika sebaliknya. Dari nilai desimalnya didapat 4 kelas:
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.
4. Algoritma Penggantian Page 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 yaitu yang akan keluar duluan juga. Untuk algoritma ini menggunakan structure data stack. Jadi kerjanya yaitu dimana kalau 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.
Utamanya 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.
5. Algoritma Penggantian Page Modifikasi FIFO
Algoritma FIFO murni jarang digunakan, tetapi dikombinasikan (modifikasi).
Kelemahan FIFO yang jelas adalah algoritma dapat memilih memindahkan page yang sering digunakan yang lama berada di memori. Kemungkinan ini dapat dihindari dengan hanya memindahkan page tidak diacu Page ditambah bit R mencatat apakah page diacu atau tidak. Bit R bernilai 1 bila diacu dan bernilai 0 bila tidak diacu.
Variasi dari FIFO antara lain:
- Algoritma penggantian page kesempatan kedua (second chance page replacement algorithm)
-Algoritma penggantian clock page (clock page replacement algorithm)
Algoritma yang pertama adalah algoritma second chance. Algoritma second chance berdasarkan pada algoritma FIFO yang disempurnakan. 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.
6. Algoritma Penggantian Page 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. ama 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.
Nah itu penjelasan saya tentang Algoritma dalam virtual memory. Semogaa bermanfaat... (^_^)
