Algoritma pergantian page

Algoritma Penggantian Page Acak

Pada algoritma pergantian page acak setiap kali terjadi page fault penggantian page di pilih secara acak atau default. Teknik ini tidak memerlukan informasi apapun untuk menentukan page yang di ganti tersebut. 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

Cara kerja dari algoritma penggantian page optimal 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,

• 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,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. Intinya adalah mengasumsikan kelas-kelas bernomor lebih rendah akan baru akan di gunakan kembalil dalam waktu relatif lama.

Algoritma Penggantian Page FIFO (First-In, First-Out)

Cara kerja algoritma ini dimana page yang masuk lebih dulu maka akan keluar lebih dulu juga. 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.

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)

• Algoritma penggantian clock page (clock page replacement algorithm)

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.

Sekian penjelasan materi tentang algoritma pergantian page dari saya semoga bermanfaat.

Algoritma banker, safety dan ostrich

Blogging lagi nih gan, heu...
kali ini saya akan membahas tentang algoritma banker, Safety dan Ostrich, saya akan membahas mulai dari algoritma Banker terlebih dahulu.

1. Algoritma banker

        Algoritma Banker pertama kali dipelopori oleh Edsger W Djikstra, merupakan algoritma resource allocation dan deadlock avoidance. Algoritma ini dipakai untuk menangani deadlock pada sistem operasi. Lantas kenapa disebut dengan algoritma banker ? karena algoritma ini di analogikan seperti sistem perbankan, dimana ada transaksi (penarikan dan peminjaman) antara nasabah dengan bank. Di sini nasabah di ibaratkan sebagai proses, uang sebagai resource dan bank sebagai sistem operasi. Agar proses harus tetap berjalan bank tidak boleh kehabisan uang agar nasabah dapat meminjam uang dan nasabah harus tepat waktu dalam mengembalikan uang. Dari penjelasan tersebut intinya algoritma ini adalah sistem operasi akan memberikan resource pada proses yang harus siap di eksekusi asalakan tidak melebihi limit resource sistem,dan jikaproses sudah selesai di eksekusi maka proses harus segera mengembalikan resource yang sudah digunakan, Sistem operasi juga bisa menolak proses yang dapat sistem berada pada kondisi unsafe state melalui algoritma ini.

   2. Algoritma safety

      Algoritma ini juga merupakan algoritma untuk penanganan terjadinya deadlock pada sistem operasi. Cara kerjanya 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. 

misalnya contoh seperti ini :

1. work and finish vektor 

    dengan panjang m dan n , jika work : available dan finish[i] : false

    untuk i = 1,2,3......

2. cari i dengan finish[i] = false , need ≤ work

    jika i tidak terdapat 

3. work + work = allocation
     finish[i]= true , kembali ke 2

4. finish[i] = true  pada semua i maka sistem selamat

3. Algoritma Ostrich

    Agoritma ostrich adalah algoritma penanganan deadlock yang mungkin terjadi 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. 

Kesimpulannya  dari penjelasan mengenai algoritma di atas bagaimana cara menangani deadlock,deadlock dalah keadaan saling menunggu antara dua proses atau lebih untuk dapat menggunakan resource yang sedang di pakai.  pada sebuah sistem operasi karena penanganan terhadap deadlock berbeda-beda sesuai dengan bagaimana deadlock tersebut terjadi.semoga bermanfaat

jehan hariadhi

saya adalah jehan hariadhi