Algoritma – Algoritma Penggantian page
- Algoritma pengantian page acak
Page yg dikeluarkan untuk memberi tempat ke yang baru ditentukan secara acak tanpa kriteria tertentu. Pada algoritma ini terdapat kemungkinan proses yang baru berjalan bias digantikan (diberhentikan oleh proses lain) jadi sangat merugikan dan teknik ini sangat buruk, percobaan menunjukkan rate page fault yang sangat tinggi ketika menggunakan teknik ini (sangat merugikan).
- Algoritma penggantian page Optimal
Pada algoritma ini memilih page yang baru terpakai untuk digantikan oleh string acuan terbaru.
Contoh
Terdapat 12 string acuan : 2,3,2,1,5,2,4,5,3,2,5,2
Terdapat 3 Page frame, hitung page fault dengan algoritma penggantian page optimal..
$ acuan | 2 | 3 | 2 | 1 | 5 | 2 | 4 | 5 | 3 | 2 | 5 | 2 |
Page Frame-1 | 2 | 2 | 2 | 2 | 2 | 2 | 4 | 4 | 4 | 4 | 4 | 4 |
Page Frame-2 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 2 | 2 | 2 | |
Page Frame-3 | 1 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | |||
Page fault | F | F | F | F | F | F |
Fault proses tersebut = 6 Fault
- Algoritma pengantian page NRU
- Algoritma pengantian page NRU
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:
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:
R | M | Kelas | keterangan |
0 | 0 | 0 | Not referenced , not modified |
0 | 1 | 1 | Not referenced , nodified |
1 | 0 | 2 | Referenced , not modified |
1 | 1 | 3 | Referenced , modified |
Page dengan kelas terkecillah yang akan dikeluarkan.
- Algoritma pengantian page FIFO
Algoritma ini dapat memilih memindahkan page yang sering digunakan yang telah berada di memori untuk waktu yang lama. Page yang paling dulu masuk ke memori dari semua page yang ada dikeluarkan.
Contoh :
Terdapat 12 string acuan : 2,3,2,1,5,2,4,5,3,2,5,2
Terdapat 3 Page frame, hitung page fault dengan algoritma penggantian page optimal
String pengacuan | 2 | 3 | 2 | 1 | 5 | 2 | 4 | 5 | 3 | 2 | 5 | 2 | |
2 | 2 | 2 | 2 | 2 | 2 | 4 | 4 | 4 | 2 | 2 | 2 | ||
3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | |||
1 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | |||||
fault | F | F | F | F | F | F | F | 8 Fault |
Anomali pada FIFO (Belady’s Anomaly)
String pengacuan | 0 | 1 | 2 | 3 | 0 | 1 | 4 | 0 | 1 | 2 | 3 | 4 | ||
Page termuda | 0 | 1 | 2 | 3 | 0 | 1 | 4 | 4 | 4 | 2 | 3 | 3 | ||
0 | 1 | 2 | 3 | 0 | 1 | 1 | 1 | 4 | 2 | 2 | ||||
Page tertua | 0 | 1 | 2 | 3 | 0 | 0 | 0 | 1 | 4 | 4 | ||||
fault | F | F | F | F | F | F | F | F | 9 fault | |||||
(a) |
String pengacuan | 0 | 1 | 2 | 3 | 0 | 1 | 4 | 0 | 1 | 2 | 3 | 4 | ||
Page termuda | 0 | 1 | 2 | 3 | 3 | 3 | 4 | 0 | 1 | 2 | 3 | 4 | ||
0 | 1 | 2 | 2 | 2 | 3 | 4 | 0 | 1 | 2 | 3 | ||||
0 | 1 | 1 | 1 | 2 | 3 | 4 | 0 | 1 | ||||||
Page tertua | 0 | 0 | 0 | 1 | 2 | 3 | 4 | 0 | 1 | |||||
fault | F | F | F | F | F | F | F | 10 fault | ||||||
(a) |
- Algoritma pengantian page Modifikasi FIFO
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.Pada algoritma ini, daftar page bisa juga dibuat berbentuk jam (clock page replacement algorithm)
Algoritma penggantian page clock
String Pengacuan 2 3 2 1 5 2 4 5 3 2 5 2
> 2 2 2 >2* 2* 2* 2* >2* >2 >2* >2* >2*
> 3 3 3 5 5 5 5* 5 5 5* 5*
> > 1 >1 >1 4 4 3 3 3 3
Fault F F F F F F 6 Fault
Keterangan : diacu >>ditunjuk pointer
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.Pada algoritma ini, daftar page bisa juga dibuat berbentuk jam (clock page replacement algorithm)
Algoritma penggantian page clock
String Pengacuan 2 3 2 1 5 2 4 5 3 2 5 2
> 2 2 2 >2* 2* 2* 2* >2* >2 >2* >2* >2*
> 3 3 3 5 5 5 5* 5 5 5* 5*
> > 1 >1 >1 4 4 3 3 3 3
Fault F F F F F F 6 Fault
Keterangan : diacu >>ditunjuk pointer
- Algoritma penggantian page LRU
Berdasarkan observasi, page page yang digunakan pada beberapa instruksi terakhir berkemungkinan besar akan dipakai kembali nantinya. Page-page yang lama tidak digunakan akan tetap tak digunakan dalam waktu lama. Pada algoritma ini ketika terjadi page fault maka memindahkan page yang tak digunakan paling lama.
Contoh :
Terdapat 12 string acuan : 2,3,2,1,5,2,4,5,3,2,5,2
Terdapat 3 Page frame, hitung page fault dengan algoritma penggantian page optimal !
$ acuan | 2 | 3 | 2 | 1 | 5 | 2 | 4 | 5 | 3 | 2 | 5 | 2 |
Page Frame-1 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 3 | 3 | 3 | 3 |
Page Frame-2 | 3 | 3 | 3 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | |
Page Frame-3 | 1 | 1 | 1 | 4 | 4 | 4 | 2 | 2 | 2 | |||
Page fault | F | F | F | F | F | F | F |
Fault proses tersebut = 7 Fault
