8.5 Frame Allocation Policies & Thrashing (Working Set Model)

Back to Operating Systems Notes

📚Module 08: Virtual Memory & Page ReplacementTopic 8.5⏱️22 min read

🎯High-Yield For:Computer Science Foundations • Systems Engineering • Performance Tuning

💡 Core Intuition

🍳 The Everyday Analogy: The Overbooked Emergency Room

Imagine an emergency hospital ward with a fixed capacity of 20 hospital beds:

Architecture Flow

The Emergency Ward Capacity Pipeline

Contrasting balanced patient admission with catastrophic system saturation

💡 Hover or click any card for deep-dive operational details

🏥Normal Operation

Healthy Multipatient Care

Optimal Multiprogramming

10 doctors treat 15 patients across the 20 available beds.

→

Over-Admission Trigger

📋Overcrowding

The Administrator Overbooks

Increasing Degree of Multiprogramming

Seeing brief doctor idle periods, the administrator admits 60 patients into the ward.

→

System Collapse

🚨Total Gridlock

Complete Hospital Paralysis

Thrashing (High Paging Activity)

Doctors spend 99% of their time wheeling gurneys back and forth between hallways and beds.

• Thrashing: The catastrophic operating state where a system spends vastly more time moving pages between RAM and disk than executing user instructions.
• The Root Cause: Too many processes admitted into memory (high degree of multiprogramming), starving each individual process of its minimum required execution frames.

---

💻 Bridging to Computer Science

When designing virtual memory subsystems, the operating system must solve two intertwined architectural challenges:

1. Frame Allocation: How many physical frames should be allocated to each competing process?
2. Thrashing Prevention: How does the kernel detect and prevent hyperactive swapping that drives CPU utilization to zero?

Architecture Flow

The Vicious Feedback Loop of Thrashing Collapse

How scheduler misconceptions trigger total system throughput degradation

📈Stage 1

RAM Saturation

Excessive multiprogramming reduces allocated frames per process below working sets.

→

Working Set Starvation

⚠️Stage 2

Fault Explosion

Processes encounter continuous page faults and queue up waiting on swap I/O.

→

Threads Blocked on I/O

📉Stage 3

CPU Starvation

Ready queue empties. CPU utilization drops precipitously toward 0%.

→

Naive LTS Admission

💥Stage 4

Fatal Overload

Scheduler admits new processes to boost CPU usage, triggering total freeze.

The Vicious Feedback Loop of Thrashing

1. As the OS increases the Degree of Multiprogramming (DoM), more processes share memory.
2. Individual processes receive fewer frames than their active working set requires.
3. Page fault rates surge across all processes.
4. Processes transition from RUNNING to BLOCKED / WAITING while stalled on disk I/O.
5. The CPU runs out of ready threads and becomes idle.
6. The naive OS CPU scheduler observes low CPU utilization and concludes: "The system is underutilized; let's admit more processes!"
7. New processes demand even more frames $\to$ page fault rates explode $\to$ Total System Collapse.

---

📚 Core Deep-Dive & Concepts

1. Frame Allocation Strategies

The total number of frames allocated to a process must respect hardware constraints:

• Minimum Frame Bound: Determined by the Instruction Set Architecture (ISA). A single instruction may reference multiple memory operands. For instance, in an indirect addressing architecture with a two-operand instruction (ADD @A, @B), the machine requires at least $6$ frames simultaneously resident to execute the instruction without an infinite fault loop.
• Maximum Frame Bound: Bounded by total physical DRAM installed.

Worked Numerical Example: Proportional Allocation

Consider a system with $m = 30$ physical frames available for user processes. Three processes are active:

• $P_1$ size: $S_1 = 20\text{ KB}$
• $P_2$ size: $S_2 = 30\text{ KB}$
• $P_3$ size: $S_3 = 50\text{ KB}$

Step 1: Compute Total Virtual Demand ($S$): $S = S_1 + S_2 + S_3 = 20\text{ KB} + 30\text{ KB} + 50\text{ KB} = 100\text{ KB}$

Step 2: Calculate Frame Allocations ($a_i$): $a_1 = \frac{S_1}{S} \times m = \frac{20\text{ KB}}{100\text{ KB}} \times 30 = \mathbf{6\text{ Frames}}$ $a_2 = \frac{S_2}{S} \times m = \frac{30\text{ KB}}{100\text{ KB}} \times 30 = \mathbf{9\text{ Frames}}$ $a_3 = \frac{S_3}{S} \times m = \frac{50\text{ KB}}{100\text{ KB}} \times 30 = \mathbf{15\text{ Frames}}$

Verification: $6 + 9 + 15 = 30$ frames allocated cleanly!

---

2. Local vs Global Page Replacement

When a process encounters a page fault, from which pool of frames does it select a victim?

---

3. Resolving Thrashing: Peter Denning's Working Set Model

To eliminate thrashing, an operating system must understand the Locality Model: as a process executes, it moves through a sequence of execution localities.

In 1968, Peter J. Denning formulated the Working Set Model:

Parameter	Working Set Window at $t_1$	Working Set Window at $t_2$
Reference Sequence ($\Delta = 10$)	2, 6, 1, 5, 7, 7, 7, 5, 1, 6	3, 4, 4, 4, 3, 4, 3, 4, 4, 4
Working Set ($WS(t)$)	$\{1, 2, 5, 6, 7\}$	$\{3, 4\}$
**Working Set Size ($	WS(t)	$)**
Memory Allocation Action	Allocate $5$ physical frames to maintain zero-fault execution	Dynamic shrink: Kernel safely reclaims $3$ surplus frames

Definitions & Formulations

1. Working Set Window ($\Delta$): A fixed parameter representing the most recent $\Delta$ page references.
2. Working Set of Process $i$ ($WS_i(t)$): The set of unique pages referenced by process $i$ during the most recent window $[t - \Delta, t]$.
3. Working Set Size ($WSS_i$): The cardinality $|WS_i(t)|$, representing the exact number of frames process $i$ actively needs right now.
4. Total System Frame Demand ($D$): $\mathbf{D = \sum_{i=1}^{n} WSS_i}$

Thrashing Prevention Criterion

Let $m$ be the total physical frames in the system:

• Safe State ($D \le m$): Total demand does not exceed physical capacity. Allocate each process its working set frames. The system runs smoothly with negligible page faulting!
• Thrashing Imminent ($D > m$): The aggregate working set exceeds physical RAM!
  • Action: The operating system MUST suspend (swap out) one or more entire processes.
  • Evicting an entire process frees all its frames, redistributing them to remaining processes so their working sets can fit into RAM.
  • When memory pressure subsides, the suspended process is swapped back in.

---

4. Page Fault Frequency (PFF) Strategy

While the Working Set Model is mathematically elegant, tracking the exact working set on every memory reference is computationally expensive. Operating systems approximate it using Page Fault Frequency (PFF):

---

🏭 In The Real World: Production Case Study

Linux Out-of-Memory (OOM) Killer & PSI (Pressure Stall Information)

In high-density cloud environments (Kubernetes, AWS EC2, Google Borg), thrashing causes severe economic damage by locking server nodes:

Linux Memory Protection Pipeline

Multi-tier telemetry and intervention hierarchy preventing thrashing in production

Layer 1: Telemetry

Pressure Stall Information (PSI)

📊

Tracks exact percentage of CPU time spent stalled on memory and swap I/O via /proc/pressure/memory.

some / full metric gaugesEarly threshold detection

↓Memory stall exceeds configured limit (e.g. 10%)

Layer 2: User-Space Daemon

systemd-oomd Mitigation

🛡️

Proactively terminates entire runaway cgroups and container slices before the kernel locks up.

Container-level blast radiusGraceful system recovery

↓Memory demand still exceeds physical capacity

Layer 3: Kernel Emergency

Kernel OOM Killer

⚡

Emergency kernel routine computing oom_score to forcibly SIGKILL the largest offending process.

oom_badness() scoringInstant RAM reclamation

1. PSI (Pressure Stall Information):
   • Modern Linux kernels expose /proc/pressure/memory. If threads spend $> 15\%$ of their wall-clock time stalled waiting on memory/swap I/O, the kernel flags a Memory Pressure Event.
2. The OOM Killer:
   • If thrashing cannot be cured by swapping, the kernel calculates an oom_score for every process: $\text{oom\_score} \propto \frac{\text{RAM Consumed}}{\text{Total RAM}} - \text{oom\_score\_adj}$
   • The kernel abruptly terminates (SIGKILL) the rogue process with the highest score (typically a runaway browser tab or memory-leaking Python container), instantly reclaiming gigabytes of frames and saving the host machine.

---

🎯 Exam & Interview Pitfall Check

Core Conceptual Questions

Question 1: Define "Thrashing" in an operating system. What are its primary causes and primary symptoms? Answer:

1. Definition: Thrashing is the condition where a process or the entire system spends more time paging (swapping pages in and out of disk) than executing actual program instructions.
2. Primary Symptoms:
   • Page fault rate spikes dramatically.
   • Disk I/O queues become completely saturated.
   • CPU utilization drops toward zero because almost all ready processes are blocked waiting for disk I/O to complete.
3. Primary Causes:
   • Overcommitting physical memory by admitting too many processes (excessive degree of multiprogramming).
   • The sum of the working sets of all active processes exceeds the total number of physical frames available in RAM ($\sum WSS_i > m$).

---

Question 2: In the Working Set Model, how does the size of the window parameter $\Delta$ affect system performance? Answer:

1. If $\Delta$ is chosen TOO SMALL:
   • The window will not capture the entire locality of the process.
   • Active pages needed by the current loop or function will be prematurely dropped from the working set, causing continuous page faults.
2. If $\Delta$ is chosen TOO LARGE:
   • The window will encompass pages from prior localities that are no longer needed.
   • Memory will be over-allocated to the process, artificially inflating $WSS_i$ and reducing the degree of multiprogramming.
3. If $\Delta \to \infty$:
   • The working set becomes the set of all pages ever referenced throughout the entire execution history of the process!

Common Interview Traps

• The "CPU is Busy During Thrashing" Fallacy: Many students believe the CPU is at 100% load during thrashing. In reality, CPU utilization drops toward 0%! The CPU is starved of executable instructions because all processes are suspended waiting for disk controllers to swap pages.
• Confusing Page Replacement with Process Suspension: Page replacement cannot solve thrashing if total memory demand exceeds physical RAM! To stop thrashing, the OS must suspend an entire process (swapping it to disk) to reduce the degree of multiprogramming.

---

🗺️View Complete Operating Systems Roadmap & Syllabus

← Previous Topic8.4 LRU & Stack AlgorithmsNext Topic →9.1 Magnetic Disk Anatomy