Algortitma Penggantian Halaman (Part II)

Sebelumnya untuk penjelasan mengenai apa itu algoritma penggantian anda bisa lihat dan baca disini. Sedangkan kelanjutan dari penjelasan algortima penggantian halaman selanjutnya adalah pengertian apa saja yang termasuk pada algoritma penggantian halaman dan implementasinya.

Langsung saja ....

Berikut beberapa algoritma penggantian halaman (page) :

• Algoritma penggantian page acak : merupakan mekanisame algoritma setiap terjadi page fault pada page atau halaman yang diganti dipilih secara acak. Teknik ini tidak memakai informasi apapun dalam menentukan page atau halaman yang akan diganti. Semua page di memori utama mempunyai bobot yang sama untukk di pilih. Teknik ini dapat memilih sembarang page, termasuk page yang sedang diacu (page yang seharusnya tidak di ganti).

 

• Algortima penggantian page optimal : merupakam mekanisme algoritma  yang memilih page atau halaman yang berpeluang dipakai kembali di masa datang yang paling kecil. Strategi ini akan menghasilkan jumlah page fault paling sedikit. Algoritma ini bisa di bilang utopia ( ideal tanpa dapat dijadikan kenyataan) karena tak mungkin di buat prosedur yang dapat mengetahui peluang pemakaian suatu page di masa datang ( meode ini mungkin tidak diterapkan).

• Algoritma penggantian page NRU ( Not-Recently Used ) : mekanisme algoritma dimana page atau halaman di beri dua bit untuk mencatat status page, bit R dan M, yaitu :

• Bit R : referenced (menyatakan page sedang di acu)
• Bit R = 1 berarti sedang diacu
• Bit R = 0 berarti sedang tidak diacu
• Bit M : modified (menyatakan page telah dimodifikasi)
• Bit M = 1 berarti telah di modifikasi
• Bit M = 0 berarti belum dimodifikasi
• Dengan dua bit, maka page atau halaman-halaman dikelompokkan menjadi 4 kelas page, yaitu :
• Kelas 0 : tidak sedang diacu, belum di modifikasi (R = 0, M = 0)
• Kelas 1 : tidak sedang diacu, telah dimodifikasi (R = 0, M = 1)
• Kelas 2 : sedang diacu, belum di modifikasi (R = 1, M = 0)
• Kelas 3 : sedang diacu, telah dimodifikasi (R = 1, M = 1)
• Memilih mengganti page kelas bernomor terendah (bila terdapat page atau halaman yang ada pada kelas itu) secara acak.
• Bila kelas tersebut kosong maka dipilih lah page atau halaman di kelas lebih tinggi dan seterusnya. 
• Dengan kata lain algoritma ini mengasumsikan kelas-kelas bernomor lebih rendah baru akan digunakan kembali dalam jangka waktu yang relatif lama.

• Algortima penggantian page FIFO ( First In First Out ) : mekanisme algortima yang memerlukan pengolahan senarai page di memori, dimana elemen terdepan senarai adalah page tertua dan ujung belakang adalah page paling akhir datang. Algortima ini sangat simpel implementasinya yaitu ketika page atau halaman masuk terlebih dahulu page tersebut akan keluar terlebih dahulu. Intinya pada algortima ini konsep dasarnya page yang paling lama tersimpan pada memori maka page tersebut yang paling sering digunakan dapat dipindahkan pada memori.

• Algoritma penggantian modifikasi page FIFO : algortima yang merupakan modifikasi dari algoritma penggantian page FIFO karena murni algortima tersebut jarang digunakan. Namun kemungkinan kelemahan page FIFO dapat dihindari dengan hanya memindahkan page tidak diacu. Page ditambah bit R mencatat apakah page diacu atau tidak, bit R bernilai 1 maka apabila page diacu dan bernilai 0 apabila tidak diacu. 

• Variasi dari FIFO antara lain sbb :

• Algortima penggantian page kesempatan kedua (Second chance page replacement algorithm) : mekanisme algoritma pada saat terjadi page fault, maka algoritma memilih page atau halaman elemen terdepan  diganti bila bit R bernilai 0. Jika bit R bernilai 1 maka bit page terdepan senarai direset menjadi 0 dan diletakkan ke ujung belakang senarai, sehingga mekanisme ini kembali diterapkan ke elemen berikutnya.

• Algoritma penggantian clock page (clock page replacement algorithm) : mekanisme algoritma ketika semua page merupakan senarai melingkar membentuk pola jam, terdapat penunjuk (pointer) ke page tertua. Ketika terjadi page fault page yang ditunjuk diperiksa. Jika bit R = 0 maka page diganti, page baru ditempatkan ditempat page diganti, dan penunjuk dimajukan satu posisi ke page berikutnya. Namun jika bit R = 1 maka bit R direset menjadi 0, dan penunjuk dimajukan satu posisi hingga seterusnya sampai menemui page dengan bit R = 0.

• Algoritma penggantian page LRU ( Least Recently Used ) : mekanisme algoritma ketika terjadi page fault maka memindahkan page yang tidak digunakan paling lama, namun masalah utamanya algoritma ini sangat mahal.

Semoga bermanfaat.

 

 

Read More

Algoritma Penggantian Halaman (Sistem Paging)

Pada dasarnya semua program yang di jalankan pada sebuah komputer harus di muat terlebih dahulu di memori utama, namun masalah yang muncul adalah pada saat program yang akan dieksekusi lebih besar dibanding memori utama yang tersedia. Tapi ada dua solusi ketika masalah tersebut terjadi yaitu sbb :

• Overlay : program yang akan dieksekusi dipecah menjadi bagian-bagian yang dapat dimuat oleh memori utama. Ketika overlay belum diperlukan (tidak dieksekusi) maka program disimpan pada disk, overlay tersebut dimuat ke memori begitu diperlukan(dieksekusi).
• Virtual memory : kemampuan mengalamati ruang memori melebihi memori utama yang tersedia. Jadi ukuran gabungan program, data dan stack melampaui jumlah memori fisik yang tersedia. Sistem operasi dapat menyimpan bagian-bagian proses yang sedang digunakan di memori utama dan sisanya di disk.

Virtual memory dapat dilakukan dengan tiga cara, yaitu :

1. Paging
2. Segmentasi
3. Kombinasi Paging dan Segmentasi

Dalam virtual memory ada yang namanya penggantian halaman, yaitu merupakan sebuah algoritma yang menentukan atau menukar halaman dari memori utama ke disk jika halaman pada memori utama perlu dialokasikan. Penggantian memori terjadi ketika page fault yang berarti page frame pada memori fisik harus diputuskan dan segera diganti.

• Page fault : exception untuk permintaan alokasi halaman ke memori.
• Page frame : unit terkecil yang ada pada memori fisik.

Ada beberapa jenis algoritma penggantian halaman, yaitu sbb :

1. Algoritma penggantian page acak
2. Algoritma penggantian page optimal
3. Algoritma penggantian page NRU
4. Algoritma penggantian page FIFO
5. Algoritma penggantian page modifikasi FIFO
6. Algoritma penggantian page LRU

Untuk penjelasan keenam algoritma tersebut tunggu diartikel selanjutnya disini .

Semoga bermanfaat.

Read More

Algoritma Ostrich

Algoritma Ostrich sama juga dengan algoritma banker dan algoritma safety hanya algoritma yang satu ini sudah tentu berbeda dengan algoritma yang lainnya. Algoritma Safety merupakan algoritma yang mengabaikan proses yang terjadi pada sistem ibaratnya seperti burung unta yang menempelkan kepalanya di pasir dan berpura-pura tidak terjadi masalah apa pun. Maksudnya algoritma yang satu ini tidak terlalu memperhatikan kondisi sistem apakah akan terjadi deadlock atau tidak melainkan menganggap bahwa deadlock jarang terjadi pada suatu sistem tertentu.

Algortima Ostrich di gunakan oleh dua metode sebagai berikut :

1. Trade-offs : merupakan metode penanganan deadlock dengan sistem dimana ada asumsi bahwa suatu masalah (dalam hal ini deadlock) jarang terjadi atau masalah tersebut belum tentu benar bisa saja sewaktu-waktu berubah atau bahkan akan kembali terjadi, sehingga jangan terlalu terpaku akan satu masalah yang ada.
2. Pendekatan Hybird : merupakan metode yang mengasumsikan masalah (dalam hal ini misal deadlock) sangat jarang terjadi atau bahkan tidak akan pernah terjadi sama sekali, dan biasanya bisa saja beralih pada algoritma yang lebih kompleks untuk mengetahui masalah tersebut benar-benar terjadi atau tidak.

 Semoga bermanfaat :)

Read More

Algoritma Safety

Algoritma Safety sama halnya dengan algoritma banker merupakan algoritma penangan deadlock, namun algoritma safety ini lebih kepada memastikan apa kah suatu sistem dapat dikatakan aman (safe state) atau tidak aman (unsafe state). Algoritma ini cukup sederhana hanya mengecek kondisi dimana sistem jika di katakan dalam keadaan aman (safe state) maupun tidak (unsafe state), maka dapat di ilustrasikan dalam program sederhana pada gambar berikut :

Penjelasan program algoritma safety dari gambar diatas, lihat gambar di bawah ini :

Semoga bermanfaat :)

 

Read More

Algoritma Banker

Algoritma banker merupakan salah satu algoritma penanganan terjadinya deadlock, algoritma tersebut di sebut algoritma banker karena simulasi dari algoritma ini mirip dengan sistem bankir di bidang perbankan. Algoritma banker ini dikemukakan oleh Edsger W. Djiksta dan merupakan suatu simulasi sistem perbankan yang diibaratkan untuk menghindari deadlock.

Disini maksudnya jika anggap saja misal :

1. Bank : Dianggap sebagai sistem operasi.
2. Pinjaman atau uang : Dianggap resource (resouce merupakan proses yang sedang berjalan).
3. Nasabah : Dianggap proses yang memerlukan resource.

Implementasinya : 

Jadi algoritma banker ini di gunakan agar bank tidak kekurangan uang, sehingga pada saat nasabah melakukan penarikan sejumlah uang bank tersebut tetap pada kondisi safe state (dalam keadaan aman), jika nasabah tidak mendapat penarikan uang maka bank berada pada kondisi unsafe state (keadaan tidak aman), maka nasabah harus menunggu hingga ada tambahan uang dari nasabah lain. Nah jika bank ada pada kondisi dimana nasabah tidak dapat melakukan penarikan uang atau melakukan peminjaman uang maka disana lah terjadinya deadlock. Intinya agar tidak terjadi deadlock maka nasabah yang melakukan peminjaman uang harus segera mengembalikan uang pinjaman pada bank dengan tepat waktu.

Sehingga dapat dikatakan algoritma banker ini di jalankan oleh sebuah sistem operasi ketika ada request resource (permintaan proses yang akan di eksekusi). Nah penolakan dari algoritma ini terhadap deadlock terjadi pada saat request resource yang akan di eksekusi dapat membawa sistem pada kondisi unsafe state. Dengan kata lain ketika suatu proses masuk ke dalam sistem maka proses tersebut harus di eksekusi menggunakan jumlah maksimal resource yang di perlukan namun tidak boleh melebihi jumlah resource yang di miliki oleh sistem. Kemudian proses tersebut harus segera mengembalikan resource pada sistem dengan tepat waktu, jika tidak maka akan terjadi deadlock dimana suatu proses akan saling tunggu atau terhenti secara tiba-tiba karena resource yang akan di gunakan sedang di gunakan oleh proses lain.

Semoga bermanfaat :)

Read More