Tujuan Pembelajaran
Memahami pengalamatan dengan menggunakan paging
Paging
Paging ⇒ mekanisme yang memungkinkan proses user ditempatkan pada memori secara tidak berurutan. Paging diimplementasikan dengan membagi : - Memori fisik menjadi blok-blok dengan besaran tetap ⇒ Frame - Memori logika menjadi blok-blok dengan besaran yang sama ⇒ Page Karakteristik Paging : - 1 proses = n blok - Ukuran frame & page tetap
Ilustrasi Penempatan Proses
Ilustrasi Penempatan Proses
Page table untuk setiap proses
Skema Penerjemahan Alamat
Alamat yang dihasilkan CPU dibagi menjadi dua -
-
Page number (p) – digunakan sebagai indeks dalam page table yang berisikan alamat awal (base address) frame memori fisik. Page offset (d) – dikombinasikan dengan alamat awal memori (base address) untuk mendapatkan alamat physical memory. page number p m-n
-
page offset d n
Ukuran ruang alamat logika adalah 2m dan ukuran page adalah 2n
Latihan
Diketahui : ukuran page = 1024byte = 210 alamat memory = 1502 = 0000010111011110 ruang alamat memory = 16 bit Tentukan nomor page dan nomor offset!
Latihan
Diketahui ukuran fisik memory=1024MB, ukuran frame 4096 byte. Berapa jumlah page table, jika besar proses user 24577 byte? A. 249 B. 251 C. 250 D. 6 E. 7
Paging
Paging dengan ukuran page 4 byte
frame 0 frame 1
frame 2
Paging
Ukuran page dan frame didefinisikan oleh hardware. Ukuran page umumnya 2i dengan variasi besar tiap page antara 512 byte hingga 16MB, tergantung dari arsitektur mesin.
Contoh Paging 0 1 2 3
Alamat logika 0 = page 0, offset 0 Alamat fisik = 20 (=((5x4)+0) Alamat logika 3 = page 0, offset 3 Alamat fisik = 23 (=((5x4)+3) Alamat logika 4 = page 1, offset 0 Alamat fisik = 24 (=((6x4)+0) Alamat logika 13 = page 3, offset 1 Alamat fisik = 20 (=((2x4)+1)
Ukuran memori fisik 32 byte dan ukuran page 4 byte
Paging
Kelemahan paging ⇒ Fragmentasi Internal - Proses
A = 72.766 bytes - Page size=2.048 - Page yang dibutuhkan : (Process A / Page size)=(72766/2048)=35, 53 (2048*35)=71680 ; 72766 – 71680= 1086 Proses A butuh 35 page + 1086 byte n pages + 1 byte n + 1 Frame Prosess A butuh 36 Page
Paging
Satu page proses membutuhkan satu frame n page proses membutuhkan n frame Sistem operasi mempunyai frame table untuk menyimpan informasi frame memori Satu entri frame table menyimpan informasi satu entri frame fisik. Informasi yang disimpan : - Frame fisik tersebut kosong atau terisi - Jika frame terisi, page/proses mana yang menempati frame tersebut
Alokasi Page Keterangan : Sebuah proses mempunyai 4 page. 4 page membutuhkan 4 frame
Sebelum alokasi
Setelah alokasi
Dukungan Hardware
Page table dapat disimpan dalam register atau memori. Jika terlalu besar, page table disimpan di memori. Page-table base register (PTBR) merujuk ke page table yang ada dimemory PTLR (Page-Table Length Register) ⇒ register yang menyimpan panjang page table. PTLR dibandingkan dengan alamat logika suatu proses untuk keperluan validasi alamat. Berapa kali akses memori untuk setiap alamat? - Akses memori membutuhkan dua kali akses memori, yaitu akses ke page table dan akses ke frame di memori
PTBR dan PTLR
Page Table dengan TLB
Agar dapat sekali akses, gunakan cache hadware (associative memory) ⇒ Translation Look-aside Buffers (TLBs) Page #
Frame #
pemetaan alamat logika (p, d) Jika p berada dalam associative register, ambil frame #
Jika tidak maka ambil frame # dari page table dalam memory
Page Table dengan TLB
Umumnya jumlah entry dalam TLB berkisar antara 64 hingga 1,024 byte Pergantian nilai pada entry TLB dapat menggunakan LRU maupun random Beberapa TLB menyimpan address-space identifiers (ASIDs) pada setiap entry. ASIDs digunakan untuk memberikan proteksi terhadap ruang alamat proses. - ASIDs setiap proses berbeda - Tanpa ASIDs, setiap kali proses yang berbeda akan dieksekusi, entri pada TLB harus dihapus agar tidak terjadi kesalahan translasi alamat.
TLB hit dan TLB Miss
TLB Hit → page number pada entri TLB ditemukan TLB Miss - Page
number pada TLB tidak ditemukan - ASIDs milik proses tidak sesuai dengan ASIDs pada entri TLB
Page Table dengan TLB
Effective Access Time
Hit ratio – persentase sebuah nomor page ditemukan dalam TLB Effective Access Time (EAT) TLB EAT=(AT+AM) α + (AT+AM+AP)(1-α) AT=Akses keTLB; AM=Akses Ke Memori Fisik; AP=akses ke Page Table; α=Hit ratio Misalnya: - Akses ke TLB membutuhkan waktu 20 ns - Akses ke page table = 100 ns - Akses ke memory = 100 ns - Hit ratio = α = 80% - EAT= (20+100) α +(20+100+100)(1-α) - EAT= (120*0.8)+(220*0.2)=140ns
Page Table Entry
Satu entri page table terdiri dari beberapa bit untuk: - Page Frame Number - Present/Absent bit (V) : Bit = 0 → invalid, page tidak ada di memory (page fault) Bit = 1 → valid, page berada di memory - Protection bit (Prot) Bit = 0 → Read/Write Page Bit = 1 → Read Only Page - Modified bit (M) Bit= 0 → page tidak dimodifikasi Bit= 1 → page sudah dimodifikasi - Referenced bit (R) Bit= 0 → page tidak digunakan Bit= 1 → page sedang digunakan (direferensi)
Bit Valid (v) or Invalid (i) Valid ⇒ page 0,1,2,3,4,5 Invalid
⇒ page 6,7
Program menempati alamat 00000-10468 (fragmentasi internal) Akses valid 00000 – 12287
Page yang digunakan bersama (Shared Pages)
Shared code
Kode (read-only) digunakan bersama oleh lebih dari satu proses. Contohnya: aplikasi editor teks, compiler, windows system Eksekusi dengan private code -
-
1 user
⇒150 kb (program) + 50 kb (data) ⇒ 200kb memory
-
20 user
⇒ 200kb x 20 =4000Kb
Eksekusi dengan shared code -
1 user
⇒150 kb (program) + 50 kb (data)
⇒ 200kb memory 20 user ⇒ 150kb + (50kb x 20) = 1150Kb
Shared Pages
Ketentuan shared code: - Kode
harus berada di lokasi yang sama pada ruang alamat fisik - kode harus read only (reentrant code)
Shared Pages
Latihan
Sistem memori utama (fisik) mempunyai kapasitas 256 MB (228). Ukuran pagenya 64 byte - Berapa jumlah framenya? - Jika program A butuh 645 byte, berapa page yang dibutuhkan - Berdasarkan tabel dibawah ini, berapa alamat fisik dari alamat logika : 30, 234, 377