TUGAS KELOMPOK SISTEM INFORMASI
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.
Prinsip
ganti halaman adalah sebagai berikut:
1. Proses
meminta halaman tertentu.
2. Jika halaman
berada di memori, tidak dilakukan ganti halaman.
3. Jika halaman
tidak berada di memori, maka:
1. Jika ada
frame kosong, maka halaman itu di-load ke dalam frame yang kosong tersebut.
2. Jika tidak
ada frame yang kosong, maka pilih halaman yang akan di-swap dengan menggunakan
algoritma ganti halaman.
4. Update tabel
halaman dan table memori.
5. Restart
proses.
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
|
6 Fault
|
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:
R
|
M
|
Kelas
|
Keterangan
|
|
0
|
0
|
0
|
not referenced,
|
not modified
|
0
|
1
|
1
|
not referenced,
|
modified
|
1
|
0
|
2
|
referenced,
|
not modified
|
1
|
1
|
3
|
referenced,
|
modified
|
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.
Algoritma Penggantian Page FIFO
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
|
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
|
2
|
|||||
Page Tertua
|
0
|
0
|
0
|
1
|
2
|
3
|
4
|
0
|
1
|
|||||
Fault
|
F
|
F
|
F
|
F
|
F
|
F
|
F
|
F
|
10 Fault
|
0 komentar: