1. Algoritma Penggantian Page Acak
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 yang kurang baik). Teknik ini kurang baik, percobaan menunjukkan
algoritma acak menimbulkan rate terjadinya page fault yang sangat tinggi.
2. Algoritma 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.
Gambar algoritma optimal
3. Algoritma
Penggantian Page NRU (Not-Recenly Used)
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.
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. Dengan hanya informasi mengenai lama berada di memori, maka
algoritma ini dapat memindahkan page yang sering digunakan. Boleh jadi page itu
berada terus di memori karena selalu digunakan. Page itu karena mengikuti pola
antrian berdasar lamanya berada di memori menjadi elemen terdepan, diganti, dan
segera harus masuk kembali ke memori sehingga terjadi page fault kembali.
Gambar Algoritma
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.
Gambar Anomali Algoritma FIFO
5. Algoritma 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. 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 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.
Gambar Algoritma
LRU
Implementasi
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.
Stack, cara 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.
Gambar Algoritma
LRU dengan Stack
0 komentar:
Posting Komentar