Cause: Insufficient Frames

In the previous page, we defined thrashing and observed its devastating effects. Now we examine the root cause: insufficient frame allocation. Understanding this cause is essential because it reveals that thrashing is not random or unpredictable—it's the direct, deterministic result of a fundamental resource shortage.

The core insight is straightforward but profound: thrashing occurs when processes receive fewer frames than they need to hold their working sets in memory. This page explores every dimension of this problem.

Every operating system faces a fundamental resource allocation challenge: how should limited physical memory frames be distributed among competing processes? This is the frame allocation problem, and its solution directly determines whether the system thrashes.

The Constraints:

The Mathematical Reality:

Let's formalize the constraint. Given:

• m = total physical frames available for user processes
• n = number of active processes
• f(i) = frames allocated to process i
• WSS(i) = working set size of process i

The fundamental constraint is:

∑ f(i) ≤ m    (Cannot allocate more frames than exist)

For stability, we need:

f(i) ≥ WSS(i)    for all i    (Each process needs enough frames)

Combining these:

∑ WSS(i) ≤ m    (Sum of working sets must fit in memory)

When this condition is violated—when processes collectively need more frames than exist—thrashing is inevitable.

Before discussing how many frames processes should receive, we must establish how many they must receive. Every process has a minimum frame requirement—the bare minimum frames needed for the process to execute at all.

This minimum is determined by the architecture's instruction set and addressing modes:

Why the Minimum Matters:

Consider an instruction like MOV [addr1], [addr2] that copies data from one memory location to another:

1. Instruction page — Contains the MOV instruction itself
2. Source operand page — Contains the data at addr1
3. Destination operand page — Contains the location at addr2

Now imagine the system allocates only 2 frames to this process:

1. Fetch instruction → Page fault, load instruction page (uses frame 1)
2. Read source operand → Page fault, load source page (uses frame 2)
3. Write destination → Page fault, need to load destination page
4. Evict a page—but which one?
5. Evict instruction page → Cannot continue instruction execution
6. Evict source page → Cannot complete the read

Neither option allows the instruction to complete!

Minimum vs. Adequate:

Meeting the minimum prevents infinite loops but doesn't prevent thrashing. The minimum allows a single instruction to complete, but if the working set far exceeds the minimum, the process will still thrash—just not infinitely.

Thrashing fundamentally stems from a demand-supply imbalance. Processes demand frames (through their working sets), and the system supplies them (through physical memory). When demand exceeds supply, something must give.

Visualizing the Imbalance:

              DEMAND SIDE                    SUPPLY SIDE
        ┌─────────────────────┐         ┌─────────────────────┐
        │   Process 1: Web    │         │                     │
        │   Server (WSS=800)  │         │    Total Physical   │
        ├─────────────────────┤         │    Memory: 2048     │
        │   Process 2: DB     │         │    frames           │
        │   Server (WSS=600)  │         │                     │
        ├─────────────────────┤         │    Kernel Reserve:  │
        │   Process 3: App    │         │    256 frames       │
        │   Server (WSS=500)  │         │                     │
        ├─────────────────────┤         │    Buffer Cache:    │
        │   Process 4: Redis  │         │    256 frames       │
        │   Cache (WSS=400)   │         │                     │
        └─────────────────────┘         │    Available:       │
                                        │    1536 frames      │
        Total Demand:                   └─────────────────────┘
        800+600+500+400 = 2300 frames

        DEMAND (2300) > SUPPLY (1536)  →  THRASHING INEVITABLE

In this scenario, there's no allocation strategy that prevents thrashing. The collective working set exceeds available memory by 764 frames (50% oversubscribed).

Sources of Demand Increase:

Understanding where demand comes from helps prevent thrashing:

Sources of Supply Decrease:

Different frame allocation policies handle memory pressure differently, but all eventually fail when demand exceeds supply. Understanding how each policy fails illuminates the fundamental nature of the problem.

The Priority Allocation Trap:

Priority-based allocation gives more frames to high-priority processes. This seems sensible—important work should proceed smoothly. But it creates perverse effects:

1. High-priority processes get enough frames—they run well
2. Low-priority processes get starved—they thrash severely
3. Low-priority processes block on page faults constantly
4. They hold resources (locks, connections) while blocked
5. High-priority processes block waiting for those resources
6. Priority inversion: High-priority work is blocked by low-priority thrashing

The low-priority processes, unable to make progress, cannot release resources the high-priority processes need.

Comparative Failure Analysis:

Each policy makes different tradeoffs, but none escapes the fundamental constraint.

One of the most tragic aspects of thrashing is how the operating system's own scheduling logic accelerates the collapse. The scheduler, following reasonable heuristics, makes decisions that worsen the very problem it should prevent.

The Scheduler's Logic:

Timeline of Scheduler-Induced Collapse:

Time    Event                           CPU%   Page Faults/s   Processes
─────   ─────────────────────────────   ────   ─────────────   ─────────
t₀      Normal operation                 80%        50              10
t₁      Memory pressure begins           75%       100              10
t₂      Scheduler observes low CPU       70%       200              10
t₃      Scheduler admits 2 new procs     60%       500              12
t₄      Thrashing intensifies            40%     1,500              12
t₅      Scheduler admits 3 more procs    20%     5,000              15
t₆      System nearly unresponsive        5%    20,000              15
t₇      Scheduler still trying            2%    50,000              18
t₈      Complete collapse                <1%   100,000+             18

Notice how CPU utilization and page fault rate move in opposite directions. The scheduler's attempts to raise CPU utilization only accelerate the collapse.

The Missing Feedback:

The core problem is that the scheduler lacks memory-aware feedback. It optimizes for CPU utilization without considering memory constraints:

• What the scheduler sees: CPU utilization (too low)
• What the scheduler misses: Page fault rate, paging I/O, working set pressure
• What it should do: Reduce multiprogramming when memory is exhausted
• What it does: Increase multiprogramming, making everything worse

Modern schedulers incorporate memory pressure signals, but the fundamental tension remains.

We can formalize the relationship between frame shortage and thrashing intensity using quantitative analysis.

Page Fault Rate as a Function of Shortage:

Empirical studies show that page fault rate increases non-linearly with shortage ratio:

Page Fault Rate
        ▲
        │
   1.0  ┤                              ╱ Saturation
        │                            ╱
   0.8  ┤                          ╱
        │                        ╱
   0.6  ┤                      ╱
        │                    ╱   Thrashing zone
   0.4  ┤                  ╱
        │                ╱
   0.2  ┤              ╱
        │            ╱
   0.1  ┤──────────╱
        │  Stable ╱
        └─────────┴────┴────┴────┴────┴────► Shortage Ratio
              0    0.2  0.4  0.6  0.8  1.0

The curve shows:

• Stable region (S < 0): Low, constant page fault rate
• Transition (0 < S < 0.3): Rapidly increasing faults
• Thrashing zone (S > 0.3): Fault rate dominates execution
• Saturation (S > 1.0): Fault rate at maximum; all time spent paging

The Non-Linear Cliff:

The transition from "slightly sluggish" to "completely unusable" can occur with a small change in shortage ratio. A system at S=0.2 might feel "a bit slow." At S=0.4, it's "very slow." At S=0.6, it's "frozen."

This non-linearity makes thrashing dangerous:

• Systems can operate near the edge without obvious symptoms
• A small additional load (one more process, one dataset loaded) pushes past the cliff
• Recovery requires substantial load reduction, not just removing what triggered collapse

The page replacement scope—global or local—significantly affects how frame shortage manifests and how thrashing propagates through the system.

Scenario Comparison:

Consider a system with 1000 frames and 4 processes:

• Process A: WSS = 400 (normal application)
• Process B: WSS = 300 (database)
• Process C: WSS = 200 (web server)
• Process D: WSS = 800 (suddenly goes memory-intensive)

With Global Replacement:

1. Process D needs 800 frames, has 250
2. D aggressively faults and evicts pages from A, B, C
3. A, B, C now fault when they try to access evicted pages
4. The entire system's effective throughput collapses
5. Even well-behaved processes suffer from D's behavior

With Local Replacement:

1. Process D has 250 frames, needs 800
2. D can only evict its own pages—thrashes within its allocation
3. A, B, C continue with their allocations intact
4. D's throughput collapses, but A, B, C are unaffected
5. System can still serve requests from functioning processes

Tradeoff Summary: