Skills101

AdvancedOperating Systems · Lesson 12 of 12 · Updated ·

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

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):

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

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:

RefPageFrames beforeNext usesVictim
441, 2, 31 → ref 6, 2 → ref 5, 3 → ref 123
751, 2, 41 → ref 10, 2 → ref 9, 4 → never4
861, 2, 51 → ref 10, 2 → ref 9, 5 → never5
1231, 2, 61 → ref 17, 2 → ref 16, 6 → ref 141

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.

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")})
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

  • 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 what you learned

📝 Quiz: Page Replacement Numericals5 questions · instant answers & explanations · +10 XP · counts towards your free certificateTake the quiz →