Lesson 9.6: Page Replacement

01 Introduction

Lesson 9.4 introduced demand paging: the mechanism by which a page is loaded into memory only when it is accessed. Lesson 9.5 presented the page-fault handler that brings the page in, and it showed that the handler needs a free frame to hold the page. When the system has a free frame available — because physical memory is not yet full — the handler takes it, and the fault is serviced. But what happens when no free frame is available? The system must then evict a page: it must choose a page currently in memory, write it back to disk if it has been modified, and reuse its frame for the new page.

The choice of which page to evict is the page-replacement policy, and it is one of the most important design decisions in a virtual-memory system. A good policy keeps the process's working set in memory, minimising the fault rate and keeping performance high. A bad policy evicts pages that will be needed soon, increasing the fault rate and potentially triggering the catastrophic collapse of performance known as thrashing (Lesson 9.7). The policy must therefore predict the future — which pages will be used next — from the past, and it must do so with limited information and limited computational resources.

The classical replacement algorithms are studied through a simplified model called the reference string: a sequence of page numbers representing the memory accesses of a process. The model abstracts away the details of the hardware and the workload, and it allows the algorithms to be compared on the same input. The algorithms — FIFO, optimal replacement, LRU, and their approximations — are evaluated by counting the number of page faults they produce on the reference string. The algorithm with the fewest faults on the same string is the best, at least for that string.

This lesson presents the classical algorithms and their properties. It begins with the reference string model and the framework for comparing algorithms. It presents FIFO and Belady's anomaly — the counterintuitive result that a larger number of frames can sometimes produce more faults. It presents optimal replacement, the theoretical best algorithm, and LRU, its practical approximation. It presents the clock algorithm and the enhanced second-chance algorithm, which are the practical implementations of LRU in real systems. It presents the counting algorithms (LFU and MFU) that use access frequencies rather than recency, and it presents the working-set model and page-fault frequency, which are the frameworks for the frame-allocation problem. It closes with a discussion of the frame-allocation policies — equal versus proportional, global versus local — and with the policies used in modern kernels.

Prerequisites

This lesson builds directly on Lessons 9.4 and 9.5. The demand-paging mechanism, the page-fault handler, and the distinction between minor and major faults are all assumed. The role of the dirty bit and the accessed bit in the page-table entry (Lesson 9.1) is used throughout, because the replacement algorithms depend on this information. The memory hierarchy from Lesson 8.1 — in particular the huge latency gap between main memory and disk, and the concept of working set — is the foundation for the performance analysis. No prior knowledge of the replacement algorithms is assumed; all are introduced here. The material on reference strings is self-contained.

02 Learning objectives

By the end of this lesson you will be able to

Describe the reference string model and use it to evaluate a page-replacement algorithm.
Trace FIFO, optimal, and LRU replacement on a given reference string and count the faults each produces.
Explain Belady's anomaly and the stack property of algorithms that do not exhibit it.
Describe the clock and enhanced second-chance algorithms and explain why they approximate LRU.
Explain frame-allocation policies (equal versus proportional, global versus local) and the working-set model.

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

03 Required reading

Operating System Concepts — Chapter 10, Section 10.4, Page Replacement. The standard treatment of FIFO, optimal replacement, LRU, the clock algorithm, and Belady's anomaly, with the canonical reference string example.
OSTEP — Chapter 22, Swapping: Policies. The clearest available treatment of the page-replacement problem, with worked examples of FIFO, optimal, LRU, and the clock algorithm. OSTEP's treatment is the basis for the worked example in this lesson.
Tanenbaum & Bos — Modern Operating Systems, Chapter 3, Section 3.4, Page Replacement Algorithms. A complementary treatment that places the algorithms in the context of the working-set model and discusses the practical considerations.
Silberschatz et al. — Chapter 10, Sections 10.4–10.6. Read the discussion of the algorithms, the frame-allocation policies, and the global-versus-local replacement distinction.
Denning, P. J. — The Working Set Model for Program Behavior. Communications of the ACM, 1968. The paper that introduced the working-set model, which is the foundation for understanding page-replacement performance.
Belady, L. A. — A Study of Replacement Algorithms for Virtual-Storage Computer Systems. IBM Systems Journal, 1966. The paper that introduced the optimal replacement algorithm and analysed the behaviour of FIFO.
Belady, L. A., Nelson, R. A., & Shedler, G. S. — An Anomaly in Space-Time Characteristics of Certain Programs Running in a Paging Machine. Communications of the ACM, 1969. The paper that discovered Belady's anomaly.
Bryant, R. E., & O'Hallaron, D. R. — Computer Systems: A Programmer's Perspective, 3rd ed., Chapter 9, Virtual Memory, section 9.10. The programmer's view of the replacement policy, including the interaction with the page cache.
Love, R. — Linux Kernel Development, 3rd ed., Chapter 12, Memory Management. The Linux implementation of the page-replacement policy, including the active and inactive LRU lists and the kswapd daemon.
Linux man pages: man 2 madvise (the MADV_COLD and MADV_PAGEOUT flags), man 5 proc (the /proc/<pid>/stat and /proc/vmstat fields that report paging activity), man 1 perf-stat.

Reading strategy

Read the Silberschatz section first for the formal statement of the algorithms and the canonical reference string example. Then read the OSTEP chapter on swapping policies, which develops the same material from the perspective of the operating-system designer and adds the crucial discussion of the interaction between the replacement policy and the workload. Pay particular attention to Belady's anomaly: it is a small counterintuitive fact, but it shapes the design of the algorithms that followed. The Denning paper on the working-set model is the deeper theoretical treatment; read it if you want to understand why LRU-like policies work well on real workloads. The Linux kernel's memory management chapter is the practical view, showing how a modern kernel implements the ideas in the lesson.

04 Core content

4.1 The page-replacement problem

When a page fault occurs and no free frame is available, the operating system must choose a page to evict. The chosen page is called the victim. The eviction procedure is:

Choose a victim page. The page-replacement policy selects the victim. The choice is made from the set of pages currently in memory — typically, from the pages of the process that faulted, if the policy is local, or from all pages in the system, if the policy is global.
Check the dirty bit. If the victim page has been modified (its dirty bit is set), it must be written back to disk before its frame can be reused. If the page is clean (dirty bit clear), it can simply be discarded, because the disk already holds an up-to-date copy.
Write back if dirty. The operating system initiates a write-back operation for the victim. This is an expensive operation — the cost of a disk write — and it dominates the cost of the eviction.
Update the page tables. The victim's page-table entry is marked as not-present, and its frame-number field is cleared (or, for a swapped-out page, is replaced by the page's swap slot number).
Invalidate the TLB entry. Any stale TLB entry for the victim page is invalidated, both locally and on other cores (TLB shootdown, Lesson 9.3).
Use the frame. The newly-freed frame is given to the faulting page, and the page-fault handler proceeds as usual: read the page from disk, install it in the frame, update the page table, and resume.

The step that the policy controls is the first: which page to evict. The policy's goal is to choose the page whose eviction will cause the fewest future faults. If the policy chooses well, the evicted page is one the process will not need again for a long time, and the eviction has no immediate cost. If the policy chooses poorly, the evicted page is one the process will need again almost immediately, and the eviction causes a fault on the very next access to that page. The difference between a good and a bad policy is the difference between a system that runs at full speed and one that spends all its time on disk I/O.

The policy's problem is that it must predict the future from the past. At the moment of an eviction, the policy does not know which pages the process will access next. It must use the information it has — the recent history of accesses, the dirty and accessed bits in the page tables, and any hints the process has provided — to make a reasonable guess. The classical algorithms differ in how they use this information, and their behaviours differ accordingly.

4.2 The reference string model

The classical replacement algorithms are evaluated using a simplified model called the reference string. A reference string is a sequence of page numbers representing the memory accesses of a process: for example, 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1. Each number is a page number, and the sequence represents the pages the process accesses, in order.

The model is a simplification of reality. It assumes that all pages have the same size, that all accesses take the same time, that the sequence is the same on every run, and that the process has a fixed number of frames available to it. These assumptions are rarely true in practice, but they make the algorithms comparable: two algorithms evaluated on the same reference string with the same number of frames can be compared directly by counting the number of page faults each produces.

The model also makes the algorithms easy to evaluate by hand. The canonical example in the textbooks is the reference string 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1, with three frames available. The three classical algorithms — FIFO, optimal, and LRU — produce different numbers of faults on this string, and the comparison is the subject of the worked example in this lesson.

It is worth emphasising that the reference string model is a pedagogical tool, not a description of a real workload. Real reference strings are not available in advance, and even if they were, they would be too long to process. The model is valuable because it makes the algorithms' behaviours visible on a small example, and because it allows the theoretical properties of the algorithms (Belady's anomaly, the stack property) to be analysed. The algorithms that are used in practice are approximations of the classical ones, designed to work without the reference string model.

4.3 FIFO

The simplest replacement algorithm is FIFO: evict the page that has been in memory for the longest time. The algorithm maintains a queue of pages in the order they were loaded; when a frame is needed, the page at the head of the queue is evicted, and its frame is given to the new page; the new page is appended to the tail of the queue.

FIFO is easy to implement — a queue is a simple data structure — and it has a certain intuitive appeal: the page that has been in memory longest is the one that has survived the most evictions, so it might be the least useful. But FIFO has a serious flaw: it does not consider how often or how recently a page has been used. A page that has been in memory for a long time but is accessed frequently will still be evicted when its turn comes, even though it is clearly in active use. This is particularly bad for workloads with a large working set, where the frequently used pages are exactly the ones FIFO will eventually evict.

FIFO has a second, more surprising, flaw: it exhibits Belady's anomaly, the counterintuitive result that increasing the number of frames can sometimes increase the number of page faults. The anomaly is a genuine property of FIFO, not an artefact of the reference string model, and it was discovered by Belady, Nelson, and Shedler in 1969. It shows that FIFO is not simply "suboptimal" — it can be perversely suboptimal, in the sense that giving it more resources makes it worse.

4.4 Belady's anomaly

Belady's anomaly is illustrated by the reference string 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5. On this string, FIFO with three frames produces 9 faults, and FIFO with four frames produces 10 faults. Giving FIFO an extra frame makes it perform worse. The anomaly is a consequence of FIFO's lack of a stack property: the set of pages that FIFO keeps in memory with n frames is not necessarily a subset of the set it keeps with n+1 frames.

Figure 9.6 — Belady's anomaly. FIFO's behaviour on the reference string

1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4,
              5

. With three frames, FIFO produces 9 page faults; with four frames, it produces 10. The extra frame makes FIFO perform worse, which is the anomaly. The stack algorithms (optimal replacement and LRU) do not exhibit this behaviour: their fault counts are monotone non-increasing in the number of frames.

The anomaly is a consequence of FIFO's failure to satisfy the stack property. A replacement algorithm has the stack property if the set of pages it keeps in memory with n frames is always a subset of the set it keeps with n+1 frames, for all reference strings and all n. Algorithms with the stack property — LRU and optimal replacement are the classical examples — have monotonically non-increasing fault counts as the number of frames increases: adding a frame can only reduce the number of faults (or leave it unchanged), never increase it. Algorithms without the stack property — FIFO is the classical example — can exhibit the anomaly. The property is important because it is a guarantee: an administrator who adds memory to a system using a stack algorithm knows that the fault rate will not go up; an administrator using FIFO has no such guarantee.

4.5 Optimal replacement

The optimal replacement algorithm, often abbreviated OPT or MIN, is the theoretical best replacement policy. It evicts the page that will not be used for the longest time in the future. If a page will never be used again, it is evicted first; if several pages will never be used again, any of them can be evicted.

Optimal replacement has the lowest possible fault rate of any algorithm, on any reference string, with any number of frames. This is a theorem, and it is the standard by which every other algorithm is judged. The algorithm also has the stack property, so it does not exhibit Belady's anomaly. Its fault count is monotone non-increasing in the number of frames.

Optimal replacement is not implementable, because it requires knowledge of the future. At the moment of an eviction, the operating system does not know which pages the process will access next. Even if the reference string were known — as it is in the textbook model — the algorithm's comparison of "the page that will not be used for the longest time" requires a lookahead that is not available in real time. Optimal replacement is therefore a theoretical benchmark, useful for evaluating other algorithms but not usable in practice.

On the canonical reference string 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1 with three frames, optimal replacement produces 9 faults. On the same string, LRU produces 12 faults, and FIFO produces 15 faults. The numbers are illustrative but the ordering is not: optimal is best, LRU is next, and FIFO is worst, on a wide range of workloads. The gap between LRU and optimal is usually small (a few percent), which is why LRU-like policies are attractive; the gap between FIFO and optimal can be large, which is why FIFO is not used.

4.6 LRU

Least Recently Used (LRU) replacement evicts the page that has not been used for the longest time. The algorithm's intuition is that a page that has not been used recently is unlikely to be used soon, because programs have temporal locality: a page that is being used now is likely to be used again in the near future, and a page that was last used long ago is likely to be used again far in the future. This intuition is the reason LRU approximates optimal replacement well, and it is the reason LRU has the stack property.

LRU is a good algorithm — it is the best of the classical algorithms that are implementable in principle — but it is difficult to implement exactly. To evict the least-recently-used page, the operating system must track the access time of every page in memory, and it must find the minimum of those times on every eviction. Both of these operations are expensive: tracking the time requires updating a timestamp on every memory access, and finding the minimum requires a scan of the page table. On a system with millions of memory accesses per second and hundreds of thousands of resident pages, the overhead is prohibitive.

The theoretical implementation of LRU uses a doubly-linked list of pages, ordered by recency of use. Each memory access moves the accessed page to the head of the list; each eviction removes the page at the tail. The list operations are O(1) in principle, but the constant factor is large: each memory access requires a pointer update, and the page's location in the list must be found, which requires either a back-pointer from the page table entry to the list node (adding memory to the page table) or a search. On a system with billions of memory accesses per second, the overhead is too much.

For this reason, real systems do not implement LRU exactly. They implement approximations that use the accessed bit in the page-table entry — a single bit set by the MMU on every access — to estimate recency without the cost of a full LRU list. The most common approximations are the clock algorithm and the enhanced second-chance algorithm, described next.

4.7 The clock algorithm

The clock algorithm (also called the second-chance algorithm, or not-recently-used with a reference bit) is the standard approximation of LRU in real systems. It uses a single reference bit per page — the accessed bit in the page-table entry — and a circular list of pages.

The algorithm's data structures are simple. The resident pages are arranged in a circular list, with a hand that points to the current candidate for eviction. Each page has a reference bit, set by the MMU on every access and cleared by the algorithm.

When an eviction is needed, the algorithm proceeds as follows:

Examine the page at the hand. If its reference bit is 0, the page has not been used since the last time the hand passed it. Evict it.
If the reference bit is 1, the page has been used recently. Clear the bit (giving the page a "second chance"), advance the hand to the next page, and repeat.
Continue until a page with a clear reference bit is found. The hand sweeps around the circular list, giving second chances to the pages it passes, and evicts the first page whose reference bit is still clear after a full sweep.

Figure 9.6b — The clock algorithm. Resident pages are arranged in a circular list, with a hand pointing at the current candidate for eviction. Each page has a reference bit, set by the MMU on every access. When an eviction is needed, the hand examines the page it points at: if the reference bit is 0, the page is evicted; if it is 1, the bit is cleared and the hand advances. The hand sweeps around the circle, giving second chances to recently used pages, until it finds one whose reference bit is clear.

The clock algorithm is an approximation of LRU. It does not track the exact recency of every page, but the reference bit gives a reasonable estimate: a page whose bit is set has been used since the hand last passed it, and a page whose bit is clear has not. Because the hand sweeps the circular list regularly, the algorithm gradually demotes pages that have not been used: each sweep clears the reference bits, so a page that is not accessed during a full sweep will have its bit clear when the hand returns to it.

The clock algorithm's cost is small. Each page needs one bit (the reference bit, which the MMU already maintains for other purposes), and each eviction requires the hand to scan some number of pages. The scan is bounded in practice because most pages have their reference bits clear by the time the hand reaches them: the hand's sweeping clears the bits, and pages that are not accessed between sweeps accumulate as clear-bit pages.

The clock algorithm has one important property that makes it attractive in practice: it is easy to implement incrementally. The hand's position can be saved between evictions, and the algorithm's state is entirely in the page table's reference bits and in a single index. This is why most real operating systems use a clock-like algorithm rather than an exact LRU.

4.8 The enhanced second-chance algorithm

The enhanced second-chance algorithm is a refinement of the clock algorithm that considers two bits per page: the reference bit and the dirty bit. The two bits together give four classes of pages:

(0, 0): not recently used, not modified. The best candidate for eviction — the page can be discarded without any write-back.
(0, 1): not recently used, modified. A candidate for eviction, but the page must be written back to disk before its frame can be reused.
(1, 0): recently used, not modified. Not a good candidate — the page may be needed soon.
(1, 1): recently used, modified. The worst candidate — the page may be needed soon, and it will be expensive to evict.

The enhanced algorithm prefers to evict pages from class (0, 0), because those pages are both unused recently and clean (no write-back is needed). If no page in class (0, 0) is available, the algorithm sweeps the list again and looks for a page in class (0, 1). On the third sweep, it clears the reference bits and looks for a page in class (0, 0) again, and so on.

The advantage of the enhanced algorithm is that it avoids the write-back cost when possible. Evicting a clean page (dirty bit 0) costs only the page-table update and the TLB invalidation; evicting a dirty page (dirty bit 1) costs a disk write in addition. On a system with a spinning disk, the difference is a factor of a hundred in the cost of the eviction, and the enhanced algorithm can therefore improve the system's throughput significantly.

The enhanced algorithm is the standard replacement policy in many real systems. It is what the Linux kernel's kswapd daemon effectively implements, and it is the basis for the policies in several other operating systems. The combination of the reference bit and the dirty bit captures enough information to make reasonable decisions without the cost of a full LRU implementation.

4.9 Counting algorithms

A different family of algorithms uses the frequency of page references rather than the recency. These algorithms maintain a counter for each page, incremented on every reference, and evict based on the counter's value.

Least Frequently Used (LFU): Evict the page with the smallest reference count. The intuition is that a page that has been used rarely is less important than one that has been used often. LFU works well for workloads with a stable set of frequently used pages, but it has two problems. First, a page that was heavily used early in the process's life accumulates a large count and is never evicted, even if it has not been used recently. Second, a page that is used for the first time has a count of 1 and is an immediate candidate for eviction, even if it will be used heavily in the future.
Most Frequently Used (MFU): Evict the page with the largest reference count. The intuition is the opposite of LFU's: a page that has been used often is probably a page that has already served its purpose, and a page that has been used rarely is probably new and about to be used heavily. MFU works well for some workloads, but its intuition is less reliable than LFU's, and it is rarely used.
LFU with aging: A variant of LFU that periodically halves the reference counts of all pages. The aging reduces the weight of old references, so a page that was heavily used early but not recently has its count reduced and becomes a candidate for eviction. The aged LFU combines the frequency information of LFU with the recency information of LRU, and it performs better than either on realistic workloads.

The counting algorithms are less common than the clock-based algorithms in practice, because they require a counter per page (more memory than a single bit) and the counters must be updated on every access (more overhead). They are used in some systems — particularly those with a small number of resident pages, where the overhead is manageable — and they are a useful pedagogical contrast to the recency-based algorithms.

4.10 Frame allocation

The replacement policy decides which page to evict, but it does not decide how many pages each process may have in memory. That decision is the frame-allocation policy, and it is complementary to the replacement policy: the two together determine the system's behaviour.

The frame-allocation problem arises when multiple processes are running concurrently. Each process needs a certain number of frames — its working set — to run efficiently. If a process has too few frames, its pages will be evicted before they can be reused, and it will fault on nearly every access; if a process has too many, the other processes will have too few. The system must decide how to divide the available frames among the processes, and the decision affects the system's overall performance.

The classical allocation policies are:

Equal allocation: Divide the frames equally among the processes. If there are m frames and n processes, each process gets m/n frames. This is the simplest policy, and it is fair in the sense that every process gets the same number of frames. But it is inefficient, because processes have different working set sizes. A process with a small working set is given more frames than it needs (wasting them), and a process with a large working set is given fewer frames than it needs (causing it to thrash).
Proportional allocation: Divide the frames in proportion to the processes' sizes. If process i has virtual address space of size s_i, it receives m × s_i / Σ s_j frames. This is fairer than equal allocation, because a larger process receives more frames. But it is not perfect, because a process's working set is not proportional to its address space: a process with a large code base but a small working set would receive more frames than it needs, and a process with a small address space but a large working set would receive fewer.
Proportional to priority: Divide the frames in proportion to the processes' priorities, so that higher-priority processes receive more frames. This is used in systems with explicit priority classes.
Working-set based: Allocate each process enough frames to hold its working set — the set of pages it has used in the last w time units. The working set's size is measured dynamically, and the allocation is adjusted accordingly. If the total of all working sets exceeds the available frames, the system is overcommitted, and one or more processes must be suspended (swapped out) to reduce the load. The working set model is the subject of section 4.11.
Page-fault-frequency: Adjust the allocation based on each process's observed fault rate. If a process is faulting frequently, it needs more frames; if it is faulting rarely, it can afford to give up some. The page-fault-frequency policy is the subject of section 4.12.

The choice of policy depends on the system and on the workload. Systems with a homogeneous workload — all processes similar in size and behaviour — can use equal allocation. Systems with a heterogeneous workload need a more sophisticated policy, and the working-set or page-fault-frequency policies are common. In all cases, the policy must balance the goal of giving each process enough frames to run efficiently against the goal of using the system's memory as fully as possible.

4.11 Global versus local replacement

A related decision is whether the replacement policy considers all pages in the system or only the pages of the faulting process.

Local replacement: The victim is chosen from the pages of the faulting process. Each process's frame allocation is fixed (or adjusted by a separate policy), and the replacement policy operates within that allocation. The advantage is that a process's fault rate depends only on its own behaviour, not on the other processes': a process that is thrashing is doing so because it needs more frames, not because another process is stealing its pages. The disadvantage is that a process with a large working set cannot benefit from another process's unused frames, so the system's memory is not used as efficiently as it could be.
Global replacement: The victim is chosen from all pages in the system, regardless of which process owns them. A process that needs more frames can take them from other processes, if those processes' pages are less useful. The advantage is that the system's memory is allocated dynamically to where it is needed, which improves the overall utilization. The disadvantage is that a process's fault rate depends on the other processes' behaviour: a process can be starved of frames by another process that is aggressively claiming memory, and the system's behaviour is harder to predict and control.

In practice, most operating systems use a hybrid approach. Linux, for example, uses a global replacement policy for most pages, but with per-process controls (the oom_score_adj parameter and the cgroup memory limits) that constrain how much memory a process can claim. The result is a system where memory is allocated dynamically but the allocation can be controlled by the administrator.

4.12 The working-set model

The working-set model, introduced by Peter Denning in 1968, is the theoretical framework for understanding the frame-allocation problem. Its central concept is the working set: the set of pages a process has accessed in the last w time units. The parameter w is the working-set window, and its choice determines what "recently used" means.

The working set captures the process's current locality. At any moment, the process is actively using a small number of pages — its working set — and the pages outside the working set are not currently being used. The working set's size changes over time: it grows when the process moves to a new phase of its computation, and it shrinks when the process finishes with old pages.

The working-set model's insight is that a process needs exactly its working set in memory to run efficiently. If the process has at least its working set's worth of frames, it will experience very few faults, because the pages it uses are the pages it has, and the pages it doesn't use don't need to be in memory. If the process has fewer frames than its working set, it will fault frequently, because pages will be evicted before they can be reused.

The working-set model has several implications.

The sum of the working sets must fit in memory. If the processes' working sets together exceed the physical memory, the system is overcommitted, and one or more processes must be suspended. The working-set model gives a precise criterion for overcommitment: the system is overcommitted when Σ W(t, w) > M, where W(t, w) is the working set of process i at time t with window w, and M is the number of frames.
The working set's size determines the frame allocation. Each process should be given enough frames to hold its working set. If this is impossible for all processes at once, the system must choose which processes to run and which to suspend.
Thrashing is the state in which the system cannot satisfy all working sets. When the sum of the working sets exceeds the memory, pages are evicted before they can be reused, and the fault rate increases without bound. The system spends all its time doing I/O, and none of its processes make progress. This is the subject of Lesson 9.7.

The working-set model is not directly implemented in practice, because measuring the exact working set requires tracking every page reference over a time window, which is expensive. It is implemented in approximation, using the reference bits and a periodic scan of the page tables, or using a sample of the process's references. The working-set clock and the working-set pages algorithms are two such approximations. The model remains valuable as a conceptual framework for reasoning about the frame allocation problem, even when it is not implemented exactly.

4.13 Page-fault frequency

A simpler and more practical approach to frame allocation is page-fault frequency (PFF). The operating system measures each process's fault rate, and adjusts its frame allocation to keep the rate within an acceptable band.

The policy is:

If a process's fault rate is above an upper threshold — say, one fault per thousand accesses — the process needs more frames. Give it additional frames (taken from processes whose fault rates are low, or from the free list).
If a process's fault rate is below a lower threshold — say, one fault per million accesses — the process has more frames than it needs. Take some away.
If the total memory is insufficient to keep all processes' fault rates below the threshold, suspend one or more processes (swap them out) to reduce the load.

The page-fault-frequency policy is easy to implement: the operating system already tracks the fault counts for each process (they are reported in /proc/<pid>/stat on Linux), and the policy's decisions are simple. It adapts dynamically to changes in the workload, and it does not require the theoretical machinery of the working-set model. Its main disadvantage is that it is reactive: it adjusts to observed behaviour, so it lags behind sudden changes in the workload. In practice, the lag is acceptable for most workloads.

On Linux, the page-fault-frequency policy is implemented in a modified form. The kernel's kswapd daemon periodically scans the page tables, identifies pages that have not been used recently, and moves them to a list of candidates for eviction. When memory is needed, the pages at the head of the candidate list are evicted, and the process whose pages are being evicted receives an increasing share of the kernel's attention if its fault rate is high. The details are complex, but the structure is the same: measure the fault rate, adjust the allocation, and suspend processes if necessary.

4.14 Common misconceptions

"FIFO is a reasonable replacement policy."

FIFO is not reasonable for most workloads. It ignores recency and frequency, and it exhibits Belady's anomaly. Real systems use LRU approximations, not FIFO.

"A larger number of frames always reduces faults."

Only for algorithms with the stack property. FIFO does not have the property, and it can exhibit Belady's anomaly: an extra frame can increase the fault count.

"Optimal replacement is used in practice."

Optimal replacement requires knowledge of the future and cannot be implemented. It is a theoretical benchmark, not an algorithm.

"LRU is easy to implement."

LRU is conceptually simple but expensive to implement exactly: it requires a timestamp or a linked-list position for every page, updated on every access. Real systems use approximations (clock, enhanced second chance) instead.

"The clock algorithm is LRU."

The clock algorithm is an approximation of LRU. It uses a single reference bit per page, and its decisions are less precise than LRU's. But it is much cheaper to implement and its performance is close to LRU's on real workloads.

"The dirty bit has no role in replacement."

The dirty bit is central. Evicting a clean page is cheap; evicting a dirty page requires a disk write. The enhanced second-chance algorithm uses the dirty bit explicitly to prefer clean pages for eviction.

"Global replacement is always better than local."

Global replacement uses memory more efficiently but makes individual processes' fault rates depend on other processes' behaviour. Local replacement is more predictable. The right choice depends on the system.

"The working set is the same as the address space."

The working set is the set of pages a process has accessed in the last w time units. The address space is the set of all pages the process can access. The working set is typically much smaller than the address space.

05 Worked example

The following example traces FIFO, optimal replacement, and LRU on the canonical reference string, comparing their fault counts and analysing their behaviours. It then demonstrates the working-set model on a small trace.

FIFO, optimal, and LRU on the canonical reference string

The reference string is 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1, and the number of frames is 3.

Optimal replacement

At each fault, optimal replacement evicts the page whose next use is farthest in the future. If a page will never be used again, it is evicted first. The trace is:

Access	Page	Frame 0	Frame 1	Frame 2	Result
1	7	7	—	—	fault (fill)
2	0	7	0	—	fault (fill)
3	1	7	0	1	fault (fill)
4	2	2	0	1	fault (evict 7, next use never)
5	0	2	0	1	hit
6	3	2	0	3	fault (evict 1, next use pos 14)
7	0	2	0	3	hit
8	4	2	4	3	fault (evict 0, next use pos 16)
9	2	2	4	3	hit
10	3	2	4	3	hit
11	0	2	0	3	fault (evict 4, next use never)
12	3	2	0	3	hit
13	2	2	0	3	hit
14	1	2	0	1	fault (evict 3, next use never)
15	2	2	0	1	hit
16	0	2	0	1	hit
17	1	2	0	1	hit
18	7	7	0	1	fault (evict 2, next use never)
19	0	7	0	1	hit
20	1	7	0	1	hit

Optimal faults: 9

LRU

LRU evicts the page that has not been used for the longest time. The trace is:

Access	Page	Frame 0	Frame 1	Frame 2	Result
1	7	7	—	—	fault (fill)
2	0	7	0	—	fault (fill)
3	1	7	0	1	fault (fill)
4	2	2	0	1	fault (evict 7)
5	0	2	0	1	hit
6	3	2	0	3	fault (evict 1)
7	0	2	0	3	hit
8	4	4	0	3	fault (evict 2)
9	2	4	0	2	fault (evict 3)
10	3	4	3	2	fault (evict 0)
11	0	0	3	2	fault (evict 4)
12	3	0	3	2	hit
13	2	0	3	2	hit
14	1	1	3	2	fault (evict 0)
15	2	1	3	2	hit
16	0	1	0	2	fault (evict 3)
17	1	1	0	2	hit
18	7	1	0	7	fault (evict 2)
19	0	1	0	7	hit
20	1	1	0	7	hit

LRU faults: 12

FIFO

FIFO evicts the page that has been in memory the longest, using a queue. The trace is:

Access	Page	Frame 0	Frame 1	Frame 2	Result
1	7	7	—	—	fault (fill)
2	0	7	0	—	fault (fill)
3	1	7	0	1	fault (fill)
4	2	2	0	1	fault (evict 7, oldest)
5	0	2	0	1	hit
6	3	2	3	1	fault (evict 0, oldest)
7	0	2	3	0	fault (evict 1, oldest)
8	4	4	3	0	fault (evict 2, oldest)
9	2	4	2	0	fault (evict 3, oldest)
10	3	4	2	3	fault (evict 0, oldest)
11	0	0	2	3	fault (evict 4, oldest)
12	3	0	2	3	hit
13	2	0	2	3	hit
14	1	1	2	3	fault (evict 0, oldest)
15	2	1	2	3	hit
16	0	1	0	3	fault (evict 2, oldest)
17	1	1	0	3	hit
18	7	7	0	3	fault (evict 1, oldest)
19	0	7	0	3	hit
20	1	7	0	1	fault (evict 3, oldest)

FIFO faults: 15

Comparison

Algorithm	Faults	Relative to optimal	Notes
Optimal	9	1.00×	Theoretical best; not implementable.
LRU	12	1.33×	Best implementable in principle; approximates optimal well.
FIFO	15	1.67×	Worst of the three; exhibits Belady's anomaly.

The comparison shows the ordering that holds on a wide range of workloads: optimal is best, LRU is next, and FIFO is worst. The gap between LRU and optimal is 33 percent on this string, which is larger than on typical real workloads (where the gap is usually a few percent). The gap between FIFO and optimal is 67 percent, which is typical for workloads with a moderate working set.

The important observation is that LRU is much closer to optimal than FIFO is. This is why real systems use LRU-like policies (or approximations) rather than FIFO. The clock algorithm and the enhanced second-chance algorithm, described earlier, approximate LRU with a single reference bit per page, and their performance is close to LRU's on typical workloads.

The working-set model on a small trace

Consider a process whose references over a window of 10 time units are:

t:    1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
page: 1  2  3  4  1  2  5  1  2  3  4  5  1  2  3

The working set at each time t with window w = 4 is the set of distinct pages referenced in the previous 4 units:

t	References in window	Working set	Size
4	1, 2, 3, 4	{1, 2, 3, 4}	4
5	2, 3, 4, 1	{1, 2, 3, 4}	4
6	3, 4, 1, 2	{1, 2, 3, 4}	4
7	4, 1, 2, 5	{1, 2, 4, 5}	4
8	1, 2, 5, 1	{1, 2, 5}	3
9	2, 5, 1, 2	{1, 2, 5}	3
10	5, 1, 2, 3	{1, 2, 3, 5}	4
11	1, 2, 3, 4	{1, 2, 3, 4}	4
12	2, 3, 4, 5	{2, 3, 4, 5}	4
13	3, 4, 5, 1	{1, 3, 4, 5}	4
14	4, 5, 1, 2	{1, 2, 4, 5}	4
15	5, 1, 2, 3	{1, 2, 3, 5}	4

The working set's size fluctuates between 3 and 4 over the trace, showing that the process's locality is modest and stable. The maximum working-set size is 4, which means the process needs at least 4 frames to run efficiently. If it has fewer — say, 3 — it will fault on nearly every access to a new page, because pages are evicted before they can be reused.

The working-set model's value is that it gives a criterion for how many frames the process needs. A system that allocates each process at least its working set's worth of frames will run efficiently; a system that does not will thrash. The choice of the window size w is a policy decision: a smaller window captures only the most recent references, and a larger one captures more of the process's history. The optimal value depends on the workload, and it is often tuned empirically.

06 Interactive activity

Activity · implement and compare page-replacement algorithms

The goal of this activity is to implement the classical replacement algorithms, evaluate them on a reference string, and observe their behaviour on a real system. Work through the steps in your course VM.

Implement FIFO. Write a program that reads a reference string and a frame count from standard input and simulates FIFO replacement, printing the number of faults and the state of the frames after each access.

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

int main(int argc, char **argv) {
    int nframes = atoi(argv[1]);
    int *frames = malloc(nframes * sizeof(int));
    for (int i = 0; i < nframes; i++) frames[i] = -1;

    int hand = 0;       /* FIFO: the queue's head */
    int faults = 0;
    int page;

    while (scanf("%d", &page) == 1) {
        /* check if page is in a frame */
        int hit = 0;
        for (int i = 0; i < nframes; i++)
            if (frames[i] == page) { hit = 1; break; }

        if (!hit) {
            faults++;
            frames[hand] = page;
            hand = (hand + 1) % nframes;
        }
        /* print the state */
        printf("page %d:", page);
        for (int i = 0; i < nframes; i++)
            printf(" %2d", frames[i]);
        printf("  %s\n", hit ? "hit" : "FAULT");
    }
    printf("total faults: %d\n", faults);
    free(frames);
    return 0;
}

Test it with the canonical reference string 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 and 3 frames. Confirm that the fault count is 15.

Implement optimal replacement. Modify the program to simulate optimal replacement. At each fault, the algorithm scans the future references and evicts the page whose next use is farthest away (or never).
```
/* Build an array of the reference string first.
   At each fault, for each resident page, scan forward
   from the current position to find its next use.
   Evict the page with the largest next-use distance. */
```
Test it on the same reference string and confirm that the fault count is 9.
Implement LRU. Modify the program to simulate LRU. Maintain a "last used" timestamp for each resident page, and evict the page with the oldest timestamp.
```
/* Maintain an array of timestamps, one per frame.
   On each access, update the timestamp of the accessed
   page's frame. On a fault, evict the frame with the
   oldest timestamp. */
```
Test it on the same reference string and confirm that the fault count is 12.
Implement the clock algorithm. Modify the program to simulate the clock algorithm. Add a reference bit to each frame; set it to 1 on each access. On a fault, sweep the circular list from the hand: if the current frame's reference bit is 0, evict it; otherwise, clear the bit and advance.
```
/* The hand is an index into the frames array.
   On a fault:
     while (1) {
         if (frames[hand].ref == 0) break;
         frames[hand].ref = 0;
         hand = (hand + 1) % nframes;
     }
     evict frames[hand];
     frames[hand].page = new_page;
     frames[hand].ref = 1;
     hand = (hand + 1) % nframes;
*/
```
Compare the clock algorithm's fault count to LRU's on the same reference string. How close is the approximation?
Demonstrate Belady's anomaly. Run FIFO on the reference string 1 2 3 4 1 2 5 1 2 3 4 5 with 3 frames and with 4 frames. Confirm that the 3-frame run produces 9 faults and the 4-frame run produces 10. Then run LRU on the same string with 3 and 4 frames, and confirm that the fault count is monotone non-increasing (the stack property).
Measure the working set on a real program. Write a program that walks a large array in a pattern with a controllable working set: for example, a loop that touches every element of an array of size N, repeated for several iterations. Run the program under perf stat with the page-fault events, and observe how the fault count changes as N increases.
```
for n in 100 1000 10000 100000; do
    echo "N = $n"
    perf stat -e minor-faults,major-faults ./workload $n
done
```
As N grows beyond the number of available frames, the fault count should grow sharply, because the working set no longer fits in memory. This is the onset of thrashing (Lesson 9.7).
Observe the kernel's paging activity. Run a memory-intensive workload and observe the kernel's paging counters in /proc/vmstat.
```
grep -E 'pgpgin|pgpgout|pswpin|pswpout|pgfault|pgmajfault' /proc/vmstat
```
The pgpgin and pgpgout counters report the total pages read and written; pswpin and pswpout report the swap-in and swap-out activity. Run a workload with a small memory limit (using a cgroup or a container) and observe how the counters change as the kernel evicts pages.
Read the OSTEP chapter. Read OSTEP Chapter 22, Swapping: Policies. Compare its presentation of the replacement algorithms to this lesson. What additional considerations does OSTEP raise — for example, the workload model, the historical context of the algorithms, and the interaction between the replacement policy and the page cache? Write a short paragraph summarising the differences.

Reflect: the page-replacement policy is one of the most important design decisions in a virtual-memory system, and yet it is also one of the least visible to the programmer. A program that has good locality runs efficiently under any reasonable policy; a program that has poor locality runs poorly under any policy. What does this suggest about the balance between the operating system's responsibility and the programmer's? Should the operating system try to compensate for bad programs, or should it optimise for good ones? And how does this balance change as the size of memory and the number of cores increase?

07 Knowledge check

Check your understanding

Question 1

Define the page-replacement problem and describe the reference string model. What are the model's assumptions, and why is it useful despite them?

Show answer

The page-replacement problem is the problem of choosing which page to evict when a page fault occurs and no free frame is available. The operating system must select a victim page, write it back to disk if it is dirty, and reuse its frame for the new page. The choice determines the fault rate, the amount of I/O, and the overall performance of the system. A good policy keeps the process's working set in memory and minimises the fault rate; a bad policy evicts pages that will be needed soon and can trigger thrashing. The reference string model is a simplified representation of a process's memory accesses: a sequence of page numbers, where each number represents an access to that page. For example, the string

7, 0, 1, 2, 0, 3, 0, 4,
                  2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1

represents twenty accesses to a small set of pages. The model's assumptions are: all pages have the same size; all accesses take the same time; the reference sequence is fixed and known in advance; and the process has a fixed number of frames available. These assumptions are rarely true in practice, but they make the algorithms comparable: two algorithms evaluated on the same reference string with the same number of frames can be compared directly by counting the page faults each produces. The model is valuable as a pedagogical tool, because it makes the algorithms' behaviours visible on a small example, and because it allows theoretical properties (Belady's anomaly, the stack property) to be analysed precisely. The algorithms used in practice are approximations designed to work without the reference string model, but the classical algorithms that the model analyses are the basis for the approximations.

Question 2

Trace FIFO, optimal, and LRU on the reference string 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 with three frames. Count the faults for each algorithm, and identify the anomaly.

Show answer

FIFO (three frames):

1 → fault, frames {1}
2 → fault, frames {1, 2}
3 → fault, frames {1, 2, 3}
4 → fault, evict 1, frames {4, 2, 3}
1 → fault, evict 2, frames {4, 1, 3}
2 → fault, evict 3, frames {4, 1, 2}
5 → fault, evict 4, frames {5, 1, 2}
1 → hit
2 → hit
3 → fault, evict 5, frames {3, 1, 2}
4 → fault, evict 1, frames {3, 4, 2}
5 → fault, evict 2, frames {3, 4, 5}

FIFO faults: 9

Optimal (three frames):

1 → fault, frames {1}
2 → fault, frames {1, 2}
3 → fault, frames {1, 2, 3}
4 → fault, evict 3 (next use pos 10; 1 at pos 5, 2 at pos 6), frames {1, 2, 4}
1 → hit
2 → hit
5 → fault, evict 1 (next use pos 8; 2 at pos 9, 4 at pos 11), frames {5, 2, 4}
1 → fault, evict 2 (next use pos 9; 4 at pos 11, 5 never), frames {5, 1, 4}
2 → fault, evict 4 (next use pos 11; 5 never, 1 never), frames {5, 1, 2}
3 → fault, evict 5 (never), frames {3, 1, 2}
4 → fault, evict 1 (never), frames {3, 4, 2}
5 → fault, evict 3 (never), frames {5, 4, 2}

Optimal faults: 7

LRU (three frames):

1 → fault, frames {1}
2 → fault, frames {1, 2}
3 → fault, frames {1, 2, 3}
4 → fault, evict 1 (least recent), frames {4, 2, 3}
1 → fault, evict 2, frames {4, 1, 3}
2 → fault, evict 3, frames {4, 1, 2}
5 → fault, evict 4, frames {5, 1, 2}
1 → hit
2 → hit
3 → fault, evict 5, frames {3, 1, 2}
4 → fault, evict 1, frames {3, 4, 2}
5 → fault, evict 2, frames {3, 4, 5}

LRU faults: 10

The anomaly: FIFO with three frames produces 9 faults. If we run FIFO with four frames on the same string, we get 10 faults — more than with three. This is Belady's anomaly: increasing the number of frames can increase the fault count for FIFO, because FIFO does not have the stack property. Optimal and LRU do have the stack property, so their fault counts are monotone non-increasing in the number of frames.

Question 3

Explain Belady's anomaly and the stack property. Why is the stack property important for a replacement algorithm, and which of the classical algorithms have it?

Show answer

Belady's anomaly is the counterintuitive result that, for some replacement algorithms, increasing the number of available frames can increase the number of page faults. The anomaly is a genuine property of FIFO: on the reference string

1, 2, 3, 4, 1, 2, 5, 1, 2,
                  3, 4, 5

, FIFO with three frames produces 9 faults, and with four frames it produces 10. The anomaly was discovered by Belady, Nelson, and Shedler in 1969 and is named after them. The stack property is the property of a replacement algorithm that the set of pages it keeps in memory with n frames is always a subset of the set it keeps with n+1 frames, for all reference strings and all n. An algorithm with the stack property never exhibits Belady's anomaly: its fault count is monotone non-increasing in the number of frames, because adding a frame can only increase the set of resident pages, never change it in a way that evicts a page that would have been kept with fewer frames. The stack property is important for two reasons. First, it provides a guarantee to the system administrator: an administrator who adds memory to a system using a stack algorithm knows that the fault rate will not increase. Second, it allows the algorithm's fault rate to be analysed as a function of the number of frames, because the resident set at any time is determined by the number of frames in a monotone way. The classical algorithms that have the stack property are optimal replacement and LRU. The algorithms that do not have the property include FIFO and, for some reference strings, LFU. The reason optimal and LRU have the property is that their decisions are based on a total order of the pages: optimal orders pages by their next use, and LRU orders pages by their last use. The resident set with n frames is the n pages that come first in that order, and adding a frame adds the next page in the order without removing any of the existing pages. FIFO's order, by contrast, is by load time, and this order can change when the number of frames changes, breaking the subset relation.

Question 4

Describe the clock algorithm and the enhanced second-chance algorithm. How do they approximate LRU, and what are their advantages over an exact LRU implementation?

Show answer

The clock algorithm (also called the second-chance algorithm) approximates LRU using a single reference bit per page and a circular list of resident pages. A hand points at the current candidate for eviction. When an eviction is needed, the hand examines the page it points at: if the page's reference bit is 0, the page has not been used since the hand last passed it, so it is evicted; if the reference bit is 1, the page has been used recently, so the algorithm clears the bit and advances the hand to the next page. The hand sweeps the circular list, giving second chances to pages with set reference bits, until it finds a page whose bit is clear. The algorithm's approximation of LRU comes from the fact that the reference bit records whether the page has been used since the last sweep: a page with a clear bit has not been used in a full sweep's worth of time, while a page with a set bit has been used more recently. The hand's sweep gradually demotes pages, so a page that is not accessed is eventually evicted. The enhanced second-chance algorithm adds the dirty bit to the reference bit, giving four classes of pages: (0, 0) not recently used and not modified; (0, 1) not recently used but modified; (1, 0) recently used and not modified; (1, 1) recently used and modified. The algorithm prefers to evict pages in class (0, 0), because those pages are both unused recently and clean (no write-back is needed). If no such page is available, it sweeps the list again looking for a page in class (0, 1). The advantages of the clock algorithms over exact LRU are the implementation cost and the memory overhead. Exact LRU requires a timestamp or a linked-list position for every page, updated on every access, and the timestamp or position must be maintained in addition to the page-table entry. The clock algorithms need only a single bit per page (the reference bit, which the MMU already maintains), and the hand's position is a single index. The clock algorithms therefore use less memory and have lower per-access overhead, while their fault rates are close to LRU's on real workloads. This is why real systems use the clock algorithms rather than exact LRU.

Question 5

What is the working set? How does the working-set model inform the frame-allocation policy, and how does the page-fault-frequency policy relate to it?

Show answer

The working set of a process at time t with window w is the set of distinct pages the process has accessed in the last w time units. The working set captures the process's current locality: the pages it is actively using, as opposed to the pages it could access but is not currently using. The size of the working set changes over time — it grows when the process moves to a new phase of its computation and shrinks when it finishes with old pages — and its maximum value over the process's lifetime is a measure of the process's peak memory demand. The working-set model, introduced by Peter Denning in 1968, uses the working set to inform the frame-allocation policy. Its central observation is that a process needs exactly its working set in memory to run efficiently: if the process has at least its working set's worth of frames, it will experience very few faults, because the pages it uses are the pages it has; if it has fewer, it will fault frequently, because pages will be evicted before they can be reused. The model therefore provides a criterion for frame allocation: give each process at least as many frames as its working set's size, and if the sum of all working sets exceeds the available frames, the system is overcommitted and one or more processes must be suspended. The page-fault-frequency policy is a practical alternative to the working-set model. It measures each process's fault rate and adjusts its frame allocation to keep the rate within an acceptable band: a process with a high fault rate needs more frames, and a process with a low fault rate has more than it needs. The relationship between the two policies is that they address the same problem — how many frames each process should have — from different angles. The working-set model is a predictive criterion based on the process's observed locality; the page-fault-frequency policy is a reactive criterion based on the process's observed fault rate. Both aim to give each process enough frames to run efficiently without wasting frames on processes that do not need them. In practice, the page-fault-frequency policy is easier to implement, because the operating system already tracks the fault counts, while the working-set model requires tracking every page reference over a time window. Real systems therefore use the page-fault-frequency approach (or a variant of it) rather than measuring the working set exactly.

08 Unit discussion

Discussion prompt

The page-replacement policy is one of the most theoretically studied problems in operating-system design, and one of the least directly visible to the programmer. A program with good locality — a compiler, a media player, a web server serving small requests — runs efficiently under any reasonable policy, because its working set fits in memory and few evictions are necessary. A program with poor locality — a random-access database, a graph traversal, a machine-learning training loop with a working set larger than memory — runs poorly under any policy, because the working set does not fit and every eviction is a mistake.

This suggests that the replacement policy's role is not to make bad programs good, but to allocate memory as well as possible among programs that are competing for it. The policy's value is highest when several programs are running concurrently and the system is overcommitted, because that is when the allocation decisions have the greatest effect. When only one program is running and its working set fits in memory, the replacement policy is almost never invoked, and its details do not matter.

This has implications for the way we think about operating-system design. The theory of replacement algorithms — Belady's anomaly, the stack property, the working-set model — is elegant and complete, but its direct application is limited to systems where overcommitment is a real problem: databases, virtual machine hosts, containers running many small services, and scientific computations with large working sets. For a desktop or a mobile device running a handful of applications with modest working sets, the replacement policy is nearly irrelevant.

Consider the systems you use. Which ones are overcommitted? Which ones have a comfortable margin of memory? How would your choice of replacement policy differ for the two cases? Should the operating system detect which case it is in and adjust its policy accordingly — using a simple policy when memory is abundant and a sophisticated one when it is scarce — or should it always use the same policy for predictability? Post your response to the Unit 9 discussion forum and reply to at least two classmates. Supports CLO1, CLO4, and CLO6.

09 Practice exercise

This ungraded exercise consolidates the lesson and prepares you for Lesson 9.7. Aim to spend 90–120 minutes on it.

Trace the three algorithms by hand. For the reference string 1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6 with four frames, trace FIFO, optimal, and LRU. Count the faults for each. Present the traces in a table and identify the access at which each algorithm's behaviour diverges from the others.
Demonstrate Belady's anomaly. Construct a reference string on which FIFO exhibits Belady's anomaly, and verify by hand that the anomaly occurs. Then run the same string under LRU with the same frame counts and confirm that LRU does not exhibit the anomaly (its fault count is monotone non-increasing).
Simulate the clock algorithm. Write a program that simulates the clock algorithm on a given reference string. Compare its fault count to LRU's on the same string. Then modify the program to implement the enhanced second-chance algorithm, distinguishing clean and dirty pages. How much better is the enhanced version on a workload where many pages are dirty?

Measure the working set of a real program. Write a program that touches a region of memory with a configurable working set size. Use perf stat or /usr/bin/time -v to measure the fault count as the working set grows. Plot the fault count versus the working set size, and identify the point at which the working set exceeds the available frames (the onset of thrashing). Compare this to the size of physical memory reported by free -h or /proc/meminfo.

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

int main(int argc, char **argv) {
    size_t n = atol(argv[1]);       /* working set size */
    char *buf = malloc(n);
    memset(buf, 0, n);

    struct timespec t0, t1;
    clock_gettime(CLOCK_MONOTONIC, &t0);
    for (int rep = 0; rep < 100; rep++)
        for (size_t i = 0; i < n; i += 64)
            buf[i]++;
    clock_gettime(CLOCK_MONOTONIC, &t1);

    double elapsed = (t1.tv_sec - t0.tv_sec)
                   + (t1.tv_nsec - t0.tv_nsec) / 1e9;
    printf("n = %zu: %.3f s\n", n, elapsed);
    free(buf);
    return 0;
}

Analyse the frame-allocation policies. Three processes with working sets of 10, 30, and 60 pages share a system with 100 frames. Compute each process's allocation under equal allocation, proportional allocation (proportional to working set size), and working-set-based allocation. Which policy gives each process enough frames to hold its working set? If the total working set (100 pages) exactly equals the number of frames, what is the system's margin for error?
Compare global and local replacement. Write a short paragraph (200–250 words) comparing global and local replacement. Your paragraph should address: (a) how the victim is chosen in each case; (b) how each affects the system's memory utilization; (c) how each affects the predictability of individual processes' performance; (d) a workload in which each is preferable. Then state which you would choose for a general-purpose operating system, and why.
Investigate Linux's page-replacement policy. The Linux kernel maintains two lists of pages — active and inactive — and moves pages between them based on whether they have been accessed recently. Read the kernel's documentation or source code for the details, and write a short summary of the policy. How does it relate to the clock algorithm? How does it handle the dirty bit? What is the role of the kswapd daemon?
```
grep -i -E 'pgactivate|pgdeactivate|pgrefill|pgscan|pgsteal' /proc/vmstat
```
The pgactivate and pgdeactivate counters report the number of pages moved between the active and inactive lists; the pgscan and pgsteal counters report the number of pages scanned and reclaimed. Run a workload that stresses memory and observe how these counters change.
Reflect. In your own words, explain why the page-replacement policy matters most when the system is overcommitted, and why it matters least when memory is abundant. Then describe one situation in your own experience — a system you have used or administered — where the replacement policy's behaviour was important. What was the workload, and how did the policy affect the system?

10 Summary

The page-replacement policy decides which page to evict when a page fault occurs and no free frame is available. The policy's goal is to keep the process's working set in memory, minimising the fault rate and the amount of I/O.
The reference string model is a simplified representation of a process's memory accesses: a sequence of page numbers. The model makes the replacement algorithms comparable, and it allows their properties to be analysed precisely.
FIFO evicts the page that has been in memory the longest. It is simple but performs poorly, because it ignores recency and frequency, and it exhibits Belady's anomaly.
Belady's anomaly is the counterintuitive result that increasing the number of frames can increase the fault count for some algorithms. FIFO exhibits it; optimal and LRU do not, because they have the stack property.
Optimal replacement evicts the page whose next use is farthest in the future. It is the best possible algorithm, but it requires knowledge of the future and cannot be implemented. It is a theoretical benchmark.
LRU evicts the page that has not been used for the longest time. It approximates optimal replacement well, and it has the stack property. It is difficult to implement exactly, so real systems use approximations.
The clock algorithm approximates LRU using a single reference bit per page and a circular list of pages. The hand sweeps the list, giving second chances to recently used pages, and evicts the first page whose reference bit is clear.
The enhanced second-chance algorithm adds the dirty bit, distinguishing four classes of pages. It prefers to evict clean, unrecently-used pages, because those are the cheapest to evict.
The counting algorithms (LFU and MFU) use access frequency rather than recency. They are less common than the clock-based algorithms, but they are useful in systems with a small number of resident pages.
The frame-allocation policy decides how many frames each process receives. The classical policies are equal allocation, proportional allocation, working-set-based allocation, and page-fault-frequency allocation.
Global replacement chooses victims from all pages in the system, which improves utilization but makes individual processes' fault rates depend on the others. Local replacement chooses victims from the faulting process's pages, which is more predictable but less efficient.
The working-set model defines the working set as the set of pages a process has accessed in the last w time units. A process needs at least its working set's worth of frames to run efficiently; if the sum of all working sets exceeds the memory, the system is overcommitted.
The page-fault-frequency policy is a practical alternative to the working-set model. It measures each process's fault rate and adjusts its frame allocation to keep the rate within an acceptable band.
Real operating systems use approximations of the classical algorithms. Linux uses an active/inactive list structure with a variant of the clock algorithm, and the kswapd daemon scans the page tables periodically to identify candidates for eviction.

Looking ahead

This lesson presented the page-replacement policy: the classical algorithms, their properties, and the frame allocation policies that complement them. It referred several times to thrashing, the failure mode that occurs when the sum of the processes' working sets exceeds the physical memory. Thrashing is the subject of Lesson 9.7, the final lesson of Unit 9. The lesson presents the symptoms and causes of thrashing, the working-set and page-fault-frequency methods for detecting it, and the strategies for recovering from it: reducing the degree of multiprogramming, swapping out processes, and adjusting the replacement policy. Thrashing is the endpoint of the virtual-memory mechanism that this unit has developed: the point at which the mechanism's assumptions break down and the system's performance collapses.

11 References

Silberschatz, A., Galvin, P. B., & Gagne, G. Operating System Concepts, 10th ed., Chapter 10, Sections 10.4–10.6.
Arpaci-Dusseau, R. H., & Arpaci-Dusseau, A. C. Operating Systems: Three Easy Pieces, Chapter 22, Swapping: Policies. Available online at ostep.org.
Tanenbaum, A. S., & Bos, H. Modern Operating Systems, 4th ed., Chapter 3, Section 3.4.
Belady, L. A. A Study of Replacement Algorithms for Virtual-Storage Computer Systems. IBM Systems Journal, 1966.
Belady, L. A., Nelson, R. A., & Shedler, G. S. An Anomaly in Space-Time Characteristics of Certain Programs Running in a Paging Machine. Communications of the ACM, 1969. The paper that discovered Belady's anomaly.
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. Virtual Memory. ACM Computing Surveys, 1970.
Corbato, F. J. A Paging Experiment with the Multics System. In In Honor of Philip M. Morse, MIT Press, 1969. An early empirical study of paging behaviour.
Love, R. Linux Kernel Development, 3rd ed., Chapter 12, Memory Management, and Chapter 16, The Page Cache and Page Writeback. The Linux implementation of the page-replacement policy, including the active and inactive lists and the kswapd daemon.
Gorman, M. Understanding the Linux Virtual Memory Manager. Prentice Hall, 2004. A detailed reference for the Linux memory-management subsystem, including the page-replacement policy.
Linux kernel source: mm/vmscan.c (the page-reclamation code) and mm/page_alloc.c (the page allocator).
Linux man-pages: man 2 madvise, man 5 proc, man 1 perf-stat, man 1 time.