DSA, Database System & Operating System — Memory Management, File Systems & Administration, NEC licence examination syllabus (Nepal Engineering Council).
Virtual Memory Management
Running a program larger than physical memory — paging, page tables, and the TLB that makes translation affordable.
🌍 Where this lives: virtual memory is why you can open a 4 GB video file on an 8 GB machine, why every process gets its own private address space, and why a segfault kills one program instead of the machine. It is also the mechanism behind features that look unrelated: mmap makes a file look like memory, copy-on-write makes fork cheap, and shared libraries are one physical copy mapped into many address spaces. All four are the same page-table trick applied differently. Search "mmap shared memory copy on write".
Paging
Divide the LOGICAL address space into fixed-size PAGES and
physical memory into equal-sized FRAMES. Any page may live in
any frame.
page size = frame size, always a power of two
MEASURED on this machine: 16,384 bytes (16 KB), not the 4 KB
most textbooks assume.
→ external fragmentation is ELIMINATED (any free frame fits
any page)
→ internal fragmentation remains (the last page is partly
empty)
ADDRESS SPLITTING — a logical address is split, not added:
logical address = | page number p | offset d |
high bits low bits
If the page size is 2^n bytes, the low n bits are the offset
and the rest is the page number. No arithmetic is needed —
the split is just bit positions, which is why the page size
must be a power of two.
ON THIS MACHINE: page size 16 KB = 2^14
offset = low 14 bits
page no = the remaining bits
for a 48-bit address space: 48 − 14 = 34 bits of page
number → 2^34 pages = 17 billion
TRANSLATION:
1. extract p and d from the logical address
2. look up frame f = PageTable[p]
3. physical address = f × page_size + d
(equivalently: concatenate f and d)
WORKED EXAMPLE — the standard exam calculation.
Page size 4 KB (2^12), logical address 8196, page table:
page 0 → frame 5
page 1 → frame 9
page 2 → frame 1
8196 in binary needs splitting at bit 12:
p = 8196 / 4096 = 2 (integer division)
d = 8196 % 4096 = 4 (remainder)
PageTable[2] = frame 1
physical = 1 × 4096 + 4 = 4100
THE SAME ADDRESS on this machine's 16 KB pages:
p = 8196 / 16384 = 0
d = 8196 % 16384 = 8196
A different page entirely. Always check the page size before
computing — this is exactly why assuming 4 KB is dangerous.
PAGE TABLE SIZE — the problem that motivates everything below:
32-bit address space, 4 KB pages, 4-byte entries
pages = 2^32 / 2^12 = 2^20 = 1,048,576
table = 2^20 × 4 B = 4 MB PER PROCESS
With 100 processes that is 400 MB of page tables alone.
64-bit address space, 16 KB pages, 8-byte entries
pages = 2^48 / 2^14 = 2^34
table = 2^34 × 8 B = 128 GB PER PROCESS
A flat page table is impossible for 64-bit. Hence multilevel
tables.
Making page tables affordable
MULTILEVEL (HIERARCHICAL) PAGING
page the page table itself. Only the parts actually used are
allocated.
TWO-LEVEL, 32-bit, 4 KB pages:
| outer p1 (10) | inner p2 (10) | offset d (12) |
outer table 2^10 = 1024 entries
each inner 1024 entries covering 4 MB
A process using 8 MB needs the outer table plus TWO inner
tables:
(1024 + 2×1024) × 4 B = 12 KB
versus 4 MB for a flat table — a 341× saving, and that is the
whole point.
x86-64 uses FOUR levels (and now five), each 9 bits:
9 + 9 + 9 + 9 + 12 = 48 bits
COST: four memory accesses per translation, plus the data
access. Five accesses for one load — which is why the TLB
below is not optional.
INVERTED PAGE TABLE
one entry per PHYSICAL FRAME rather than per virtual page,
storing which (process, page) occupies it.
✔ size proportional to PHYSICAL memory, not virtual — so one
table for the whole machine
✗ translation requires SEARCHING it, so a hash table is
needed
✗ shared memory becomes awkward (one frame, many virtual
pages)
HASHED PAGE TABLE
hash the virtual page number into a table of chains. Common
on 64-bit architectures for the same reason.
PAGE TABLE ENTRY CONTENTS — every bit does real work:
frame number
VALID/INVALID is this page in memory? → page fault if not
PROTECTION read / write / execute → SIGSEGV if
violated
DIRTY (modified) has it been written? → if clean, no need
to write it out
on eviction
REFERENCED has it been accessed? → used by clock/LRU
approximation
CACHING may this page be cached? → must be off for
device registers
The dirty bit alone can halve page-out traffic: a clean page
can simply be discarded because the copy on disk is still
valid.
The TLB — and why translation is not 5× slower
A four-level page table means four memory accesses per
translation. Without help, every load would cost five memory
accesses. The TRANSLATION LOOKASIDE BUFFER fixes this.
The TLB is a small, fully-associative HARDWARE CACHE of
recent page-table entries. Typically 64–1536 entries.
ON A TLB HIT translation costs ~1 cycle (parallel with the
cache lookup) — effectively free
ON A TLB MISS walk the page table (4 accesses), then load
the entry into the TLB
EFFECTIVE ACCESS TIME (EAT) — the standard numerical:
EAT = hit_ratio × (TLB + memory)
+ miss_ratio × (TLB + page_table_accesses + memory)
WORKED: TLB lookup 1 ns, memory access 100 ns, single-level
page table, hit ratio 98%
hit : 1 + 100 = 101 ns
miss : 1 + 100 + 100 = 201 ns
EAT = 0.98×101 + 0.02×201
= 98.98 + 4.02 = 103.0 ns
slowdown vs 100 ns ideal = 3.0%
AT 90% HIT RATIO:
EAT = 0.90×101 + 0.10×201 = 90.9 + 20.1 = 111.0 ns
slowdown = 11.0%
AT 98% WITH A FOUR-LEVEL TABLE (4 extra accesses on a miss):
miss = 1 + 400 + 100 = 501 ns
EAT = 0.98×101 + 0.02×501 = 98.98 + 10.02 = 109.0 ns
slowdown = 9.0%
THE LESSON: the hit ratio dominates. Going from 98% to 90%
costs more than adding three page-table levels. That is why
real TLBs are highly optimised and why HUGE PAGES exist —
a 2 MB page covers 128× more memory per TLB entry than a
16 KB page, so the same TLB covers 128× the working set.
CONTEXT SWITCH AND THE TLB:
entries are per-process, so a naive switch must FLUSH the
TLB — and the new process then takes hundreds of TLB misses.
This is a large part of the indirect context-switch cost from
the process topic.
MODERN FIX: tag each entry with an ADDRESS SPACE ID (ASID /
PCID), so entries from several processes coexist and no flush
is needed.
That last comparison is the useful one: a 98% hit ratio on a four-level table beats a 90% hit ratio on a single-level table (109 ns vs 111 ns). Deepening the page table is cheap; degrading TLB locality is expensive. It is the same lesson as cache behaviour generally — the miss rate matters far more than the miss cost.
Segmentation, and why paging won
SEGMENTATION divides the address space into VARIABLE-SIZED
logical units that match program structure: code, data, stack,
each symbol table.
logical address = | segment s | offset d |
segment table entry: base, limit
physical = base[s] + d, provided d < limit[s]
✔ matches the programmer's view — a segment IS an array or a
function, so protection can be per-object (execute-only
code, read-only constants)
✔ sharing is natural: map the same code segment into two
processes
✗ EXTERNAL FRAGMENTATION returns, because segments have
different sizes and leave odd-sized holes
✗ a segment must be CONTIGUOUS in physical memory
PAGING vs SEGMENTATION:
PAGING SEGMENTATION
block size FIXED VARIABLE
divided by the OS the programmer/compiler
external fragm. NONE yes
internal fragm. yes (half page) none
address p, d s, d
protection unit a page a logical object
table size large small
SEGMENTED PAGING — the practical combination:
segment the address space, then PAGE each segment. You get
segmentation's logical structure and paging's freedom from
external fragmentation.
logical = | segment s | page p | offset d |
Used by x86 historically (and still visible in its segment
registers), and by MULTICS originally.
WHY PURE SEGMENTATION LOST: external fragmentation and the
contiguity requirement. x86-64 essentially removed
segmentation — the segment registers survive vestigially for
thread-local storage — and everything is paged. Fixed-size
blocks are simply easier to manage, and the internal
fragmentation of half a page per segment is a price worth
paying.
🌍 Go further: the TLB pressure argument has a direct production consequence: huge pages. A database with a 64 GB buffer pool needs 4 million TLB entries at 16 KB pages, which no TLB can hold, so it takes constant TLB misses. Switch to 2 MB pages and the same memory needs 32,000 entries — a 128× reduction, often worth 5–15% throughput on PostgreSQL or the JVM. The catch is that huge pages cannot be swapped and are harder to allocate once memory is fragmented, which is why Linux offers both explicit hugetlbfs and automatic transparent_hugepage. Search "huge pages database performance TLB".
💡 Exam angle: the address-splitting calculation is guaranteed — given a page size and a logical address, compute p and d, then the physical address from a page table. Note that p = address / page_size and d = address % page_size. Be able to compute page table size and explain why a flat 64-bit table is impossible, then describe multilevel paging with a worked saving. The EAT formula with a TLB hit ratio is the other standard numerical. Finish with the paging versus segmentation table, stressing that paging has no external fragmentation and segmentation has no internal fragmentation.
Syllabus points
Virtual memory concept
Create a free account to tick topics off, take notes as you read, watch the video lessons and get a day-by-day study plan built around your exam date.
Related topics in Memory Management, File Systems & Administration