B.Sistem Paging
Sistem paging mengimplementasikan ruang alamat besar pada
memori kecil menggunakan index register, base register,
dan segment register.
Gambar. Penerjemah Page
Alamat Maya
Alamat
yang dihasilkan perhitungan menggunakan index
register, base register, dan
segment register.
Alamat Nyata
Alamat
di memori fisik.
Page
Unit
terkecil pada ruang alamat maya (virtual
address space).
Page Frame
Unit
terkecil pada ruang alamat fisik (real
address space).
Page Fault
Exception untuk permintaan alokasi
“page” ke memori.
Memory Management Unit (MMU)
Kumpulan
chip yang memetakan alamat maya ke alamat fisik.
Rutinitas
yang dilakukan dalam pemindahan halaman antara lain:
1.Mencari lokasi dari
halaman yang diinginkan pada disk.
2.Mencari frame yang
kosong:
a.Jika ada, maka gunakan frame tersebut.
b.Jika tidak ada, maka tentukan frame yang
tidak sedang
dipakai atau yang tidak akandigunakan dalam jangka waktu lama,
lalu kosongkan frame tersebut. Gunakan algoritma
pemindahan halaman
untuk menentukan frame yang akan
dikosongkan. Usahakan agar tidak
menggunakan frame yang
akan digunakan dalam waktu dekat. Jika terpaksa, maka
sebaiknya segera masukkan kembali frame tersebut agar
tidak terjadi overhead.
c.Tulis
halaman yang dipilih ke disk, ubah tabel halaman dan
tabel frame.
3.Membaca halaman yg diinginkan ke dalam frame
kosong yg baru.
4.Mengulangi proses pengguna dari awal.
1.Memory Management Unit
(MMU)
Berfungsi Pemetaan memori maya ke
memori fisik dan
menerbitkan exception adanya
page fault yang melewatkan
ke sisitem
operasi yang menanganinya. Pada dasarnya MMU
terdiri dari tabel halaman
yang merupakan sebuah rangkaian
array dari masukan-masukan (entries)
yang mempunyai indeks
berupa nomor halaman (p). Setiap masukan terdiri
dari flags
(contohnya bit sahih dan nomor frame). Alamat fisik
dibentuk
dengan menggabungkan nomor frame dengan ofset,
yaitu bit paling rendah dari alamat logis.
Pemetaan :
a.Nomor page maya
digunakan sebagai indeks ke
tabel page untuk menemukan isian page maya.
b.Dari isian tabel page
dapat diketahui, apakah
page dipetakan ke memori fisik (dengan memeriksa
presen/absent bit).
c.Apabila alamat terdapat
di memori fisik maka isian
tabel page memuat nomor page frame. Nomor page
frame
di tabel page dikopi sebagai bit-bit berorder tinggi
di register alamat fisik
dan ditambah offset di alamat maya.
d.Bila alamat tidak ada di
memori fisik maka MMU
menerbitkan page fault.
Skema Pemetaan
Misalkan:Ruang alamat maya adalah V = {0,1, … ,
v-1}
Ruang alamat fisik adalah M = {0,1, …, m-1}
Umumnya:ruang alamat maya > ruang alamat fisik (v > m)
MMU
melakukan mekanisme translasi alamat
mengasosiasikan alamat maya ke
alamat
fisik. MMU merealisasikan fungsi f : V -> M, yaitu :
f
(x) = {r, jika item x terdapat di memori fisik dengan lokasi d r}
{page fault jika item x tidak terdapat pada memori fisik}.
Skenario Pemetaan:
Contoh
instruksi : MOV REG, 0x08
1.Alamat maya 8 dikirim ke
MMU
2.MMU mengetahui alamat 8
di page 0 (page 0
memuat alamat maya 0-4095)
3.Dari tabel, page 0
dipetakan ke frame 7
(page 7 adalah alamat fisik 28672 32768)
4.MMU mentransformasikan
alamat 8 sebagai
(28672+8=28680)
5.MMU mengeluarkan alamat
28680 ke bus.
Implementasi Pemetaan:
Komponen
MMU, yaitu :
a.Register Alamat Maya
-Menyimpan
alamat maya yang diacu
-Nilai
di register alamat maya dibagi dua :
1.Bit
berorder tinggi menyatakan nomor page maya
2.Bit-bit
sisa adalah offset alamat maya
b.Tabel Page
Tiap
elemen tabel berisi informasi :
1.Present/absent
bit
(bernilai
1 jika page di memori fisik, bernilai
0 jika tidak).
2.Nomor
page frame
Berisi
nomor page frame dimana page berada
c.Register Alamat Fisik
Menyimpan
alamat fisik yang disinyalkan ke bus.
Nilai
di register alamat fisik dibagi menjadi :
1.Bit
berorder tinggi menyatakan nomor page frame
2.Bit-bit
sisa adalah offset alamat frame.
PENGGANTIAN PAGE
a.Algoritma penggantian
page acak (Random)
1.Setiap terjadi page
fault, penggantian page dipilih
secara acak.
2.Tidak memakai informasi
apapun untuk menentukan
page yang akan diganti.
3.Semua page di memori
utama dianggap memiliki
bobot yang sama.
4.Dapat memilih sembarang
page termasuk page yang
sedang diacu.
b.Algoritma penggantian
page optimal
1.Memilih page yang
berpeluang dipakai kembali
di masa datang yang paling kecil. (Memprediksi/melihat
page berikutnya yang tidak dipakai)
2.Strategi ini
menghasilkan jumlah page fault sedikit
tapi tidak mungkin diterapkan.
Penjelasan :
a.Algoritma dengan 7 page
sebagai string pengacuan
(page 5 dan 6 dinyatakan invalid / memiliki
present/absent bit 0).
b.Memiliki 3 page frame
dan page fault.
c.Page 7 diacu/ditempatkan
di frame : Fault (F)
d.Page 0 diacu/ditempatkan
di frame : Fault (F)
e.Page 1 diacu/ditempatkan
di frame : Fault (F)
f.Page 2 diacu/ditempatkan
di frame dgn mengganti page 7:(F)
Page 7 diganti karena page berikutnya adalah
page 0 dan
page 3, dan page 7 hanya sedikit (1x) pada antrian page
berikutnya
berikutnya.
g.Page 0 diacu/ditempatkan
di frame tanpa mengganti page.
h.Page 3 diacu/ditempatkan
di frame dgn mengganti page 1:(F)
i.Page 0 diacu/ditempatkan
di frame tanpa mengganti page.
j.Page 4 diacu/ditempatkan
di frame dgn mengganti page 0:(F)
Page 0 diganti karena page berikutnya adalah
page 2 dan page 3.
k.Page 2 diacu/ditempatkan
di frame tanpa mengganti page.
l.Page 3 diacu/ditempatkan
di frame tanpa mengganti page.
m.Page 0 diacu/ditempatkan
di frame dgn mengganti page 4:(F)
n.Page 4 diganti karena page berikutnya adalah page
3 dan page 2,
bahkan page 4 sudah tidak dipakai kembali.
o.Page 3 dan page 2 diacu/ditempatkan di frame tanpa
mengganti page.
p.Page 1 diacu/ditempatkan
di frame dgn mengganti page 3:(F)
dan
seterusnya…hingga urutan page selesai.
c.Algoritma penggantian page
NRU
Page
diberi dua bit mencatat status page :
- Bit
R (referenced) menyatakan page sedang diacu
Bit
R = 0 , page sedang diacu
Bit
R = 1, page tidak sedang diacu
- Bit
M (Modified) menyatakan page telah dimodifikasi
Bit
M = 0 , page belum dimodifikasi
Bit
M = 1, page telah dimodifikasi
d.Algoritma penggantian
page FIFO
Bila
terjadi page fault, page elemen terdepan diganti dan
page baru ditambahkan di
bagian belakang senarai.
Penjelasan
:
Ø Page 7 diacu/ditempatkan
di frame : Fault (F)
Ø Page 0 diacu/ditempatkan
di frame : Fault (F)
Ø Page 1 diacu/ditempatkan
di frame : Fault (F)
Ø Page 2 diacu/ditempatkan
di frame dengan mengganti
page terdepan dalam senarai yaitu page 7 : Fault (F)
Ø Page 0 diacu/ditempatkan
di frame tanpa mengganti
page.
Ø Page 3 diacu/ditempatkan
di frame dengan mengganti
page terdepan setelah page 7 dalam senarai yaitu
page
0 : Fault (F)
Ø Page 0 diacu/ditempatkan
di frame dengan mengganti
page terdepan setelah page 0 dalam senarai yaitu
page
1 : Fault (F)
Ø Page 4 diacu/ditempatkan
di frame dengan mengganti
page terdepan setelah page 1 dalam senarai yaitu
page
2 : Fault (F)
Ø Page 2 diacu/ditempatkan
di frame dengan mengganti
page terdepan setelah page 2 dalam senarai yaitu
page
3 : Fault (F) Page O setelah page 2 tidak
diperiksa karena
tidak fault
Ø Page 3 diacu/ditempatkan
di frame dengan
mengganti page terdepan setelah page 3 dalam
senarai yaitu page
0 : Fault (F)
Ø Page 0 diacu/ditempatkan
di frame dengan
mengganti page terdepan setelah page 0 dalam
senarai yaitu page
4 : Fault (F)
Ø Page 3 dan page 2
diacu/ditempatkan di frame
tanpa mengganti page.
Ø Page 1 diacu/ditempatkan
di frame dengan
mengganti page terdepan setelah page 4 dalam
senarai yaitu page
2 : Fault (F).
Ø Page 2 diacu/ditempatkan
di frame dengan
mengganti page terdepan setelah page 2 dalam
senarai yaitu page
3 : Fault (F).
Ø dan seterusnya… hingga
senarai selesai.
e.Algoritma penggantian
page modifikasi FIFO
1)Algoritma penggantian
page kesempatan kedua
2)Algoritma penggantian
clock page
f.Algoritma penggantian
page LRU
Beberapa
instruksi terakhir dari page, kemungkinan masih dipakai. Jika terjadi page
fault, maka algoritma mengganti page yang paling lama tidak digunakan.
Penjelasan
:
Ø Page 7 diacu/ditempatkan
di frame : Fault (F)
Ø Page 0 diacu/ditempatkan
di frame : Fault (F)
Ø Page 1 diacu/ditempatkan
di frame : Fault (F)
Ø Page 2 diacu/ditempatkan
di frame dengan
mengganti page terdepan dalam senarai yaitu
page 7 : Fault (F).
Ø Page 0 diacu/ditempatkan
di frame tanpa
mengganti page.
Ø Page 3 diacu/ditempatkan
di frame dengan
mengganti page yang tidak digunakan pada
instruksi sebelumnya
yaitu page 1 : Fault (F).
Page 0 dan 2 merupakan instruksi sebelumnya
yang
masih dipakai.
Ø Page 0 diacu/ditempatkan
di frame tanpa
mengganti page.
Ø Page 4 diacu/ditempatkan
di frame dengan
mengganti page yang tidak digunakan pada
instruksi sebelumnya
yaitu page 2 : Fault (F)
Page 0 dan 3 merupakan instruksi sebelumnya
yang
masih dipakai.
Ø Page 2 diacu/ditempatkan
di frame dengan
mengganti page yang tidak digunakan pada
instruksi sebelumnya
yaitu page 3 : Fault (F).
Page O dan 4 merupakan instruksi sebelumnya
yang
masih dipakai.
Ø Page 3 diacu/ditempatkan
di frame dengan
mengganti page 0: Fault (F) Page 2 dan 4
merupakan instruksi sebelumnya yg
masih dipakai.
Ø Page 0 diacu/ditempatkan
di frame dengan
mengganti page 4: Fault (F)
Page
2 dan 3 merupakan instruksi sebelumnya
yang masih dipakai
Ø Page 3 dan page 2
diacu/ditempatkan di frame
tanpa mengganti page.
Ø Page 1 diacu/ditempatkan
di frame dengan
mengganti page 0: Fault (F)
Page
2 dan 3 merupakan instruksi sebelumnya
yang masih dipakai
Ø dan seterusnya… hingga
senarai selesai.
3. Masalah Utama Sistem
Paging
1.Working set model
Prinsip Lokalitas
Proses-proses
cenderung mengacu penyimpanan
secara tak seragam, mempunyai pola-pola sangat
setempat.
a)Lokalitas berdasarkan
waktu
Proses
cenderung terkonsentrasi acuannya ke satu
interval waktu eksekusi yang dekat.
b)Lokalitas berdasarkan
ruang
Proses
cenderung terkonsentrasi acuannya ke satu
kelompok data yang berdekatan.
2.Working Set of Program
Behavior
Kumpulan
page proses yang secara aktif diacu yang
terlokalisasi pada waktu itu dan harus
dijaga berada
di memori utama. Perpindahan program dari satu
lokalitas ke lokalitas lain saat dieksekusi.
3.Pre paging
Teknik
memuatkan page-page lebih dulu
sebelum proses berjalan.
4.Demand Paging
Teknik
yang segera memuatkan page-page
begitu page dibutuhkan.
a.Kebijaksanaan
penggantian lokal vs global
1)Penggantian lokal yaitu
page yang dipilah untuk
diganti hanya pada partisi dimana proses diletakkan.
2)Penggantian global yaitu
page yang dipilah untuk
diganti adalah tempat kosong dengan tidak
mempedulikan
partisi proses.
b.Frekuensi page fault
>Sistem operasi
mendefinisikan frekuensi page fault
kritis sistem (atau per proses)
>Sistem operasi mengukur
waktu proses maya dan
menyimpan waktu page fault mutakhir di PCB proses
>Ketika page fault
terjadi, sistem operasi bertindak :
-Jika
page fault terakhir terjadi kurang dari
T=1/P ms detik yang lalu, proses beroperasi di atas
ambang maka page frame baru ditambahkan.
-Selain
itu, berarti proses beroperasi di bawah ambang
PFF, maka page frame page bit
R=0 dan W=0
dibebaskan untuk alokasi wage baru proses lain.
c.Ukuran page
v Ukuran page ditentukan
perancang sistem operasi.
v Ukuran page harus
ditentukan agar sistem
berperilaku optimal.
v Penentuan ukuran page
memerlukan penilaian
dan pemahaman mendalam tentang perangakat keras,
perangkat
lunak, dan aplikasi sistem.
v Ukuran page lebih kecil
berarti jumlah page dan
page frame lebih banyak sehingga memerlukan
tabel page
lebih besar.
v Ukuran page besar
berarti sejumlah informasi yang
tidak diacu juga dimasukkan ke memori utama
sehingga terjadi fragmentasi internal yang tinggi.
v Transfer
masukan/keluaran relatif sangat mengkonsumsi
waktu sehingga perlu meminimumkan
jumlah transfer
masukan/keluaran saat program berjalan.
v Program cenderung
mengikuti prinsip lokalitas
yang cenderung berukuran kecil.
4.Masalah Implementasi
Sistem Paging
a.Back up instruksi yang
terakhir dijalankan sebelum
terjadi page fault.
b.Buffer perangkat
masukan/keluaran
(penguncian page di memory).
c.Page yang dipakai
bersama.
d.Backing store.
e.Paging daemon.
f.Pananganan
page fault.
Sumber: Diolah dari berbagai sumber
>>>>>TERIMAKASIH<<<<<<
