Algoritma Penggantian Page Acak

Algoritma Penggantian Page Acak atau Algoritma Random adaah Page yang dikeluarkan untuk memberi tempat ke yang baru ditentukan secara acak tanpa kriteria tertentu.  

Adapun mekanisme algoritmanya adalah 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 terburuk).

 

Dalam penggunaannya algoritma page acak ini tidak menggunakan informasi apapun dalam menentukan page yang diganti, semua page di dalam memori utama mempunyai bobot yang sama untuk dipakai. Dengan menggunakan algoritma ini dapat memilih sembarang page.

Kekurangan dari algoritma page acak ini sendiri yaitu bisa menimbulakan rate terjadinya page error yang sering dan akan terjadi.

Pengertian Deadlock

Deadlock merupakan penumpukan proses pada sebuah sistem yang mengakibatkan benturan antar proses. Diilustrasikan dengan sebuah jalur jalan, dimana mobil sebagai proses yang akan menuju sumnber daya. Beberapa mobil harus mundur untuk memudahkan mobil lainnya untuk maju terlebih dahulu dan menghindari penumpukan pada jalur tersebut.

Deadlock terjadi bila terdapat empat kondisi berikut ini secara simultan.

• Mutual Exclusion : Satu proses terjadi pada satu waktu untuk dapat menggunakan sumber daya.
• Hold and Wait : suatu proses membawa sedikitnya satu sumber daya dan menunggu mendapatkan tambahan sumber daya baru yang dibawa oleh proses berikutnya.
• Non-Preemption : sebuah sumber daya dapat dibebaskan dengan sukarela oleh proses yang memegangnya, setelah proses tersebut menyelesaikan bagiannya.
• Circular Wait : Situasi dimana terjadi saling menunggu antara  beberapa proses sehingga membentuk waiting chain (circular).

Terdapat beberapa metode penanganan deadlock diantaranya Algoritma Banker, Algoirtma Safety dan Algoritma Ostrich.

Semoga bermanfaat.

Algoritma Ostrich

Algoritma Ostrich didefinisikan sebagai sebuah strategi dengan mengabaikan masalah yang bisa saja terjadi dengan asumsi bahwa kemungkinan terjadinya masalah tersebut sangat jarang. Algoritma ini memiliki dua pendekatan untuk menangani deadlock yaitu Trade-offs dan Pendekatan Hybrid.

• Trade-offs
  Metode ini memiliki sistem yang berasumsi bahwa suatu masalah akan jarang terjadi dan mungkin belum tentu benar terjadi karena sewaktu-waktu bisa berubah dan kembali terjadi masalah yang sama.
  
• Pendekatan Hybrid
  Pendekatan Hybrid menggunakan algoritma Ostrich yaitu menentukan bahwa kasus sangat jarang tidak terjadi, dan kemudian beralih dari algoritma lain yang lebih kompleks. 

Sumber

Algoritma Safety

Algoritma Safety adalah sebuah metode yang digunakan untuk meminimalisir resiko pada sebuah sistem. Algoritma ini terbilang sederhana karena cara kerjanya yang hanya mencari dan memastikan apakah sebuah sistem berstatus aman (Safe state) atau tidak aman (Unsafe safe).

Algoritma dari Algoritma Safety :

Algoritma Banker

Algoritma Banker merupakan algoritma yang dikembangkan oleh Edsger Dijkstra. Algoritma ini bekerja dengan menguji tingkat keamanan dari kemungkina terjadinya deadlock yaitu dengan melakukan simulasi berdasarkan jumlah maksimum resource lalu kemudian memeriksa kondisi safe state terhadap semua kemungkinan terdinya kondisi deadlock pada seluruh aktifitas dalam posisi pending sebelum memutuskan pengalokasian resorce.

Algoritma Banker ini dijalankan oleh sistem operasi ketika proses melakukan request resource. Penghindaran terhadap deadlock dilakukan dengan menolak atau menunda suatu request jika sekiranya penerimaan terhadap request tersebut dapat membawa sistem dalam kondisi unsafe state. Berdasar algoritma ini, ketika suatu proses masuk ke dalam sistem, proses ini harus memberikan jumlah maksimum resource yang diperlukan dimana resource tersebut tidak boleh melebihi total resource yang dimiliki oleh sistem. Selain itu, ketika suatu proses mendapatkan resource yang diinginkan, proses tersebut harus mengembalikan resource yang digunakan dalam jangka waktu tertentu.

Agar algoritma Banker’s ini dapat berkerja, harus ada tiga hal yang dimiliki/diketahui, yaitu:

1. Jumlah resource dari tiap proses yang mungkin di request.
2. Jumlah resource dari tiap proses yang sedang di pegang atau di gunakan (hold).
3. Jumlah sisa resource yang dimiliki oleh sistem.

Resource hanya dapat diberikan pada suatu proses jika:

1. request ≤ max, jika tidak set error, karena request melebihi jumlah klaim sebelumnya.
2. request ≤ available, jika tidak proses harus menunggu hingga resource yang diminta ada.

Keterangan :

• Request adalah jumlah resource yang di request oleh proses.
• Max adalah jumlah resource yang sebelumnya sudah di klaim oleh proses. Seperti yang telah disebutkan di awal, ketika masuk ke dalah sistem, proses harus memberikan jumlah maksimum proses yang diperlukan.
• Available adalah jumlah sisa resource system yang sedang tidak terpakai.

Gambar dibawah ini merupakan contoh mengenai safe state yang berkaitan dengan Algoritma Banker untuk multiple resource.

Dicontohkan sebuah sistem memiliki proses dengan resource A, B, C dan D.

Sumber