Memory Management, Paging & Virtual Memory

1. What is memory management in an OS?

Memory management is the OS function that handles allocation and deallocation of memory to processes. It tracks which parts of memory are in use, allocates memory to new processes, and frees it when processes terminate.

It also provides protection — each process’s memory is isolated so one process can’t read or corrupt another — and it supports the virtual memory illusion that lets processes see a larger, contiguous address space than the physical RAM installed.

2. What is the difference between contiguous and non-contiguous allocation?

Contiguous allocation gives each process a single contiguous block of physical memory. It’s simple and fast for address translation, but it suffers from external fragmentation — holes form as processes come and go, and a new process may not fit even though total free memory is sufficient.

Non-contiguous allocation splits a process across multiple, non-adjacent memory blocks. Paging uses fixed-size pages placed in arbitrary frames (suffers internal fragmentation, no external). Segmentation uses variable-size logical segments (suffers external fragmentation). Non-contiguous allocation solves the “can’t find one big block” problem at the cost of more complex address translation.

3. What is the difference between internal and external fragmentation?

Internal fragmentation is wasted space inside an allocated block — the block is larger than what the process requested. For example, a 14KB process in a 16KB fixed partition wastes 2KB. It occurs with fixed-size partitions and with paging: the last page of a process is rarely full.

External fragmentation is free space scattered in small holes across memory. Total free memory is sufficient, but no single contiguous block is large enough for a request. It occurs with contiguous allocation and segmentation. The classic fix is compaction, but paging eliminates it entirely by removing the need for contiguous blocks.

4. What is paging and how does address translation work?

Paging divides physical memory into fixed-size frames and logical memory into pages of the same size (typically 4KB). A per-process page table maps each virtual page number to a physical frame number.

A logical address is split into [page number | offset]. The CPU’s MMU looks up the page number in the page table, finds the frame number, and concatenates it with the offset to form the physical address. Paging eliminates external fragmentation completely — pages can land in any free frame — at the cost of internal fragmentation from partially-filled last pages.

5. What is a page table and what is a TLB?

A page table is a per-process data structure mapping virtual page numbers to physical frame numbers. The CPU’s MMU uses it to translate every memory address.

The TLB (Translation Lookaside Buffer) is a fast hardware cache that stores recent page-to-frame translations. Without it, every memory access would require two physical accesses — one to read the page table, one for the actual data — doubling memory latency. The TLB caches recent translations in fast CPU memory (usually fully associative), making the common case a single access. A TLB miss requires walking the page table and possibly flushing on context switch.

6. What is segmentation and how does it compare to paging?

Segmentation divides memory into variable-size logical units that match the programmer’s view: code segment, data segment, stack segment. Each segment has a base address and a limit.

Compared to paging: segmentation has no internal fragmentation (segments are exactly the right size) but suffers external fragmentation, because segments come and go in different sizes. Paging has no external fragmentation but internal fragmentation. Segmentation is visible to the programmer (addresses carry a segment id); paging is transparent. In practice modern systems use paging, sometimes layered under segmentation (x86).

7. Why do we need virtual memory?

Four reasons:

• Run programs larger than physical RAM — a 3GB executable can run on a 1GB machine.
• Process isolation — each process has its own address space and can’t see or corrupt another’s memory.
• Efficiency — only the actively-used pages of a program are kept in RAM.
• Simplified linking — all programs can link at the same virtual addresses without coordination.

Virtual memory decouples the logical address space a process sees from the physical RAM installed, mapping virtual pages to physical frames on demand.

8. What is demand paging and what happens during a page fault?

Demand paging loads pages into RAM only when they’re accessed, not up front. When a process touches a virtual address whose page isn’t in RAM, a page fault occurs.

The handling flow: the MMU detects the invalid page and traps to the OS; the OS validates the address (if invalid, it’s a segmentation fault); it finds a free frame or evicts a page; it initiates disk I/O to read the page into the frame; it updates the page table entry; then it restarts the faulting instruction. Page faults are expensive — disk I/O takes millions of CPU cycles — so the goal of virtual memory management is to minimize them.

9. What is thrashing and how is it solved?

Thrashing is when a process spends more time paging (handling page faults) than executing. The disk is constantly busy but no useful work gets done.

The cause: the sum of the working sets of all processes exceeds physical memory. Each process doesn’t have enough frames to hold its active pages, so it constantly faults. The counterintuitive fix is to reduce the degree of multiprogramming — swap out entire processes to free frames. The remaining processes stop thrashing, so CPU utilization actually increases.

10. What is the working set model?

The working set is the set of pages a process is currently using, bounded by its locality of reference. It’s grounded in two observations: temporal locality (recently accessed pages will be accessed again soon) and spatial locality (pages near recently accessed pages will be accessed).

If the OS keeps the sum of all working sets ≤ available frames, thrashing is avoided. The working set is the theoretical basis for the practical rule: give each process enough frames to cover its locality, and page faults stay low.

11. What are the page replacement algorithms?

When a page fault occurs and no free frame exists, the OS must evict a page:

• FIFO — evicts the page that has been in memory longest. Simple, but can evict a heavily-used page that happened to load early. Suffers Belady’s anomaly.
• Optimal (OPT/MIN) — evicts the page that will be used farthest in the future. Provably minimal fault rate but needs an oracle, so it’s only a benchmark.
• LRU — evicts the page not used for the longest time, exploiting temporal locality. No Belady’s anomaly (it’s a stack algorithm), but exact LRU is expensive, so it’s approximated with a reference bit.

12. What is Belady’s anomaly?

Belady’s anomaly is the counterintuitive phenomenon where increasing the number of page frames results in more page faults. It occurs with FIFO (and some other algorithms) but not with LRU or Optimal.

The reason LRU is immune: it’s a stack algorithm — the set of pages in memory with N frames is always a subset of the set with N+1 frames, so more frames can never hurt. FIFO is not a stack algorithm, so adding frames can evict a frequently-used page early and cause it to fault back in repeatedly.

13. Why is LRU better than FIFO?

LRU uses past behavior to predict the future — if a page was used recently, it’s likely to be needed again soon (temporal locality). FIFO ignores usage patterns entirely and may evict a critical page that happened to be loaded early, even if it’s used constantly.

LRU also avoids Belady’s anomaly, since it’s a stack algorithm. Its cost is the reason it’s approximated: exact LRU requires timestamping every memory access. The hardware approximation uses a reference bit — set whenever a page is accessed; the OS periodically clears the bits, and pages whose bits stay clear haven’t been used recently.

14. What is the clock algorithm (second chance)?

The clock algorithm is the practical hardware approximation of LRU. Pages sit in a circular list, with a reference bit on each. The clock hand scans the circle: if a page’s reference bit is set, it clears the bit and gives the page a “second chance” — moving the hand on. If the bit is already clear, the page hasn’t been used recently and is evicted.

It costs almost nothing — one bit per page and a periodic scan — and captures the essence of LRU: recently-used pages survive, unused pages get evicted. This is what real systems implement.

15. What is a dirty bit and why does it matter for eviction?

The dirty (modify) bit is a hardware bit set when a page is written to. During eviction it decides the cost: a dirty page must be written back to disk before the frame is reused (expensive — disk I/O); a clean page can be discarded immediately (cheap).

Better page replacement algorithms prefer evicting clean pages, because a clean eviction costs only the frame reuse, while a dirty eviction adds a full write. This is a real optimization in OS kernels: preferentially evict clean pages first, and only write dirty ones when necessary.

16. What is false sharing and how is it fixed?

False sharing happens when two threads access different variables that happen to sit on the same cache line (typically 64 bytes on x86). Neither thread uses the other’s variable, but the cache coherence protocol (like MESI) treats the line as shared: when Thread A writes its variable, Core B’s copy of the line is invalidated, and vice versa. Both cores keep reloading the same line — performance can collapse by up to 100x with zero actual data sharing.

The fix is padding: align fields accessed by different threads onto different cache lines — struct { int x; char pad[64]; int y; } or alignas(64). Detection is via perf counters showing high cache-miss rates with low actual sharing.

17. What is a memory barrier and when is it needed?

A memory barrier (fence) is a CPU instruction that prevents the reordering of memory operations across it. CPUs reorder loads and stores for performance, which breaks hand-rolled synchronization: Thread 1 writes data = 42; flag_ready = 1; and Thread 2 reads while (!flag_ready); print(data); — without a barrier, Thread 2 could see flag_ready == 1 but data == 0.

Barrier types: mfence (full, prevents all reordering), acquire (prevents later operations from moving before), and release (prevents earlier operations from moving after). You need them when implementing lock-free code or custom synchronization; regular mutexes already include the necessary barriers, and std::atomic / synchronized make the compiler insert them for you.

18. What are the First-Fit, Best-Fit, and Worst-Fit allocation algorithms?

These choose which free hole to allocate for a process (used with contiguous allocation / fixed partitioning). Given the list of free holes:

• First-fit — scans the free list and allocates the first hole large enough. Fast (stops at the first match) and tends to leave good reuse at the start of memory.
• Best-fit — scans the entire list and allocates the smallest hole that fits. Minimizes wasted space per allocation but produces many tiny, unusable leftover fragments and is slower (full scan).
• Worst-fit — scans everything and allocates the largest hole, leaving the biggest possible remainder. Intended to reduce small fragments, but in practice it fragments memory just as badly and is rarely the best.

In practice, first-fit is usually the winner: it’s faster than the others and performs comparably to best-fit in memory utilization. The interview takeaway: first-fit = first hole that fits; best-fit = smallest hole that fits; worst-fit = largest hole that fits. All three suffer external fragmentation and are used only for contiguous allocation — paging avoids the whole problem.

19. What is copy-on-write (COW)?

Copy-on-write is an optimization that delays copying shared data until one side actually modifies it. Instead of duplicating a resource eagerly, multiple users share a single read-only copy; the OS duplicates the page only when someone tries to write.

Its most famous use is fork(): when a parent forks, the child would normally get a full copy of the parent’s memory. With COW, both share the same physical pages, marked read-only. If neither writes, no copy happens — the fork is nearly free. The first write by either process traps (page fault), and only that page is copied and made writable.

Benefits: fork() becomes fast and cheap (O(1) per page table instead of copying the whole address space), and memory is saved since untouched pages are never duplicated. It’s used throughout Unix/Linux for fork, for shared libraries, and in memory-mapped files. The cost: a page fault on every first write and the bookkeeping to track sharing.

20. Why use multi-level (hierarchical) page tables?

A single-level page table for a large address space is huge and must be contiguous in memory. For a 64-bit address space with 4KB pages, a flat page table would need trillions of entries — impossibly large. Multi-level paging splits the page table into a tree:

outer page table  →  inner page table  →  frame

The logical address is split into several page-number fields plus an offset, e.g. [p1 | p2 | offset] for a two-level table. The outer table indexes an inner table, which indexes the frame.

The advantage is memory efficiency: only the page tables actually in use need to exist. The outer table is small, and inner tables are allocated on demand. The cost is extra memory accesses — each level is another lookup, though the TLB hides this in the common case. This is why real systems (x86 two-level, modern four-level) use hierarchical tables instead of one flat table. Inverted and hashed page tables are alternatives for the same size problem.

21. What is the memory hierarchy and why does it exist?

The memory hierarchy orders storage by speed and capacity:

Level	Speed	Capacity	Cost/bit
Registers	Fastest	Tiny	Highest
L1/L2/L3 cache	Very fast	Small	High
RAM (main memory)	Fast	Medium	Medium
SSD/HDD (secondary)	Slow	Massive	Lowest

Moving down the hierarchy: speed decreases, capacity increases, cost per bit decreases. Registers are ~0.3ns, cache ~1–10ns, RAM ~50–100ns, disk ~milliseconds — a gap of six orders of magnitude.

It exists because fast memory is expensive and small — you can’t build a machine with an entire disk-sized cache. So the system keeps only the hottest data in the fast levels (register → cache) and relies on locality of reference (programs reuse recently-accessed data) to make the fast levels the common case. The result: you get near-cache speed at near-disk cost by keeping the working set up high and the rest down low.

22. How do you count page faults for FIFO and LRU?

The numerical page-replacement question. You’re given a reference string and a frame count; count how many times a page must be brought in.

Example: reference string 7 0 1 2 0 3 0 4 2 3 0 3 2, 3 frames:

• FIFO (evict the oldest loaded page): track frames in order. Total faults = 10.
• LRU (evict the page used longest ago): track recency. For this string LRU gives 9 faults.

Walk through FIFO to see why: 7,0,1 fault in (3), 2 evicts 7 (4), 0 hits (still 4), 3 evicts 0 (5), 0 evicts 1 (6), 4 evicts 2 (7), 2 evicts 3 (8), 3 evicts 0 (9), 0 evicts 4 (10), then 3,2 are hits — 10 total. LRU keeps the recently-used pages, so the later misses are fewer — 9 total.

The method for any algorithm:

1. Walk the reference string one page at a time.
2. If the page is already in a frame → hit, no fault.
3. If not → fault: if a frame is free, load it; otherwise evict per the rule (FIFO: oldest; LRU: least recently used) and load.
4. Count every load as one fault.

Key things the question tests: a page already present (even if marked for eviction) is a hit, not a fault; FIFO can show Belady’s anomaly (more frames → more faults); LRU never does. Always draw the frame table column by column — that’s the safe way to avoid mistakes under pressure.