Algoritma penggantian page acak
Page yang ditujukan untuk membut slot baru yang di tentukan dengan cara acak tanpa ada criteria-kriteria khusus. Pada algoritma page acak terdapat kemungkinan terjadinya proses diberhentikan sewaktu-waktu dan jelas merugikan.
Algoritma penggantian page optimal
Algoritm ini menjadikan page baru terpakai untuk digantikan oleh string acuan tertentu.
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 penggantian page fifo
Algoritma ini berkompeten memindahkan page yang berada dimemori yang banyak digunakan dfengan jangka waktu yang lumayan lama. namun mengeluarkan terlebih dahulu page uyang pertama masuk
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 penggantian modifikasi fage fifo
Mencari page penghuni lama di memori yang sudak tidak dilirik lagi. 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
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 URL
Page-page yang dipakai di instruksi-instruksi terakhir nantinya akan dipakai kembali, tapi kalau dalam waktu terlalu lama tetap tak dapat digunakan. Tetapi jika terjadi 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
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:
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.
Tidak ada komentar:
Posting Komentar