SME
Computer Organization & Architecture · Problem type
Page table size
Use this for “A system has 32-bit virtual addresses, 4 KiB pages and 4-byte page table entries. How big is a flat page table?”
Diagram
page number 20 + offset 12 = 32 bits, the whole 32-bit word.
Entries N = 1,048,576
This is an example. Type your own values to start a new problem.
VA
Virtual address bits
example · bit
P
Page size
example
offset
Offset bits
calculated · bit
VPN
Page number bits
calculated · bit
N
Entries
calculated
E
Entry size
example · B
T
Table size
calculated
Formulas
offset
=
log₂
P
12 = log₂ 4,096
VPN = VA − offset
20 = 32 − 12
N
=
2VPN
1,048,576
=
2
20
T
=
N
×
E
4,194,304 = 1,048,576 × 4
Formulas are worked in B. The step-by-step shows the conversions.
Assumptions
•
Addresses name single bytes, and 1 KiB = 1024 bytes (many texts write KB).
•
The table is flat (one level) with an entry for every virtual page, used or not.
•
The size grows fast with the address bits (39 and 48 are common 64-bit CPU widths), so real systems use multi-level tables.
Step-by-step
WE KNOW
VA = 32 bit, P = 4 KiB, E = 4 B
FIND
offset bits (offset), page number bits (VPN), entries (N), table size (T)
Step 1 · Convert to the formula’s units
The formulas don’t work directly in the units you chose, so convert first (to B).
P = 4 KiB = 4,096 B (1 KiB = 1024 B)
Step 2 · Find offset bits (offset)
Use offset = log₂ P
The offset needs one pattern for every byte of a page.
log₂
4,096
=
12,
since
2
12
=
4,096
offset = 12 bit
Step 3 · Find page number bits (VPN)
Use VPN = VA − offset
The bits above the offset number the page.
VPN = 32 − 12
VPN = 20 bit
Step 4 · Find entries (N)
Use N = 2ⱽᴾᴺ
Each page-number bit doubles the virtual pages, and each page needs an entry.
2
20
=
1,048,576
N
=
1,048,576
Step 5 · Find table size (T)
Use T = N × E
A flat table keeps one entry for every virtual page.
T
=
1,048,576
×
4
T
=
4,194,304
B
Step 6 · Convert the answers
Change each answer back to the unit you chose.
T = 4,194,304 B = 4 MiB (1 MiB = 1048576 B)
Check
Put the numbers back in. Both sides should match.
12 = log₂ 4,096 ✓
20 = 32 − 12 ✓
1,048,576
=
2
20
✓
4,194,304 = 1,048,576 × 4 ✓
Topic check
See what you know: 5 questions on this topic
New questions each time. Pass to mark it complete.