Menganalisis Algoritma-algoritma

ALGORITMA PENGGANTIAN PAGE

Saat terjadi fault berarti harus diputuskan page frame yang harus diganti.

1.Algoritma penggantian page acak:
Page yg dikeluarkan untuk memberi tempat ke yang baru ditentukan secara acak tanpa kriteria tertentu.

2. Algoritma penggantian page optimal:
Setiap page diberi label untuk menandai berapa instruksi lagi baru dia digunakan. Page dengan label tertinggi (waktu dari sekarang sampai pemakaian berikutnya paling lama) yang akan dikeluarkan.

Algoritma Penggantian Page Optimal

3. Algoritma penggantian page NRU (not recently used):
Setiap page diberi status bit R (referenced) dan M (modified).
Bit bernilai 0 jika page belum direferensi/dimodifikasi, dan 1 jika sebaliknya. Dari nilai desimalnya didapat 4 kelas:

Page dengan kelas terkecillah yang akan dikeluarkan.

4. Algoritma penggantian page FIFO (First In First Out):
Page yang paling dulu masuk ke memori dari semua page yang ada dikeluarkan.

5. Algoritma penggantian page Modifikasi FIFO (Second Chance):
Mencari page yang berada di memori paling lama, tetapi juga tidak dipakai.
Jika sebuah page dipakai (direferensi) bit R diset. Jika sistem menemukan bahwa bit R page yang paling lama ter-set, page tersebut tidak jadi dikeluarkan, tetapi bit R-nya di-reset.

Gambar 1. (a) Page dalam urutan FIFO. (b) Daftar page setelah page fault pada waktu 20 dan bit R page A dalam keadaan set.

Pada algoritma ini, daftar page bisa juga dibuat berbentuk jam (clock page replacement algorithm)

Algoritma penggantian page clock

6. Algoritma penggantian page LRU (Least Recently Used):
Yang dikeluarkan ialah page yang sudah tidak terpakai dalam waktu paling lama.

Algoritma Penggantian Page LRU