Skip to content
Tutorials Center
My learning

Topics

Lesson 44 of 66 ยท Virtual Memory

Frame Allocation, Thrashing and the Working-Set Model

Learn how frames are divided among processes, why too much multiprogramming causes thrashing, and how the working-set model and page-fault frequency prevent it.

Page replacement decides which page to evict. A second question remains: how many frames does each process get? Give a process too few and it faults all the time. Give the system too many processes and every process has too few. The result, called thrashing, can bring a computer almost to a halt.

Allocating frames

Every process needs a minimum number of frames, set by the hardware: one instruction may reference several pages (for example an instruction plus two operands, possibly indirect), and all of those pages must be present for it to complete. The OS divides the remaining frames among processes:

Scheme Rule Weakness
Equal allocation m frames for n processes: m / n each A tiny process wastes frames, a big one starves
Proportional allocation Frames in proportion to process size Ignores priority and actual behaviour
Priority-based Frames in proportion to priority (or size and priority) Low-priority processes may fault heavily
Python Equal and proportional allocation

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Global versus local replacement

  • Global replacement: a faulting process may take a frame from any process. Throughput is usually higher because frames move to wherever they are needed, but a process's fault rate depends on the behaviour of others, and a memory-hungry process can hurt everyone.
  • Local replacement: a process may only replace one of its own frames. Behaviour is predictable and isolated, but a process cannot use frames that others leave idle.

Most general-purpose systems use global replacement with limits and background reclamation, and servers or containers often add per-group memory limits (cgroups on Linux) that act like local allocation.

Thrashing

A process that does not have enough frames for the pages it is actively using faults, replaces a page, and faults again soon on the page it just evicted. It spends more time paging than executing. This is thrashing.

The classic vicious circle:

  1. CPU utilization looks low, because processes are waiting for page I/O.
  2. The scheduler responds by starting more processes to use the CPU.
  3. The new processes take frames from the others, causing more faults.
  4. Even more processes wait on the paging disk, utilization falls further, and the OS starts yet more.
flowchart LR
    A["More processes"] --> B["Fewer frames each"]
    B --> C["More page faults"]
    C --> D["Disk queue grows, CPU idles"]
    D --> E["Scheduler adds processes"]
    E --> A

Plot CPU utilization against the degree of multiprogramming and you see it climb, then collapse sharply.

The next simulation gives a fixed number of frames to N identical processes. Each process has a hot set of 12 pages that it accesses in a random pattern (strong locality), and uses LRU with its share of the frames. We compute the page-fault rate and an upper bound on CPU utilization when one disk can serve a fault in 100 time units.

Python The thrashing cliff

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Up to 8 processes (12 frames each) every working set fits and utilization is 100%. At 9 processes each gets 10 frames, 2 fewer than the working set, and the fault rate leaps from 0.003 (only the first touches) to about 0.18: utilization drops to about 5%. From there on the system is thrashing: more multiprogramming only makes things worse. The cliff is sharp because of locality: a process with slightly fewer frames than its working set faults very often, since LRU keeps evicting exactly the page that is needed next.

The working-set model

The working-set model, proposed by Peter Denning, is built on locality. Choose a window of ฮ” (delta) most recent page references. The working set of a process, WS(t, ฮ”), is the set of distinct pages referenced in the last ฮ” references. It approximates the pages that the process is actively using. If ฮ” is too small it misses part of the locality; if too large it spans several localities.

Let WSS_i be the size of process i's working set. The total demand is D = sum of WSS_i. If D exceeds the number of available frames, thrashing will occur.

OS policy: admit or run a process only if its working set fits. When D > frames, suspend (swap out) one or more processes; when D drops below the frame count, start or resume one. Each process keeps its working set in memory, so it runs efficiently; the others wait their turn.

Python Computing working sets from a trace

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The first process has a working set of 3 pages in its first phase and grows to 5 or 6 while it moves to its second locality. Process 2, which scans, has a working set equal to the window size. When their combined demand exceeds the frames available, the OS should suspend one of them rather than let both thrash.

Tracking exact working sets on every reference is too expensive, so systems approximate them with periodic timer interrupts and reference bits: if the reference bit was set at any of the last few ticks, the page is in the working set.

Page-fault frequency (PFF)

A more direct control loop avoids computing working sets. Measure each process's page-fault rate and keep it inside a band:

  • Fault rate above the upper bound: the process needs more frames, so give it one (if none are free, suspend a process).
  • Fault rate below the lower bound: the process has too many; take a frame away.
flowchart LR
    R["Measure fault rate"] --> A{"Too high?"}
    A -- yes --> G["Allocate another frame (or suspend a process)"]
    A -- no --> B{"Too low?"}
    B -- yes --> T["Take a frame away"]
    B -- no --> K["Leave allocation as is"]

Keeps each process near the sweet spot between thrashing and wasting memory.

What to do about thrashing in practice

  • Limit the degree of multiprogramming (the number of runnable processes) based on memory demand, not CPU idleness alone.
  • Use local or limited replacement, so one runaway process cannot take all frames.
  • Add RAM. It is the best cure; but also reduce memory use: fix leaks, shrink caches, tune the working set of the application.
  • Recognize the symptoms: high disk activity (swap in/out), very low CPU usage, a sluggish system. On Linux, vmstat shows si/so (swap in/out) and free, and /proc/pressure/memory reports memory pressure.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is thrashing?

    When frames are insufficient for the working sets, faults dominate and useful work nearly stops.
  2. 2. Why can a scheduler that adds processes when CPU utilization is low make thrashing worse?

    The CPU is idle because of page waits, so adding processes deepens the memory shortage.
  3. 3. What does the working set of a process represent?

    It approximates the pages the process is actively using at the moment, based on locality.
  4. 4. The total working-set demand D is larger than the number of frames. What should the OS do?

    Running fewer processes whose working sets fit is better than running all of them while thrashing.
  5. 5. How does page-fault-frequency control work?

    Too many faults: give frames. Too few: take frames away.

Summary

  • Frames are shared out by equal, proportional or priority-based allocation; replacement may be global or local.
  • Thrashing happens when processes have fewer frames than their working sets: faults dominate, the CPU idles, and naive schedulers make it worse.
  • The working-set model uses the last ฮ” references to estimate needed frames; admit processes only if total demand fits.
  • Page-fault-frequency control adjusts frames to keep the fault rate in a band.
  • Practical cures: limit multiprogramming, add RAM, reduce memory use.

Next: Copy-on-Write, Memory-Mapped Files and Kernel Memory