Intuition The one core ideaYour computer pretends it has more memory than it really does, by keeping only a handful of "pages" in fast RAM and leaving the rest on the slow disk. Page replacement is simply the rule for which page to kick out of RAM when a new one needs to come in — and every symbol below exists only to help us count how often that kicking-out goes wrong.
This page assumes you have seen nothing . Before we can read a single row of the parent note's tables, we must earn every word and symbol it uses. We build them in an order where each one leans on the one before it.
See the parent: Page replacement — FIFO, LRU, Clock, Optimal .
Start with the most physical picture possible: memory is a long row of numbered boxes, and each box holds one number.
A sequence of numbered storage boxes. The number of a box is its address ; the value in the box is the data . When we say "the CPU reads address 12", we mean: go to box number 12 and hand back what's inside.
Why the topic needs it: every idea below is about where data lives (fast box vs slow box) and how we name those places. Without the box picture, "page", "frame", and "address" are just words. See Virtual Memory & Paging for the full machinery.
There are two kinds of storage in our story, and their speed gap is the whole reason the topic exists.
RAM (Random Access Memory): the fast boxes the CPU can read directly. Small.Disk : the slow boxes (hard drive / SSD). Huge, but the CPU cannot use them directly — data must first be copied into RAM.
Intuition The speed gap in one pictureThink of RAM as the small desk right in front of you, and disk as a warehouse across town. Reaching something on your desk takes a second; fetching from the warehouse takes a road trip. In real numbers a disk access is about 1 0 5 one hundred thousand times . The symbol 1 0 5 1 5 = 100000
Why the topic needs it: because the warehouse trip is so expensive, the entire goal is to avoid it. Every policy in the parent note is a strategy to keep the right things on the desk.
We never move memory one box at a time; that would be wasteful. We move it in fixed-size blocks.
Definition Page and Frame
A page is a fixed-size chunk of the program's own address space (its imagined, spacious memory). We number pages 0 , 1 , 2 , …
A frame is a fixed-size slot in real RAM, exactly big enough to hold one page.
A page is the content ; a frame is the parking spot . At any moment a page either sits in some frame (fast) or waits on disk (slow).
P age = the P icture (the data). F rame = the F older that holds it. Many pages exist; only a few frames.
Why the topic needs it: the parent note's tables show frames filling up with page numbers. "3 frames" means "3 parking spots". When all spots are full and a new page arrives — that is exactly when replacement happens.
F F at the same time . In the parent's examples F = 3 F
Read F = 3
A running program does not touch pages randomly; it asks for them one after another in a definite order. We write that order down.
Definition Reference stringThe sequence of page numbers the program touches, in time order. Example: 7 0 1 2 0 3 0 4 means "first the program needs page 7, then page 0, then page 1, …". Time flows left to right.
string ?
Read it like a shopping list you must fulfil one item at a time, in order. Each item is a page the CPU wants right now . Our policies are judged on this exact list — change the list, change the answer.
Why the topic needs it: every worked example in the parent walks this string left to right, one column per reference. It is the raw input to all four policies.
For each page on the list, exactly one of two things happens. There is no third case — this cleanliness is what makes counting possible.
Mnemonic Fault = "not found"A page fault is not an error/crash — it just means "the page you asked for is not on the desk, go fetch it." Think of "fault" as "found-at-fault: missing."
Why the topic needs it: the whole subject is minimizing page faults . Each fault is one expensive warehouse trip. See TLB & Address Translation for how the CPU checks "is p
Definition Evict and VictimWhen a fault happens and all F victim ; the act of removing it is eviction . The replacement policy is the rule that picks the victim.
This one word — which victim? — is the entire subject. FIFO, LRU, Clock, Optimal are four different answers to that single question.
The parent note tracks "the pages currently in frames" using a set . Let's earn that symbol.
S ∣ S ∣
S { … } S = { 7 , 0 , 1 } ∣ S ∣ S size of the set = how many pages are in it. If S = { 7 , 0 , 1 } ∣ S ∣ = 3 ∣ S ∣ ≤ F ≤
set and not a list?
A set only cares whether a page is present, not the order boxes sit in. "Is p p ∈ S p S p ∈ / S p not in S
When we evict victim v p S ← ( S ∖ { v }) ∪ { p } .
Let's decode it piece by piece — nothing here is scary.
Definition The three symbols
∖ S ∖ { v } S v removed ." If S = { 7 , 0 , 1 } S ∖ { 7 } = { 0 , 1 } ∪ A ∪ B A or B { 0 , 1 } ∪ { 2 } = { 0 , 1 , 2 } ← S ← (new thing) S is that new thing."
Worked example Reading the whole lineS ← ( S ∖ { v }) ∪ { p } S v p
A raw fault count of "6" is meaningless without knowing how long the list was — 6 faults out of 8 requests is bad; 6 out of 1000 is excellent. Dividing turns the count into a fraction between 0 and 1 you can compare across programs. Because every reference is either a hit or a fault (Section 6, no third case), these two counts add up to the total, so the fraction is a clean "chance of missing." Related idea: Locality of Reference explains why this fraction is usually small in real programs.
Worked example A tiny fault rateString 7 0 1 2 0 3 0 4 has 8 6 8 6 = 0.75 75%
The Clock policy needs one last tiny symbol.
R bit (a light that is either 0 = 1 = 1 R = 1 was touched since I last checked"; R = 0
Intuition Why just one bit?Tracking the exact last-use time of every page (true LRU) would need the hardware to write a timestamp on every single memory access — far too slow. One bit answers a cheaper yes/no question — "used recently?" — and that turns out to be good enough to imitate LRU. See Cache Replacement Policies where the same trick appears.
Replacement Policy question
Every arrow means "you need the left idea before the right one makes sense." Notice all roads lead to the bottom box — the four policies — which is what the parent note is really about.
Cover the right side and answer aloud. If any one stumps you, re-read its section above before opening the parent.
What is an address, in the boxes picture? The number of a memory box; the data is what's inside it.
Roughly how much slower is a disk access than a RAM access? About 1 0 5
What is the difference between a page and a frame? A page is a chunk of the program's data; a frame is the fixed-size slot in real RAM that holds one page.
What does F The number of frames — how many pages fit in RAM at once.
What is a reference string? The time-ordered sequence of page numbers the program touches.
Name the only two outcomes for any page reference. A hit (page already in a frame) or a page fault (page not in a frame).
What does p ∈ S "p S p
What does p ∈ / S p not in RAM — a page fault.
Read S ← ( S ∖ { v }) ∪ { p } "S v p
What is a victim? The page chosen by the policy to be evicted to make room for a new one.
Write the fault-rate formula and say why we divide. fault rate = # references # faults
What is the reference bit R A one-bit flag per frame set to 1 0
