# Page Replacement Numericals — FIFO, LRU, Optimal and Clock on a 20-Page String

Source: https://skills101.in/learn/operating-systems/os-page-replacement-numericals — Skills101 free tutorial (Operating Systems). Updated 2026-11-18.

Lesson 7 explained why page replacement is needed and solved a short string. Exam questions are usually longer — 15 to 20 references — and ask you to compare policies or change the number of frames. A single mistake early on spoils every later column, so this lesson shows a **method** for working on paper and a **program** to check yourself.

The reference string used throughout (a common textbook string):

```text
1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
```

It has **20 references** and **7 different pages** (1 to 7).

## 1. Two facts that catch mistakes

1. **Faults ≥ number of distinct pages** when memory starts empty. Every page must be loaded at least once, so this string causes **at least 7** faults with any policy and any number of frames.
2. **Faults ≤ number of references.** With 1 frame, every reference that differs from the previous one is a fault. Here no page repeats immediately, so 1 frame gives **20** faults.

If your answer is outside this range, recheck it.

## 2. FIFO with 3 frames

FIFO replaces the page that was **loaded earliest**, no matter how often it was used since. On paper, keep the frames in **load order** — then the victim is always the top one.

![FIFO with 3 frames on the 20-reference string: 16 page faults and only 4 hits, at references 5, 11, 15 and 18](https://skills101.in/learn-img/operating-systems/fifo-trace.svg)

Look at reference 6 (page 1): page 1 was loaded at reference 1 and evicted at reference 4 by page 4. It comes back almost at once — a typical FIFO weakness, because FIFO ignores how recently a page was used.

**Result: 16 faults, 4 hits.**

## 3. LRU with 3 frames

LRU replaces the page whose **last use** is furthest in the past. On paper: when a fault happens, look **back** along the string from the current position; among the three pages in memory, the one you meet **last** is the victim.

Example — reference 12 (page 3). After reference 11, memory holds pages 1, 2 and 6. Looking back: 2 (ref 11), 1 (ref 10), 2, then 6 (ref 8). Page **6** was used longest ago → replace 6 with 3.

**Result: 15 faults, 5 hits.**

## 4. Optimal (OPT) with 3 frames

OPT replaces the page whose **next use** is furthest in the **future** (or that is never used again). It needs the future, so no real OS can use it — but it gives the **lowest possible** fault count, which is why exams use it as a benchmark.

Step through the first decisions:

| Ref | Page | Frames before | Next uses | Victim |
|---|---|---|---|---|
| 4 | 4 | 1, 2, 3 | 1 → ref 6, 2 → ref 5, 3 → ref 12 | 3 |
| 7 | 5 | 1, 2, 4 | 1 → ref 10, 2 → ref 9, 4 → never | 4 |
| 8 | 6 | 1, 2, 5 | 1 → ref 10, 2 → ref 9, 5 → never | 5 |
| 12 | 3 | 1, 2, 6 | 1 → ref 17, 2 → ref 16, 6 → ref 14 | 1 |

A page that is **never used again** is always the perfect victim.

**Result: 11 faults, 9 hits.**

## 5. Check yourself with Python

This short simulator handles all three policies. Write your paper answer first, then run it.

```python
def faults(refs, frames, policy):
    mem, count = [], 0
    for i, page in enumerate(refs):
        if page in mem:
            if policy == "LRU":            # move to the "most recent" end
                mem.remove(page)
                mem.append(page)
            continue
        count += 1
        if len(mem) == frames:
            if policy == "OPT":
                future = refs[i + 1:]
                victim = max(mem, key=lambda p: future.index(p) if p in future else len(future))
                mem.remove(victim)
            else:                          # FIFO and LRU both evict the front
                mem.pop(0)
        mem.append(page)
    return count

refs = [1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6]
for n in (3, 4, 5):
    print(n, "frames:", {p: faults(refs, n, p) for p in ("FIFO", "LRU", "OPT")})
```

```text
3 frames: {'FIFO': 16, 'LRU': 15, 'OPT': 11}
4 frames: {'FIFO': 14, 'LRU': 10, 'OPT': 8}
5 frames: {'FIFO': 10, 'LRU': 8, 'OPT': 7}
```

One idea makes the code short: for FIFO the list is in **load order**, and for LRU it is kept in **use order** (a hit moves the page to the end). In both cases the victim is the **front** of the list.

## 6. More frames, fewer faults (usually)

![Line chart of page faults against frames 1 to 7 for FIFO, LRU and OPT: all start at 20 with one frame, OPT stays lowest, and all reach 7 faults with 7 frames](https://skills101.in/learn-img/operating-systems/faults-vs-frames.svg)

- With **7 frames** every page fits, so only the 7 compulsory faults remain.
- **OPT is always the lowest.** LRU is usually between OPT and FIFO.
- LRU and OPT are **stack algorithms**: the pages in memory with n frames are always a subset of those with n + 1 frames, so adding a frame can never add a fault. FIFO is not a stack algorithm, which is why it can show **Belady's anomaly** (lesson 7).

## 7. Clock (second chance)

True LRU needs to record the time of every memory access — too expensive in hardware. The **Clock** algorithm approximates it with one **reference bit** per frame:

1. Frames form a circle with a pointer (the "hand").
2. When a page is used, the hardware sets its bit to **1**.
3. On a fault, look at the frame under the hand: if its bit is **1**, clear it to 0 (a "second chance") and move on; if it is **0**, replace that page.

On our string with 3 frames, Clock gives **16** faults — the same as FIFO here (in this version a newly loaded page starts with bit 1; some books start it at 0, which can change the count, so follow your question's convention). Clock beats FIFO only when hits land on pages that FIFO would otherwise throw out. It is used in real systems because it is cheap, not because it is optimal.

## 8. Speed tips for the exam

- Write the string across the top and fill the frame columns below it, exactly as in the diagram.
- Mark hits as you go; at the end, **faults = references − hits**. Counting the smaller number is faster.
- The first k distinct pages always fault (k = frames). Start deciding only after that.
- For OPT, underline the next use of each page in memory; the page with no underline, or the furthest one, goes.

## Common mistakes

- In LRU, choosing by **load time** instead of **last use** — that is FIFO.
- In OPT, looking backwards instead of forwards.
- Updating the FIFO order on a hit. A hit changes nothing in FIFO.
- Reporting hits when the question asks for faults (or the fault **rate** = faults / references).

## Quick recap

- Faults are at least the number of distinct pages and at most the number of references.
- 3 frames on this string: FIFO 16, LRU 15, OPT 11.
- FIFO evicts the oldest load; LRU the oldest use; OPT the furthest next use.
- LRU and OPT never get worse with more frames; FIFO can (Belady's anomaly).
- Clock uses a reference bit to approximate LRU cheaply.


Practice quiz and free certificate: https://skills101.in/learn/operating-systems/os-page-replacement-numericals