Virtual Memory
Virtual memory is a technique that allows a program to be executed even when it is not entirely in main memory. It gives every process the illusion of a large, private, contiguous address space, while the physical memory is small, shared and fragmented.
ADDRESS SPACE (virtual/logical) : the addresses the PROGRAM uses
MEMORY SPACE (physical/real) : the addresses MAIN MEMORY actually has
Typically: address space >> memory space
e.g. a 64-bit virtual space on a machine with 8 GB of RAM
1. Benefits
| Benefit | Explanation |
|---|
| Programs larger than RAM | Only the active parts need to be resident |
| Multiprogramming | Many processes fit, because each keeps only its working set in memory |
| Protection | Each process has its own page table — it literally cannot address another's memory |
| Relocation | A program can be loaded anywhere; the page table hides the physical location |
| Sharing | Two page tables can point at the same physical frame (shared libraries) |
| Simplified programming | The programmer never manages overlays by hand |
2. Paging
The virtual address space is divided into fixed-size PAGES.
The physical memory is divided into equal-size PAGE FRAMES.
Page size = frame size, typically 4 KB (also 2 MB / 1 GB "huge pages")
Virtual address:
+-------------------+------------------+
| Page number (p) | Offset (d) |
+-------------------+------------------+
Physical address:
+-------------------+------------------+
| Frame number (f) | Offset (d) |
+-------------------+------------------+
The OFFSET is UNCHANGED by translation — only the page number is
translated into a frame number, via the PAGE TABLE.
Address-split numericals
Q: A system has a 32-bit virtual address and 4 KB pages.
How many bits are the page number and the offset?
Offset = log2(4096) = 12 bits
Page number = 32 - 12 = 20 bits
Number of pages = 2^20 = 1,048,576 pages
Q: The same system has 1 GB of physical memory. How many bits
is the frame number, and how large is the page table
(assuming 4 bytes per entry)?
Physical address = log2(1 GB) = 30 bits
Frame number = 30 - 12 = 18 bits
Page table size = 2^20 entries x 4 bytes = 4 MB per process
Q: Virtual address 0x00003A7C on a system with 4 KB pages.
Split it.
Offset = 0xA7C (lowest 12 bits)
Page number = 0x00003 = 3 (upper 20 bits)
If page 3 maps to frame 9, the physical address is:
(9 << 12) | 0xA7C = 0x9A7C
3. The Page Table
One entry per virtual page, containing:
Frame number : where the page lives in physical memory
VALID / PRESENT : 1 = the page is in memory; 0 = it is on disk
DIRTY / MODIFIED: 1 = the page was written to since being loaded
(must be written back to disk before eviction)
REFERENCED : 1 = the page was accessed recently (for LRU)
PROTECTION : read / write / execute permissions
CACHING bit : whether this page may be cached
The size problem, and its solutions
A 4 MB page table per process (from the numerical above) is too large
to keep entirely in memory, and a 64-bit address space would need
a table of astronomically greater size.
Solutions:
MULTI-LEVEL PAGE TABLE : page the page table itself. A 2-level
scheme splits the page number into two indexes; a whole
second-level table is created only if that region is used.
INVERTED PAGE TABLE : one entry per PHYSICAL FRAME instead of
per virtual page. Size depends on RAM, not on address space.
HASHED PAGE TABLE : hash the virtual page number to find the entry.
Two-level translation for a 32-bit address with 4 KB pages:
+----------+----------+------------+
| Dir (10) | Page(10) | Offset(12) |
+----------+----------+------------+
Dir indexes the outer page directory -> gives the address of
an inner page table
Page indexes the inner page table -> gives the frame number
Offset selects the byte within the frame
Cost: TWO extra memory accesses per translation. Hence the TLB.
4. The Translation Lookaside Buffer (TLB)
Without a TLB, every memory reference needs:
1 access to read the page table entry, plus
1 access to read the actual data
-> the machine runs at HALF speed (or a third, with two-level tables).
The TLB is a small, fully associative cache of recent
page-number -> frame-number translations. Typically 32-1024 entries.
Because it is searched by CONTENT, it IS an associative memory
(the previous lesson).
Effective memory access time with a TLB:
EMAT = h x (T(tlb) + T(mem)) + (1 - h) x (T(tlb) + 2 x T(mem))
where h is the TLB hit ratio.
Q: TLB access = 20 ns, memory access = 100 ns, TLB hit ratio = 80%.
Find the effective access time.
Hit : 20 + 100 = 120 ns
Miss : 20 + 100 + 100 = 220 ns
EMAT = 0.8 x 120 + 0.2 x 220 = 96 + 44 = 140 ns
Q: Same system with a 98% TLB hit ratio.
EMAT = 0.98 x 120 + 0.02 x 220 = 117.6 + 4.4 = 122 ns
(A 2% improvement in hit ratio buys an 13% speed improvement —
the same steep sensitivity as the cache.)
5. Page Faults
A PAGE FAULT occurs when the valid bit of the required page is 0.
Handling sequence:
1. The MMU raises a page-fault TRAP (an internal interrupt).
2. The OS saves the process state.
3. The OS locates the page on disk.
4. If no free frame exists, a victim page is chosen by the
REPLACEMENT ALGORITHM; if it is DIRTY it is written to disk first.
5. The page is read from disk into the free frame (a DMA transfer).
6. The page table is updated; the valid bit is set.
7. The faulting instruction is RESTARTED.
Cost: a disk access is ~10 ms versus ~100 ns for memory —
a page fault is about 100,000 times more expensive than a hit.
6. Page Replacement Algorithms
Reference string: 7 0 1 2 0 3 0 4 2 3 0 3 2
Frames available: 3
FIFO
7 | 7 F 4 | 4 0 1 F
0 | 7 0 F 2 | 4 2 1 F
1 | 7 0 1 F 3 | 4 2 3 F
2 | 2 0 1 F 0 | 0 2 3 F
0 | 2 0 1 hit 3 | 0 2 3 hit
3 | 2 3 1 F 2 | 0 2 3 hit
0 | 2 3 0 F
Total page faults = 9
Optimal (Belady) — replace the page not needed for the longest time
Total page faults = 7 (the theoretical minimum for this string)
LRU — replace the least recently used page
Total page faults = 10 for this particular string
(LRU is usually close to optimal, though not always)
| Algorithm | Rule | Practicality |
|---|
| FIFO | Oldest page out | Simple; suffers Belady's anomaly |
| Optimal | Page needed furthest in the future | Impossible — requires the future |
| LRU | Least recently used | Good; needs counters or a stack |
| LFU | Least frequently used | Needs counters; a once-hot page lingers |
| Second chance / Clock | FIFO plus a reference bit | The practical approximation of LRU used by real OSes |
BELADY'S ANOMALY:
With FIFO, INCREASING the number of frames can INCREASE the
number of page faults.
Reference string 1 2 3 4 1 2 5 1 2 3 4 5:
3 frames -> 9 page faults
4 frames -> 10 page faults <- more frames, MORE faults!
LRU and Optimal are "stack algorithms" and never exhibit this.
7. Thrashing
THRASHING: the system spends more time swapping pages than executing.
Cause: the sum of the processes' WORKING SETS exceeds physical memory,
so every process constantly faults on pages the others just evicted.
Symptoms: CPU utilisation collapses while disk activity saturates.
Cures:
- Reduce the degree of multiprogramming (suspend some processes)
- Working-set model: give each process enough frames for its
current working set, or suspend it
- Page-fault frequency control: monitor each process's fault rate
and adjust its frame allocation
- Add more physical memory
8. Segmentation
SEGMENTATION divides the address space by LOGICAL UNITS rather than
by fixed-size blocks: code segment, data segment, stack segment,
one segment per array or module.
Address = (segment number, offset)
Segment table entry: BASE address + LIMIT (length) + protection bits
Translation:
if (offset >= limit) -> addressing error (segmentation fault!)
else physical address = base + offset
| Basis | Paging | Segmentation |
|---|
| Block size | Fixed | Variable |
| Divided by | Hardware | The programmer / compiler (logical units) |
| Fragmentation | Internal (unused space in the last page) | External (gaps between segments) |
| Address | One number, split by hardware | Explicit (segment, offset) pair |
| Protection | Per page (uniform) | Per segment (matches logical units — better) |
| Table size | Large (many pages) | Small (few segments) |
| Sharing | Per page | Per segment (more natural) |
SEGMENTED PAGING combines both: memory is divided into segments,
and each segment is divided into pages. This gives the logical
structure of segmentation with the fragmentation-free allocation
of paging. It is what x86 and most modern systems actually use.
9. Cache vs Virtual Memory — the same idea at two scales
| Basis | Cache | Virtual memory |
|---|
| Between | CPU and main memory | Main memory and disk |
| Block name | Line / block (32–128 bytes) | Page (4 KB–2 MB) |
| Miss name | Cache miss | Page fault |
| Miss penalty | ~100 ns (10–100×) | ~10 ms (100,000×) |
| Managed by | Hardware | OS software (hardware assists via the MMU) |
| Replacement | Hardware (approximate LRU) | Software (Clock/LRU approximation) |
| Purpose | Speed | Capacity + protection + relocation |
Summary
Virtual memory : programs run without being fully resident
Paging : fixed-size pages -> frames, translated by the page table
Address split : offset = log2(page size); page number = rest
TLB : associative cache of translations
EMAT = h(T_tlb + T_mem) + (1-h)(T_tlb + 2.T_mem)
Page fault : valid bit = 0 -> trap -> fetch from disk -> restart
Replacement : FIFO (Belady's anomaly), LRU, Optimal, Clock
Thrashing : working sets exceed memory
Segmentation : variable-size logical units, external fragmentation
Unit IV is complete, and with it the whole course: from a single Boolean law in Unit I to a full computer with I/O and a memory hierarchy in Unit IV.
