Virtual Memory Ch. 9
Review: Demand Paging n
Asumsi pemakaian memori:
n
Problems?
n
n
SISTIM OPERASI (Operating System) IKI- 20230
n
n
n
n Fakultas Ilmu Komputer Universitas Indonesia
Slow (apalagi proses besar => transfer ke memori) Wasteful of space (process doesn’t use all of its memory)
Solusi: sebagian saja program berada di memori n
Johny Moningka (
[email protected])
Load entire process into memory. Run it. Exit.
demand paging: ambil pages yang digunakan/diakses paging: only keep frequently used pages in memory
Mekanisme: n
Semester 2000/2001
Gunakan virtual memory untuk melakukan: map address, manage replacement, manage page di disk.
OS/ JM-2001/v1.1/3
Virtual Memory
Review: VM = OS big lie
n
Background
n
n
Demand Paging Page- Replacement Algorithms
n
n
Allocation of Frames Thrashing
n n
Program execution: 10% program mempunyai 90% porsi diakses/digunakan (memori reference). Jadi, usahakan 10% program berada di memori dan sisanya di disk => kecepatan akses mendekati memori (90% reference).
# of references
n
Objektif: disk-sized memory yang secepat akses physical memory (DRAM).
Physical memory OS/ JM-2001/v1.1/2
Memory address
Disk
OS/ JM-2001/v1.1/4
1
Review: VM Mechanism
LRU: perfect
n
n
Ekstensi page table entry: extra 1 bit valid/invalid n n n
Apakah page di memori? 1 = ada, 0 = tidak ada. Jika bit == 1, translasi dan akses langsung ke memori. Jika bit == 0, menyebabkan page fault. • • • • •
What happens on page fault? OS finds a free page or replace one (which one??) Issues a disk request to read in data into that page Puts process on blocked queue, switches to other process when disk completes: set present = 1, put back on ready queue
32 :P=1 4183:P=0 177 :P=1 5721:P=0
Random: sembarang page (any page). n
n
n
n
n
LRU (least recently used): ganti page yang tidak digunakan dalam waktu yang terlama. n
Past = future? LRU = OPT.
OS/ JM-2001/v1.1/6
t=4 t=14
0xffdcd: add r1,r2,r3 0xffdd0: ld r1, 0(sp)
t=14 t=5
14
Approximation n
n
Gunakan cara sederhana tapi cepat mencari page yang tidak di reference. Tidak sempurna, tapi mewakili LRU.
OS/ JM-2001/v1.1/7
LRU: Clock algorithm n
Setiap page frame => reference bit (1 bit) n n
n
Adil: semua pages akan diganti (menjadi “tua”). Problem: bukan objektif, tidak melihat pemakaian pages.
Sulit diramalkan (dapat dijadikan benchmark => simulasi).
13
Memori: 256 MB (page: 4 KB) => 64 K entry * 1 byte stamp. Tidak ada dukungan h/w (lambat).
Hardware set pada saat diakses => OS secara periodik reset. Pages dengan bit yang di -set => recently used.
Implementasi: simpan page dalam FIFO circular list n
OS scan: page’s ref bit = 1, set to 0 & skip, otherwise replace. R=1
OPT (optimal): ganti page yang tidak akan digunakan untuk waktu terlama. n
n
n
Pro: good for avoiding worst case Con: good for avoiding best case (hasil … lumayan, cukup).
FIFO: ganti page yang terlama di memori n
n
Mem
Review: Page replacement n
n
Disk
OS/ JM-2001/v1.1/5
n
n
Saat mengakses page frame: Gunakan time stamp informasi kapan terakhir page diakses. Saat penggantian: cari/compare yang terlama. Problems: Page frame besar
R=1 R=0
R=0 n
Good? Bad?: n Waktu scan lambat/cepat?
R=1
R=0
R=1
R=1
n
Interval pendek => informasi hilang,
n
Interval lama => semua page di akses
R=0
R=1 R=0
OS/ JM-2001/v1.1/8
2
LRU: Implementation n n
Problem: sweep interval? Gunakan: n bits per page n n n
n
Jika page digunakan: set use bit (1 bit) = 1. OS sweep: gunakan sisa bit sebagai counter (used count, shift register) Misalkan: n = 1 (Second chance): reset bit reference = 0; Page akan diganti jika pada saat sweep yang kedua bitnya tetap 0. Misalkan: n = 2, gunakan 1 bit untuk reference, dan 1 bit untuk counter
Allocation of Frames n
Setiap proses memerlukan pages jumlah minimum. n Contoh: n
n
Two major allocation schemes. n
• Sweep: jika bit reference 1, maka set bit counter = 1, clear bit reference. jika bit reference 0, maka reset bit counter = 0, clear bit reference.
Instruksi yang panjang dan melibatkan lebih dari satu memori reference, contoh MOVE dapat mencakup 2 pages (instruksi) + 2 pages (data)
n
fixed allocation priority allocation
• Page yang akan diganti adalah page: 00. OS/ JM-2001/v1.1/9
LRU: Unix SunOS Script started on Mon Apr 16 13:03:45 2001 caplin% vmstat -s 9049361 pages paged in 7061493 pages paged out 4421662 pages examined by the clock daemon 377 revolutions of the clock hand 9298235 pages freed by the clock daemon … 57724440 cpu context switches 143532739 system calls
OS/ JM-2001/v1.1/11
Fixed Allocation n
Alokasi jumlah page sama: n
n
Jika jumlah memori fisik (page frame): 100 pages, dan jumlah proses 5, maka setiap proses => 20 pages.
Alokasi proporsionil: n
Sesuai ukuran besarny proses. m = 64
s i = size of process p i S = ∑ si m = total number of frames ai = allocation for p i =
OS/ JM-2001/v1.1/10
si S
×m
s i = 10 s 2 = 127 10 × 64 ≈ 5 137 127 a2 = × 64 ≈ 59 137 a1 =
OS/ JM-2001/v1.1/12
3
Priority Allocation
Why?
n
P1
Gunakan alokasi yang proporsionil sesuai dengan prioritas proses. n Jika proses Pi => page fault: n
Pilih penggantian frame dari alokasi untuk proses tersebut (frame yang digunakan oleh Pi). • Setiap proses mempunyai jatah pages yang dapat digunakan (pool).
n
Pilih penggantian frame dari proses dengan “low prioritiy number”, CPU intensive etc.
P2
P3
Real mem Setiap kali sebuah page akan di copy ke memori, terdapat page lain yang harus diganti, dan page yang akan diganti tersebut akan di referensi lagi => page fault meningkat drastis. Implikasi: Proses block => operasi I/O ke disk, I/O sibuk (full utilization), Tapi hanya melakukan swap in/out page dari memori ke disk. What we wanted: virtual memory the size of disk with access time of of physical memory What we have: memory with access time = disk access
OS/ JM-2001/v1.1/13
Thrashing n n
Jika page frame yang dapat disediakan untuk seluruh proses tidak mencukupi. Dalam kasus tertentu proses tidak pernah dapat mempunyai jumlah pages yang cukup (misalkan jika jumlah proses terlalu banyak): n n
OS/ JM-2001/v1.1/15
OS coping with thrashing n
n
n
Terjadi page-faults terus menerus. Low CPU utilization.
Thrashing ≡ a process is busy swapping pages in and out.
n
n
Throughput/kemajuan proses tersebut sangat kecil/ tidak ada sama sekali.
OS/ JM-2001/v1.1/14
n n
n
Jika proses terlalu besar dan tidak terstruktur atau reuse memor y (malloc dan free) => OS tidak dapat membantu banyak, tapi melindungi proses lain.
System thrashing? n
• operating system thinks that it needs to increase the degree of multiprogramming. • another process added to the system. n
Single process thrashing?
Jika karena page tidak mencukupi untuk seluruh proses: Evaluasi kebutuhan pages setiap proses. Jadwal/prioritas proses yang run, hanya memori mencukupi. Menolak menerima proses baru.
Note: n n n
OS tidak dapat menjamin “tidak ada problem”. Solusi (“rule of thumb”): upgrade memory (go to M -2). Cara lain: gunakan “ps” dan kill proses lain.
OS/ JM-2001/v1.1/16
4
Thrashing Diagram
n
Why does paging work? Locality model n n
n
Pendekatan 1: page fault frequency (PFF) n
n
n
Working Set n
PFF = page faults / instructions executed Jika PFF meningkat di atas “threshold”, proses memerlukan memory yang lebih banyak (give pages).
Pengamatan: n
Jika PFF menurun jauh di bawah “threshold”, memory pages dapat diambil dari proses, dan memperbanyak proses yang aktif.
n
Pendekatan 2: working set n n
Jika kita dapat memperkirakan berapa kebutuhan pages supaya terdapat progress (needs a working set of pages). Hanya menjalankan proses yang kebutuhannya dapat dipenuhi pada saat tersebut. • OS dapat melihat “real demand” untuk keseluruhan jumlah proses dan page frame yang tersedia.
OS/ JM-2001/v1.1/18
If actual rate too low, process loses frame. If actual rate too high, process gains frame.
OS/ JM-2001/v1.1/19
• Tidak mencukupi memori di sistim? Proses swap out ke disk. n
Establish “acceptable” page-fault rate. n
Why does thrashing occur? Σ size of locality > total memory size
Methodology for solving? n
n
Process migrates from one locality to another. Localities may overlap.
OS/ JM-2001/v1.1/17
n
Page-Fault Frequency Scheme
n
Menambah jumlah alokasi frame untuk satu proses tidak berpengaruh banyak terhadap performance akses memori dari proses tsb (misalkan sulit meniadaka page fault). Mengurangi jumlah alokasi frame untuk satu proses => pada titik tertentu berpengaruh besar: page fault akan meningkat drastis => thrashing.
Evaluasi kebutuhan pages oleh satu proses dalam kurun waktu T tertentu: n n
Real need: jumlah pages untuk proses tersebut. Problem? T is “magic”, how long?
OS/ JM-2001/v1.1/20
5
WS Model n
n
WSSi (working set of Process P i ) = jumlah total pages yang direferensi dalam interval waktu tertentu. total number of pages referenced in the most recent ∆ (varies in time) n n n
n
n
The concept is a good perspective on system behavior. n
n
n
if D > m ⇒ Thrashing
Policy if D > m, then suspend (block) one of the processes.
OS/ JM-2001/v1.1/21
As optimization trick, it’s less important: Early systems thrashed lots, current systems not so much.
Have OS designers gotten smarter? No. It’s the hardware guys (cf. Moore’s law): n
D = Σ WSSi ≡ total demand frames untuk semua proses. n
n
if ∆ too small will not encompass entire locality. if ∆ too large will encompass several localities. if ∆ = ∞ ⇒ will encompass entire program.
Working set less important
n
Obvious: Memory much larger (more to go around) Less obvious: CPU faster so jobs exit quicker, return memory to freelist faster. Some app can eat as much as you give, the percentage of them that have “enough” seems to be increasing.
OS/ JM-2001/v1.1/23
How to implement working set?
Other Considerations
n
n
Kita memerlukan informasi “idle time” untuk setiap page frame: n n
n
n
Idle time => berhubungan dengan jumlah waktu CPU proses tsb, sejak page diakses. Jika page’s idle time > T? page bukan bagian dari working set.
Scan semua page di memori oleh proses tsb. • Use bit di set (1)? Reset page’s idle time. • Use bit masih reset (0)? Tambahkan CPU time proses tersebut ke idle time. n
Prepaging
Unix: • Scan dilakukan dalam orde detik. • T dalam orde menit.
OS/ JM-2001/v1.1/22
Pada saat proses start (suspend, baru), jumlah pages yang diberikan ke proses tersebut memenuhi perkiraan working set untuk proses tersebut • Sekaligus ditransfer ke memori (sehingga page faults akan berkurang pada saat awal). • Masalah: kemungkinan page tersbut tidak penah diakses.
n
Page size selection n n
Ukuran dari 512 bytes – 16 KB. Pertimbangan: • • • •
besarnya page table (setiap proses) => large Internal fragmentation => small Transfer time dari disk ke memori => large Page faults => large
OS/ JM-2001/v1.1/24
6
