Analisa Algoritma-algoritma Virtual Memory

Analisa Algoritma-algoritma Virtual Memory

Didalam Virtual Memory terdapat Algoritma-algoritma yang beroperasi didalam suatu memory,maka dari itu disini saya akan menjelaskan tentang Algoritma-algoritma tersebut.

Sebelum menjelaskan Algoritma saya akan menjelaskan dulu pengertian VIRTUAL MEMORY

Virtual Memory Adalah  kemampuan mengalamati ruang memory melebihi memory utama yang tersedia.

Prinsip Virtual Memory adalah kecepatan maksimum eksekusi proses di virtual memory dapat sama tapi tak pernah melampaui kecepatan eksekusi proses yang sama di sistem tanpa virtual memory.

1. Pengertian tentang Algortima 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.

2. Pengertian tentang 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.

3. Pengertian tentang Algoritma Page NRU (Not-Recently Used)

Untuk mekanisme dari algoritma ini diberi dua bit untuk mencatat status page, diantaranya bit M dan R yaitu :

Bit M : Page yang telah dimodifikasi

Bit M = 0 berarti tidak dimodif

Bit M = 1 berarti sudah dimodif

Bit R : Page yang sedang dipacu / referenced

Bit R = 1 berarti sedang di acu

Bit R = 0 berarti tidak sedang di acu

Adanya dua bit di atas maka akan dapat dikelompokkan menjadi 4 kelas page, yaitu :

Kelas 0 => Tidak sedang di acu / belum di modif (R=0, M=0)

Kelas 1 => Tidak sedang di acu / telah di modif (R=0, M=1)

Kelas 2 => Sedang di acu / belum di modif (R=1, M=0)

Kelas 3 => Sedang di acu / telah di modif (R=1, M=1)

Jadi apabali algoritma ini diasumsikan kelas-kelas bernomor lebih rendah baru akan di gunakan kembali dalam relatif jangka waktu lama.

Intinya algoritma ini mudah dipahami dan dikembangkan karena sangat efisien walaupun tak banyak langkah dalam pemilihan page dan kelemahannya juga tidak optimal tapi dalam kondisi normal yang memadai.

4. Pengertian tentang Algoritma page FIFO (First In First Out)

Inti dari algoritma ini adalah simple / paling sederhana karena prinsipnya sama seperti prinsip antrian tak berprioritas. Page yang masuk terlebih dahulu maka yaitu yang akan keluar duluan juga. Untuk algoritma ini menggunakan structure data stack. Jadi kerjanya yaitu dimana kalau tidak ada frame yang kosong saat terjadi page fault maka korban yang dipilih adalah frame dengan stack paling bawah seperti hal nya halaman yang sudah lama tersimpan didalam memory maka dari itu algoritma ini juga bisa memindahkan page yang sering digunakan.

Utamanya algoritma ini di anggap cukup mengatasi pergantian page sampai pada tahun 70-an, pada saat itu juga Belady menemukan keganjalan pada algoritma ini dan dikenal dengan anomali Belady. Anomali Belady itu sendiri ialah keadaan dimana page fault rate meningkat seiring dengan pertambahannya jumlah frame.

5. Pengertian tentang 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 .

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.

6. Pengertian tentang Algoritma page LRU (Least Recently Used)

Dikarenakan algoritma optimal sangat sulit dalam pengimplementasiannya, maka dibuatlah algoritma lain yang performance-nya mendekati algoritma optimal dengan sedikit cost yang lebih besar. Sama seperti algoritma optimal, algoritma LRU tidak mengalami anomali Belady.