makalah sistem operasi

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: