SME
Operating Systems
Memory management
Use this for “With 4 KiB pages, virtual address 20 500 is on which page, at what offset?”
Diagram
Page
=
⌊
20,500
4,096
⌋
=
5;
offset
=
20,500
−
5
×
4,096
=
20.
PA = 9 × 4,096 + 20 = 36,884.
This is an example. Type your own values to start a new problem.
p
=
⌊
VA
÷
S (B)
⌋
d
=
VA
mod
S (B)
f
Frame number
example
PA
Physical address
worked out (not typed)
bd
Offset bits
worked out (not typed)
bₚ
Page-number bits
worked out (not typed)
Formulas
p
=
⌊
VA
S
⌋
5
=
⌊
20,500
4,096
⌋
d
=
VA
mod
S
20 = 20,500 mod 4,096
bd
=
log₂
S
12 = log₂ 4,096
PA
=
f
×
S
+
d
36,884 = 9 × 4,096 + 20
bₚ = 32 − bd
20 = 32 − 12
Assumptions
•
Virtual addresses are 32-bit and name single bytes; 1 KiB = 1024 bytes (many texts write KB).
•
Pages and frames are the same size, a power of 2, so the offset is the address’s low bits.
•
The page table maps the page number to a frame; type the frame your table gives.
Step-by-step
WE KNOW
S = 4,096 B, VA = 20,500, f = 9
FIND
page number (p), offset (d), offset bits (bd), physical address (PA), page-number bits (bₚ)
Step 1 · Find page number (p)
Use p = ⌊VA ÷ S⌋
The page number counts the whole pages before the address.
⌊
20,500
4,096
⌋
=
⌊5.0049⌋
=
5
p
=
5
Step 2 · Find offset (d)
Use d = VA mod S
The offset is what is left over: the place inside the page.
20,500
mod
4,096
=
20,500
−
4,096
×
⌊
20,500
4,096
⌋
=
20,500
−
4,096
×
5
=
20
d
=
20
Step 3 · Find offset bits (bd)
Use bd = log₂ S
The offset needs one bit pattern for every byte of a page.
log₂
4,096
=
12,
since
2
12
=
4,096
bd = 12
Step 4 · Find physical address (PA)
Use PA = f × S + d
Frame
f
starts
at
byte
f
×
S
,
and
the
offset
lands
at
the
same
place
inside
it.
PA = 9 × 4,096 + 20
PA = 36,864 + 20
PA = 36,884
Step 5 · Find page-number bits (bₚ)
Use bₚ = 32 − bd
A 32-bit address keeps the bits the offset does not use for the page number.
bₚ = 32 − 12
bₚ = 20
Check
Put the numbers back in. Both sides should match.
5
=
⌊
20,500
4,096
⌋
✓
20 = 20,500 mod 4,096 ✓
12 = log₂ 4,096 ✓
36,884 = 9 × 4,096 + 20 ✓
20 = 32 − 12 ✓
Topic check
See what you know: 5 questions on this topic
New questions each time. Pass to mark it complete.
More problem types
Effective access time with a TLB
Use this for “A TLB lookup takes 10 ns, memory takes 100 ns, and 90% of lookups hit. What is the effective access time?”
Effective access time with page faults
Use this for “Memory takes 100 ns, a page fault takes 8 ms to service, and 1 access in 100 000 faults. What is the effective access time?”
Page replacement: FIFO and LRU
Use this for “Pages are referenced 1, 3, 1, 2, 4, 3, 1, 4 with 3 frames, all empty at the start. How many page faults does FIFO make, and LRU?”