Memory management and virtual memory

In short

Memory management is the part of the operating system that decides which process occupies which physical memory, translates the addresses a program uses into real RAM addresses, and protects one process's memory from another. Virtual memory extends this so a process can run with only part of its address space resident, using the disk (swap) as an extension of RAM; this is what lets a 2 GB build run on a 4 GB laptop alongside a browser. The topic is the heaviest-scoring OS area in GATE CS (address splitting, page-table size, effective access time, page-replacement traces are near-certain questions) and is standard in placement technical rounds at TCS, Infosys, Wipro, Cognizant and in system-design/debugging interviews at Amazon, Microsoft IDC, Oracle, VMware, Qualcomm and Samsung R&D. On the job it decides JVM heap sizing, container memory limits, DBMS buffer-pool tuning and why an embedded board without an MMU behaves differently.

Explained

Address binding, protection and swapping

• Logical (virtual) address is generated by the CPU; physical address is what the memory unit sees. The MMU (memory management unit, hardware) translates one into the other on every access.
• Binding times: *compile time* (absolute addresses, used in simple embedded firmware), *load time* (relocatable code fixed by the loader), *execution time* (needs MMU support — required for swapping and virtual memory).
• Base and limit registers: the simplest hardware protection — physical address = logical + base, and any logical address ≥ limit raises a trap (addressing error → SIGSEGV on Linux).
• Swapping: a whole process is moved out to a backing store and back later. Modern systems swap *pages*, not whole processes; full-process swapping survives only as "suspend".
• Dynamic loading loads a routine only when first called; dynamic linking with shared libraries (.so, DLL) keeps one copy of library code in memory for many processes; overlays were the pre-virtual-memory manual technique.

Contiguous allocation and fragmentation

• Single contiguous allocation: one user process at a time (MS-DOS style). Fixed (static) partitions: memory divided in advance; degree of multiprogramming = number of partitions.
• Variable (dynamic) partitions: the OS keeps a list of holes and cuts a partition to fit; requires a placement policy:
  • First fit — first hole big enough; fastest.
  • Best fit — smallest hole big enough; must search the whole list, leaves tiny useless slivers.
  • Worst fit — largest hole; generally performs worst.
  • Next fit — first fit resuming from the last allocation point.
• Internal fragmentation: memory allocated to a process but unused inside its block (whole-page rounding).
• External fragmentation: free memory exists but is split into holes too small to use. Cured by compaction (only possible with execution-time binding; expensive) or avoided by paging.
• 50-percent rule: with first fit, statistically about 0.5N blocks are lost to fragmentation for N allocated blocks — roughly one-third of memory unusable.

Paging

• Physical memory is split into fixed-size frames, logical memory into equal-size pages (typically 4 KB; x86 also supports 2 MB/1 GB huge pages).
• A logical address splits into page number p (index into the page table) and offset d (copied through unchanged). Physical address = frame number f concatenated with d.
• The page table is per process; the PTBR (page-table base register) is reloaded on context switch. A PTE holds the frame number plus valid/invalid, protection (r/w/x), dirty (modified), reference (accessed) and caching bits.
• No external fragmentation at all; internal fragmentation is at most one page per process (average half a page).
• TLB (translation look-aside buffer): a small, fully associative cache of recent PTEs inside the MMU. A TLB hit needs no memory reference for translation; a miss costs an extra memory access (or a page-table walk). TLB entries carry an ASID so the TLB need not be flushed entirely on every context switch.
• Structures for large address spaces:
  • Hierarchical (multi-level) paging — the page table is itself paged; x86-64 uses 4 levels of 9 bits each over 4 KB pages (48-bit VA), with optional 5-level paging for 57-bit VA.
  • Hashed page table — virtual page number hashed into a chain; used on some 64-bit RISC designs.
  • Inverted page table — one entry per *frame* (not per page), so its size depends on RAM, not on address-space size; shared memory becomes harder.
• Shared pages: reentrant code (libc, a text editor's text segment) mapped into many processes' page tables pointing at the same frames.

Segmentation and the x86 hybrid

• Segmentation gives the programmer a view of memory as variable-length logical units — code, data, stack, heap, a table — addressed as <segment number, offset>.
• The segment table holds a base and limit per segment; offset ≥ limit is a trap. Protection and sharing are natural because a segment is a logical object.
• Drawback: variable sizes bring back external fragmentation.
• Segmentation with paging: each segment is paged (Intel 80386 onwards, MULTICS). This gives segmentation's logical structure with paging's fragmentation-free allocation. On x86-64, segmentation is largely vestigial (flat model) except for FS/GS bases used for thread-local storage.

Virtual memory and demand paging

• Virtual memory separates logical address space from physical memory, so a program may be larger than RAM, more processes fit, and less I/O is needed at start-up.
• Demand paging: a page is brought in only on first reference. Pure demand paging starts a process with zero resident pages. Prepaging loads a group of pages in anticipation.
• Page-fault handling (steps):
  1. MMU finds the valid bit clear → trap to the OS.
  2. OS checks whether the address is legal (in a valid mapping) — if not, terminate the process (segmentation fault).
  3. Find a free frame; if none, run the page-replacement algorithm to pick a victim.
  4. If the victim is dirty, write it to swap (clean pages are simply dropped).
  5. Schedule a disk/SSD read of the wanted page into the frame; the process blocks.
  6. On I/O completion, update the page table and TLB, set valid.
  7. Restart the faulting instruction exactly.
• Instruction restart needs care: an instruction that modified memory before faulting (block move with overlapping source/destination, auto-increment addressing) must be made restartable by the hardware or undone.
• Copy-on-write: fork() maps the child's pages to the parent's frames read-only; the first write to a page faults and copies only that page. Makes fork()+exec() cheap. Zero-filled-on-demand is the analogue for a fresh heap/stack page.
• **Memory-mapped files (mmap)** treat file I/O as memory access; the page cache holds the pages, and writes are flushed lazily. Shared mappings give shared memory.
• Locked (pinned) frames: needed for DMA buffers during I/O (I/O interlock) and kernel code; mlock() prevents eviction.

Page-replacement algorithms

• FIFO: evict the oldest-loaded page. Simple; suffers Belady's anomaly — more frames can mean *more* faults.
• Optimal (OPT / MIN): evict the page that will not be used for the longest time. Lowest possible fault count but needs the future — used only as a benchmark.
• LRU: evict the least recently used page. A stack algorithm, so no Belady's anomaly. Exact implementation needs a counter per PTE or a doubly linked stack updated on *every* reference — too costly in software, so it is approximated.
• LRU approximations:
  • Second chance / Clock: circular scan of frames; if the reference bit is 1, clear it and move on; evict the first page with reference bit 0.
  • Enhanced second chance: uses (reference, dirty) pairs; prefers (0,0), then (0,1), then (1,0), then (1,1) — avoids writing back dirty pages.
  • Additional-reference-bits / NRU: shift the reference bit into an 8-bit history byte periodically; smallest byte value is the victim.
• Counting: LFU (least frequently used — a page heavily used once stays forever unless counts are aged) and MFU; both are rare in practice.
• Page buffering: keep a pool of free frames so a fault can be served immediately, and write dirty pages out in the background (Linux kswapd, Windows modified-page writer).
• Linux uses two LRU-ish lists (active/inactive, split for anon and file pages) with reference bits, plus swappiness to bias between dropping file cache and swapping anonymous pages; it ends with the OOM killer when reclaim fails.

Frame allocation, thrashing and the working set

• Minimum frames per process is set by the instruction set (an instruction with indirect operands may need several frames to complete).
• Allocation policies: equal (m/n frames each), proportional (by process size), priority-weighted.
• Local replacement takes a victim from the faulting process's own frames (predictable performance); global replacement takes it from any process (better throughput, but one process's behaviour hurts another's).
• Thrashing: processes spend more time paging than executing; CPU utilisation collapses while the paging device saturates. Trigger: the degree of multiprogramming is raised until Σ(working-set sizes) exceeds available frames — and a global-replacement scheduler that sees low CPU use *adds* more processes, making it worse.
• Working-set model (Denning): WS(t, Δ) = the set of pages referenced in the last Δ references; WSS is its size. Policy: suspend (swap out) a process if ΣWSS > m. Δ too small misses locality; too large spans several localities.
• Page-fault-frequency (PFF) control: measure each process's fault rate; above an upper bound give it a frame, below a lower bound take one away; if no frames are free, suspend a process.
• Locality of reference is why all of this works; a program's references cluster, so a small resident set serves most accesses.
• Page-size trade-off: large pages → smaller page tables, better TLB reach, fewer faults per byte transferred, but more internal fragmentation and more unnecessary I/O. Trend is towards larger and multiple page sizes (transparent huge pages).
• Kernel memory is not paged like user memory: the buddy system allocates power-of-two frame blocks, and the slab/SLUB allocator carves caches of same-size kernel objects (inodes, task_structs) to avoid fragmentation.
• Practice note: memory contents are data. Core dumps, swap and container images can carry personal data, so production systems commonly disable core dumps or encrypt swap — relevant to the "reasonable security safeguards" duty on data fiduciaries under India's Digital Personal Data Protection Act, 2023 (rules have been notified in phases; check the current text before quoting specifics).

Key points

• Logical vs physical address - logical is CPU-generated, physical is RAM-level; MMU translates on every access.
• Paging - fixed-size pages and frames; eliminates external fragmentation, leaves ≤1 page internal per process.
• Page table - per-process map from page number to frame number, plus valid, dirty, reference and protection bits.
• Offset is never translated - only the page/segment number is looked up; the offset passes straight through.
• TLB - MMU-level cache of PTEs; hit ratio dominates effective access time.
• Multi-level paging - pages the page table itself; makes sparse 48-bit address spaces affordable at the cost of extra walks.
• Inverted page table - one entry per frame, so size scales with RAM, not with address space.
• Segmentation - variable-length logical units with base and limit; natural protection, but external fragmentation.
• Demand paging - bring a page in on first reference; valid bit clear triggers the page fault.
• Page fault vs segmentation fault - a fault on a valid-but-not-resident page is serviced; a fault on an unmapped address kills the process.
• Copy-on-write - share frames read-only after fork, copy only the page actually written.
• Belady's anomaly - FIFO can fault more with more frames; stack algorithms (LRU, OPT) cannot.
• LRU is approximated, not implemented exactly — clock/second chance with reference bits is what real kernels use.
• Dirty bit saves a disk write when the victim page is unmodified.
• Thrashing - ΣWSS > available frames; fix by reducing multiprogramming or adding RAM, not by faster paging.
• Working set - pages referenced in the last Δ references; the resident set a process needs to run without thrashing.
• Local vs global replacement - own frames only (predictable) vs any process's frames (higher throughput).
• Buddy and slab allocators manage non-pageable kernel memory.

Formulas and examples

1. Address splitting and page-table size. 32-bit logical addresses, 4 KB pages, 4-byte PTE, 1 GB RAM.

• Offset = log2(4096) = 12 bits; page number = 32 − 12 = 20 bits → 2²⁰ = 1,048,576 pages.
• Flat page table = 1,048,576 × 4 B = 4 MB per process — far too big to keep contiguously for hundreds of processes.
• Frames = 1 GB / 4 KB = 262,144, needing 18 bits of frame number (physical address 30 bits).
• Two-level split 10 | 10 | 12: outer table 1,024 × 4 B = 4 KB, each inner table 4 KB; a process touching 3 regions needs 4 KB + 3 × 4 KB = 16 KB instead of 4 MB. Cost: 2 memory accesses for the walk (3 total on a TLB miss).
• For 48-bit VA with 4 KB pages, a flat table would be 2³⁶ × 8 B = 512 GB — the reason x86-64 uses 4 levels.

2. Effective access time. TLB search 20 ns, memory access 100 ns.

• h = 80%: EAT = 0.80 × (20 + 100) + 0.20 × (20 + 200) = 96 + 44 = 140 ns (40% slowdown over raw 100 ns).
• h = 98%: EAT = 0.98 × 120 + 0.02 × 220 = 117.6 + 4.4 = 122 ns → only 22% slowdown; the TLB hit ratio is what matters.
• Demand paging: ma = 200 ns, page-fault service = 8 ms = 8,000,000 ns, p = 0.001. EAT = 0.999 × 200 + 0.001 × 8,000,000 = 199.8 + 8,000 = 8,199.8 ns ≈ 8.2 µs — a 41× slowdown.
• For under 10% degradation (EAT ≤ 220 ns): 220 ≥ 200 + p × 8,000,000 → p ≤ 20/8,000,000 = 2.5 × 10⁻⁶, i.e. fewer than one fault per 400,000 accesses.

3. Page replacement. Reference string 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 (12 references).

FIFO with 3 frames, step by step: 1F[1] 2F[1,2] 3F[1,2,3] 4F evict 1→[2,3,4] 1F evict 2→[3,4,1] 2F evict 3→[4,1,2] 5F evict 4→[1,2,5] 1H 2H 3F evict 1→[2,5,3] 4F evict 2→[5,3,4] 5H = 9 faults, 3 hits. With 4 frames the same string gives 10 faults — proof that FIFO is not a stack algorithm. Optimal with 3 frames faults at references 1,2,3,4,7,10,11 = 7.

4. Fits and internal fragmentation. Holes in order: 100K, 500K, 200K, 300K, 600K. Requests in order: 212K, 417K, 112K, 426K.

• Internal fragmentation under paging: a 72,766-byte process with 2,048-byte pages needs ceil(72,766/2,048) = ceil(35.53) = 36 pages = 73,728 bytes allocated → 962 bytes wasted (less than half a page, as expected).

5. Segmentation translation and thrashing. Segment table: s0 base 1400 limit 1000; s1 base 6300 limit 400; s2 base 4300 limit 400; s3 base 3200 limit 1100.

• (0, 430) → 430 < 1000 → physical 1830.
• (2, 53) → 53 < 400 → physical 4353.
• (1, 500) → 500 ≥ 400 → trap: addressing error.
• Thrashing check: three processes with WSS 20, 35 and 45 frames need 100 frames; the machine has 90 → ΣWSS > m, so one process must be suspended or given fewer frames (and the system will thrash if the scheduler instead admits a fourth process).

Where it is used

• Cloud and backend engineering (Flipkart, Zomato, Swiggy, Razorpay, PhonePe): sizing JVM/Node heaps against container memory.limit_in_bytes; a cgroup OOM kill in Kubernetes is page-reclaim failure, diagnosed with free, vmstat, /proc/<pid>/smaps and RSS vs VSZ.
• Databases and caches (Oracle, Postgres, MySQL, Redis deployments): buffer-pool/shared-buffers tuning, huge pages for the SGA, mmap-based storage engines, and why Redis fork() for RDB snapshots relies on copy-on-write.
• Embedded and automotive (Bosch, Qualcomm, Samsung R&D, ISRO/DRDO labs): MMU-less microcontrollers use static allocation and MPU regions instead of paging; RTOS code avoids demand paging because a page fault destroys determinism.
• Mobile (Android, Jio, Samsung): no swap by default; the low-memory killer and ZRAM (compressed in-RAM swap) replace disk paging, so app lifecycle and memory trimming matter.
• Systems, SRE and performance roles: reading page-fault counts (minor vs major) in /proc/<pid>/stat, perf, pmap; tuning vm.swappiness, overcommit_memory, THP on or off for latency-sensitive services.
• Exams and recruitment: GATE CS (OS section), ISRO/BARC/DRDO scientist papers, UGC-NET CS, PSU interviews, and the OS round in most Indian product-company placements.

Interview questions

• Q: What is the difference between a logical and a physical address? A: A logical address is generated by the CPU relative to the process's address space; the MMU translates it to a physical address in RAM at run time. The process never sees physical addresses.
• Q: Why does paging remove external fragmentation but not internal? A: Any free frame fits any page because all are the same size, so no unusable holes form; but the last page of a process is usually partly empty, wasting on average half a page.
• Q: What happens on a page fault, step by step? A: Trap to the kernel, validate the address, find or free a frame (writing back the victim if dirty), read the page from swap or file, update the page table and TLB, then restart the faulting instruction.
• Q: Difference between a page fault and a segmentation fault? A: A page fault is normal — the page is valid but not resident, and the OS services it. A segmentation fault means the address is not mapped at all or violates permissions, and the process is killed with SIGSEGV.
• Q: Why is a TLB needed and what happens on a context switch? A: Without it every access would need an extra memory read for the page table. On a context switch the TLB must be flushed or distinguished by address-space IDs, otherwise stale translations would leak between processes.
• Q: What is Belady's anomaly and which algorithms avoid it? A: FIFO can produce more page faults with more frames. Stack algorithms — LRU and OPT — cannot, because their resident set with n frames is always a subset of that with n+1.
• Q: Why is true LRU not implemented in hardware/OS? A: It needs a timestamp or list update on *every* memory reference, which is prohibitively expensive, so kernels approximate it with reference bits and the clock algorithm.
• Q: What is thrashing and how do you fix it? A: The system pages so heavily that CPU utilisation collapses because the sum of working sets exceeds available frames. Fix by reducing the degree of multiprogramming (suspend processes), using local replacement/working-set or PFF control, or adding RAM — a faster disk only hides it.
• Q: How does copy-on-write help fork()? A: Parent and child initially share frames marked read-only; only a page that is actually written gets duplicated, so forking a large process is cheap and exec() wastes no copying.
• Q: Paging versus segmentation — which is better and why do x86 systems combine them? A: Paging gives fragmentation-free allocation but no logical structure; segmentation gives logical, shareable, protectable units but suffers external fragmentation. Paged segmentation gets the protection and sharing of segments with the allocation behaviour of pages.
• Q: What are the costs and benefits of a larger page size? A: Smaller page tables, better TLB reach and fewer faults per byte read, against more internal fragmentation and transferring data that may never be used.
• Q: Can a process's virtual size exceed physical RAM plus swap? A: Yes, if the OS overcommits — Linux allows reservations beyond backing store (vm.overcommit_memory), which is why malloc can succeed and the OOM killer fire later on first touch.

Common mistakes

• Translating the offset as well as the page number; only the page/segment number is looked up, the offset is copied through.
• Using the logical address size to compute frame-number bits (frame bits come from *physical* memory size) or forgetting that page and frame sizes are always equal.
• Rounding pages down: pages needed is ceil(size / page size) — a 10 B leftover still costs a whole page.
• Claiming paging has no fragmentation at all, or that segmentation has internal fragmentation (it has external).
• Mixing units in EAT problems — page-fault service in milliseconds against memory access in nanoseconds; convert first (1 ms = 10⁶ ns).
• Running a replacement trace without stating the convention: a reference already resident is a hit with no change of frames (but LRU must still update recency), and the first references are compulsory faults.
• Treating LRU as always better than FIFO; on a looping reference string slightly larger than the frame count, LRU can be the worst possible choice.
• Diagnosing a thrashing system as "needs a faster disk" instead of "resident sets do not fit".

Related topics

Processes and threads · CPU scheduling · File systems and disk scheduling · I/O systems and device management · Virtualisation and containers · Cache memory and memory hierarchy (Computer Organisation)