Memory Management and Virtual Memory
Address spaces, paging, page tables and the TLB, page faults, replacement algorithms, and thrashing.
Each Process Sees a Virtual View of Memory
A process uses virtual addresses, not raw physical RAM locations. The memory-management unit (MMU) and OS-managed page tables translate virtual addresses to physical frames and enforce access permissions. This abstraction allows processes to have isolated address spaces, simplifies allocation, and lets the OS move or share physical pages under controlled rules.
With paging, virtual memory is divided into fixed-size pages, and physical memory into frames. A virtual address can be split into a virtual page number and an offset. Translation maps the page number to a frame while preserving the offset. Page size and address width are platform properties; avoid hard-coding them when writing portable software.
| Term | Meaning | Role |
|---|---|---|
| Virtual page | Fixed-size region in a process address space | Address-translation unit |
| Physical frame | Fixed-size region of physical memory | Where a resident page is stored |
| Page table | Mapping and permission metadata | Connects virtual pages to frames |
| Offset | Position within a page | Copied unchanged during translation |
The TLB Caches Recent Page Translations
Walking page tables for every memory reference would be costly, so processors cache recent translations in a translation lookaside buffer (TLB). A TLB hit provides a cached translation; a miss triggers a page-table walk (hardware-assisted on many systems) and may then fill the TLB. Address-space switches can affect translation caches; modern CPUs use techniques such as address-space identifiers, but exact behavior varies.
A valid page-table entry can still point to a page that is not resident. An access then causes a page fault, a hardware exception that transfers control to the OS. The kernel checks whether the access is legal. It may load a page, create a zero-filled page, perform copy-on-write, or reject the access and deliver an error to the process.
A Fault Can Be Minor or Require Storage I/O
On a legal nonresident access, the OS locates the backing data, finds a free frame or chooses a victim, writes a dirty victim back if needed, reads or constructs the requested page, updates mappings, and resumes the faulting instruction. If storage is needed, the task may block while the device works. An illegal address or permission violation can instead terminate the process or signal an error.
# Observe memory and paging counters over time
free -h
vmstat 1 5
# Per-process memory maps (Linux; permissions may restrict details)
cat /proc/self/maps | head -n 12free and vmstat are snapshots or interval reports, not a direct count of one application's page faults. Linux often uses otherwise idle RAM for cache; low “free” memory alone does not prove memory pressure. Check trends, reclaim, swap, and workload symptoms together.
FIFO, LRU, and Optimal on the Same Reference String
When no frame is free, a replacement policy chooses a victim. We will use three frames and the reference string 1, 2, 3, 1, 4, 2, 5, 1, 2, 3, 4, 5. For FIFO, the oldest loaded page is evicted; hits do not change its age. For LRU, evict the page least recently used. Optimal evicts the page whose next use is farthest in the future; it is an offline benchmark because the future is not known to a live OS.
| Reference | FIFO frames (F= fault, H=hit) | LRU frames (F= fault, H=hit) | Optimal frames (F= fault, H=hit) |
|---|---|---|---|
| 1 | 1 — — F | 1 — — F | 1 — — F |
| 2 | 1 2 — F | 1 2 — F | 1 2 — F |
| 3 | 1 2 3 F | 1 2 3 F | 1 2 3 F |
| 1 | 1 2 3 H | 1 2 3 H | 1 2 3 H |
| 4 | 4 2 3 F | 1 4 3 F | 1 2 4 F |
| 2 | 4 2 3 H | 1 4 2 F | 1 2 4 H |
| 5 | 4 5 3 F | 5 4 2 F | 1 2 5 F |
| 1 | 4 5 1 F | 5 1 2 F | 1 2 5 H |
| 2 | 2 5 1 F | 5 1 2 H | 1 2 5 H |
| 3 | 2 3 1 F | 3 1 2 F | 3 2 5 F |
| 4 | 2 3 4 F | 3 4 2 F | 4 2 5 F |
| 5 | 5 3 4 F | 3 4 5 F | 4 2 5 H |
For example, after the first four references, the frames contain 1, 2, 3 and the next reference 4 faults. FIFO evicts 1, the earliest arrival. LRU evicts 2, whose last use was earlier than 3 (1 was just used). Optimal evicts 3 because its next use is later than the next uses of 1 and 2. At reference 7, both FIFO and LRU fault again; Optimal has 7 total faults across the full string.
Thrashing Is a Working-Set Problem
Thrashing occurs when a system spends a disproportionate amount of time servicing page faults and moving pages rather than doing useful application work. It often happens when the active working sets of processes do not fit in available frames. Adding more runnable processes can then reduce overall throughput instead of increasing it.
A working set is the pages a process has actively referenced over a recent window. If the total working sets of active processes exceed the frames available, pages evicted from one process may be needed again almost immediately. Fault frequency rises, useful CPU utilization falls, and a naive controller might mistakenly admit even more processes. Reducing concurrency or reclaiming a process's working set can restore progress.
Locality explains why paging can work well despite an address space being larger than RAM: code tends to reuse nearby instructions and data for a period. A loop over contiguous array elements often has better locality than random pointer chasing across a huge structure. This is a software-level performance property interacting with the OS memory policy.
OS strategies include reducing the degree of multiprogramming, allocating frames based on working-set or page-fault-frequency ideas, and improving locality. Applications help by processing data in a cache-friendly order and avoiding enormous random working sets. Swapping is not a free substitute for RAM: storage latency can make repeated faults expensive.
#include <stdint.h>
#include <stdio.h>
#include <unistd.h>
int main(void) {
long page_size = sysconf(_SC_PAGESIZE);
int value = 42;
uintptr_t address = (uintptr_t)&value;
if (page_size <= 0) return 1;
printf("virtual address=%p page=%llu offset=%llu
", (void *)&value,
(unsigned long long)(address / (uintptr_t)page_size),
(unsigned long long)(address % (uintptr_t)page_size));
return 0;
}This prints the process's virtual address split into page number and offset for the running system's page size. It does not reveal the physical frame and the address can vary between runs.
def fifo_faults(references, frame_count):
frames = []
next_victim = 0
faults = 0
for page in references:
if page in frames:
continue
faults += 1
if len(frames) < frame_count:
frames.append(page)
else:
frames[next_victim] = page
next_victim = (next_victim + 1) % frame_count
return faults
refs = [1, 2, 3, 1, 4, 2, 5, 1, 2, 3, 4, 5]
print(fifo_faults(refs, 3))Check the Model Before Counting Faults
Replacement exercises assume a fixed number of frames, an initially empty memory, and one page reference at a time. State whether writes make pages dirty if write-back cost matters; the basic fault-counting model ignores that cost. On real systems, file cache, shared pages, huge pages, prefetching, and working-set changes make raw comparisons more involved.
- Mark hit or fault for each reference.
- On a fault, load into an empty frame before evicting.
- For FIFO, advance queue order only on load; for LRU, update recency on every hit and fault.
- For Optimal, inspect only future references and choose the farthest next use.
- Recount totals and verify that each displayed frame contains the referenced page after the step.
Answer with Precision
Giving a memorized slogan without assumptions
Why: A scheduling or replacement answer changes with the workload and model.
Fix: State arrivals, frame count, preemption, and tie-breaking before calculating.
Confusing two neighboring concepts
Why: Similar terms describe different layers or guarantees.
Fix: Define each concept and provide one contrast before adding detail.
Treating an observation as a universal guarantee
Why: A command samples one system at one moment.
Fix: Describe the observation limits and what additional evidence is needed.
Ignoring trade-offs and failure modes
Why: An idealized definition omits the engineering constraints.
Fix: Name one cost, edge case, or recovery path for every mechanism.
Apply It to a Small System
Practice
Trace, calculate, and explain
- Draw the state, resource, or address transitions for a realistic workload, including a wait or failure path.
- Run a relevant Linux observation command from this lesson and explain what it can and cannot prove.
- Implement the small C or Python exercise, change one input, and predict the result before executing it.
- Explain one design choice with a precise invariant, a concrete example, and a trade-off.
Hint: Write assumptions first, then use a trace or calculation to support your explanation.
🎯 Key Takeaways
- ✓Virtual addresses are translated through page tables; pages map to physical frames while preserving offsets.
- ✓The TLB caches translations; a miss may need a page-table walk, while a nonresident access can fault.
- ✓Page faults may be recoverable demand loads or illegal accesses; inspect the cause, not just the event name.
- ✓For the given three-frame reference string, FIFO and LRU each fault 10 times and Optimal 7 times.
- ✓Optimal is a future-aware benchmark; FIFO, LRU, and real policies have different costs and behaviors.
- ✓Thrashing reflects working sets that overwhelm available memory and can make extra multiprogramming harmful.
Next
What comes next
After exploring memory that backs running processes, next see how persistent files and devices are organized.
Lesson 07 · File Systems and I/O →HELP US IMPROVE
How was this lesson?
Your note is shared with the Chaduvuko team for review. Please don’t include personal or sensitive information.
Spotted a mistake or something unclear? Suggest a fix on GitHub or email us. Select the text first and it is quoted for you.
Discussion
0Have a better approach? Found something outdated? Share it — your knowledge helps everyone learning here.
