Formula Sheets: Virtual Memory

 Page 1


Virtual Memory F orm ula Sheet
Virtual Memory Basics
• Virtual A ddress Space : V = 2
n
, wheren is n um b er of address bits.
• Ph ysical A ddress Space : P = 2
m
, wherem is ph ysical memory address bits, t ypicallym<n .
• P age Size : S = 2
k
, t ypically 4 KB (k = 12 ).
• Num b er of P ages : N
pages
=
V
S
= 2
n-k
.
• Num b er of F rames : N
frames
=
P
S
= 2
m-k
.
• Virtual A ddress : (p,d) , whe rep is page n um b er,d is offset ( d<S ).
• Ph ysical A ddress : P =F ·S +d , whereF is frame n um b er.
P a ge F aults
• P age F ault Rate : P
fault
=
N
page-faults
N
total-accesses
.
• P age F ault Service Time : T
page-fault
=T
disk-read
+T
page-table-up date
+T
queue
, t ypicallyT
disk-read
˜
10-20 ms.
• Effectiv e A ccess Time :
EAT = (1-P
fault
)·(T
TLB
+T
memory
)+P
fault
·(T
page-fault
+T
TLB
+T
memory
),
whereT
TLB
is TLB access time, T
memory
is memory access time.
• TLB Hit Ratio : H =
N
TLB-hits
N
total-accesses
.
• TLB Effectiv e A ccess Time : EAT
TLB
=H ·T
TLB
+(1-H)·(T
TLB
+T
memory
) .
P a ge Replacemen t Algorithms
• First-In-First-Out (FIF O) :
– P age F aults: N
faults
=N
pages
-N
frames
, increases with Belady’s anomaly .
• Optimal P age Replacemen t :
– Replaces page not used for longest time in future.
– Minim umN
faults
, used as b enc hmark.
• Least Recen tly Used (LR U) :
– Replaces least recen tly accessed page.
– F ault Rate: P
fault
?
1
N
frames
.
– Ov erhead: O(1) with stac k,O(n) with coun ter, wheren is n um b er of pages.
• Least F requen tly Used (LFU) :
– Replaces page with lo w est access coun t.
– Ov erhead: O(logn) with heap-based implemen tation.
• Most Recen tly Used (MR U) :
– Replaces most recen tly accessed page, useful for sp ecific w orkloads.
• P age F ault F requency : F =
N
faults
T
in terv al
, adjust N
frames
ifF >F
threshold
.
1
Page 2


Virtual Memory F orm ula Sheet
Virtual Memory Basics
• Virtual A ddress Space : V = 2
n
, wheren is n um b er of address bits.
• Ph ysical A ddress Space : P = 2
m
, wherem is ph ysical memory address bits, t ypicallym<n .
• P age Size : S = 2
k
, t ypically 4 KB (k = 12 ).
• Num b er of P ages : N
pages
=
V
S
= 2
n-k
.
• Num b er of F rames : N
frames
=
P
S
= 2
m-k
.
• Virtual A ddress : (p,d) , whe rep is page n um b er,d is offset ( d<S ).
• Ph ysical A ddress : P =F ·S +d , whereF is frame n um b er.
P a ge F aults
• P age F ault Rate : P
fault
=
N
page-faults
N
total-accesses
.
• P age F ault Service Time : T
page-fault
=T
disk-read
+T
page-table-up date
+T
queue
, t ypicallyT
disk-read
˜
10-20 ms.
• Effectiv e A ccess Time :
EAT = (1-P
fault
)·(T
TLB
+T
memory
)+P
fault
·(T
page-fault
+T
TLB
+T
memory
),
whereT
TLB
is TLB access time, T
memory
is memory access time.
• TLB Hit Ratio : H =
N
TLB-hits
N
total-accesses
.
• TLB Effectiv e A ccess Time : EAT
TLB
=H ·T
TLB
+(1-H)·(T
TLB
+T
memory
) .
P a ge Replacemen t Algorithms
• First-In-First-Out (FIF O) :
– P age F aults: N
faults
=N
pages
-N
frames
, increases with Belady’s anomaly .
• Optimal P age Replacemen t :
– Replaces page not used for longest time in future.
– Minim umN
faults
, used as b enc hmark.
• Least Recen tly Used (LR U) :
– Replaces least recen tly accessed page.
– F ault Rate: P
fault
?
1
N
frames
.
– Ov erhead: O(1) with stac k,O(n) with coun ter, wheren is n um b er of pages.
• Least F requen tly Used (LFU) :
– Replaces page with lo w est access coun t.
– Ov erhead: O(logn) with heap-based implemen tation.
• Most Recen tly Used (MR U) :
– Replaces most recen tly accessed page, useful for sp ecific w orkloads.
• P age F ault F requency : F =
N
faults
T
in terv al
, adjust N
frames
ifF >F
threshold
.
1
F rame Allo cation
• Equal Allo cation : F
i
=
N
frames
N pro cesses
, where F
i
is frames for pro cess i .
• Prop ortional Allo cation : F
i
=N
frames
·
Si
?
Sj
, whereS
i
is memory size of pro ces si .
• Priorit y-Based Allo cation : F
i
?P
i
, where P
i
is priorit y of pro cessi .
• Minim um F rames : F
min
=N
pages-activ e
, where N
pages-activ e
is w orking set size.
Thrashing
• Thrashing Condition : P
fault
>P
threshold
, due to insu?icien t frames.
• W orking Set Mo del : W(t,?) ={ pages referenced in w indo w [t-?,t]} .
• W orking Set Size : |W(t,?)|=N
frames
, else thrashing o ccurs.
• Thrashing Ov erhead : T
thrash
=P
fault
·T
page-fault
·N
pro cesses
.
• Prev en tion : A djustN
frames
or susp end pro cesses,N
activ e
=
N
frames
W a vg
.
Sw ap Space
• Sw ap Space Size : S
sw ap
=
?
M
pro cess
i
, whereM
pro cess
i
is memory size of pro cessi .
• Sw ap Time : T
sw ap
=T
disk-write
+T
disk-read
, t ypicallyT
disk-write/read
˜ 10-20 ms.
• Sw ap Throughput : S =
N pro cesses
T
sw ap-total
, whereT
sw ap-total
is total sw ap time.
• Sw ap F ault Ov erhead : T
sw ap-fault
=T
sw ap
+T
page-table-up date
.
Ov erla ys
• Ov erla y Size : S
o v erla y
=M
a v ailable
, whereM
a v ailable
is free ph ysical memory .
• Ov erla y Switc h Time : T
o v erla y
=T
load
+T
unload
, where T
load/unload
?S
o v erla y
.
• Num b er of Ov erla ys : N
o v erla ys
=?
M program
M
a v ailable
? , whereM
program
is total program size.
Sp o oling
• Sp o ol Buffer Size : B
sp o ol
=D
max
, where D
max
is maxim um data siz e p er job.
• Sp o oling Ov erhead : T
sp o ol
=T
buffer-write
+T
device-write
, whereT
buffer-write
<T
device-write
.
• Throughput : S
sp o ol
=
N
jobs
T
sp o ol-total
, where T
sp o ol-total
is total sp o oling time.
P erformance Metrics
– Memory Utilization : U =
M
used
M
total
×100% , whereM
used
is allo cated memory .
– P age F ault Ov erhead : T
fault-o v erhead
=P
fault
·T
page-fault
.
– A v erage Memory A ccess Time : T
a vg-access
=EAT +T
sw ap-fault
·P
sw ap
.
2