A
AiTechWorlds
AiTechWorlds
A student's desk fits exactly 5 open textbooks. She is studying for finals and has 10 textbooks she might need. She keeps the 5 she is using right now open on the desk. When she needs a 6th, she must put one away.
Which one does she put away?
Not the one she is reading right now. Not the one she just opened two minutes ago. She thinks — which book have I not looked at in the longest time? She puts that one back on the shelf.
This decision — which page to evict when RAM is full — is the entire problem of page replacement, and it has been studied since the 1960s.
Programs often need more memory than physically exists in RAM. A video editor, a browser with 50 tabs, a database — all of these can exceed available RAM. Without virtual memory, these programs would crash or refuse to run.
Virtual memory uses disk storage as a slower extension of RAM. Pages that have not been recently used are written to a swap space (Linux) or pagefile.sys (Windows) on disk. When they are needed again, they are loaded back into RAM.
From the process's perspective, it has as much memory as the address space allows (up to 128 TB on x86-64 Linux). The OS manages what is actually in RAM at any moment.
The cost: disk access is ~100,000× slower than RAM. Virtual memory only works well if the OS is smart about what it keeps in RAM.
Instead of loading an entire process into RAM at launch, demand paging loads pages only when they are actually accessed.
Process starts: NO pages loaded into RAM
Process accesses address X:
--> CPU checks page table for X's page
--> Valid bit = 0 (page not in RAM)
--> CPU raises PAGE FAULT (trap to OS)
OS Page Fault Handler:
1. Find the page on disk (swap space)
2. Find a free frame in RAM
3. Load the page from disk into the frame
4. Update page table entry (valid bit = 1, frame = f)
5. Resume the process at the faulting instruction
Benefits: Faster startup (only load what you use), support programs larger than RAM, share unused pages across processes.
If there is a free frame: load the page there directly.
If RAM is full: choose a victim page to evict, write it to disk if dirty, then use that frame.
We use a reference string to compare algorithms: 7 0 1 2 0 3 0 4 2 3 0 3 2 with 3 frames.
Evict the page that has been in RAM the longest.
Ref: 7 0 1 2 0 3 0 4 2 3 0 3 2
-------------------------------------------
F1: 7 7 7 2 2 2 2 4 4 4 0 0 0
F2: 0 0 0 0 3 3 3 2 2 2 2 2
F3: 1 1 1 1 0 0 0 3 3 3 3
-------------------------------------------
PF: * * * * * * * * * * = 9 page faults
Belady's Anomaly: Adding more frames can increase page faults with FIFO. This counter-intuitive result was proven by László Bélády in 1969. It is unique to FIFO.
Evict the page that will not be used for the longest time in the future.
Ref: 7 0 1 2 0 3 0 4 2 3 0 3 2
-------------------------------------------
F1: 7 7 7 2 2 2 2 2 2 2 2 2 2
F2: 0 0 0 0 0 0 4 4 4 0 0 0
F3: 1 1 1 3 3 3 3 3 3 3 3
-------------------------------------------
PF: * * * * * * * = 6 page faults
OPT gives the minimum possible page faults — it is the theoretical best.
Problem: It requires knowing the future, which is impossible in practice.
Use: It is the benchmark. If your algorithm achieves 90% of OPT's performance, that is excellent.
Evict the page that was used longest ago in the past.
Ref: 7 0 1 2 0 3 0 4 2 3 0 3 2
-------------------------------------------
F1: 7 7 7 2 2 2 0 0 0 0 0 0 0
F2: 0 0 0 0 0 0 4 4 4 4 4 2
F3: 1 1 1 3 3 3 2 2 2 2 2 <-- wait, let me redo
(LRU tracking is complex; use stack model)
-------------------------------------------
PF: * * * * * * * * = 8 page faults
LRU performs close to OPT on real workloads. The problem is implementation cost — tracking exact LRU order requires timestamps on every memory access, which is extremely expensive in hardware.
Approximation — Reference Bits: Hardware sets a reference bit to 1 when a page is accessed. Periodically the OS scans and clears reference bits. Pages with reference bit = 0 are candidates for eviction.
A practical LRU approximation used in real OSes (including Linux's inactive/active list scheme).
On page fault: IF reference bit of current page = 1: set to 0, advance pointer ("give it a second chance") IF reference bit = 0: EVICT this page, replace with new page
Evict page 3 (ref=0). New page goes here.
The clock algorithm is O(n) in the worst case but O(1) on average. Linux uses a two-handed clock with active and inactive lists.
| Algorithm | Page Faults | Implementation | Used In Practice |
|---|---|---|---|
| FIFO | High | Trivial | Rarely (Belady's anomaly) |
| OPT | Minimum | Impossible (needs future) | Benchmark only |
| LRU | Near-optimal | Expensive in hardware | Approximated |
| Clock | Near-LRU | Efficient | Linux, BSD, others |
Thrashing occurs when the OS spends more time handling page faults than running processes.
Too many processes in RAM:
Each process has too few frames
--> Frequent page faults
--> OS busy loading pages from disk
--> CPU utilization drops to near zero
--> OS thinks "CPU is idle, add more processes"
--> Even more page faults --> THRASHING
Causes:
Solutions:
A process's working set at time t is the set of pages it has referenced in the last Δ time units.
Reference string: ... 1 2 3 2 1 4 5 1 2 3 4 ...
^-- time t
Δ = 5 references back
Working set = {1, 2, 3, 4} (pages referenced in last 5 accesses)
The OS allocates enough frames to hold each process's working set. If total working set size exceeds physical RAM, suspend some processes entirely rather than running all of them in thrashing conditions.
Linux implements this via the OOM Killer — when RAM is critically full, it calculates a "badness score" for each process and kills the one with the highest score (typically largest memory user).
Get this course's notes on Telegram!
Free cheat sheets, summaries & practice exercises