Kamis, 10 Januari 2013

Algoritma - Algoritma Penggantian Page

Postingan kali saya akan memaparkan mengenai macam - macam algoritma penggantian halaman.

  •  Algoritma Penggantian Page Acak
Pada algoritma ini setiap kali terjadi page fault penggantian page nya di pilih dengan cara acak. Dan teknik ini tidak memerlukan informasi apapun untuk menentukan page yang di ganti tersebut. Itu karena semua page di memori utamanya mempunyai bobot yang sama sehingga tidak ada kriteria tertentu untuk di pilih. 
Karena teknik ini mengganti page dengan  cara acak dan bebas, maka bisa saja page yang sedang diacu (page yang seharusya tidak di ganti) pun dapat di pilih, sehingga menimbulkan rate terjadinya page fault yang sangat tinggi. 
  • Algoritma Penggantian Page Optimal
Algoritma ini di sebut juga sebagai Algoritma utopia (ideal tanpa dapat di jadikan kenyataan), mengapa demikian? Sebab algoritma ini tak mungkin di buat prosedur yang dapat mengetahui peluang pemakaian suatu page kembali di masa datang. 
Mekanisme dari algoritma ini adalah dengan mengumpulkan dan memakai informasi untuk menentukan page yang di ganti sehingga mendekati optimal. Dasar dari algoritma ini yakni memilih page yang berpeluang dapat di pakai kembali di masa yang akan datang yang paling kecil. Maksudnya memakai kembali page yang kemungkinan kecil tidak dapat di gunakan lagi, otimalisasi page. 
Algoritma ini penting untuk kajian teoritis sebagai pembanding bagi algoritma-algoritma penggatian page yang lain.
  • Algoritma Penggantian Page NRU (Not-recently Used)
Pada algoritma ini ada pemberian status (2 bit : R dan M) untuk setiap page, berikut keterangannya:
Bit R : referenced (menyatakan page yang sedang diacu)
          Bit R = 0 berarti sedang diacu
          Bit R = 1 berarti tidak sedang diacu
Bit M : modified (menyatakan page telah dimodifikasi)
          Bit M = 1 berarti dimodifikasi
          Bit M = 0 berarti tidak dimodifikasi
Sehingga, page-page dapat dikelompokan menjadi 4 kelas page, yaitu:
    • Kelas 0 (R=0, M=0) : tidak sedang diacu dan belum dimodifikasi
    • Kelas 1 (R=0, M=1) : tidak sedang diacu tapi telah dimodifikasi
    • Kelas 2 (R=1, M=0) : sedang diacu tapi belum dimodifikasi
    • Kelas 3 (R=1, M=1) : sedang diacu dan sudah dimodifikasi
Berdasarkan pembagian kelas tersebut diatas, maka untuk pemilihan page pengganti dilihat dari kelas yang bernomor paling rendah, tapi apabila terdapat page-page di kelas tersebut pemilihan dilakukan secara acak. Dan apabila kelas tersebut kosong maka dipilih page dikelas yang paling tinggi, begitupun seterusnya.
Inti dari algoritma ini adalah mengasumsikan kelas-kelas  bernomor lebih rendah akan baru akan di gunakan kembalil dalamwaktu relatif lama.
  • Algoritma Penggantian Page FIFO (First-In, First-Out)
Cara kerja algoritma ini simple, seperti halnya dengan antrian tak berprioritas. Dimana page yang masuk lebih dulu maka akan keluar lebih dulu juga. Oleh karena algoritma ini menggunakan struktur data stack, yaitu jika tidak ada frame yang kosong pada saat terjadi page fault maka frame yang berada pada stack paling bawah akan dipilih. 
Algoritma ini dapat memindahkan page yang sering digunakan berdasarkan informasi mengenai lamanya berada di memori. Dan bisa saja page itu selalu berada di memori karena selalu digunakan.
  • Algoritma Penggantian Page Modifikasi dari Algoritma FIFO 
Untuk menyempurnakan kelemahan dari algoritma FIFO maka algoritma tersebut dimodifikasi, yakni dengan hanya memindahkan page yang tidak diacu dan dengan menambahkan bit R mencatat apakah page diacu atu tidak. Bila bit R bernilai 1 maka diacu, bila bernilai 0 tidak diacu. 
Ada 2 variasi FIFO, yakni:
    • Algoritma penggantian page kesempatan kedua (second chance page replacement agorithm)
                Merupakan penyempurnaan dari Algoritma FIFO, bedanya jika FIFO menggunakan struktur  data stack, maka second chance ini menggunakan circular queue. Yakni page yang baru digunakan akan di beri nilai 1 pada reference bitnya, jika halaman sudah bernilai 1 pada reference bit-nya maka tidak langsung diganti walaupun dia berada pada tumpukan terbawah (berbeda dengan FIFO).
    • Algoritma penggantian clock page (clock page replacement algorithm)
                Algoritma ini merupakan perbaikan dari kelemahan second chance yang mana tidak efisien karena memindahkan page-page di senarainya. Pada  algoritma ini, semua page merupakan  senarai melingkar membentuk pola jam. Terdapat petunjuk (pointer) ke page tertua.

Kedua algoritma ini adalah sama, hanya berbeda pada implementasinya, jika second chance menggunakan senarai lurus tidak sirkular, sedangkan clock page menggunakan senarai sirkular.

  • Algoritma Penggantian Page LRU (Least Recently Used)
Performance dari algoritma ini mendekati algoritma optimal yang di kenal sangat sulit dalam pengimplementasiannya, hanya saja LRU menjadi lebih mahal sebab algoritma ini harus mengelola informasi seluruh page di memori dengan membuat linked list untuk mendata page mana yang paling lama tidak terpakai, serta harus mengupdate setiap kali ada page yang di akses.

Itulah beberapa point tentang algoritma penggantian page, 
hmm,, mudah-mudahan bermanfaat ya,,,  
Terima Kasih Sudah Membaca,, ^_^

Diposting oleh Unknown di 20.43 0 komentar  

Minggu, 06 Januari 2013

Algoritma Banker, Safty dan Ostrich

Wah wah,, hampir aja lumutan nih blog,, hehehe
lama tak jumpa nih readers,, apa kabar..? ^_^
baiklah kita langsung saja pada topik postingan kali ini mengenai deadlock, dan kali ini saya akan membahas tentang algoritma-algoritma untuk menangani deadlock tersebut.

Pertama kita pahami dulu apa itu deadlock. Deadlock jika di analogikan dalam kehidupan nyata seperti sebuah kemacetan kendaraan yang akan menyebrangi sebuah jembatan yang hanya bisa di lalui oleh satu antrian kendaran. Sehingga akan ada jeda saling menunggu antara kendaraan dari dua seberang jembatan untuk mengosongkan jembatan tersebut dan bisa di lalui oleh kendaraan secara beriringan. Maka di sini bisa di simpulkan bahwa Deadlock adalah keadaan saling menunggu antara dua proses atau lebih untuk dapat menggunakan resource yang sedang di pakai. 

Maka dari itu untuk menghindari hal ini, ada beberapa algoritma-algoritma untuk menangani permasalahan di atas. Mari kita bahas satu persatu:
  • Algoritma Banker
Algoritma banker adalah sebuah algoritma resource allocation dan deadlock avoidance yang di pelopori oleh Edsger W Djikstra untuk menangani terjadinya deadlock pada sistem operasi. Algoritma banker dapat di analogikan seperti sistem perbankan. Dimana ada kegiatan penarikan dan peminjaman uang dari nasabah kepada bank. Disini nasabah dapat di ibaratkan sebagai proses, uang yang di pinjamkan atau yang di setorkan di ibaratkan sebagai resource dan bank secara keseluruhan dapat di ibaratkan sebagai sistem operasi. Intinya disini jika bank tidak boleh sampai kehabisan uang agar para nasabah tetap dapat melakukan peminjaman, oleh karena itu para peminjam di haruskan untuk mengembalikan pinjamannya tepat waktu. 

Begitu pula yang terjadi pada algortima ini. Dimana sistem operasi akan memberikan resource pada proses yang sudah siap di eksekusi asalkan tidak melebihi batas resource sistem. Dan jika proses sudah selesai di eksekusi maka proses harus segera mengembalikan resource yang telah di gunakannya. Sistem operasi juga bisa menolak proses yang dapat membuat sistem berada pada kondisi unsafe state melalui algoritma ini. 
  • Algoritma Safety
Algoritma ini pun juga merupakan algoritma untuk penanganan terjadinya deadlock pada sistem operasi. Cara kerjanya yakni melakukan pengecekan pada sistem apakah sistem berada pada kondisi aman (safe state) atau tidak aman (unsafe state). Sistem operasi akan menanyakan apakah suatu proses telah selesai atau masih berjalan, jika proses tersebut masih berjalan maka proses lain harus menunggu hingga proses awal selesai di eksekusi. Hal ini merupakan inti dari algoritma ini, dengan membandingkan waktu pengeksekusian proses maka dapat di simpulkan apakah sistem dalam keadaan aman atau tidak.
  • Algoritma Ostrich
Agoritma ostrich adalah algoritma penanganan deadlock yang mungkin terjadi atas dasar bahwa deadlock di yakini sangat jarang terjadi dengan kata lain adalah dengan mengabaikan trejadinya deadlock tersebut. Algoritma ini memiliki 2 pendekatan dalam pengimplementasiannya, yaitu pendekatan trade-offs dan pendekatan hybrid.
Pendekatan trade-offs yaitu jika kondisi atau keadaan berubah atau belum teridentifikasi, masalah yang sangat jarang terjadi dapat kembali lagi. Sedangkan pendekatan hybrid yakni menentukan bahwa kasus deadlock sangat jarang atau bahkan tidak pernah terjadi. 

Naahh sekian postingan kali ini, semoga bermanfaat ya,,, ^_^

Diposting oleh Unknown di 04.52 0 komentar  

Postingan Lebih Baru Postingan Lama Beranda

Langganan: Postingan (Atom)

Blogger Template by Blogcrowds