When does thrashing occur?

When the frames given to a process are fewer than its working set

When a process has more frames than its working set

Why does the OS often make thrashing worse?

It sees low CPU utilization and admits more processes

For 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1 with 3 frames, how many faults does Optimal give, and how does it compare?

9, the lowest of FIFO 15, LRU 12, LFU 13

Which is a recognised way to control thrashing?

Page-fault-frequency control or the working-set model

Increase the degree of multiprogramming

2074 Bhadra · 2+8 marks

Thrashing; page faults on 3 frames

Short answer

Thrashing is excessive paging when a process has too few frames for its working set. With three frames, FIFO causes 15 faults, Optimal 9, LRU 12, and LFU 13.

What is thrashing? Consider the following page-reference string: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1. How many page faults would occur for the following page replacement algorithms, assuming 3 frames: a) FIFO b) Optimal c) LRU d) LFU

Thrashing

Thrashing is excessive paging activity: a process spends more time swapping pages in and out than executing. It occurs when the number of frames given to a process is smaller than its working set, so a replaced page is needed again almost immediately. CPU utilization falls, the OS may add more processes (worsening it), and system throughput collapses. It is controlled with the working-set model, page-fault-frequency (PFF) control, local replacement and reducing the degree of multiprogramming.

Simulation (3 frames, initially empty)

Reference string (20 references): 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1. * = fault.

a) FIFO

ref  7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
F1   7 7 7 2 2 2 2 4 4 4 0 0 0 0 0 0 0 7 7 7
F2   - 0 0 0 0 3 3 3 2 2 2 2 2 1 1 1 1 1 0 0
F3   - - 1 1 1 1 0 0 0 3 3 3 3 3 2 2 2 2 2 1
     * * * *   * * * * * *     * *     * * *

Faults = 15.

b) Optimal

ref  7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
F1   7 7 7 2 2 2 2 2 2 2 2 2 2 2 2 2 2 7 7 7
F2   - 0 0 0 0 0 0 4 4 4 0 0 0 0 0 0 0 0 0 0
F3   - - 1 1 1 3 3 3 3 3 3 3 3 1 1 1 1 1 1 1
     * * * *   *   *     *     *       *

Faults = 9.

c) LRU

ref  7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
F1   7 7 7 2 2 2 2 4 4 4 0 0 0 1 1 1 1 1 1 1
F2   - 0 0 0 0 0 0 0 0 3 3 3 3 3 3 0 0 0 0 0
F3   - - 1 1 1 3 3 3 2 2 2 2 2 2 2 2 2 7 7 7
     * * * *   *   * * * *     *   *   *

Faults = 12.

d) LFU (least frequently used page is replaced; ties broken by oldest arrival)

ref  7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
F1   7 7 7 2 2 2 2 4 4 3 3 3 3 3 3 3 3 3 3 3
F2   - 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
F3   - - 1 1 1 3 3 3 2 2 2 2 2 1 2 2 1 7 7 1
     * * * *   *   * * *       * *   * *   *

Faults = 13.

Algorithm	Page faults
FIFO	15
Optimal	9
LRU	12
LFU	13

Answer: FIFO = 15, Optimal = 9, LRU = 12, LFU = 13 (LFU depends on the tie-break rule).

✓ Answer checked by Claude Opus 5.5 (high effort)

Page faults: FIFO, Optimal, LFU, LRU · Operating System, chapter 4 · asked 2×
Page faults with 3 frames: LRU, FIFO, OPT · Operating System, chapter 4 · asked 2×
Page faults: LRU, FIFO, Optimum · Operating System, chapter 4
LRU algorithm; page faults on string · Operating System, chapter 4
Hits and faults: FIFO, LRU, Optimal · Operating System, chapter 4

All Operating System chapter 4 questions →

Thrashing; page faults on 3 frames

Thrashing

Simulation (3 frames, initially empty)

Related questions