Algoritma Penggantian Page FIFO

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

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)

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

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.

• 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.

Algoritma Penggantian Page Optimal

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.

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