Organisasi Sistem Komputer
Bagian 11 Virtual Memory
Sekolah Teknik Elektro dan Informatika – ITB 2009 1
Pembahasan u gs virtual tua memory e oy Fungsi Penerjemah (translasi) alamat pada virtual memoryy Mempercepat translasi dengan TLB Sistem memori sederhana
2
Fungsi Virtual Memory (VM) Virtual Memory (VM) memiliki tiga fungsi penting : 1 Sebagai 1. S b i perangkat k cache h
VM memanfaatkan memori utama (DRAM) lebih efisien dengan memperlakukannya sebagai cache alamat yang tersimpan dalam disk Memori utama hanya menyimpan data yang aktif VM melakukan transfer data antara disk dan memori seperlunya saja
2. Sebagai perangkat manajemen memori
VM menyederhanakan manajemem memori dengan melakukan teknik pengalamatan yang seragam untuk setiap proses
Pengalamatan disk, memori, cache dilakukan secara uniform
3. Sebagai perangkat untuk memproteksi memori
VM melindungi alokasi alamat setiap proses terhadap gangguan
Suatu proses tidak dapat diganggu oleh proses lain. Proses tidak dapat mengakses informasi yang bukan hak-nya Setiap alokasi alamat memiliki hak yang berbeda berbeda-beda beda
3
Pengalamatan secara Fisik Memori Alamat fisik
0: 1:
CPU
Disebut ‘physical addressing’ add essing’ Alamat yang dihasilkan CPU menunjukkan j langsung lokasi byte dalam memori secara fisik Digunakan pada :
M-1:
mesin Cray PC generasi pertama sistem embedded pada umumnya
4
Sistem dengan Virtual Memory Penerjemahan/translasi alamat (address translation) : berbentuk perangkat keras yang mengkonversi alamat virtual menjadi alamat fisik menggunakan page table (look-up table), dikendalikan oleh sistem operasi
0: 1:
Page Table Alamat virtual
0: 1:
Memori
Alamat fisik
CPU
Digunakan pada server, workstation dan PC modern d
P-1:
M-1: Disk 5
Address Space Address space adalah kumpulan alamat-alamat yang letaknya berurutan {0, 1, 2, … }
Pada sistem dengan virtual memory, CPU menghasilkan alamat virtual dari address space N = 2n alamat, disebut virtual address space p {0, 1, 2, … , N-1}
Sistem jjuga g memiliki physical p y address space p yang y g merupakan memori fisik sebesar M byte {0, 1, 2, … , M-1}
6
1. VM : Perangkat Caching Ukuran seluruh address space sangat besar : bit : dapat mengalamati ~4,000,000,000 4,000,000,000 (4 milyar) byte Bus alamat 32 32-bit Bus alamat 64-bit : ~16,000,000,000,000,000,000 (16 quintilliun) byte
Harga Harddisk kira-kira 300 kali lebih murah dari DRAM 80 GB DRAM: 80 GB harddisk:
~ $33,000 $33 000 ~ $110
Agar data berukuran besar dapat diakses secara murah, maka data tersebut harus disimpan dalam disk, disk sementara data yang sedang aktif saja yang disimpan dalam DRAM/SRAM 1GB: ~$200
80 GB: ~$110
4 MB: ~$500 SRAM
DRAM
Disk 7
DRAM vs SRAM sebagai Cache DRAM vs. disk lebih ekstrim dari SRAM vs. DRAM Waktu akses : DRAM ~10X lebih lambat SRAM Disk ~100,000X lebih lambat DRAM
Pentingnya spatial locality: Byte pertama ~100,000X lebih lambat dari byte yang berurutan pada disk
Pertimbangan desain cache menggunakan DRAM harus memperhatikan ‘cost’ yang timbul akibat miss
SRAM
DRAM
Disk
8
SRAM Cache Tag disimpan bersama baris cache Memetakan Memet k n d darii blok cache he ke blok memori memo i Dari bentuk cached ke uncached
Tag ag tidak da ada bila b a blok b o tidak da ada dalam da a cache a e “Cache”
Object Name X
= X?
Tag
Data
0:
D
243
1 1:
X • • • J
17 • • • 105
N-1:
9
DRAM Cache Setiap page yang dialokasikan oleh virtual memory memiliki entry pada page p p g table Memetakan virtual page ke physical page Dari bentuk uncached menjadi bentuk cached
Page table entry tetap ada walaupun page belum ada di memori Menunjukkan alamat pada disk
Page Table
“Cache”
Lokasi
Data
Object Name
D:
0
0:
243
X
J:
On Disk
1:
X:
• • • 1
N-1:
17 • • • 105 10
DRAM Cache Jika suatu obyek berada dalam disk, bukan di memori, maka : Page table entry memperlihatkan alamat virtual tidak ada di memori OS exception handler melakukan pemindahan data dari disk ke memori
Sebelum fault
Setelah fault
Memori
Memori
Page Table Alamat virtual
Page Table
Alamat fisik
CPU
Alamat virtual
Alamat fisik
CPU
Disk
Disk 11
2. VM : Manajemen Memori Beberapa proses dapat tersimpan secara bersamaan dalam memori Masalah akan timbul bila dua proses mengakses alamat yang sama Konflik alamat tersebut harus diatasi kernel virtual memory stack
%esp
memory invisible to user code
Memory mapped region forshared libraries
th “brk” the “b k” ptr t runtime heap (via malloc)
0
uninitialized data (.bss) initialized data (.data) program text (.text) forbidden
Peta memori Linux/X86 12
Solusi : Pisahkan Alamat Virtual Ruang alamat virtual dan fisik dibagi menjadi beberapa blok berukuran sama Block disebut “pages” (virtual dan fisik)
Setiap proses memiliki ruang alamat virtual sendiri Sistem operasi mengendalikan konversi virtual pages ke memori fisik 0
Ruang alamat l t virtual proses 1:
Translasi alamat
0 VP 1 VP 2
PP 2
...
N-1 PP 7
Ruang alamat virtual proses 2:
Ruang alamat fisik (DRAM)
0
VP 1 VP 2
PP 10
...
N-1
((e.g., read/only d/ l library code)
M-1 13
3. VM : Proteksi Memori Page table entry berisi informasi tentang hak akses Proteksi dilakukan secara hardware Page Table Read? Write? VP 0: Yes No
Proses i:
Physical Addr PP 9
VP 1: Yes
Yes
PP 4
No
No
XXXXXXX
• • •
• • •
• • •
VP 2:
Read? Write? Yes VP 0: Yes
Proses j:
Memori 0: 1:
Physical Addr PP 6
VP 1: Yes
No
PP 9
VP 2:
No
No
XXXXXXX
• • •
• • •
• • •
N-1:
14
Translasi Alamat (Add (Address T Translation) l ti ) Virtual Memory
15
Translasi Alamat : HIT
Prosesor
Alamat virtual
Mekanisme translasi Alamat Alamat fisik (hardware)
Memori utama
Bagian dari on-chip memory Management unit (MMU)
16
Translasi Alamat : MISS page fault fault handler
Prosesor
Alamat virtual
Mekanisme M k i translasi Alamat (hardware)
∅
Memori utama
Disk
Al Alamat t fisik fi ik Bagian dari on-chip memory Management unit (MMU)
jika terjadi miss, sistem operasi melakukan transfer data
17
Translasi Alamat VM Parameters g size (byte) ( y ) P = 2p = p page N = 2n = batas alamat virtual M = 2m = batas alamat fisik n–1 1
p p–1 1 virtual page number
0 Alamat virtual
page offset
address translation
m–1 p p–1 physical page number page offset
0 Alamat fisik
18
Page Table Virtual Page Number
Memory resident page table (physical page Valid or disk address) 1 1 0 1 1 1 0 1 0 1
Memori fisik
Disk Storage (file swap atau File sistem biasa)
19
Operasi Page Table page table base register VPN acts as table index
if valid=0 then page not in memory
virtual address p p p–1 n–1 virtual page number (VPN) page offset
0
physical y page p g number (PPN) ( ) valid access p
m–1 p p–1 physical page number (PPN) page offset
0
physical address 20
Operasi Page Table Translasi Pisahkan page tabel per proses VPN membentuk indeks pada page table (menunjukkan page table entry)
Menghitung alamat fisik Page Table Entry (PTE) memberikan informasi tentang page Jika bit valid =1, maka page berada dalam memori, gunakan physical page number (PPN) untuk mengkonstruksi alamat Jika bit valid = 0, maka page berada dalam disk (page fault)
C k proteksi Cek k Cek ‘right access’ untuk menentukan akses yang diijinkan Read-only, y read-write, executyy onlyy
21
Integrasi VM dan Cache VA CPU
miss
PA Translation
Cache
Main Memory
hit data
C h diakses di k k alamat l fi ik Cache menggunakan fisik Translasi alamat dilakukan sebelum cache lookup
22
Percepat Translasi dengan TLB TLB = Translation Lookaside Buffer Berbentuk perangkat keras cache yang terletak dalam MMU Memetakan virtual page number (VPN) menjadi physical page number (PPN) Dapat menggantikan page table dalam ukuran yang lebih kecil hit PA
VA CPU
TLB Lookup miss
miss Cache
Main M i Memory
hit
Translation data 23
Translasi Alamat dengan TLB n–1 p p–1 0 virtual page number page offset
valid
.
virtual address
tag physical page number
.
TLB
.
=
TLB hit physical address tag
index
valid tag
byte offset
data
Cache
=
cache hit
data 24
Contoh Sistem Memori Sederhana
25
Pengalamatan 14-bit alamat virtual (virtual address) 12-bit alamat fisik (physical address) Page size = 64 byte = 26 13
12
11
10
9
8
7
6
5
4
VPN
10
2
1
0
VPO (Virtual Page Offset)
(Virtual Page Number) 11
3
9
8
7
6
5
4
3
2
1
PPN
PPO
(Physical Page Number)
(Physical Page Offset)
0
26
Page Table VPN
PPN
Valid
VPN
PPN
Valid
00
28
1
08
13
1
01
–
0
09
17
1
02
33
1
0A
09
1
03
02
1
0B
–
0
04
–
0
0C
–
0
05
16
1
0D
2D
1
06
–
0
0E
11
1
07
–
0
0F
0D
1
Tabel di atas hanya menampilkan 16 entry pertama (total 256 entry) 27
TLB 16 entries 4-way associative TLBT 13
12
11
10
TLBI 9
8
7
6
5
4
3
VPN
2
1
0
VPO
Set
Tag
PPN
Valid
Tag
PPN
Valid
Tag
PPN
Valid
Tag
PPN
Valid
0
03
–
0
09
0D
1
00
–
0
07
02
1
1
03
2D
1
02
–
0
04
–
0
0A
–
0
2
02
–
0
08
–
0
06
–
0
03
–
0
3
07
–
0
03
0D
1
0A
34
1
02
–
0 28
Cache 16 lines 4-byte line size Direct mapped
CI
CT 11
10
9
8
7
6
5
4
PPN
CO 3
2
1
0
PPO
Idx
Tag
Valid
B0
B1
B2
B3
Idx
Tag
Valid
B0
B1
B2
B3
0
19
1
99
11
23
11
8
24
1
3A
00
51
89
1
15
0
–
–
–
–
9
2D
0
–
–
–
–
2
1B
1
00
02
04
08
A
2D
1
93
15
DA
3B
3
36
0
–
–
–
–
B
0B
0
–
–
–
–
4
32
1
43
6D
8F
09
C
12
0
–
–
–
–
5
0D
1
36
72
F0
1D
D
16
1
04
96
34
15
6
31
0
–
–
–
–
E
13
1
83
77
1B
7
16
1
11
C2
DF
03
F
14
0
–
–
–
D3 29
–
Translasi Alamat (1) Alamat virtual 0x03D4 TLBT 13
12
11
TLBI
10
9
8
7
6
5
4
3
VPN VPN ___
2
1
0
VPO
TLBI ___ TLBT ____ TLB Hit? __ Page Fault? __ PPN: ____
Alamat fisik CI
CT 11
10
9
8
7
6
PPN Offset ___ CI___
CT ____
5
4
CO 3
2
1
0
PPO Hit? __
Byte: ____ 30
Translasi Alamat (1) Alamat virtual 0x03D4 TLBT
TLBI
13
12
11
10
9
8
7
6
5
4
0
0
0
0
1
1
1
1
0
1
3
0
VPN
2
1
0
1
0
0
VPO
VPN:0x0F TLBI:0x03 TLBT:0x03 TLB Hit?:Y Page Fault? :N PPN:0x0D
Alamat fisik CI
CT 11
10
9
8
7
6
0
0
1
1
0
1
5
0
PPN Offset:0x00
CI:0x05 CT:0x0D Hit?:Y
CO
4
3
2
1
0
1
0
1
0
0
PPO Byte:0x36 31
Translasi Alamat (2) Alamat virtual 0x0B8F TLBT 13
12
11
TLBI
10
9
8
7
6
5
4
3
VPN VPN ___
2
1
0
VPO
TLBI ___ TLBT ____ TLB Hit? __ Page Fault? __ PPN: ____
Alamat fisik CI
CT 11
10
9
8
7
6
PPN Offset ___ CI___
CT ____
5
4
CO 3
2
1
0
PPO Hit? __
Byte: ____ 32
