Memory Management in Operating Systems

Learning Objectives

By the end of this page, you should be able to:

• Explain the difference between logical (virtual) and physical addresses and how translation happens.
• Compare contiguous allocation, paging, and segmentation as memory management schemes.
• Translate a virtual address into a physical address given a page table and page size.
• Trace FIFO, LRU, and Optimal page replacement algorithms on a given reference string and count page faults.
• Define thrashing, explain why it happens, and describe how the working set model helps prevent it.
• Explain what a TLB is, why it exists, and how it affects address translation performance.

Quick Answer

Memory management is the part of the operating system that decides where in RAM each process's code and data live, and how the CPU's memory addresses get translated into actual physical locations. Modern OSes use virtual memory: each process sees its own private, contiguous address space, while the OS secretly maps it onto scattered physical frames using paging (fixed-size blocks) or segmentation (logical, variable-size chunks). This matters because it lets multiple processes share limited RAM safely, run programs larger than physical memory, and stay isolated from each other. When RAM gets tight, the OS decides which pages to evict using algorithms like FIFO, LRU, or Optimal — get this wrong and the system spends more time swapping pages than doing real work, a state called thrashing.

Core Concepts

Logical vs. Physical Addresses

A running process only ever deals in logical (virtual) addresses — numbers relative to its own private address space, starting conceptually at 0. The Memory Management Unit (MMU), a piece of hardware, translates every logical address into a physical address before it hits the actual RAM chip. The process never needs to know (or be able to find out) where it truly lives in RAM.

Contiguous Allocation

The earliest approach: give each process one unbroken block of physical memory.

• Fixed partitioning — memory is divided into fixed-size regions ahead of time. Simple, but causes internal fragmentation (a 200 KB process in a 512 KB partition wastes 312 KB).
• Variable partitioning — partitions are sized exactly to each process. This avoids internal fragmentation but creates external fragmentation: free memory exists but is split into gaps too small individually to satisfy new requests.
• Allocation strategies for variable partitioning: First-Fit (use the first hole big enough), Best-Fit (use the smallest hole that fits, minimizes leftover but creates tiny unusable slivers), Worst-Fit (use the largest hole, leaves a more usable leftover chunk but is often slow).

Contiguous allocation is largely a historical/foundational model now — real systems use paging or segmentation because a process's memory doesn't need to be physically contiguous at all.

Paging

Paging splits both physical memory and each process's logical address space into fixed-size blocks:

• Frames — fixed-size chunks of physical RAM (commonly 4 KB on x86/x86-64 and ARM Linux systems; some systems support 2 MB or 1 GB "huge pages" to reduce translation overhead).
• Pages — same-size chunks of a process's logical address space.
• Page table — a per-process array mapping each virtual page number to a physical frame number.

Because any page can live in any free frame, paging eliminates external fragmentation entirely. It still has internal fragmentation, but it's bounded to less than one page size per process (at most 4 KB of waste per segment of memory used, not megabytes).

Multi-level page tables. A single flat page table for a 64-bit address space would itself be enormous, so real systems use hierarchical (multi-level) page tables — x86-64 typically uses four levels — so that unused regions of the address space don't need table entries allocated at all.

Address Translation Worked Example

Suppose a system uses 4 KB pages (2^12 bytes, so the offset is 12 bits) and a process has the following page table:

Virtual Page #	Frame #
0	5
1	2
2	9

Translate virtual address 0x2050 (decimal 8272) to a physical address.

1. Split the virtual address into page number and offset. With a 12-bit offset, the low 12 bits are the offset, and the remaining high bits are the page number. 0x2050 = 0010 0000 0101 0000 (binary). Offset = low 12 bits = 0000 0101 0000 = 0x050 = 80. Page number = remaining bits = 0010 = 2.
2. Look up page 2 in the page table → frame 9.
3. Physical address = (frame number × page size) + offset = (9 × 4096) + 80 = 36864 + 80 = 36944 (0x9050).

Notice the offset bits (050) are identical in both the virtual and physical address — only the page/frame number part changes. This is the core trick of paging.

Segmentation

Segmentation divides a process's address space into logically meaningful, variable-length units — code segment, stack segment, heap segment, data segment — each with its own base and limit (length) stored in a segment table. This matches how programmers and compilers naturally think about a program, and makes it easy to grow the stack or heap independently and to share a code segment read-only between processes.

The tradeoff: because segments are variable size, segmentation reintroduces external fragmentation, the very problem paging was designed to solve. Many real systems (like x86 historically) combined the two into segmentation with paging, where each segment is itself paged internally.

Virtual Memory and Demand Paging

Virtual memory lets a process's total address space exceed physical RAM by keeping only the actively used pages in memory and the rest on disk (in a swap file or swap partition). With demand paging, a page is loaded from disk only the first time it's actually accessed, not when the process starts.

• Page fault — occurs when a process accesses a page not currently in RAM. The OS traps this, finds/creates a free frame, loads the page from disk, updates the page table, and resumes the process. A page fault is transparent to the program — it just sees a (slightly slow) memory access.
• Linux implements this with its own demand-paging subsystem; when physical memory and swap both run critically low, the kernel's OOM (out-of-memory) killer steps in and forcibly terminates a process to recover memory rather than let the whole system grind to a halt.
• Windows has an equivalent component, the Virtual Memory Manager (VMM), which manages the pagefile (pagefile.sys) and working sets per process.

Page Replacement Algorithms

When RAM is full and a new page must be loaded, the OS must evict an existing page. Which one it picks has a huge effect on performance.

Reference string: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2 with 3 frames available.

FIFO (First-In, First-Out). Evict whichever page has been in memory longest, regardless of use.

Step	Ref	Frames after	Fault?
1	7	7	Fault
2	0	7,0	Fault
3	1	7,0,1	Fault
4	2	0,1,2	Fault (evict 7)
5	0	0,1,2	Hit
6	3	1,2,3	Fault (evict 0)
7	0	2,3,0	Fault (evict 1)
8	4	3,0,4	Fault (evict 2)
9	2	0,4,2	Fault (evict 3)
10	3	4,2,3	Fault (evict 0)
11	0	2,3,0	Fault (evict 4)
12	3	2,3,0	Hit
13	2	2,3,0	Hit

FIFO total: 10 faults.

LRU (Least Recently Used). Evict the page that hasn't been used for the longest time.

Step	Ref	Frames after	Fault?
1	7	7	Fault
2	0	7,0	Fault
3	1	7,0,1	Fault
4	2	0,1,2	Fault (evict 7, least recently used)
5	0	0,1,2	Hit
6	3	0,2,3	Fault (evict 1)
7	0	0,2,3	Hit
8	4	0,3,4	Fault (evict 2)
9	2	0,4,2	Fault (evict 3)
10	3	4,2,3	Fault (evict 0)
11	0	2,3,0	Fault (evict 4)
12	3	2,3,0	Hit
13	2	2,3,0	Hit

LRU total: 9 faults — one better than FIFO here, because LRU keeps page 0 (repeatedly reused) around longer instead of evicting it on schedule.

Optimal (Belady's algorithm). Evict whichever page will be used furthest in the future (or never again). This is provably the best possible algorithm, but it requires knowing the future reference string in advance, so it's only usable as a theoretical benchmark, not a real OS policy. On this same reference string, Optimal achieves 7 faults — fewer than both FIFO and LRU — which is exactly why it's used as the yardstick for judging real algorithms.

Real operating systems approximate LRU cheaply using a clock (second-chance) algorithm, since true LRU requires tracking exact access order, which is expensive at scale.

Thrashing

Thrashing occurs when the system is so overcommitted on memory that processes spend more time faulting pages in and out than executing instructions — CPU utilization actually drops even though the system looks maximally busy, because most cycles go to disk I/O wait. The classic cause is running too many processes for the available RAM, each with a working set (the set of pages it needs resident to make progress without constantly faulting) that no longer fits.

Fixes: reduce the degree of multiprogramming (run fewer processes at once), add more physical RAM, or use the working-set model to admit new processes only when enough frames are free to hold their working set.

Translation Lookaside Buffer (TLB)

Walking a multi-level page table on every memory access would be prohibitively slow — for a 4-level table, a single memory reference could require 4 extra memory reads just for translation. The TLB is a small, very fast hardware cache inside the MMU that stores recent virtual-to-physical translations.

• TLB hit — the translation is found in the TLB; address translation completes in essentially zero extra time.
• TLB miss — the CPU must walk the page table (or the OS handles it in software on some architectures), then caches the result in the TLB.
• Because the TLB is tied to a specific process's address space, switching processes (a context switch) can invalidate TLB entries — one reason context switches are costly. Some CPUs tag TLB entries with an address-space ID to avoid full flushes on every switch.

Key Terms

Term	Definition	Context/Related
Logical (virtual) address	An address generated by the CPU relative to a process's own address space	Translated by the MMU into a physical address
Physical address	The actual location in RAM hardware	Target of address translation
Page	A fixed-size block of a process's virtual address space (commonly 4 KB)	Paired with frames via the page table
Frame	A fixed-size block of physical RAM, same size as a page	Where pages are actually stored
Page table	Per-process data structure mapping virtual pages to physical frames	Walked on a TLB miss
Segment	A variable-length logical unit of a process (code, stack, heap, data)	Alternative to/combinable with paging
Page fault	Trap raised when a process accesses a page not currently in RAM	Triggers demand paging
Thrashing	State where the system spends more time paging than executing	Caused by working sets exceeding available RAM
Working set	The set of pages a process needs resident to run without excessive faulting	Basis of the working-set admission model
TLB (Translation Lookaside Buffer)	Small hardware cache of recent virtual-to-physical translations	Avoids repeated page table walks
Internal fragmentation	Wasted space inside an allocated block that's larger than needed	Seen in fixed partitioning and paging (last page)
External fragmentation	Wasted space between allocated blocks, too small individually to use	Seen in variable partitioning and segmentation
Belady's Anomaly	The counter-intuitive case where adding more frames increases FIFO's fault count	Does not occur with LRU or Optimal

Common Mistakes

Misconception 1: "Paging causes external fragmentation just like variable partitioning." Why it's wrong: Students conflate paging with contiguous variable-size allocation because both involve "blocks" of memory. Correct explanation: Because every page and frame is exactly the same fixed size, any free frame can hold any page — there's no way for oddly-shaped gaps to accumulate. Paging only has (bounded) internal fragmentation, in the last, partially-used page of a process.

Misconception 2: "LRU is always better than FIFO, so real operating systems just implement true LRU." Why it's wrong: This ignores the practical cost of the two algorithms — the worked example above happens to favor LRU, but real systems don't use exact LRU regardless. Correct explanation: True LRU requires hardware or software to timestamp or track every single memory access, which is too expensive at scale. Real OSes use cheaper approximations, like the clock/second-chance algorithm, that behave similarly to LRU without that overhead. Also, LRU is not universally optimal — Optimal (Belady's) beats it on some reference strings, and LRU can perform worse than FIFO on others.

Misconception 3: "A page fault means the program did something wrong and will crash." Why it's wrong: Learners hear "fault" and assume it means "error," conflating it with a segmentation fault (illegal access), which is a genuinely different, fatal event. Correct explanation: A (valid) page fault is a completely normal, expected part of demand paging — it just means the needed page isn't currently in RAM and must be fetched from disk or the swap file. The OS handles it transparently and the program resumes as if nothing happened, just a bit slower. Only an invalid page fault, e.g. accessing memory outside any of the process's valid segments, becomes a real segmentation fault that kills the process.

Comparison and Connections

Aspect	Paging	Segmentation
Unit size	Fixed (e.g., 4 KB)	Variable (matches logical unit, e.g. a function or the stack)
Basis of division	Physical/mechanical, arbitrary boundaries	Logical, matches program structure
External fragmentation	None	Yes, can occur
Internal fragmentation	Yes, up to one page per process	None (segment sized exactly to need)
Sharing code between processes	Possible but coarse-grained	Natural — share a whole segment
Programmer visibility	Invisible to programmer	Can be partly visible (base+limit per segment)

Algorithm	Needs future knowledge?	Faults on example (3 frames)	Real-world use
FIFO	No	10	Rarely used alone; simple but can suffer Belady's Anomaly
LRU	No (needs recent history)	9	Approximated via clock/second-chance in real OSes
Optimal (Belady's)	Yes (impossible in practice)	7	Theoretical benchmark only

Practice Questions

Recall

1. What is the difference between a page and a frame? Answer guidance: A page is a fixed-size unit of a process's virtual address space; a frame is a fixed-size unit of physical RAM, the same size as a page. Pages are mapped onto frames via the page table.

2. What triggers a page fault, and what does the OS do in response? Answer guidance: Accessing a page not currently resident in RAM. The OS traps the access, locates or creates a free frame, loads the page from disk (or the swap file), updates the page table, and resumes the process at the faulting instruction.

Understanding

3. Why does paging eliminate external fragmentation while segmentation does not? Answer guidance: All pages and frames are exactly the same fixed size, so any free frame fits any page — no leftover unusable gaps form. Segments are variable length, so as they're allocated and freed, gaps of varying (and sometimes unusable) sizes appear between them.

4. Why is a true LRU implementation impractical on real hardware, and what do real systems use instead? Answer guidance: True LRU requires tracking the exact recency order of every memory access, which needs expensive hardware support or software bookkeeping on every access. Real systems approximate it with algorithms like clock/second-chance, which use a reference bit rather than exact ordering.

Application

5. Given 4 KB pages and the page table {0→3, 1→7, 2→1}, translate virtual address 0x1800 to a physical address. Show your work. Answer guidance: Offset bits = 12. 0x1800 = binary 0001 1000 0000 0000. Offset = low 12 bits = 1000 0000 0000 = 0x800 = 2048. Page number = remaining bits = 0001 = 1. Page 1 → frame 7. Physical address = (7 × 4096) + 2048 = 28672 + 2048 = 30720 (0x7800).

6. For reference string 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 with 4 frames, how many page faults does FIFO produce? (Bonus: does this reference string exhibit Belady's Anomaly if frames are reduced to 3?) Answer guidance: With 4 frames, FIFO faults on 1,2,3,4 (fill), then 1,2 hit, then 5 faults (evict 1), then 1 faults (evict 2), then 2 faults (evict 3), then 3 faults, then 4 faults, then 5 hits → 10 faults total. This particular string is a commonly cited example (Belady's original) where reducing frames from 4 to 3 with FIFO can actually increase faults — demonstrating Belady's Anomaly — whereas LRU would not show this behavior.

Analysis

7. A system is thrashing badly. Explain two different fixes and the tradeoff of each. Answer guidance: (a) Reduce the degree of multiprogramming — kill or suspend some processes so remaining ones' working sets fit in RAM; tradeoff is lower system throughput/fewer concurrent users. (b) Add more physical RAM; tradeoff is cost and a hardware/hardware-availability limit, not an immediate software fix. A third option, using the working-set model to refuse to start new processes until enough frames are free, trades some admission latency for stability.

8. Why can a context switch between two processes be expensive with respect to the TLB, and how do modern CPUs mitigate this? Answer guidance: Each process has its own address space and page table, so the previous process's cached translations in the TLB become invalid for the incoming process; naive designs flush the whole TLB on every switch, causing a burst of TLB misses (and page-table walks) right after the switch. Modern CPUs mitigate this by tagging TLB entries with an address-space identifier (ASID/PCID), so entries for multiple processes can coexist and don't need to be flushed on every switch.

FAQ

Q: Is virtual memory the same thing as swap space? A: No. Virtual memory is the overall abstraction that gives each process its own private address space, larger than physical RAM if needed. Swap space (a disk partition or file) is just the backing storage virtual memory uses to hold pages that don't currently fit in RAM. You can have virtual memory (address space abstraction) with paging even with generous physical RAM and rarely touch swap.

Q: Why do modern systems mostly use paging instead of pure segmentation? A: Paging's fixed-size units make allocation bookkeeping simple and completely avoid external fragmentation, which matters enormously at the scale of gigabytes of RAM and many processes. Segmentation is more "natural" for programmers but its fragmentation problems don't scale well, so most systems today use paging, sometimes with segmentation layered on top for logical structure (as older x86 did).

Q: What's the practical effect of a TLB miss on performance? A: Instead of one fast RAM access, the CPU/OS has to walk the (potentially multi-level) page table, each level itself requiring a memory access, before it can even do the "real" memory access the program wanted. On a 4-level page table, a TLB miss can turn one memory reference into 5 (four table walks plus the real access), making TLB hit rate a major factor in real-world performance.

Q: Can page replacement algorithms guarantee zero page faults? A: No — the very first access to any page is always a fault (called a "cold" or "compulsory" fault) because nothing has been loaded yet. Page replacement algorithms only control which page gets evicted once memory is full; they can't eliminate the unavoidable faults needed to bring pages in for the first time.

Q: Why does adding more RAM sometimes not fix thrashing? A: If the added RAM still isn't enough to hold the combined working sets of all currently-running processes, the system will keep thrashing, just slightly less severely. Thrashing is fundamentally a mismatch between demand (working sets) and supply (available frames) — the real fix is making sure that mismatch is closed, whether via more RAM, fewer processes, or smarter working-set-aware scheduling.

Quick Revision

• Logical (virtual) addresses are translated to physical addresses by the MMU; the process never sees real physical addresses.
• Contiguous allocation gives each process one solid block; suffers internal fragmentation (fixed partitions) or external fragmentation (variable partitions).
• Paging splits memory into fixed-size pages/frames (commonly 4 KB) — eliminates external fragmentation, has bounded internal fragmentation.
• Segmentation splits memory into variable-size logical units (code, stack, heap) — matches program structure, but reintroduces external fragmentation.
• Address translation: physical address = (frame number × page size) + offset; offset bits come straight from the virtual address unchanged.
• FIFO evicts the oldest-loaded page; simple but can suffer Belady's Anomaly (more frames → more faults).
• LRU evicts the least-recently-used page; better in practice than FIFO but expensive to implement exactly, so it's approximated (clock/second-chance algorithm).
• Optimal (Belady's) evicts the page used furthest in the future; best possible but requires knowing the future, so it's a theoretical benchmark only.
• A page fault is normal (demand paging); it's only fatal if the access is invalid (true segmentation fault).
• Thrashing = system spends more time paging than computing; fix by reducing multiprogramming, adding RAM, or using the working-set model.
• TLB caches recent virtual-to-physical translations to avoid repeated, expensive page-table walks on every memory access.
• Linux uses demand paging plus an OOM killer as a last resort; Windows uses its Virtual Memory Manager and a pagefile.

Related Topics

Prerequisites: Process Management and Scheduling

Related Topics: CPU Scheduling Algorithms, Deadlocks and Synchronization, Storage Devices and I/O Management

Next Topics: File Systems