IX. 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 faultyang terjadi berkurang) dan terbebas dari anomali belady.
Strategi ini akan menghasilkan jumlah page fault paling sedikit. 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 tidak 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.
X. Algoritma LRU(LEAST RECENTLY USED)
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.
XI.
Pengalokasian Frame
Ø Algoritma Priority
Allocation
Merupakan pengalokasian dengan
memberikan jumlah bingkai sesuai dengan prioritas proses tersebut.
Pendekatannya mirip dengan proportional allocation, perbandingan frame-nya
tidak tergantung ukuran relatif dari proses, melainkan lebih pada prioritas
proses atau kombinasi ukuran dan prioritas. Jika suatu proses mengalami page fault maka proses tersebut akan
menggantinya dengan salah satu frameyang
dimiliki proses tersebut atau menggantinya denganframe dari proses yang prioritasnya lebih rendah. Dengan kedua
algoritma di atas, tetap saja alokasi untuk tiap proses bisa bervariasi
berdasarkan derajat multiprogramming-nya. Jika multiprogramming-nya
meningkat maka setiap proses akan kehilangan beberapa frame yang akan digunakan
untuk menyediakan memori untuk proses lain. Sedangkan jika derajat multiprogramming-nya
menurun, frame yang sudah
dialokasikan bisa disebar ke proses-proses lainnya.
Ø Alokasi Global dan Lokal
Dalam pengalokasian bingkai salah satu hal yang
penting adalah penggantian halaman. Kita dapat mengklasifikasikan algoritma
penggantian halaman ke dalam dua kategori:
·
Penggantian Global.
Penggantian secara global
memperbolehkan suatu proses mencari bingkai pengganti dari semua bingkai yang
ada meskipun bingkai tersebut sedang dialokasikan untuk proses lain. Hal ini
memang efisien, tetapi ada kemungkinan proses lain tidak mendapatkan bingkai
karena bingkainya terambil oleh proses lain.
·
Penggantian Lokal.
Penggantian lokal hanya mengijinkan
proses untuk mencari bingkai pengganti dari bingkai-bingkai yang memang
dialokasikan untuk proses tersebut.
Pada algoritma penggantian lokal jumlah bingkai yang
dialokasikan pada suatu proses tidak akan berubah. Sedangkan pada algoritma
penggantian global jumlah bingkai pada proses tersebut mungkin akan bertambah
dengan asumsi proses lain tidak mengambil bingkai proses ini sebagai pengganti
dari bingkai proses tersebut.
Masalah pada algoritma penggantian global adalah
proses tidak dapat mengontrol page
fault rate proses itu sendiri. Keunggulan algoritma ini adalah
menghasilkan system throughput yang lebih bagus oleh karena itu algoritma
ini lebih sering dipakai.
XII. Thrashing
Thrashing adalah
keadaan dimana proses sibuk untuk mengganti halaman yang dibutuhkan secara
terus menerus. Ketika proses membutuhkan bingkai yang lebih, maka akan terjadi page fault yang menyebabkan CPU utilization semakin menurun. Ketika
sistem operasi mendeteksi hal ini, derajat multiprogramming makin ditingkatkan yang menyebabkan CPU utilization kembali menurun
drastis hal ini yang menyebabkan thrashing.
Untuk membatasi efek thrashing dapat
menggunakan algoritma penggantian lokal. Dengan algoritma penggantian lokal,
jika terjadi thrashing, proses tersebut dapat menggambil bingkai dari
proses lain dan menyebabkan proses tersebut tidak mengalami thrashing.
Salah satu cara untuk menghindari thrashing adalah dengan cara
menyediakan jumlah bingkai yang pas sesuai dengan kebutuhan proses tersebut.
cc:
