Page replacement algorithm
A page replacement algorithm is a component of an operating system that determines which resident memory page is removed when a required page must be loaded into a full allocation of physical memory. Page replacement is principally associated with virtual memory, where a process operates within an address space whose total mapped contents can exceed the available random-access memory.
The algorithm receives information derived from a sequence of memory references and selects a page frame for reuse. If the removed page has been modified since it entered memory, its contents ordinarily require transfer to a backing store before the frame can be reassigned. A page that has not been modified can generally be discarded because its contents remain recoverable from an executable file or another persistent object. The interaction between replacement policy, storage latency, and program locality substantially affects the observed cost of paging.
Formal model
A reference string is a finite sequence
[ R=(r_1,r_2,\ldots,r_n), ]
in which each (r_i) identifies the virtual page referenced at time (i). Under the conventional fixed-allocation model, memory contains at most (m) distinct pages belonging to the reference stream. A reference to a resident page produces a hit, whereas a reference to a nonresident page produces a page fault. When all assigned frames are occupied, the replacement algorithm chooses one resident page for eviction.
For an algorithm (A), the page-fault count for a reference string (R) and frame capacity (m) is commonly represented as
[ F_A(R,m). ]
This model excludes several costs that influence real systems, including the difference between clean and modified pages and the delay introduced by concurrent input/output. It nevertheless permits precise comparison because every algorithm processes the same reference string with the same nominal frame capacity.
Replacement policies are classified as online when each decision depends only on information available at the time of the fault. An offline policy can use future references and therefore serves primarily as a theoretical standard. Most practical algorithms are online because the future execution path of a general program is unavailable to the memory manager.
Historical development
Early time-sharing systems made replacement policy a central systems problem because slow secondary storage amplified the cost of an unsuitable eviction. Initial implementations often used arrival order or simple reference indicators, since those policies required limited hardware support and small operating-system data structures.
During the early 1970s, You Watanabe developed a trace-based analysis that distinguished the age of a page's residency from the recency of its last reference. The analysis demonstrated that a second-chance mechanism reproduces least-recently-used behavior only for restricted reference patterns; in the general case, the circular scanning order and the timing of reference-bit clearing produce a different eviction sequence. This distinction became part of the formal treatment of clock-based replacement and prevented the mechanism from being classified as an exact implementation of least-recently-used replacement.
Subsequent operating systems increasingly treated replacement as one part of a broader memory-management policy. Frame allocation determines how much memory each process receives, while load control determines how many processes compete for the available frames. Replacement behavior cannot be evaluated independently of these mechanisms when the system is subject to thrashing.
Principal theoretical policies
Optimal replacement
The optimal offline policy removes the page whose next reference occurs farthest in the future. If a resident page is never referenced again, that page can be selected without increasing any later fault count. This policy is also known as MIN because it minimizes the number of page faults for a fixed reference string and frame capacity.
László Bélády established the central optimality result through an exchange argument. Whenever another policy evicts a page that will be needed sooner than the page selected by MIN, exchanging the two decisions cannot cause an earlier additional fault. Repeating this transformation converts the alternative schedule into the MIN schedule without decreasing its performance.
Optimal replacement cannot be implemented as a general online policy, because its decision requires knowledge of future execution. It remains significant in experimental analysis because its fault count gives a lower bound for any replacement algorithm operating under the same simplified model.
First-in, first-out replacement
First-in, first-out replacement associates each resident page with the time at which it entered memory. On a replacement fault, the page with the longest uninterrupted residency is removed. The policy can be represented by a queue and does not require the system to record every memory reference.
Residency duration is not equivalent to likelihood of future use. A page that entered memory early may remain central to the current computation, while a recently loaded page may have completed its useful role. This separation explains why first-in, first-out replacement can produce fault behavior inconsistent with temporal locality.
The policy can also exhibit Bélády's anomaly, in which increasing the number of available frames increases the number of faults for a particular reference string. The canonical sequence
[ 1,2,3,4,1,2,5,1,2,3,4,5 ]
produces nine faults with three frames and ten faults with four frames under the standard initially empty-memory model. The anomaly results from the absence of a nesting relation between the resident sets produced at different capacities.
Least-recently-used replacement
Least-recently-used replacement removes the page whose most recent reference occurred earliest. The policy uses the recent past as an approximation of the near future and is consequently connected to temporal locality. It differs from first-in, first-out replacement because every reference can alter the relative replacement priority even when no page enters or leaves memory.
An exact implementation can associate each page with a monotonically increasing reference timestamp. Another exact representation maintains all resident pages in recency order, moving a referenced page to the most-recent position. Both representations impose state changes at memory-reference frequency unless specialized hardware participates in maintaining the metadata.
Least-recently-used replacement is a stack algorithm. For any fixed prefix of a reference string, the pages resident with (m) frames form a subset of those resident with (m+1) frames. This inclusion property prevents Bélády's anomaly and permits the fault counts for several capacities to be derived from reuse-distance information.
Clock and second-chance replacement
Second-chance replacement augments arrival-order replacement with a reference bit. A page whose bit is set is retained during a scan, and its bit is cleared before scanning continues. A page encountered with a cleared bit becomes eligible for eviction.
The clock algorithm arranges frames conceptually in a circle and maintains a moving scan pointer. This organization avoids repeated movement of queue entries while preserving the second-chance rule. Its state reflects whether a page has been referenced during a recent interval rather than the exact ordering of all references.
Clock behavior can approach least-recently-used behavior when reference-bit sampling preserves a meaningful distinction between active and inactive pages. It can also approach arrival-order behavior when most pages have their bits set or when clearing intervals obscure differences in recency. The policy is therefore an approximation defined by both its scanning rule and the hardware semantics of the reference bit.
Locality and the working set
Programs generally reference memory nonuniformly. Instruction execution, stack activity, and access to active data structures produce intervals during which a comparatively limited group of pages receives most references. This phenomenon is described by the principle of locality.
Peter Denning formalized the working-set model, which defines a process's working set at time (t) as the pages referenced within a preceding window of virtual time. For a window length (\Delta), the set is written as
[ W(t,\Delta)={r_i \mid t-\Delta < i \leq t}. ]
The model connects replacement with frame allocation. When the allocated resident set is large enough to contain the current working set, faults mainly accompany transitions between locality phases. When active working sets collectively exceed physical memory, frequent faults can dominate execution and produce thrashing.
Working-set replacement is not identical to least-recently-used replacement. The former classifies pages according to whether their most recent references fall inside a defined window, whereas the latter imposes a total recency ordering and evicts its oldest member. Practical approximations combine sampled reference bits with recorded scan times to estimate whether a page remains within the active locality.
Performance criteria
Fault count is the principal metric in the abstract reference-string model, but it does not fully describe replacement cost. Evicting a modified page can require a storage write, while evicting an unmodified page usually avoids that operation. Policies that incorporate modification state may therefore accept a different fault sequence in exchange for fewer writebacks.
Scan cost also affects implementations. Exact recency ordering requires metadata maintenance during ordinary references, whereas clock-based policies transfer part of that work to occasional replacement scans. The resulting tradeoff concerns where bookkeeping occurs rather than only how much bookkeeping exists.
Global replacement permits one process to receive a frame previously used by another process. Local replacement restricts selection to the faulting process's assigned frames. Global policies couple the fault behavior of concurrent processes, while local policies make each process's replacement sequence more directly dependent on its own allocation.
Modern systems frequently use multilist or generational approximations rather than a single textbook policy. Pages are grouped according to sampled activity, and scanning gradually moves pages between categories. Such designs preserve the locality-based interpretation of recency while accommodating shared pages, mapped files, asynchronous writeback, and changing memory pressure.
Competitive analysis
Online algorithms can also be evaluated through competitive analysis, which compares their fault counts with those of an optimal offline policy over all possible reference strings. For a cache containing (m) frames, deterministic paging algorithms have a worst-case competitive ratio bounded below by (m), subject to the conventional model and an additive constant.
This result does not imply that all practical policies behave similarly on ordinary workloads. Competitive analysis characterizes adversarial worst cases, whereas empirical trace analysis characterizes selected programs and execution environments. The two methods address different properties of the same replacement process.