Formula Sheets: Memory Management | Operating System - Computer Science Engineering (CSE) PDF Download

 Page 1


Memory Managemen t F orm ula Sheet
Logical vs. Ph ysical A ddress Space
• Logical A ddress : Generated b y CPU, mapp ed to ph ysical address.
• Ph ysical A ddress : A ctual memory lo cation, P = L+B , where L is logical address, B is base
address.
• A ddress T ranslation : P =f(L) , where f is mapping function (e.g., page table, segmen t table).
P aging
• P age Size : S = 2
n
, t ypically 4 KB (n=12).
• Logical A ddress : (p,d) , where p is page n um b er, d is page offse t.
• Ph ysical A ddress : P =F ·S +d , where F is frame n um b er, S is page size.
• P age T able Size : T
page-table
=N
pages
·E , whereN
pages
=
Virtual A ddress Space
S
,E is en try size (e.g.,
4 b ytes).
• Num b er of P ages : N
pages
=?
Pro cess Size
S
? .
• TLB (T ranslation Lo okaside Buffer) Hit Ratio : H =
N
TLB-hits
N
total-accesses
.
• Effectiv e A ccess Time : EAT = H ·T
TLB
+ (1-H)· (T
TLB
+T
memory
) , where T
TLB
is TLB
access time, T
memory
is memory access t ime.
Segmen tation
• Segmen t A ddress : (s,d) , where s is segmen t n um b er, d is offset.
• Ph ysical A ddress : P =B
s
+d , where B
s
is base address of segmen t s .
• Segmen t T able En try : Con tains base address and limit, c hec k ed as d< Limit
s
.
• Segmen t T able Size : T
seg-table
=N
segmen ts
·E , where E is en try size.
Virtual Memory
• P age F ault Rate : P
fault
=
N
page-faults
N
total-accesses
.
• Effectiv e A ccess Time with P age F aults :
EAT = (1-P
fault
)·T
memory
+P
fault
·(T
page-fault
+T
memory
),
where T
page-fault
includes disk I/O and p age table up date time.
• Demand P aging Ov erhead : T
demand
=P
fault
·T
disk
, where T
disk
is disk access time.
F ragmen tation
• In ternal F ragmen tation : F
in ternal
=S-M , where S is allo cated page/segmen t size, M is used
memory .
• External F ragmen tation : F
external
= M
total-free
-M
largest-blo c k
, where M
total-free
is total free
memory , M
largest-blo c k
is largest con tiguous free blo c k.
• 50% R ule (First-Fit/Best-Fit) : A v erage external fragmen tation ˜
M
total
2
.
1
Page 2


Memory Managemen t F orm ula Sheet
Logical vs. Ph ysical A ddress Space
• Logical A ddress : Generated b y CPU, mapp ed to ph ysical address.
• Ph ysical A ddress : A ctual memory lo cation, P = L+B , where L is logical address, B is base
address.
• A ddress T ranslation : P =f(L) , where f is mapping function (e.g., page table, segmen t table).
P aging
• P age Size : S = 2
n
, t ypically 4 KB (n=12).
• Logical A ddress : (p,d) , where p is page n um b er, d is page offse t.
• Ph ysical A ddress : P =F ·S +d , where F is frame n um b er, S is page size.
• P age T able Size : T
page-table
=N
pages
·E , whereN
pages
=
Virtual A ddress Space
S
,E is en try size (e.g.,
4 b ytes).
• Num b er of P ages : N
pages
=?
Pro cess Size
S
? .
• TLB (T ranslation Lo okaside Buffer) Hit Ratio : H =
N
TLB-hits
N
total-accesses
.
• Effectiv e A ccess Time : EAT = H ·T
TLB
+ (1-H)· (T
TLB
+T
memory
) , where T
TLB
is TLB
access time, T
memory
is memory access t ime.
Segmen tation
• Segmen t A ddress : (s,d) , where s is segmen t n um b er, d is offset.
• Ph ysical A ddress : P =B
s
+d , where B
s
is base address of segmen t s .
• Segmen t T able En try : Con tains base address and limit, c hec k ed as d< Limit
s
.
• Segmen t T able Size : T
seg-table
=N
segmen ts
·E , where E is en try size.
Virtual Memory
• P age F ault Rate : P
fault
=
N
page-faults
N
total-accesses
.
• Effectiv e A ccess Time with P age F aults :
EAT = (1-P
fault
)·T
memory
+P
fault
·(T
page-fault
+T
memory
),
where T
page-fault
includes disk I/O and p age table up date time.
• Demand P aging Ov erhead : T
demand
=P
fault
·T
disk
, where T
disk
is disk access time.
F ragmen tation
• In ternal F ragmen tation : F
in ternal
=S-M , where S is allo cated page/segmen t size, M is used
memory .
• External F ragmen tation : F
external
= M
total-free
-M
largest-blo c k
, where M
total-free
is total free
memory , M
largest-blo c k
is largest con tiguous free blo c k.
• 50% R ule (First-Fit/Best-Fit) : A v erage external fragmen tation ˜
M
total
2
.
1
Buddy System
• Blo c k Size : S
k
= 2
k
, where k is order of blo c k.
• Memory Allo cation : Split blo c k of size 2
k
in to t w o 2
k-1
buddies un til 2
k
= Request Size.
• In ternal F ragmen tation : F
in ternal
= 2
k
-R , where R is requested size, 2
k-1
<R= 2
k
.
• Merge Time : O(logN) , where N is total memory size divided b y sm allest blo c k size.
P artition Allo cation Metho ds
• First-Fit : Allo cate first blo c k = pro cess size.
• Best-Fit : Allo cate smallest blo c k = pro cess size, minimizes F
in ternal
.
• W orst-Fit : Allo cate large st blo c k, F
in ternal
=M
largest
-M
pro cess
.
• Allo cation Time :
– First-Fit: O(n) , where n is n um b er of free blo c ks.
– Best-Fit/W orst-Fit: O(n) for linear searc h, O(logn) with priorit y queue.
Sw apping
• Sw ap Time : T
sw ap
=T
disk-write
+T
disk-read
, where T
disk-write/read
? Pro cess Size.
• Sw ap Space Requiremen t : S
sw ap
=
?
M
pro cess
i
, where M
pro cess
i
is me mory size of pro cess i .
• Sw ap Throughput : S =
N pro cesses
T
sw ap-total
, where T
sw ap-total
is total sw ap time.
Shared Libraries
• Memory Sa vings : M
sa v ed
= (N
pro cesses
-1)·M
library
, where M
library
is library size.
• Load Time : T
shared-load
<T
static-load
, due to single cop y in memory .
Memory Managemen t Requiremen ts
• Memory Utilization : U =
M
used
M
total
×100% .
• Ov erhead : T
o v erhead
=T
allo cation
+T
deallo cat ion
+T
page-fault
.
• Compaction Time (External F ragmen tation) : T
compact
?
?
M
mo v ed
, whereM
mo v ed
is mem-
ory relo cated.
2