Sistem Operasi Komputer
Sistem Operasi Komputer Pertemuan IX – Memori Virtual
Memori Virtual • • • • • • •
Latar belakang Demand paging Unjuk kerja demand paging Page replacement Algoritma page replacement Pengalokasian frame Trashing
Universitas Kristen Maranatha -- IT Department
1
Sistem Operasi Komputer
Latar belakang • Memori virtual – Pemisahan antara memori lojik dan memori fisik dari programprogram yang dipakai user – Caching • Ruang alamat lojik dapat lebih besar daripada ruang alamat fisik • Menambah efektivitas dan utilitas CPU
– Hanya sebagian dari program yang dibutuhkan dalam memori pada saat eksekusi (penyederhanaan pengelolaan memori) – Ruang alamat dapat di-share oleh proses (security dan protection)
• Dapat diimplementasikan dengan – Demand paging – Demand segmentation
• Virtual memori memindahkan (mengcopy) isi RAM yang tidak digunakan ke dalam secondary memory (disk)
Penggunaan Kapasitas Memori
Universitas Kristen Maranatha -- IT Department
2
Sistem Operasi Komputer
Hirarki memori cache
CPU regs
Register ukuran: kecepatan: $/Mbyte: transfer:
32 B 1 ns 8B
C a c h e
8B
32 B
virtual memory
Memory
Cache
4 KB
Memory
32 KB-4MB 2 ns $125/MB 32 B
Disk
Disk Memory
1024 MB 30 ns $0.20/MB 4 KB
100 GB 8 ms $0.001/MB
Lebih besar, lambat, murah
Sistem Virtual Memori Memory 0: 1:
Page Table Virtual Addresses
0: 1:
Physical Addresses
CPU
P-1:
N-1:
Disk
Universitas Kristen Maranatha -- IT Department
3
Sistem Operasi Komputer
Memori virtual > Memori fisik
Memori virtual adalah bagian dari memori lojik dari memori fisik
Demand paging • Konsep sama dengan swapping (sistem paging) – Proses disimpan dalam memori sekunder (disk) – Jika proses akan dieksekusi, dipindahkan ke memori (lazy swapper) – Digunakan valid/invalid bit – Valid page yang diperlukan ada dalam memori utama – Invalid page yang diperlukan tidak ada dalam memori utama
• Page dibutuhkan gunakan referensi – Referensi invalid hentikan proses – Tidak ada di memori bawa ke memori
Universitas Kristen Maranatha -- IT Department
4
Sistem Operasi Komputer
Transfer page secara contiguous
Page fault (1) • Valid / invalid bit
Frame #
valid-invalid bit
1 1 1 1 0 M
0 0 0
page table
• Mula-mula diset dengan 0, untuk semua entry • Pada saat translasi, jika valid/invalid bit menunjukkan 0 page fault, dengan kata lain jika frame yang diinginkan tidak ada di memori virtual
Universitas Kristen Maranatha -- IT Department
5
Sistem Operasi Komputer
Page Fault (2) Setelah page fault
Sebelum page fault
Memory
Memory
Page Table
Page Table Virtual Addresses
Physical Addresses
Virtual Addresses
Physical Addresses
CPU
CPU
Disk
Disk
Page tidak ada di memori
Universitas Kristen Maranatha -- IT Department
6
Sistem Operasi Komputer
Mengatasi page fault 1. Mengecek tabel internal (biasa tersimpan dalam PCB) untuk menentukan bit referensi valid / invalid 2. Referensi 1. invalid stop proses 2. valid, dan page belum dikenali panggil ke memori 3. Cari frame kosong 4. Algoritma page replacement 5. Refresh tabel internal 6. Restart instruksi
Effective access time (1) • Demand paging turut menentukan kinerja sistem komputer Page Fault Rate 0 ≤ p ≤ 1.0 if p = 0 no page faults if p = 1, every reference is a fault Effective Access Time (EAT): EAT = (1 – p) x memory access time + p ( page fault overhead + [swap page out ] + [swap page in] + [restart overhead] )
• Memory access time (ma), komputer modern antara 10 – 200 nsec (1 nsec = 10-9 sec) • Jika tidak ada page fault, maka EAT sama dengan ma
Universitas Kristen Maranatha -- IT Department
7
Sistem Operasi Komputer
Effective access time (2) • Memory access time = 1 µsec = 10-3 msec • 50% page telah digunakan dan akan di-swappedout • Swap Page Time = 10 msec = 10000 µsec Maka: EAT = (1 – p) x 1 + p (15000) = 1 + 14900p (dalam µsec) EAT berbanding lurus dengan kecepatan page fault
Page Replacement (1) Virtual Page Number
Memory resident page table Valid
(physical page or disk address)
1 1 0 1 1 1 0 1 0 1
Universitas Kristen Maranatha -- IT Department
Physical Memory
Disk Storage (swap file or regular file system file)
8
Sistem Operasi Komputer
Page replacement (2)
Memori fisik penuh Page replacement
Page replacement (3)
•
•
Jika sudah tidak ada memori yang kosong, sedangkan proses membutuhkan tempat di memori untuk eksekusi page replacement Page fault dimodifikasi dengan menambahkan page replacement
Universitas Kristen Maranatha -- IT Department
9
Sistem Operasi Komputer
Algoritma Page Replacement
• • • • •
FIFO Optimal Least Recently Use (LRU) Diinginkan page fault rate yang terendah Dijalankan dengan menggunakan urutan referensi memori tertentu, dan menghitung banyaknya page fault rate
Algoritma FIFO
• Posisi page yang paling lama yang digantikan
• Cara pandang “mundur” • Muncul Belady’s Anomaly kecepatan page fault akan bertambah jika frame dalam memori virtual juga bertambah •Jumlah page fault = 15
Universitas Kristen Maranatha -- IT Department
10
Sistem Operasi Komputer
Ilustrasi FIFO – Belady’s Anomaly
Algoritma Optimal
•
Page yang tidak digunakan dalam waktu dekat akan digantikan • Cara pandang “maju” • Jumlah page fault = 9
Universitas Kristen Maranatha -- IT Department
11
Sistem Operasi Komputer
Algoritma LRU
• Menggantikan page yang “baru saja tidak dipakai”
• Gabungan FIFO dan Optimal • Stack implementation Referensi page: Page yang menggantikan diletakkan di atas Page yang sudah “lama” (baru saja tidak dipakai) ada di bawah • Jumlah page fault = 12
Pengalokasian Frame • •
• •
•
Setiap proses butuh jumlah frame minimum yang diperlukan dalam eksekusi Equal allocation – Jika disediakan 100 frame (=m) untuk 5 proses (=n), maka tiap proses, mendapat 20 page (=m / n) Proportional allocation – Mengalokasikan sesuai dengan ukuran proses Global allocation – Proses-proses boleh “berkompetisi” mengalokasikan page yang dialokasikan kepada dirinya Local allocation – Proses hanya dapat mereplace page yang dialokasikan pada dirinya – Jumlah page untuk suatu proses tetap
Universitas Kristen Maranatha -- IT Department
12
Sistem Operasi Komputer
Proportional allocation si = size of process pi S = ∑ si m = total number of pages (frames)
s ai = allocation for pi = i x m S
m = 64 s 1 = 10 s 2 = 127 10 137 127 = 137
a1 =
X 64
≈ 5
a2
X 64
≈ 59
Trashing
•
•
Terjadi jika suatu proses sibuk melakukan page replacement terusmenerus (tidak memiliki page yang cukup) dan mengabaikan pemrosesan Efek dari global allocation (“mencuri” page (frame) dari proses lain) atau jika jumlah local page melebihi kapasitas memori yang ada
Universitas Kristen Maranatha -- IT Department
13
Sistem Operasi Komputer
Linux VM process virtual memory
vm_area_struct
task_struct
mm_struct
mm
vm_end vm_start vm_prot vm_flags
pgd mmap
shared libraries
vm_next
0x40000000
vm_end vm_start vm_prot vm_flags
pgd: • page directory address vm_prot: • read/write permissions for this area vm_flags • shared with other processes or private to this process
data 0x0804a020
vm_next text vm_end vm_start vm_prot vm_flags vm_next
0x08048000 0
Linux mengorganisasikan VM sebagai koleksi “Area”
Win NT/2000: Memory Management RAM
App 1 2 GB Program Address Space
App 2
App 1
1
2
App 1 App 2
Virtual Memory Manager
2 GB Program Address Space
App 1 App 2
3
Pages
System Demand Paging 4 Disk Pagefile.sys
Universitas Kristen Maranatha -- IT Department
Virtual Memory
14
Sistem Operasi Komputer
Win 2000: Memory Management Information 1•
Total penggunaan virtual memory dari memori fisik (Total “VM” + Kernel Memory yang dipaged-kan) 2• “Limit yang disetujui” = jumlah memori fisik tersedia + ukuran total paging yang terjadi
1
1 2
Win 2000: Informasi Memori pada Proses 1•
•
“Mem Usage” = memori fisik yang digunakan proses Note: page yang dishare dihitung pada tiap proses
2•
“VM Size” = virtual memori yang tidak dishare (private)
3•
“Mem Usage” total memori yang digunakan (jumlah kolom mem.usage)
1
2
3
Universitas Kristen Maranatha -- IT Department
15
Sistem Operasi Komputer
Win: Informasi pengelolaan memori 1•
“System Cache” ukuran total memori fisik untuk page, berisi: • NtosKrnl.Exe • Drivers • File system cache 2• “Available” = jumlah memori fisik yang belum dialokasikan untuk proses
2 1
Latihan soal (1) 1. Apakah yang terjadi jika alamat lojik lebih besar dibandingkan dengan alamat fisik ? 2. Jelaskan konsep memori virtual ! 3. Apa yang akan dilakukan oleh sistem operasi jika terjadi page fault ? 4. Jelaskan konsep page replacement ! 5. Mengapa Linux menggunakan memori virtual dalam melakukan manajemen memori ?
Universitas Kristen Maranatha -- IT Department
16
Sistem Operasi Komputer
Latihan soal (2) 6. Diketahui referensi page sebagai berikut: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 Diasumsikan bahwa proses dijalankan dengan urutan referensi memori di atas. Diasumsikan juga bahwa frame mula-mula kosong. Hitunglah jumlah page fault yang terjadi, apabila diketahui jumlah frame yang tersedia adalah 3. Gunakan algoritma page replacement a) FIFO (First In First Out) b) Optimal c) LRU (Least Recently Used)
Universitas Kristen Maranatha -- IT Department
17