Algoritma Penggantian Page FIFO

23 Jan 2013 · 0 komentar
Algoritma FIFO (First In First Out) merupakan algoritma yang paling sederhana, prinsip dari algoritma ini adalah seperti prinsip antrian (antrian tak berprioritas) halaman yang masuk lebih dulu maka akan 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 dimemori.
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 seperti yang akan dibahas berikut ini.

Algoritma Penggantian Page Modifikasi FIFO

· 0 komentar
Algoritma Modifikasi FIFO disebut juga Algoritma Second Change karena algoritma ini berdasarkan pada algoritma FIFO yang disempurnakan. Algoritma ini menggunakan tambahan berupa reference bit yang nilainya 0 atau 1, jika dalam FIFO menggunakan stack maka algoritma ini 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.
  • Apabila ditemukan halaman yang reference bit-nya bernilai 0, maka halaman itu yang di-swap.
  • Apabila sampai di ujung antrian tidak ditemukan halaman yang reference bit-nya bernilai 0, maka razia dilakukan lagi dari awal.

Algoritma Penggantian Page NRU (Not Recently Used)

· 0 komentar
Pada algoritma ini setiap halaman diberi status bit R (Referenced) dan M (Modified). Bit bernilai 0 jika halaman belum direference/dimodifikasi, dan 1 jika sebaliknya.
Dari nilai desimalnya didapat 4 kelas:
Halaman dengan kelas terkecillah yang akan dikeluarkan.


Baca juga Algoritma Penggantian Page LRU

Algoritma Penggantian Page LRU

21 Jan 2013 · 0 komentar
Dikarenakan Algoritma Optimal sangat sulit dalam pengimplementasiaannya, maka dibuatlah algoritma lain yang performancenya mendekati algoritma optimal dengan sedikit cost yang lebih besar. Algoritma ini menganti halaman yang sudah lama tidak digunakan sudah tidak dibutuhkan lagi dan kemungkinan besar halamann yang baru di load akan digunakan kembali.

Sama seperti algoritma optimal, algoritma LRU (Least Recently Used) 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 di linked 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.

Implementasi Algoritma LRU
Ada beberapa cara untuk mengimplementasikan algoritma LRU. Tetapi, yang cukup terkenal ada 2, yaitu counter dan stack. Contoh algoritma di atas menggunakan stack.
 


  • Counter. Cara ini dilakukan dengan menggunakan counter atau logical clock. Setiap halaman memiliki nilai yang pada awalnya diinisialisasi dengan 0. Ketika mengakses ke suatu halaman baru, nilai pada clock di halaman tersebut akan bertambah 1. Semakin sering halaman itu diakses, semakin besar pula nilai counter-nya dan sebaliknya. Untuk melakukan hal itu dibutuhkan extra write ke memori. Selain berisi halaman-halaman yang sedang di-load, memori juga berisi tentang counter masing-masing halaman. Halaman yang diganti adalah halaman yang memiliki nilai clock terkecil, yaitu halaman yang paling jarang diakses. Kekurangan dari cara ini adalah memerlukan dukungan tambahan counter pada hardware.
  • StackCara ini dilakukan dengan menggunakan stack yang menandakan halaman-halaman yang berada di memori. Setiap kali suatu halaman diakses, akan diletakkan di bagian paling atas stack. Apabila ada halaman yang perlu diganti, maka halaman yang berada di bagian paling bawah stack akan diganti sehingga setiap kali halaman baru diakses tidak perlu mencari kembali halaman yang akan diganti. Dibandingkan pengimplementasian dengan counter, cost untuk mengimplementasikan algoritma LRU dengan menggunakan stack akan lebih mahal karena seluruh isi stack harus di-update setiap kali mengakses halaman, sedangkan dengan counter, yang dirubah hanya counter halaman yang sedang diakses, tidak perlu mengubah counter dari semua halaman yang ada.

Algoritma Penggantian Page Optimal

· 0 komentar
Algoritma ini adalah algoritma yang paling optimal sesuai dengan 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.
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.
 

Copyright © 2011 Mixx Blogger Template - Blogger Templates by BloggerReflex

Sponsored by: Trucks | SUV | Cheap Concert Tickets