VIRTUAL MEMORY

Algoritma Penggantian Halaman
Apa sih algoritma penggantian halaman??

Sekilas kita menganggapnya adanya kesalahan/ error pada suatu halaman, akan tetapi bukan itu maksud dari algorima halaman. Algoritma halaman adalah suatu penggantian halaman jika terjadi page fault, page fault di sini bukan adanya error/ kesalahan yang fatal, namun page fault ini terjadi bila halaman yang ingin di akses tidak ada di memori utama sehingga terjadi-lah penggantian halaman.

Untuk prinsip dari penggantian halaman, diantaranya:

• Proses meminta halaman yang diinginkan.
• Tidak ada halaman di memori utama
• Restart proses
• Update tabel halaman dan tabel memori

Pada umumnya semakin banyak memori semakin banyak pula frame, semakin banyak frame semakin banyak pula halaman yang masuk ke memori sehingga page fault rate menurun.
Disini ada beberapa algorima pada sebuah memori:
--> Algoritma Penggantian Page Acak
sebuah algoritma dimana jika terrjadi page fault akan mengganti halaman secara acak, karena semua halaman yang berada pada memori utama mempunyai nilai yang sama, hingga halaman yang sedang diacu pun bisa di akses sehingga menimbulkan jumlah page fault yang tinggi.
--> Algoritma Penggantian Page Optimal
Algoritma yang paling optimal. Prinsip dari algorima penggantian page optimal adalah mengganti halaman yang tidak terpakai lagi dengan jangka waktu lama, sehingga page fault yang terjadi berkurang. Algoritma ini algoritma paling rendah dari page fault -nya dari semua kasus. akan tetapi keoptimalan algoritma ini susah untuk di terapkan. dan algoritma ini juga sitem tidak dapat mengetahui halaman-halaman mana saja yang akan digunakan. pendekatan ini bisa 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 mengumpulkan dan memakai informasi untuk menentukan page yang diganti sehingga mendekati optimal.

--> Algoritma Penggantian Page NRU

Algoritma penggantian page NRU (Not Recently Used):

Pada setiap page diberi status bit R (Referenced) dan M (Modified). bit bernilai 0 jika page belum di referensi/ dimodifikasi, dan akan bernilai 1 jika halaman tersebut telah di referensi/ dimodifikasi. Untuk nilai desimalnya terdapat 4 kelas, diantaranya:

• 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) 

--> Algoritma FIFO (First In First Out)

Algoritma ini merupakan algoritma sederhana, seperti algoritma antrian. Jadi suatu halaman yang lebih dahulu masuk maka lebih dahulu juga keluarnya.  algoritma ini menggunakan struktur data stack. algoritma ini dapat memindahkan halaman yang sering digunakan, bisa juga halaman tersebut berada terus pada memori karena selalu digunakan.

--> Algoritma Penggantian Page Modifikasi FIFO

Algoritma penggantian page modifikasi FIFO ini mencari suatu halaman yang berada paling lama di memori, tetapi berada pada memori itu tidak terpakai. Misalkan sebuah halaman dipakai (direferensi) bit R diset, jika sistem menemukan bahwa bit R halaman yang paling lama terset maka halaman tersebut tidak jadi dikeluarkan tetapi bakal di reset.