Lesson 9.7: Thrashing

01 Introduction

Unit 9 has built up the virtual-memory system piece by piece. Lesson 9.1 introduced paging, the division of the address space into fixed-size pages. Lesson 9.2 presented the multi-level page table that makes a 64-bit address space feasible. Lesson 9.3 presented the TLB, the small hardware cache of translations that makes paging fast. Lesson 9.4 presented demand paging, the mechanism that loads a page only when it is accessed. Lesson 9.5 presented the page-fault handler that services the fault. Lesson 9.6 presented the page-replacement policy that chooses which page to evict when a frame is needed.

Each of these mechanisms is designed to make virtual memory work well under normal conditions. But there is a regime in which the whole system breaks down. When the total demand for memory exceeds the physical memory by enough that the processes cannot all keep their working sets resident, the system enters a state called thrashing: the processes spend more time waiting for pages than executing, the CPU sits idle while the disk is saturated with paging traffic, and throughput collapses — often by two or three orders of magnitude. A system that was serving thousands of requests per second can drop to tens.

Thrashing is not a bug in any single component. It is an emergent property of the interaction between demand paging, the page-replacement policy, and the scheduler's decision to run more processes than memory can support. The mechanism is a positive-feedback loop, and it is the reason the operating system must sometimes refuse to run a process, or must suspend one that is already running. The tension between admitting more work (to keep the CPU busy) and admitting too much (which causes thrashing) is the central scheduling problem of memory management.

This lesson presents thrashing in three parts. First, it describes the phenomenon: the feedback loop, the thrashing curve, and the way the fault rate spirals out of control. Second, it presents the working-set model — Peter Denning's framework for understanding what a process actually needs — and the working-set policy that uses the model to prevent thrashing. Third, it presents the page-fault-frequency (PFF) policy, a simpler alternative that monitors the fault rate directly. The lesson also discusses the relationship between thrashing and the local-versus-global replacement decision from Lesson 9.6, the way modern Linux detects and responds to memory pressure (including the OOM killer), and the effect of container resource limits on thrashing. It closes Unit 9 and Module 3 by summarizing the virtual-memory system as a whole.

Prerequisites

This lesson is the culmination of Unit 9 and assumes familiarity with all six preceding lessons. In particular, it builds on the demand-paging mechanism of Lesson 9.4, the effective-access-time calculation of Lesson 9.5, and the page-replacement algorithms of Lesson 9.6. The key relationships — the enormous gap between memory latency and disk latency, the difference between minor and major faults, and the role of locality in determining the fault rate — are used throughout. The scheduler and the concept of the degree of multiprogramming from Unit 5 are referenced but not redeveloped. No prior knowledge of the working-set model or of thrashing is assumed.

02 Learning objectives

By the end of this lesson you will be able to

Define thrashing and describe the positive-feedback loop that produces it.
Interpret the thrashing curve (CPU utilization versus degree of multiprogramming).
Define the working set, the working-set window, and the working-set size, and explain how they relate to locality.
Describe the working-set and page-fault-frequency policies and explain how they prevent thrashing.
Explain the interaction between the degree of multiprogramming, local and global replacement, and thrashing, and describe how modern systems respond.

This lesson contributes to U9.7 and U9.8, and to course learning outcomes CLO1, CLO4, and CLO6.

03 Required reading

Operating System Concepts — Chapter 10, Section 10.6, Thrashing. The standard treatment of the phenomenon, the working-set model, the page-fault-frequency policy, and the relationship between thrashing and the degree of multiprogramming.
OSTEP — Chapter 22, Swapping: Policies, through the sections on the working-set and page-fault-frequency approaches. The clearest available treatment of the interaction between the workload, the replacement policy, and the amount of memory.
Tanenbaum & Bos — Modern Operating Systems, Chapter 3, Section 3.5, Design Issues for Paging Systems, and Chapter 3, Section 3.6, Implementation Issues. A complementary treatment that includes the load-control aspects of the problem.
Denning, P. J. — The Working Set Model for Program Behavior. Communications of the ACM, 1968. The paper that introduced the working-set model and the working-set policy, and that first characterized thrashing formally.
Denning, P. J. — Thrashing: Its Causes and Prevention. AFIPS Fall Joint Computer Conference, 1968. The companion paper that presents the thrashing phenomenon directly, including the thrashing curve and the L = S result.
Denning, P. J. — Virtual Memory. ACM Computing Surveys, 1970. A synthesis of the working-set model and its application to operating-system design. The definitive reference for this lesson.
Love, R. — Linux Kernel Development, 3rd ed., Chapter 12, Memory Management. The Linux implementation of memory pressure detection, page reclaim, and the OOM killer.
Linux man pages: man 5 proc (the /proc/meminfo and /proc/vmstat interfaces), man 1 vmstat, man 1 free, man 5 proc (the /proc/<pid>/oom_score interface), man 7 cgroups (for memory.limit_in_bytes, memory.max, and the memory controller).

Reading strategy

Read the Silberschatz section first for the formal statement of the phenomenon and the policies. Then read Denning's 1968 paper Thrashing: Its Causes and Prevention — it is short, remarkably clear, and the origin of everything the textbooks say about the topic. Pay particular attention to the thrashing curve and the working-set model; they are the conceptual core of the lesson and of the rest of the unit. Finally, read the Linux kernel's memory management material for the modern implementation, which includes the reclaim subsystem, the memory-pressure detection heuristic, and the OOM killer. These are the mechanisms a contemporary system actually uses to avoid the thrashing collapse.

04 Core content

4.1 What thrashing is

Thrashing is the state in which a system spends more time paging than executing — more time servicing page faults than making progress on the processes' actual work. It is not a specific algorithm or a specific failure; it is a property of the interaction between the workload, the amount of memory available, and the page-replacement policy. When the working sets of the running processes, taken together, exceed the physical memory, the system enters a positive-feedback loop that spirals out of control.

The mechanism of the loop is the key to understanding thrashing. Consider a process that has been given fewer frames than its working set requires. When it faults and the page-replacement policy must choose a victim, the victim is drawn from the same process's small allocation (with local replacement) or from the system as a whole (with global replacement). In either case, the victim is likely to be a page that the process will need again soon, because the process's working set is by definition the pages it uses frequently. The eviction of a working-set page causes another fault when the process next reaches that page, and that fault triggers another eviction, and so on. The process spends most of its time waiting for pages, not executing its code.

The feedback has three components, and they reinforce each other.

Insufficient frames → high fault rate. When a process's frame allocation is smaller than its working set, every access is at risk of a fault, because the required page is as likely as not to have been evicted to make room for a previous page.
High fault rate → less useful work. Each fault blocks the process while the disk reads the page. If faults are frequent, the process spends most of its time blocked, and its useful throughput drops.
Less useful work → lower CPU utilization. The process is idle waiting for I/O, and the CPU has nothing to do. The scheduler observes the idle CPU and, in a system that uses CPU utilization as an admission signal, admits more processes to keep the CPU busy.

The third component is the fatal step. Adding more processes takes frames from the existing processes, shrinking their allocations further, which increases their fault rates, which drives CPU utilization even lower, which triggers the admission of still more processes. The system converges to a state in which almost every process is blocked on I/O, the CPU is nearly idle, the disk is saturated with paging traffic, and the throughput is a small fraction of what a properly sized system would achieve.

Figure 9.7 — The thrashing curve. CPU utilization is shown as a function of the degree of multiprogramming (the number of processes running). As more processes are added, utilization rises — up to a point. Beyond that point, the total working set of the processes exceeds the physical memory, and each additional process causes more faults for everyone. Utilization collapses. The peak occurs at the point where the sum of all working sets equals the physical memory; to the left of the peak, the system is safe; to the right, it is thrashing.

4.2 The working-set model

The working-set model, introduced by Peter Denning in 1968, is the conceptual framework that explains the thrashing curve and provides the basis for preventing thrashing. The model defines the working set of a process at a given moment as the set of pages it has accessed in the last Δ references, where Δ is the working-set window. The working set is the process's current locality: the pages it is actively using, and therefore the pages it must keep in memory to run efficiently.

The size of the working set — the working-set size, or WSS — is the number of distinct pages in the window. It is the number of frames the process needs to run without excessive faulting. If a process has at least WSS frames, it can keep its current working set resident, and its fault rate will be low. If it has fewer than WSS frames, it cannot keep its working set resident, and its fault rate will be high — because the pages it evicts are exactly the pages it will need again soon.

The working-set window Δ is the model's key parameter. It must be large enough to include a full cycle of the process's locality — for example, a complete pass through an inner loop — but small enough to exclude the process's older, no-longer-needed data. If Δ is too small, the working set will be too small, and the process will have fewer frames than it actually needs. If Δ is too large, the working set will include pages the process is no longer using, and the system will overestimate the process's needs and refuse to admit new work unnecessarily. Choosing Δ is a tuning problem, and different systems choose different values; on Linux, the equivalent is the vm.swappiness parameter combined with the active/inactive LRU lists, which together define a similar window.

Denning proved a key result about the relationship between the working-set window and the fault rate. If the total number of frames S available to a process is at least its working-set size, and if the process's locality is stable over the window, then the process's fault rate is bounded — it faults only when its working set changes, which is a bounded number of times per unit of useful work. If S is less than the working-set size, the process's fault rate is not bounded: it faults repeatedly on the same pages, because they cannot all stay resident. The relationship is sometimes summarised as L = S, where L is the mean time between faults and S is the number of frames: when the number of frames is at least the working-set size, the fault rate is low and stable; when it falls below, the fault rate rises unboundedly.

Figure 9.7b — The working-set model. A sliding window of width Δ moves across the reference string, and the pages inside the window at each moment form the working set. The working-set size (WSS) varies over time: it is small during periods of stable locality (the process is in a tight loop) and larger during transitions (the process is moving from one phase to another). A process whose allocation is at least its peak WSS will run without excessive faults; one whose allocation is smaller will thrash.

4.3 The working-set policy

The working-set policy uses the working-set model directly to prevent thrashing. The operating system tracks each process's working set — the pages it has accessed in the last Δ references — and allocates each process at least its WSS frames. The sum of all the working sets is the total demand on memory, and the operating system compares this sum against the available physical memory.

If the sum fits, the system is in the safe region: every process has enough frames for its working set, and the fault rate is low. If the sum exceeds the available memory, the system is at risk of thrashing, and the working-set policy takes one of two actions.

Reduce the degree of multiprogramming. The operating system suspends one or more processes — typically the ones with the smallest working sets or the lowest priority — freeing their frames for the remaining processes. A suspended process is swapped out in its entirety and does not run until the system has enough free memory to resume it. When the sum of the remaining working sets fits in memory, the remaining processes can run efficiently.
Refuse to admit new processes. If a new process would push the sum over the limit, the operating system defers its admission until some existing process terminates or shrinks. This is the long-term scheduler's (Lesson 5.1) job: it controls the degree of multiprogramming, and the working-set policy informs its decisions.

The working-set policy is the classical solution to thrashing. It is precise — it measures exactly what each process needs — and it is effective — it keeps the system in the safe region by construction. Its disadvantage is that it requires the operating system to track the working set of every process, which means recording the time of every page access and maintaining the window of the last Δ references. On a modern system with thousands of pages per process and hundreds of processes, this tracking is expensive, and the exact window is approximated.

4.4 The page-fault-frequency policy

The page-fault-frequency (PFF) policy is a simpler alternative that avoids tracking the working set directly. Instead of measuring the working set, it measures the process's fault rate and uses it as a proxy for whether the process has enough frames. The policy sets an upper bound and a lower bound on the acceptable fault rate:

If a process's fault rate is above the upper bound, the process needs more frames — it is faulting because its working set does not fit in its current allocation. The policy gives it more frames, taking them from processes whose fault rates are below the lower bound.
If a process's fault rate is below the lower bound, the process has more frames than it needs — its working set fits easily in its allocation. The policy takes some of its frames away, to give to processes that need them.
If a process's fault rate is between the bounds, the process has about the right number of frames, and the policy does nothing.

If no frames can be freed — because every process is at or above its upper bound — the system is in a state where the total demand exceeds the memory, and the PFF policy, like the working-set policy, must reduce the degree of multiprogramming by suspending one or more processes.

The PFF policy has three advantages over the working-set policy. First, it does not require the operating system to track the working set: the fault rate is measured directly from the page-fault counter, which the kernel already maintains. Second, it responds only to faults, which are the actual symptom of insufficient memory; a process whose working set has grown but whose fault rate is still low does not need more frames. Third, its parameters — the upper and lower bounds on the fault rate — are intuitive and easy to tune: the operator sets the bounds based on the acceptable performance, and the policy handles the rest.

Its disadvantage is that it is reactive: the process must fault before the policy responds, and by the time the policy acts the process has already paid the cost of the fault. The working-set policy, in contrast, is predictive: it can detect that a process's working set is growing before the faults occur and allocate frames proactively. On systems where the fault cost is high — a spinning disk, a congested storage system — the difference matters, and the working-set policy's prediction is valuable. On systems with fast storage and cheap faults, the PFF policy's simplicity wins.

4.5 Local versus global replacement, revisited

Lesson 9.6 introduced the distinction between local and global replacement. The choice is directly related to thrashing, and the relationship is worth revisiting here.

With global replacement, a process that faults may evict a page belonging to another process. The advantage is that frames flow from where they are less needed to where they are more needed: a process that is heavily faulting takes frames from processes that are idle. The disadvantage is that a single heavily faulting process can steal frames from every other process, dragging them all into a high fault rate and precipitating a system-wide thrash. Global replacement is therefore efficient but unstable: it works well when the aggregate working set fits in memory and works badly when it does not.

With local replacement, each process's frames are protected from the others: a fault in process A can only evict a page belonging to process A. The advantage is stability: one process's behaviour cannot affect another's. The disadvantage is inefficiency: a process whose working set exceeds its allocation will thrash within its own frames, evicting its own pages repeatedly, even though there may be free frames elsewhere in the system. The frames cannot flow to where they are needed, because the policy forbids it.

Real systems use a hybrid. Linux, for example, uses global replacement within the page cache — all file pages and anonymous pages compete for the same pool of frames — but the OOM killer provides an emergency exit: when the system cannot reclaim enough memory through normal eviction, it terminates the process with the highest memory usage, freeing its frames for the survivors. The choice of which process to kill is a form of local allocation made at the moment of crisis, when the global policy has failed.

The choice between local and global also interacts with the page-fault-frequency policy. If the policy is given a process whose fault rate is above the upper bound but for which no frames can be spared, the policy must decide whether to suspend the process or to allow it to thrash. Suspending is the right choice in the short term — it frees the process's frames for the survivors — but it delays the process's work, and if the system is persistently over-committed, the suspended process may never resume. This is the tension that the OOM killer resolves by making the decision final: rather than suspending the process indefinitely, it terminates it, so that the resources are definitely freed and the rest of the system can run.

4.6 Detecting and responding to thrashing in Linux

Modern Linux does not implement the classical working-set or PFF policies in their exact form, but it implements equivalent mechanisms. Understanding how a real system handles thrashing is useful, because the classical policies are simplified models and the real system's behaviour is more nuanced.

Linux's memory management is built around a set of LRU lists. Each zone (roughly, a region of physical memory with its own characteristics) has an active list and an inactive list. Pages are initially placed on the inactive list. When a page on the inactive list is accessed, it is promoted to the active list. When the kernel needs to reclaim memory, it scans the inactive list and evicts clean pages (or writes dirty pages back and then evicts them). Pages on the active list are protected from eviction until they are demoted to the inactive list, which happens when the active list grows too large relative to the inactive list.

This two-list structure is an approximation of the working-set model. The active list is roughly "the pages that are in the working sets"; the inactive list is roughly "the pages that are not currently needed". The proportion of pages on the active list is a measure of the total working-set size, and the kernel uses this proportion to decide how aggressively to reclaim.

Linux also implements memory pressure detection. The kernel tracks the rate at which pages are being reclaimed and the rate at which they are being faulted back in. If the reclaim rate is high but the system is not making progress — that is, if pages are being reclaimed as fast as they are being faulted — the kernel concludes that the system is thrashing. It then takes progressively more aggressive action:

Direct reclaim. When the free-memory threshold is crossed, the faulting process itself reclaims pages synchronously before its page fault can be satisfied. This slows the process down but ensures that memory is available.
kswapd. A background kernel thread (kswapd) performs asynchronous reclaim, freeing pages before the free-memory threshold is crossed. Its purpose is to keep the system in the safe region without forcing processes to wait.
Swapping out anonymous pages. If reclaim cannot free enough clean file pages, the kernel writes dirty anonymous pages to the swap area, freeing their frames for reuse. The vm.swappiness parameter controls how aggressively the kernel swaps anonymous pages relative to evicting file pages.
OOM killer. If none of the above suffices — if the system runs out of physical memory and swap, and no pages can be reclaimed — the kernel invokes the OOM killer, which selects a process to terminate and frees its memory. The selection is based on a heuristic score that combines memory usage, priority, and the process's oom_score_adj setting. The process with the highest score is killed.

The OOM killer is the system's last resort. It is not a graceful mechanism: the killed process loses all its state, and the application may not be able to recover. But it is preferable to the alternative — a system that thrashes indefinitely, serving no useful work and requiring a manual reboot. Modern Linux tries very hard to avoid the OOM killer by keeping the system in the safe region, and it succeeds on most workloads. When it fails, the OOM killer is the mechanism that returns the system to a usable state.

4.7 Thrashing and containers

In modern cloud and container environments, the problem of thrashing acquires a new form. A container is a set of processes that share the host kernel but have their own resource limits, enforced through control groups (cgroups). The memory controller of cgroups imposes a limit on the total memory a container can use, and it reclaims pages when the limit is approached. If a container's working set exceeds its memory limit, the container thrashes within its limit: its pages are reclaimed and refaulted in a tight loop, and the container's throughput collapses while the host's other containers run normally.

The container's thrashing is contained — it does not affect the other containers on the host — but it is not prevented. The memory limit is a hard ceiling, and the kernel cannot exceed it. The container's operators must size the limit correctly, or the container will thrash. If the limit is exceeded by enough that reclaim cannot keep up, the cgroup's OOM killer (a per-cgroup variant of the host's OOM killer) terminates one of the container's processes, freeing memory for the survivors.

The same mechanics apply to virtual machines, though the mechanism is different. A VM has a fixed amount of memory — the size of its virtual RAM — and the guest operating system inside the VM sees that memory as physical. If the VM's workload exceeds the VM's memory, the guest thrashes inside the VM, and the hypervisor is not involved (unless the VM is over-committed at the host level, in which case the host may also reclaim pages). Containers and VMs therefore share the same fundamental problem: a memory limit is a limit, and a workload whose working set exceeds it will thrash or be killed.

4.8 Preventing thrashing in practice

The classical policies — working-set and PFF — are the theoretical answer to thrashing, but in practice, the most effective prevention is at the level of system configuration and application design. The following practices are the standard ways to avoid thrashing in real systems.

Size memory to the workload. The most effective prevention is simply to have enough memory. If the system has enough physical memory for the aggregate working set of the processes it runs, it will not thrash. This is why memory is the resource that most often determines a system's capacity: the working sets of modern workloads (a web browser, a JVM, a database) are large, and undersizing memory is the most common cause of thrashing.
Control the degree of multiprogramming. Limit the number of processes or containers running concurrently, so that the aggregate working set fits in memory. On a Linux system, this is done with systemd resource controls, cgroup memory limits, or a batch scheduler that controls job admission.
Improve the application's locality. A program that touches memory with poor locality has a large working set relative to its useful work, and it will thrash sooner than a program with good locality. The techniques of Lesson 8.1 — cache blocking, data layout, avoiding pointer chasing — apply equally to the working set. A program that would thrash on a given system can sometimes be modified to fit.
Use mlock and madvise. A program that knows which parts of its memory are critical can mlock them — pin them in memory so they are never evicted — or advise the kernel about its access patterns with madvise. Locking pages reduces the risk that the critical pages are evicted during a memory-pressure event.
Monitor and respond. A system that is beginning to thrash gives warning signs: rising fault rates, increasing swap usage, falling throughput, rising si/so (swap-in/swap-out) in vmstat. Operators who monitor these signs can respond — by killing processes, by adding memory, or by reconfiguring the workload — before the system enters the full thrashing collapse.

The common thread is that thrashing is a system-level problem, not a component-level one. The page-replacement policy can make the system more or less susceptible, but it cannot prevent thrashing if the system is fundamentally undersized. The decision to admit a process is the decision to commit its working set to memory, and if the sum of the admitted working sets exceeds memory, no policy can save the system. Prevention is therefore a matter of designing the system's workload and its memory together, not of choosing a better algorithm.

4.9 Common misconceptions

"Thrashing is a bug in the page-replacement policy."

Thrashing is a property of the workload and the memory, not of the policy. A better policy can delay the onset of thrashing, but no policy can prevent it if the aggregate working set exceeds the physical memory. The fix is more memory or less work.

"Adding more processes always improves throughput."

Only up to a point. Beyond the peak of the thrashing curve, adding processes decreases throughput, because each new process takes frames from the existing ones and increases everyone's fault rate.

"The working set is the same as the resident set."

The working set is what a process needs; the resident set is what it currently has. The two are equal only when the process has been allocated enough frames. If the resident set is smaller than the working set, the process will thrash.

"Swap space is only used when memory is full."

Swap space is used whenever the kernel decides to evict an anonymous page. This can happen even when the system has free memory — for example, when a large page cache is more valuable than the anonymous pages. The vm.swappiness parameter controls this trade-off.

"Global replacement always prevents thrashing."

Global replacement allows frames to flow to where they are needed, which helps when the system is in the safe region. But when the aggregate working set exceeds memory, global replacement makes things worse, because a single faulting process drags every other process down with it.

"The OOM killer is a failure of the operating system."

The OOM killer is a deliberate, controlled failure. It is the system's response to the impossibility of running more work than memory can support. Its alternative — indefinite thrashing — would be worse, because the system would serve no useful work at all.

"A larger swap space prevents thrashing."

A larger swap space allows the system to have more total anonymous memory, but it does not prevent thrashing: it only changes the point at which the system can no longer allocate. If the aggregate working set exceeds physical memory, the system will thrash regardless of how much swap is available.

"The working-set window Δ is easy to choose."

Choosing Δ is a genuine tuning problem. Too small a window underestimates the working set; too large a window overestimates it. The right value depends on the workload's locality and on the cost of a fault. Real systems approximate the window with heuristics rather than measure it exactly.

05 Worked example

The following example models the thrashing feedback loop with a concrete numerical simulation, and shows how the working-set policy and the PFF policy respond to the system's state.

A numerical model of the thrashing loop

Consider a system with 1000 frames available and a workload of 20 processes. Each process has a working set of 80 pages in its current phase, and each access takes 1 µs of CPU time if it does not fault. When a process faults, the page must be read from disk, which takes 200 µs (a reasonable value for an NVMe SSD).

We model the system's behaviour as the number of processes increases, using a simplified model in which the fault rate of a process depends on its frame allocation relative to its working set.

If a process is allocated at least 80 frames — its working set — it faults only on phase transitions, so its fault rate is effectively zero for our purposes. If it is allocated fewer than 80 frames, the fraction of its accesses that fault is proportional to the shortfall: a process with 40 frames (half its working set) faults on roughly half its accesses; one with 20 frames (a quarter) faults on roughly three-quarters of its accesses. (These are rough values; the exact relationship depends on the replacement policy and the reference string's structure.)

The table below shows the fault rate, the useful CPU throughput, and the total throughput for the system as the number of processes varies. Each process's allocation is 1000 / n frames.

Processes	Frames each	Fault rate per access	Effective time per access	Useful throughput
1	1000	~0	1 µs	1.00 million accesses/s
5	200	~0	1 µs	5.00 million accesses/s
12	83	~0	1.00 µs	12.00 million accesses/s
13	76	0.05	1 + 0.05 × 200 = 11 µs	13 / 11 = 1.18 million accesses/s
16	62	0.23	1 + 0.23 × 200 = 47 µs	16 / 47 = 0.34 million accesses/s
20	50	0.375	1 + 0.375 × 200 = 76 µs	20 / 76 = 0.26 million accesses/s

The behaviour is dramatic. Up to 12 processes, the system is in the safe region: each process has about 83 frames, slightly more than its working set of 80, and the fault rate is negligible. Throughput rises linearly with the number of processes, reaching 12 million accesses per second.

At 13 processes, the allocation drops below the working set — 76 frames versus 80 — and the system tips over the peak of the thrashing curve. The fault rate jumps from zero to 5 percent, and the effective time per access rises from 1 µs to 11 µs. The total throughput falls, from 12 million accesses per second to 1.18 million — a factor of ten.

Beyond 13 processes, the system is firmly in the thrashing region. At 20 processes, each process has half its working set, faults on roughly 37.5 percent of its accesses, and the total throughput is 0.26 million accesses per second — a factor of forty-six below the peak. The system is running five times as many processes as it was at the peak, but doing one-forty-sixth as much useful work.

The thrashing curve for this workload

The data above can be presented as a thrashing curve: total throughput on the vertical axis, number of processes on the horizontal axis.

Processes	Total throughput (millions/s)	Regime
1	1.00	safe — far below peak
5	5.00	safe — below peak
10	10.0	safe — approaching peak
12	12.0	peak — every process has its working set
13	1.18	thrashing — the collapse
16	0.34	thrashing — worse
20	0.26	thrashing — near the bottom

The peak is at 12 processes, exactly the point at which the aggregate working set — 12 × 80 = 960 frames — first exceeds the 1000 frames available. (At 12 processes, 1000/12 = 83.3 frames per process, just above the working set; at 13, 1000/13 = 76.9, just below.) The collapse from 12 million accesses per second to 1.18 million, caused by a single additional process, is the sharpest feature of the curve. It is the signature of the positive-feedback loop.

What the working-set policy would do

The working-set policy tracks each process's working set, and it allocates frames to match. With 20 processes and a working set of 80 pages each, the total working set is 1600 pages — more than the 1000 frames available. The policy detects this mismatch and takes action: it suspends processes until the total working set fits.

To fit 1000 frames, the policy can keep at most ⌊1000 / 80⌋ = 12 processes running. It would suspend the remaining 8, swapping them out in their entirety. The 12 running processes would each have about 83 frames, just enough for their working sets, and the system would run in the safe region.

The suspended processes are not terminated: they are swapped out and will be resumed when memory becomes available (for example, when one of the 12 running processes terminates). The total amount of work the system can do is unaffected — the 12 processes do the work of 12, and the other 8 will do theirs when they run — but the throughput of the 12 running processes is maximized, because they are not competing for frames. This is the classic working-set trade-off: it sacrifices the ability to run more processes concurrently for the ability to run the running ones efficiently.

What the PFF policy would do

The PFF policy monitors each process's fault rate and adjusts allocations based on the bounds. Suppose the bounds are 10 percent (upper) and 1 percent (lower).

At 12 processes, each has 83 frames and a fault rate near zero — below the lower bound. The policy would take frames from these processes and give them to any process that needed them, but there are none, so the frames stay where they are.
At 13 processes, each has 76 frames and a fault rate of about 5 percent — above the lower bound but below the upper. The policy does nothing.
At 16 processes, each has 62 frames and a fault rate of 23 percent — above the upper bound. The policy would try to give each process more frames, but there are no free frames, so the policy would suspend one or more processes to free their frames for the survivors.

The PFF policy's response is reactive: it acts only when the fault rate has already exceeded the upper bound. By that point, the system has spent some time in the thrashing region — the faults have already occurred, and the throughput has already dropped. But the policy detects the problem and takes corrective action, suspending processes until the fault rate of the survivors returns to an acceptable level.

The trade-off between safety and utilization

The two policies illustrate a fundamental trade-off. The working-set policy keeps the system in the safe region by construction — it never admits more work than memory can support — but it may refuse to admit processes that would, in practice, be fine. The PFF policy admits more work and reacts only when the fault rate exceeds the bound, which allows higher utilization at the cost of occasional excursions into the thrashing region.

Which is better depends on the workload. A workload with stable, predictable working sets — a long-running scientific computation, a database with a fixed schema — benefits from the working-set policy's conservatism, because the policy never causes a collapse. A workload with variable working sets — a web server with fluctuating load, a container environment with short-lived jobs — benefits from the PFF policy's flexibility, because the policy can admit more work when the working sets are small and adjust when they grow.

Real systems use a combination, and the exact policy depends on the workload's characteristics. Linux's active/inactive list structure is closer to the working-set model in spirit, but its thresholds and its response to pressure are tuned to respond reactively rather than predictively. The OOM killer is the final safety net, invoked only when the reactive mechanisms have failed.

06 Interactive activity

Activity · observe and simulate thrashing

The goal of this activity is to observe the thrashing phenomenon on a real system, measure the signals that indicate its onset, and simulate a thrashing workload under different memory configurations. Work through the steps in your course VM.

Observe the system's memory state. Use free, vmstat, and /proc/meminfo to see the system's current memory state and the amount of swap in use.
```
free -h
vmstat 1 5
cat /proc/meminfo | grep -E 'MemTotal|MemFree|MemAvailable|Swap'
```
Note the columns in vmstat: si (swap in), so (swap out), bi (blocks in), bo (blocks out). Under normal operation, si and so should be near zero. If they rise, the system is beginning to page.

Create a workload that thrashes. Write a program that allocates more memory than the system has, touches every page, and then repeatedly accesses the pages in a random order. This forces the kernel to evict pages that the process is about to touch again, producing a page-fault storm.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main(int argc, char **argv) {
    size_t n = atol(argv[1]);          /* bytes to allocate */
    char *buf = malloc(n);
    if (!buf) { perror("malloc"); return 1; }

    /* touch every page to make them resident (or to force them out) */
    for (size_t i = 0; i < n; i += 4096)
        buf[i] = 1;

    /* repeatedly access in a pseudo-random order */
    srand(42);
    struct timespec t0, t1;
    clock_gettime(CLOCK_MONOTONIC, &t0);
    volatile long sum = 0;
    for (long rep = 0; rep < 10000000; rep++) {
        size_t idx = ((size_t)rand() << 12) % n;
        sum += buf[idx];
    }
    clock_gettime(CLOCK_MONOTONIC, &t1);
    double elapsed = (t1.tv_sec - t0.tv_sec)
                   + (t1.tv_nsec - t0.tv_nsec) / 1e9;
    printf("elapsed: %.3f s, sum = %ld\n", elapsed, sum);
    free(buf);
    return 0;
}

Run it with an allocation that is comfortably less than physical memory (for example, 500 MB on a system with 4 GB) and then with an allocation that exceeds physical memory (for example, 6 GB on a 4 GB system, if swap is available). In the second case, the program should run dramatically slower, and vmstat should show high si/so.

Measure the thrashing signal. While the second version of the program runs, open a second terminal and monitor the system's memory state.
```
vmstat 1 20
# In another terminal:
watch -n 0.5 'cat /proc/meminfo | grep -E "MemFree|Cached|SwapFree|SwapCached"'
```
Note the following signals:
- si and so in vmstat should be high — the system is swapping pages in and out.
- The r column (runnable processes) should be low, and the b column (blocked processes) should be high — most processes are waiting for I/O.
- The wa column (I/O wait) in top should be high.
- MemFree should be low and SwapCached should be high — pages have been swapped out and some are being swapped back in.
Compare the throughput. Time both versions of the program (the one that fits in memory and the one that does not). Compute the ratio. On a typical system, the second version should be 10 to 100 times slower than the first, because every access misses in the TLB and requires a page fault.

Simulate the thrashing curve. Write a simulator that takes the number of processes and the total frames, computes each process's allocation, and uses a simple model of the fault rate to compute the total throughput.

# Python sketch
def throughput(n, total_frames, wss):
    """n: number of processes; total_frames: physical frames;
       wss: working-set size of each process."""
    frames_per = total_frames / n
    if frames_per >= wss:
        fault_rate = 0.0
    else:
        # rough model: fault rate proportional to shortfall
        fault_rate = 1.0 - frames_per / wss
    # each non-faulting access is 1 unit; each fault costs 200 units
    effective = 1.0 + fault_rate * 200.0
    # total useful throughput = number of processes / effective time
    return n / effective

# Run with 1000 frames, working set 80 pages
for n in range(1, 21):
    t = throughput(n, 1000, 80)
    print(f"n = {n:2d}  frames/process = {1000/n:6.1f}  throughput = {t:6.3f}")

The output should look like the table in the worked example: rising throughput up to about 12 processes, then a sharp collapse. Identify the peak and the point at which each additional process begins to reduce throughput.

Vary the working-set size. Run the simulator with different working-set sizes (40, 80, 160) and observe how the peak moves. What happens when the working set is very large? What happens when it is very small? What does this suggest about the relationship between the workload's locality and the system's capacity?
Observe the OOM killer (in a VM). In a virtual machine you can afford to lose, allocate memory faster than the kernel can reclaim it and observe the OOM killer. Do this only in a VM you can restart.
```
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(void) {
    for (long i = 0; ; i++) {
        size_t n = 500 * 1024 * 1024;   /* 500 MB */
        char *p = malloc(n);
        if (!p) { perror("malloc"); return 1; }
        memset(p, 0, n);
        printf("allocated %ld00 MB\n", i + 1);
    }
}
```
When the OOM killer fires, the kernel's log (dmesg) should show the message Out of memory: Killed process with details of the victim and its score. Read the log and identify which process was killed and why.
Read man 1 vmstat. Read the man page and identify every column related to memory and paging: swpd, free, buff, cache, si, so, bi, bo. For each, write a sentence describing what it measures and what values indicate memory pressure.
Read Denning's 1968 paper. Find a copy of Denning's paper Thrashing: Its Causes and Prevention (AFIPS Fall Joint Computer Conference, 1968). Read the sections that introduce the working-set model and the thrashing curve. How does Denning's original presentation compare to the modern textbook treatment? What aspects of the phenomenon does he emphasize that the textbooks omit?

Reflect: thrashing is a phenomenon in which the system as a whole performs worse than any of its individual components would suggest. The page-replacement policy is functioning correctly, the scheduler is functioning correctly, and the disk is functioning correctly — but the interaction between them produces a collapse. This is characteristic of complex systems, and it is one of the reasons operating systems are hard to design: the interactions between subsystems produce behaviours that none of them would produce in isolation. What other phenomena in computing have this character? What does the existence of such phenomena suggest about the difficulty of systems design?

07 Knowledge check

Check your understanding

Question 1

Define thrashing and describe the positive-feedback loop that produces it. Why does the loop spiral out of control?

Show answer

Thrashing is the state in which a system spends more time paging than executing. It is not a bug in any single component; it is a property of the interaction between the workload, the amount of memory available, and the page-replacement policy. The positive-feedback loop has three components. (1) Insufficient frames leads to a high fault rate. When a process has fewer frames than its working set requires, its page-replacement policy evicts pages that the process will need again soon, so the process faults on a substantial fraction of its accesses. (2) High fault rate leads to less useful work. Each fault blocks the process while the disk reads the page, so the process spends most of its time waiting, and its useful throughput drops. (3) Less useful work leads to lower CPU utilization. The process is idle waiting for I/O, so the CPU has nothing to do. A scheduler that uses CPU utilization as an admission signal — and most do, because keeping the CPU busy is the primary goal of multiprogramming — sees the idle CPU and admits more processes to fill it. Adding processes takes frames from the existing ones, reducing their allocations further, which increases their fault rates and drives CPU utilization even lower. The system converges to a state in which almost every process is blocked on I/O, the CPU is nearly idle, the disk is saturated with paging traffic, and the throughput is a small fraction of what a properly sized system would achieve. The loop spirals because each iteration of the cycle makes the next iteration worse: the additional processes do not help utilization (they are blocked on I/O too), and they make the existing processes' allocations smaller.

Question 2

Define the working set, the working-set window, and the working-set size. How do they relate to the concept of locality? Why does the working set change over time?

The working set of a process at a given moment is the set of pages it has accessed in the last Δ references, where Δ is the working-set window. The working-set size (WSS) is the number of distinct pages in the window. The working set is the process's current locality: the pages it is actively using, and therefore the pages it must keep in memory to run efficiently. The concept is the direct application of locality of reference (Lesson 8.1) to the memory-management problem: a program accesses a small subset of its address space in any given period, and the working set is that subset. The working set changes over time because a program's execution is not uniform. A program goes through phases: it executes a loop, moves to a new loop, returns from a function, processes the next item in a stream. Each phase accesses a different subset of the address space, and the working set is the current phase's subset. During a phase, the working set is small and stable; during a transition between phases, the working set temporarily grows, because it includes both the outgoing phase's pages (which may still be needed) and the incoming phase's pages (which have just been touched). The working-set size therefore varies over time, and the process's frame allocation must be at least the peak WSS to avoid excessive faulting. The working-set window Δ must be large enough to include a full phase — typically a complete pass through an inner loop — but small enough to exclude the previous phase's pages once they are no longer needed. The choice of Δ is a tuning problem, and the working-set policy's effectiveness depends on it.

Question 3

Describe the working-set policy and the page-fault-frequency (PFF) policy. What does each one do when the total demand for memory exceeds the available memory? What are the advantages and disadvantages of each?

The working-set policy tracks each process's working set (the pages it has accessed in the last Δ references) and allocates each process at least its WSS frames. The sum of all the working sets is the total demand on memory. If the sum fits in the physical memory, the system is in the safe region and runs efficiently. If the sum exceeds the memory, the policy takes corrective action: it suspends one or more processes (swapping them out in their entirety and freeing their frames for the survivors) and refuses to admit new processes until the sum of the remaining working sets fits. The PFF policy does not track the working set directly. Instead, it measures each process's fault rate and uses it as a proxy: if a process's fault rate is above an upper bound, it needs more frames; if it is below a lower bound, it has more frames than it needs. The policy transfers frames from processes below the lower bound to processes above the upper bound. If no frames can be freed — because every process is at or above its upper bound — the policy, like the working-set policy, suspends one or more processes to reduce the total demand. The working-set policy has the advantage of being predictive: it can detect that a process's working set is growing before the faults occur, and allocate frames proactively. Its disadvantage is that it requires the operating system to track the working set of every process — recording the time of every page access and maintaining the window — which is expensive on a modern system. The PFF policy has the advantage of being simple: it requires only the page-fault counter, which the kernel already maintains, and its parameters (the upper and lower bounds on the fault rate) are intuitive. Its disadvantage is that it is reactive: the process must fault before the policy responds, and by that point the system has already paid the cost of the fault. The two policies are complementary, and real systems use a combination.

Question 4

How does the choice between local and global replacement affect a system's susceptibility to thrashing? What is the trade-off between the two, and how does a modern system like Linux resolve it?

Show answer

With global replacement, a process that faults may evict a page belonging to another process. This is efficient when the aggregate working set fits in memory, because frames flow from processes that are idle to processes that are active. But it is unstable when the aggregate working set exceeds memory: a single heavily faulting process can steal frames from every other process, dragging them all into a high fault rate and precipitating a system-wide thrash. Global replacement amplifies thrashing, because one process's problem becomes everyone's problem. With local replacement, each process's frames are protected from the others: a fault in process A can only evict a page belonging to process A. This is stable — one process's behaviour cannot affect another's — but it is inefficient, because a process whose working set exceeds its allocation will thrash within its own frames, even though there may be free frames elsewhere. The frames cannot flow to where they are needed. The trade-off is between efficiency (global) and stability (local). Real systems use a hybrid. Linux uses global replacement within the page cache — all file pages and anonymous pages compete for the same pool of frames — but the OOM killer provides an emergency exit: when the system cannot reclaim enough memory through normal eviction, it terminates the process with the highest memory usage, freeing its frames for the survivors. The OOM killer is a form of local allocation made at the moment of crisis, when the global policy has failed. It resolves the tension by making a decisive choice — killing a process rather than allowing it to thrash indefinitely — so that the remaining processes can run normally. The alternative — suspending the process indefinitely — would be less decisive: the process might never resume, and its frames would remain committed. Termination is brutal but definite, and it returns the system to a usable state.

Question 5

A system with 1000 frames runs a workload of processes with a working set of 80 pages each. At what number of processes does the system reach the peak of the thrashing curve, and what happens as more processes are added? What would the working-set policy do at 20 processes, and what would the PFF policy do?

The peak of the thrashing curve occurs when the sum of the processes' working sets equals the physical memory. With a working set of 80 pages and 1000 frames, the sum fits when n × 80 ≤ 1000, which means n ≤ 12 (because 12 × 80 = 960 ≤ 1000 and 13 × 80 = 1040 > 1000). At 12 processes, each process has 1000 / 12 = 83.3 frames, which is more than its working set of 80, so the fault rate is negligible. At 13 processes, each has 1000 / 13 = 76.9 frames, which is less than 80, so the fault rate rises sharply: each process is now evicting pages it will need again, and the faults multiply. The system tips into thrashing. As more processes are added, the allocation per process falls further. At 20 processes, each has 50 frames — 62 percent of its working set — and each faults on a substantial fraction of its accesses. The effective time per access rises dramatically, and the total throughput collapses: at 20 processes, the system does roughly a tenth of the useful work it did at 12, even though it is running two-thirds more processes. At 20 processes, the working-set policy would compute the total working set as 20 × 80 = 1600 pages, which exceeds the 1000 frames available. It would suspend processes until the total fits: it can keep at most ⌊1000 / 80⌋ = 12 processes running, so it would suspend the other 8, swapping them out in their entirety. The 12 running processes would have about 83 frames each — enough for their working sets — and the system would be in the safe region, producing the maximum throughput the workload can support. The suspended processes would be resumed when memory becomes available (for example, when one of the 12 terminates). The PFF policy would observe each process's fault rate and take corrective action. At 20 processes, each process's fault rate is high — well above the upper bound of the acceptable range — so the policy would try to give each process more frames. But no frames are free, because every process is above the upper bound. The policy would therefore suspend one or more processes, freeing their frames for the survivors, until the survivors' fault rates fall below the upper bound. The PFF policy's response is reactive — the system spent some time in the thrashing region before the policy acted — but it detects the problem and corrects it, returning the system to an acceptable state. The end result is the same as the working-set policy's: the total number of running processes is reduced to what the memory can support, and the survivors run efficiently. The difference is that the PFF policy reaches this state after some thrashing has already occurred, while the working-set policy prevents the thrashing from occurring at all.

08 Unit discussion

Discussion prompt

This lesson closes Unit 9 and Module 3. The virtual-memory system we have studied is one of the great achievements of computer systems design: it gives every process the illusion of a large, private, uniform address space, regardless of how much physical memory the machine has or how many other processes are running. The illusion is built from a stack of mechanisms — paging, page tables, the TLB, demand paging, the page-fault handler, the page-replacement policy — each of which is simple in isolation, and whose combination produces a system far more capable than any of its parts.

But the same combination that produces the illusion also produces its failure mode. When the aggregate working set of the running processes exceeds the physical memory, the mechanisms interact in a positive-feedback loop that collapses throughput by orders of magnitude. The system does not fail gracefully: it does not slow down proportionally to the excess; it collapses suddenly, as if it had been switched off. The curve from the working-set model — a sharp peak followed by a precipice — is the signature of the collapse.

This pattern — a system whose components are individually simple and correct, but whose interaction produces emergent behaviour that no component would exhibit alone — is characteristic of complex systems in general. It appears in economics (market crashes), in ecology (population collapses), in biology (immune responses), and in computing (network congestion, distributed-system failures, cache-coherence pathologies). The lesson of thrashing is that the study of systems is the study of interactions, not of components, and that a system's behaviour is not predictable from its parts alone.

Consider the last complex system you worked with — a distributed application, a large codebase, a network of services. What interactions between its components produced behaviours that none of the components would produce alone? How were those behaviours discovered, and how were they addressed? What does this experience suggest about the way we should design and debug complex systems? Post your response to the Unit 9 discussion forum and reply to at least two classmates. This closes Unit 9 and Module 3. Supports CLO1, CLO4, and CLO6.

09 Practice exercise

This ungraded exercise consolidates the lesson and prepares you for Module 4. Aim to spend 60–90 minutes on it.

Model the thrashing curve. For a system with 512 frames and processes with a working set of 64 pages each, compute the number of processes at which the system reaches the peak of the thrashing curve. Then, using the model from the worked example (fault rate = 1 − frames/WSS, effective time = 1 + fault_rate × 200), compute the total throughput for n = 4, 8, 10, 12, 16, and 24 processes. Present the results in a table and identify the peak. What is the ratio of throughput at the peak to throughput at 24 processes?
Trace the working-set policy. A system has 800 frames and five processes with working sets of 120, 180, 90, 240, and 220 pages. Compute the total working set. Does it fit in the available memory? If not, which process or processes would the working-set policy suspend to bring the total into the available memory, and what would the resulting allocation be? Show your reasoning.
Trace the PFF policy. The same system has bounds of 5 percent (upper) and 1 percent (lower) on the fault rate. The current fault rates of the five processes are 0.5 percent, 3 percent, 8 percent, 0.3 percent, and 6 percent. Which processes need more frames, which have more than they need, and what does the policy do? What happens if no frames can be freed from the processes with low fault rates?
Analyse a real workload. Choose a workload you are familiar with — a web server, a database, a machine-learning training job, a JVM-based application, a browser with many tabs. Describe its memory access pattern. What is its working set? What is its locality like? How would it behave on a system with half the memory, a quarter, a tenth? At what point would it begin to thrash?
Design a memory-limit policy for containers. A container orchestrator is configuring memory limits for a service that handles web requests. The service has an average working set of 400 MB, with a peak of 800 MB under load. The host has 64 GB of memory and runs 30 containers. Write a short proposal: what memory limit would you set for the container, and why? What happens if the limit is too low, and what happens if it is too high? How would you monitor the container to detect when the limit is wrong?
Simulate the thrashing curve. Write a program that implements the model from the worked example and plots the total throughput as a function of the number of processes. Run it with different working-set sizes (40, 80, 160, 320) and different numbers of frames (500, 1000, 2000). How does the peak move? What does the position of the peak tell you about the workload's memory requirements?
Measure a real thrashing workload. On your VM, run the thrashing program from the interactive activity with an allocation that fits in physical memory, then with one that does not. Measure the time for each. Use vmstat and free to observe the system's state during the run. Correlate the slowdown with the observed page-fault rate, swap usage, and I/O wait.
Reflect. In your own words, explain why thrashing is a system-level phenomenon rather than a component-level one. Then describe one situation in your own experience — a program you have run, a system you have administered, a service you have used — where the system's performance was degraded by an interaction between components rather than by a failure of any single component. What was the interaction, and how was it resolved?

10 Summary

Thrashing is the state in which a system spends more time paging than executing. It is not a bug in any single component; it is an emergent property of the interaction between the workload, the amount of memory, and the page-replacement policy.
The mechanism of thrashing is a positive-feedback loop: insufficient frames lead to a high fault rate, which leads to less useful work, which leads to lower CPU utilization, which leads a scheduler to admit more processes, which takes frames from the existing processes, which increases their fault rate further. The loop spirals out of control.
The thrashing curve plots CPU utilization (or throughput) against the degree of multiprogramming. It rises to a peak and then collapses. The peak occurs at the point where the sum of all the processes' working sets equals the physical memory.
The working-set model, due to Peter Denning, defines the working set as the pages a process has accessed in the last Δ references, where Δ is the working-set window. The working-set size (WSS) is the number of distinct pages in the window: the number of frames the process needs to run efficiently.
Denning's result L = S describes the relationship between the fault rate and the frame allocation: when the allocation is at least the working-set size, the fault rate is bounded and low; when it falls below, the fault rate rises unboundedly.
The working-set policy tracks each process's working set and allocates at least its WSS frames. If the sum of all the working sets exceeds the memory, it suspends one or more processes and refuses to admit new ones until the sum fits. It is predictive: it prevents thrashing from occurring.
The page-fault-frequency (PFF) policy uses the fault rate as a proxy for the working set. It gives more frames to processes above an upper bound and takes frames from processes below a lower bound. If no frames can be freed, it suspends processes to reduce the degree of multiprogramming. It is reactive: the process must fault before the policy responds.
Global replacement is efficient but unstable under memory pressure: a single faulting process can drag all the others down with it. Local replacement is stable but inefficient: a process whose working set exceeds its allocation thrashes within its own frames even when other frames are free.
Modern Linux uses LRU lists (active and inactive) as an approximation of the working-set model, and responds to memory pressure through direct reclaim (synchronous, in the faulting process), kswapd (asynchronous, background), swapping anonymous pages, and, as a last resort, the OOM killer, which terminates a process to free its memory.
The OOM killer is a deliberate, controlled failure. It resolves the impossibility of running more work than memory can support by choosing a victim, freeing its memory, and returning the system to a usable state. It is preferable to indefinite thrashing, which serves no useful work at all.
In containers and virtual machines, thrashing is contained by resource limits but not prevented: a container whose working set exceeds its cgroup memory limit will thrash within its limit, and if the limit is exceeded by enough, the cgroup's OOM killer terminates one of its processes.
Preventing thrashing in practice is mostly a matter of system configuration and application design: size memory to the workload, control the degree of multiprogramming, improve the application's locality, use mlock and madvise, and monitor the system for the early signs of memory pressure.
Thrashing is a system-level phenomenon: a system whose components are individually simple and correct can still exhibit behaviours that none of its components would exhibit alone. The lesson of thrashing is that the study of complex systems is the study of interactions, not of components.

Unit 9 and Module 3 complete

This closes the virtual-memory unit and the memory module. You now have the full picture of modern memory management: the memory hierarchy and locality (Unit 8), address binding and the classical allocation schemes (Unit 8), and paging, page tables, the TLB, demand paging, page faults, page replacement, and thrashing (Unit 9). Module 4 turns to storage and I/O: file systems and their organization, the storage devices that back the virtual-memory system, and the I/O subsystem that connects them. The demand-paging mechanism you have just studied is built on top of the file system and the storage subsystem, so the next module will reveal the layers beneath the abstraction you have been studying.

11 References

Silberschatz, A., Galvin, P. B., & Gagne, G. Operating System Concepts, 10th ed., Chapter 10, Section 10.6.
Arpaci-Dusseau, R. H., & Arpaci-Dusseau, A. C. Operating Systems: Three Easy Pieces, Chapter 22. Available online at ostep.org.
Tanenbaum, A. S., & Bos, H. Modern Operating Systems, 4th ed., Chapter 3, Sections 3.5–3.6.
Denning, P. J. The Working Set Model for Program Behavior. Communications of the ACM, 1968. The paper that introduced the working-set model.
Denning, P. J. Thrashing: Its Causes and Prevention. AFIPS Fall Joint Computer Conference, 1968. The paper that characterizes thrashing directly.
Denning, P. J. Virtual Memory. ACM Computing Surveys, 1970. A synthesis of the working-set model and its application to operating-system design.
Courtois, P. J. Decomposability: Queueing and Computer System Applications. Academic Press, 1977. A formal treatment of the thrashing phenomenon as a queueing problem, including the instability analysis.
Love, R. Linux Kernel Development, 3rd ed., Chapter 12, Memory Management. The Linux implementation of memory pressure detection, page reclaim, and the OOM killer.
Gorman, M. Understanding the Linux Virtual Memory Manager. Prentice Hall, 2004. A detailed reference for the Linux memory-management subsystem, including the LRU lists and the reclaim logic.
Linux kernel documentation: Documentation/admin-guide/mm/ and Documentation/vm/.
Linux man-pages: man 1 vmstat, man 1 free, man 5 proc, man 7 cgroups, man 2 madvise, man 2 mlock.