Frame allocation, thrashing, working sets and the clock algorithm

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

1. Which replacement policy can show Belady's anomaly? from Lesson 5.3.2
2. EAT with page faults? from Lesson 5.3.1
3. What happens to CPU utilisation when processes wait for I/O 80% of the time? from Lesson 2.2.2

1 · The Hook

Juggling three balls is fine; give the juggler eight and he spends all his time picking balls off the floor. When processes don't have enough frames, they spend all their time page-faulting and the CPU sits idle: thrashing. This lesson shows how the OS shares frames, how it spots thrashing with the working set, and the cheap LRU substitute every real OS uses: the clock algorithm.

3 · Core Concept

Predict First — the answer

It drops further: processes queue for the disk instead of using the CPU. The OS sees low utilisation and admits even more: the spiral called thrashing.

In plain words

Each process needs a certain number of pages "at hand" to run smoothly (its working set). If the sum of everyone's working sets is more than the RAM, they keep stealing frames from each other and all of them fault constantly. The fix is to run fewer processes at once. For choosing victims cheaply, the clock gives every page a "second chance" if it was used recently.

1. How many frames per process?

• Equal allocation: m frames, n processes → m/n each.

• Proportional allocation: process i of size sᵢ gets aᵢ = (sᵢ / S) × m, where S = Σ sᵢ.

  Example: 64 frames, sizes 20, 60, 80 pages (S = 160) → 8, 24, 32 frames.

• Global replacement: the victim may belong to any process (better throughput). Local replacement: only the process's own frames.

2. Thrashing

High paging activity: a process spends more time paging than executing. Cause: degree of multiprogramming too high, so working sets don't fit. Cure: reduce the degree of multiprogramming (suspend processes), or give processes the frames they need.

3. Working-set model

• Working set WS(t, Δ) = the set of distinct pages referenced in the last Δ references (up to time t). Δ is the "window".
• WSSᵢ = size of process i's working set; D = Σ WSSᵢ = total demand.
• If D > m (frames available) → thrashing → suspend a process. If D is well below m, another process can be admitted.

Example (running string 7 0 1 2 0 3 0 4 2 3 0 3 2, positions 1 to 13, Δ = 4):

• At t = 10 the last four references are 0 4 2 3 → WS = {0, 2, 3, 4}, size 4.
• At t = 13 they are 3 0 3 2 → WS = {0, 2, 3}, size 3.

4. Page-fault frequency (PFF)

Set an upper and a lower bound on each process's fault rate: above the upper bound → give it more frames; below the lower bound → take frames away.

5. Clock (second-chance) algorithm

Frames in a circle with a pointer; each page has a reference bit, set to 1 whenever the page is used (and when it is loaded). To find a victim: look at the page under the pointer.

• Bit = 1 → set it to 0 (second chance) and move on.
• Bit = 0 → replace this page; the new page gets bit 1; the pointer moves past it.

If every bit is 1, the clock goes round once and becomes FIFO. Running string, 3 frames:

ref  frames     bits   pointer after
7    7 . .      1 0 0  -> slot 1      F
0    7 0 .      1 1 0  -> slot 2      F
1    7 0 1      1 1 1  -> slot 0      F
2    2 0 1      1 0 0  -> slot 1      F   (all bits cleared, 7 replaced)
0    2 0 1      1 1 0  -> slot 1      hit
3    2 0 3      1 0 1  -> slot 0      F   (0 gets a second chance; 1 replaced)
0    2 0 3      1 1 1  -> slot 0      hit
4    4 0 3      1 0 0  -> slot 1      F
2    4 2 3      1 1 0  -> slot 2      F
3    4 2 3      1 1 1  -> slot 2      hit
0    4 2 0      0 0 1  -> slot 0      F   (full circle: all cleared, 3 replaced)
3    3 2 0      1 0 1  -> slot 1      F
2    3 2 0      1 1 1  -> slot 1      hit

9 faults (the same as LRU here). Enhanced second chance also looks at the dirty bit and prefers victims with (reference, dirty) = (0, 0), then (0, 1), (1, 0), (1, 1).

4 · Visual

Adding processes helps until their working sets no longer fit in memory; after that, utilisation collapses.

5 · Worked Examples

Example 1 Easy

93 frames are shared equally by 3 processes. Frames each?

Solution

93 / 3 = 31.

Example 2 Medium

Proportional allocation: 100 frames, processes of 30 and 120 pages. Frames for the smaller one?

Solution

30 / 150 × 100 = 20.

Example 3 GATE

Three processes have working-set sizes 18, 25 and 30 pages; the system has 70 frames. What should the OS do?

Solution

D = 73 > 70 → thrashing risk: suspend a process (reduce the degree of multiprogramming).

6 · GATE Traps

• Thrashing is fixed by fewer processes, not more.
• Working set counts distinct pages in the window.
• In the clock algorithm a hit only sets the bit; it doesn't move the pointer.
• Proportional allocation uses process sizes, not priorities (unless told).

7 · Memory Hook

"Too many jugglers' balls → thrashing. Working set = distinct pages in the last Δ. Clock: 1 → clear and pass; 0 → out."

8 · Connect the Dots

Phase 5 is complete. Memory holds what is running; everything else lives in files on a disk. Phase 6 covers how files are stored and found, and how the OS drives disks and other I/O devices.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1 · NAT · 1 mark(s) — Proportional allocation

64 frames; three processes of 20, 60 and 80 pages. Frames for the 80-page process (proportional allocation)?

Numerical answer: ________

Q2 · NAT · 2 mark(s) — Working set

Reference string 7 0 1 2 0 3 0 4 2 3 0 3 2 (positions 1–13), window Δ = 5. Size of the working set at t = 10?

Numerical answer: ________

Q3 · NAT · 2 mark(s) — Clock

Running string 7 0 1 2 0 3 0 4 2 3 0 3 2, 4 frames, clock algorithm (bit set on load and on use). Number of page faults?

Numerical answer: ________

Q4 · MCQ · 1 mark(s) — Thrashing

The best response to thrashing is to:

1. (A) reduce the page size to 1 byte
2. (B) use a faster CPU
3. (C) admit more processes
4. (D) reduce the degree of multiprogramming

Q5 · MCQ · 1 mark(s) — Clock

In the clock algorithm, the pointer reaches a page with reference bit 1. What happens?

1. (A) The page is replaced
2. (B) The bit is cleared and the pointer moves on
3. (C) The page is locked
4. (D) The page is written to disk

10 · Rule Card

• Equal: m/n. Proportional: aᵢ = sᵢ/S × m. Global vs local replacement.
• Thrashing: more paging than work; cure by reducing multiprogramming.
• Working set: distinct pages in last Δ references; D = Σ WSS > m → suspend someone. PFF bounds.
• Clock: bit 1 → clear and move; bit 0 → replace (new page bit 1). Enhanced: prefer (0,0).

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

equal allocationproportional allocationglobal vs local replacementthrashingdegree of multiprogrammingworking-set modelworking-set windowtotal demand Dpage-fault frequencyreference bitclock (second-chance) algorithmenhanced second chance