Pertemuan 13 Virtual Memory

Algoritma pengantian page acak

Mekanisme algoritma
Setiap terjadi page fault, page yang diganti dipilih secara acak.
Teknik ini tidak memakai informasi apapun dalam menentukan page yang diganti. Semua page di memori utama mempunyai bobot sama untuk dipilih. Teknik ini dapat memilih sembarang page, termasuk page yang sedang diacu (page yang seharusnya tidak diganti, pilihan terburuk).
Teknik ini sangat buruk, percobaan menunjukkan algoritma acak menimbulkan rate terjadinya page fault yang sangat tinggi.
Algoritma pengantian page Optimal

Algoritma ini adalah algoritma yang paling optimal sesuai namanya. Prinsip dari algoritma ini adalah mengganti halaman yang tidak akan terpakai lagi dalam waktu lama, sehingga efisiensi pergantian halaman meningkat (page fault yang terjadi berkurang) dan terbebas dari anomali Belady. Strategi ini akan menghasilkan jumlah page-fault paling sedikit. Algoritma ini memiliki page fault rate paling rendah di antara semua algoritma di semua kasus. Akan tetapi, optimal belum berarti sempurna karena algoritma ini ternyata sangat sulit untuk diterapkan. Sistem tidak dapat mengetahui halaman-halaman mana saja yang akan digunakan berikutnya. Pendekatan ini dapat dilakukan dengan simulasi. Tapi simulasi hanya spesifik untuk suatu program. Bila yang terbaik tak dimungkinkan, maka yang perlu dilakukan adalah berusaha mendekatinya. Algoritma penggantian page diusahakan kinerjanya mendekati optimal. Tiap algoritma penggantian page mengumpulkan dan memakai informasi untuk menentukan page yang diganti sehingga mendekati optimal.


Algoritma pengantian page NRU

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 pengantian 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. Dengan hanya informasi mengenai lama berada di memori, maka algoritma ini dapat memindahkan page yang sering digunakan. Boleh jadi page itu berada terus di memori karena selalu digunakan. Page itu karena mengikuti pola antrian berdasar lamanya berada di memori menjadi elemen terdepan, diganti, dan segera harus masuk kembali ke memori sehingga terjadi page fault kembali.


– Algoritma pengantian page Modifikasi FIFO






Algoritma pengantian page LRU

Ada beberapa cara untuk mengimplementasikan algoritma LRU. Tetapi, yang cukup terkenal ada 2, yaitu counter dan stack. Contoh algoritma di atas menggunakan stack.
Counter . Cara ini dilakukan dengan menggunakan counter atau logical clock. Setiap halaman memiliki nilai yang pada awalnya diinisialisasi dengan 0. Ketika mengakses ke suatu halaman baru, nilai pada clock di halaman tersebut akan bertambah 1. Semakin sering halaman itu diakses, semakin besar pula nilai counter-nya dan sebaliknya. Untuk melakukan hal itu dibutuhkan extra write ke memori. Selain berisi halaman-halaman yang sedang di-load, memori juga berisi tentang counter masing-masing halaman. Halaman yang diganti adalah halaman yang memiliki nilai clock terkecil, yaitu halaman yang paling jarang diakses. Kekurangan dari cara ini adalah memerlukan dukungan tambahan counter pada hardware.
Stack. Cara ini dilakukan dengan menggunakan stack yang menandakan halaman-halaman yang berada di memori. Setiap kali suatu halaman diakses, akan diletakkan di bagian paling atas stack. Apabila ada halaman yang perlu diganti, maka halaman yang berada di bagian paling bawah stack akan diganti sehingga setiap kali halaman baru diakses tidak perlu mencari kembali halaman yang akan diganti. Dibandingkan pengimplementasian dengan counter, cost untuk mengimplementasikan algoritma LRU dengan menggunakan stack akan lebih mahal karena seluruh isi stack harus di-update setiap kali mengakses halaman, sedangkan dengan counter, yang dirubah hanya counter halaman yang sedang diakses, tidak perlu mengubah counter dari semua halaman yang ada.