Senin, 21 Januari 2013

Algoritma Pengganti Page FIFO

Algoritma ini adalah algoritma yang paling sederhana. Prinsip dari algoritma ini adalah seperti prinsip antrian (antrian tak berprioritas), halaman yang masuk lebih dulu maka akan keluar 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 berada di memori.


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 Page Modifikasi FIFO

Algoritma FIFO murni jarang digunakan, tetapi dikombinasikan (modifikasi).
Kelemahan FIFO yang jelas adalah algoritma dapat memilih memindahkan page yang sering digunakan yang lama berada di memori. Kemungkinan ini dapat dihindari dengan hanya memindahkan page tidak diacu Page ditambah bit R mencatat apakah page diacu atau tidak. Bit R bernilai 1 bila diacu dan bernilai 0 bila tidak diacu.
Variasi dari FIFO antara lain:
  • Algoritma penggantian page kesempatan kedua (second chance page replacement algorithm)
  • Algoritma penggantian clock page (clock page replacement algorithm)
Algoritma yang pertama adalah algoritma second chance. Algoritma second chance berdasarkan pada algoritma FIFO yang disempurnakan. Algoritma ini menggunakan tambahan berupa reference bit yang nilainya 0 atau 1. Jika dalam FIFO menggunakan stack , maka second chance 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.

Minggu, 20 Januari 2013

Algoritma Penggantian Page NRU (Not-Recenly Used)

Mekanisme algoritmanya
Pada algoritma ini, page diberi dua bit mencatat status page, bit R dan M, yaitu:
Bit R   : referenced (menyatakan page sedang diacu)
Bit R = 1 berarti sedang diacu
Bit R = 0 berarti tidak sedang diacu
Bit M  : modified (menyatakan page telah dimodifikasi)
Bit M = 1 berarti dimodifikasi
Bit M = 0 berarti tidak dimodifikasi
Dengan 2 bit, maka page-page dikelompokkan menjadi 4 kelas page, yaitu
Kelas 0 : Tidak sedang diacu, belum dimodifikasi (R=0, M=0)
Kelas 1 : Tidak sedang diacu, telah dimodifikasi (R=0, M=1)
Kelas 2 : Sedang diacu, belum dimodifikasi (R=1, M=0)
Kelas 3 : Sedang diacu, telah dimodifikasi (R=1, M=1)
Memilih mengganti page kelas bernomor terendah (bila terdapat page-page di kelas itu) secara acak.
Bila kelas tersebut kosong maka dipilih page di kelas lebih tinggi, dan seterusnya.
Algoritma ini mengasumsikan kelas-kelas bernomor lebih rendah akan baru akan digunakan kembali dalam waktu relatif lama.
Algoritma ini mudah dipahami dan diimplementasikan. Implementasi algoritma ini sangat efisien karena tak banyak langkah dalam pemilihan page. Algoritma ini memang tidak optimal, tapi dalam kondisi-kondisi normal telah memadai.




Algoritma Pengganti Page LRU

Merupakan algoritma penggantian isi cache, yaitu apabila cache sudah penuh dan diperlukan penyimpanan entri baru, maka entri yang paling jarang digunakan akan dihapus dan diganti dengan entri baru. Algoritma ini juga diterapkan dalam operasi paging.

Pengaturan penggunaan frame berdasarkan waktu terlama

- Clock Counter
  • Setiap entri page punya field time-of-use
  • Jika ada referensi ke suatu page, nilai register clock ditempatkan ke field time-of-use
  • Ganti page yang mempunyai waktu paling awal

LRU dengan Counter Clock

- Stack
  • Setiap ada referensi page, pindahkan page ke posisi paling atas
  • Page yang paling sering digunakan (most recently used) berada diposisi atas.
  • Page yang paling jarang digunakan (least recently used) berada diposisi bawah.
  • Umumnya berbentuk double linked-list
Penggunaan Stack

Algoritma Pengganti Page Optimal

Pengertian dari algoritma ini sendiri yaitu algoritma yang page nya paling optimal. Untuk prinsip dari algoritma ini sangat efisien sekali karena hanya mengganti halaman yang sudah tidak terpakai lagi dalam jangka waktu lama sehingga page fault yang terjadi akan berkurang dan terbebas dari anomali Belady  Selain itu juga page fault dari algoritma ini memiliki rate paling tinggi dari algoritma lainnya dari semua kasus, akan tetapi tidak belum bias disebut sempurna karena sulit untuk di mengerti dan dari segi system pun belum tentu bisa mengetahui page untuk berikutnya tetapi dapat di simulasikan hanya untuk suatu program. Untuk intinya gunakanlah hingga mendekati page optimal agar bisa memanfaatkannya.

Algoritma Pengganti Page Acak

Dari segi mekanisme algoritma tersebut, setiap akan timbul page fault, page yang diganti dengan pilihan secara acak. Untuk segi tekniknya sendiri pun algoritma ini tidak usah perlu menggunakan informasi dalam menentukan page yang diganti, didalam memory utama itu sendiri sudah mempunyai bobot yang sama untuk dipilih, karena teknik ini dapat dipakai untuk memilih page sembarang. Termasuk page yang sudah dipilih dengan benar-benar  / page yang tidak seharusnya diganti.


Kamis, 03 Januari 2013

Deadlock

Keadaan dimana 2 atau lebih proses saling menunggu meminta resources untuk waktu yang tidak terbatas lamanya. Analoginya seperti pada kondisi jalan raya dimana terjadi kemacetan parah. Deadlock adalah efek samping dari sinkronisasi, dimana satu variabel digunakan oleh 2 proses.









Model Deadlock
Model Deadlock














Penyebab Deadlock
  • Mutual Exclusion
  • Hold and Wait
  • Circular Waiting
  • No Preemption
Strategi mengatasi Deadlock
  • Prevention : memastikan paling sedikit satu penyebab Deadlock tidak berlaku
  • Avoidance : sistem menolak request terhadap resource yang berpotensi deadlock, Algoritma Banker
  • Detection and Recovery : membiarkan Deadlock terjadi, lalu mendeteksinya, kemudian melakukan recovery, Algoritma Ostrich


Algoritma Ostrich

Algoritma ostrich yaitu strategi mengabaika masalah yang mungkin terjadi atas dasar pada masalah itu sendiri yang mungkin sangat jarang terjadi melainkan jarang banget dah istilanya seperti seolah kita menempel kepala kita di pasir dan berpura-pura bahwa tidak ada masalah.
Maka lebih efektif untuk memungkinkan masalah itu terjadi dibanding upaya pencegahannya itu sendiri.
Pada algoritma ini juga bisa digunakan untuk menangani terjadi deadlock pada pemrograman concurrent jika untuk mendeteksi atau pencegahan lebih tinggi.
Sedikit gambaran pada Algoritma Ostrich ini
  • Jangan lakukan apapun, cukup restart sistem
    (ostrich: benamkan kepala ke pasir dan berpura-pura tidak masalah sama sekali)
  • Dilakukan bila:
    - Deadlock sangat jarang terjadilah
    - Algoritma deadlock lainnya biayanya lebih tinggi
  • Diimplementasikan oleh Windows dan UNIX
  • Trade off
    - Kenyamanan (convenience) vs keakuratan (correctness)

Sumber

Algoritma Safety

Algoritma ini untuk menentukan sistem berada dalam state selamat atau tidak diantaranya:
1. Work dan finish vektor dengan panjang (m) dan (n), inisialisasi : work = available dan finish[i] = false untuk i = 1,3,…,n.

2. Cari I yag memenuhi kondisi berikut:
(a) Finish [i] = false
(b) Need , ≤ Work
jika tidak terdapat I ke langkah 4.

3. Work = Work + Allocation
Finish[i] = true
Kembali ke langkah 2.

4.  Jika Finish [i]= true untuk semua I, maka sistem dalam state selamat.

Sumber

Algoritma Banker

Algoritma banker dipelopori oleh Edsger W.Djikstra, untuk metode ini adalah salah satu untuk menghindari akan terjadinya deadlock pada komputer. Pada metode algoritma ini bisa disebut juga algoritma penjadwalan tapi lebih kita kenal dengan sebutan algoritma banker. Algoritma Banker itu sendiri dapat kita gambarkan sebagai seorang bankir yang mempunyai urusan kepada kelompok orang yang meminta pinjam tetapi pada untuk yang meminjamkannya tahu akan batas maksimum peminjaman dana tersebut.
Secara umumnya algortima banker tersebut dibagi menjadi 4 struktur data, untuk variabel (n) adalah jumlah pada sistem dan (m) sendiri ialah jumlah sumber daya yang ada :
  1. Allocation :  Matriks (n) X (m) mendefinisikan sumber daya setiap tipe yang dialokasi oleh setiap proses. Jika allocation [i,j]=k, maka proses P1 dialokasikan k  instansi dari sumber daya Rj. 
  2. Available :  Sebuah vektor (m) menandakan sumber daya yg ada untuk setiap tipe, jika available [j]= k, dimana k instansi dari tipe Rj yang ada.
  3. Need : Matriks (n) X (m) menandakan sisa sumber daya yang dibutuhkan setiap proses. Jika need [i,j]= k, maka proses Pi membutuhkan k  instansi dari sumber daya Rj untuk menyelesaikan tugasnya. Need[i,j]= Max[i,j] – Allocation[i,j]. 
  4. Max : Matriks (n) X (m) menandakan maksimal permintaan tiap proses. Jika Max [i,j]= k, maka proses Pi meminta paling banyak k  instansi dari sumber daya tipe Rj.
Untuk membentuk penyajian algoritma ini secara sederhananya, misalkan X dan Y adalah vektor dengan panjang n. Sehingga X ≤ Y jika dan hanya jika X[i] ≤ Y[i] untuk semua l = 1,2..,n. contohnya : jika X=(1,7,3,2) dan Y(0,3,2,1) maka Y≤X. Y≤X dan Y≠X
Disamping itu semua Algoritma ini :

– Proses harus “declare” max. kredit resource yang diinginkan
– Proses dapat block (pending) sampai resource diberikan
– Menjamin sistem dalam keadaan safe state
– OS menjalankan algoritma banker
* Saat proses melakukan request resource
* Saat proses terminate atau release resource yang digunakan => memberikan resource ke proses yang pending
request.

Ada sedikit contoh gambar Algoritma Banker

















Kelemahan dari algoritma ini adalah:
  • Proses kebanyakan belum mengetahui jumlah maksimum resource yang dibutuhkannya
  • Beberapa resource itu sendiri dapat diambil dari sistem sewaktu-waktunya
  • Algoritma membuat sistem hingga waktu yang tidak terbatas
  • Jumlah proses tidak tetap

Sumber 
 
© Copyright 2035 Coretan Buku Kampus