FIFO page replacement orders resident pages by when they were loaded and evicts the oldest arrival. An access to a resident page does not change this order, so an old but heavily used page can be the next victim.
LRU replacement records the recency of every page access and evicts the page whose most recent access is oldest. It makes use of temporal locality, but exact reference tracking can require expensive per-access hardware or software bookkeeping.
CLOCK page replacement arranges frames in a circle with a scanning hand and one reference flag per frame. A use sets the flag. During replacement, the hand clears a set flag and moves on, giving that page another chance; it selects an eligible frame with a clear flag. Recent pages tend to survive a scan. CLOCK page replacement approximates recency rather than preserving the exact LRU replacement ordering. A dirty victim must be written back before its frame is reused, and pinned frames must be skipped.
Emulate reference observations using page table protection and page faults. When resetting a page's reference state, temporarily revoke access to its resident mapping and invalidate any corresponding translation lookaside buffer entry. The first subsequent access traps. The handler recognizes an intentionally protected resident page, sets a software reference flag and restores the mapping without performing a disk read. A later CLOCK page replacement scan can use and clear this software flag.
One protection fault records the first access after each reset, rather than trapping on every access. All mappings that can access the frame must be considered. The method requires ordinary memory-protection traps, even though hardware reference bits are absent, and adds a fault cost that native reference flags avoid.
Choose CLOCK for page replacement in a conventional operating system. Good temporal locality makes recency valuable, and CLOCK page replacement captures it reasonably well using cheap reference flags. FIFO page replacement ignores accesses after a page arrives, so it can evict a hot page. Exact LRU replacement has a stronger recency rule but recording and maintaining the order on every ordinary memory access is usually too costly. This is a practical cost-versus-hit-rate choice, not a theorem that CLOCK page replacement minimizes faults on every reference sequence.
A buffer cache keeps copies of device blocks in main memory, indexed by device identity and block number. It reduces expensive repeated device reads and can combine several modifications into one write. It also gives software a controlled place to hold data while requests are in progress.
On a read, the operating system looks up the block. A valid cached copy gives a hit and supplies the data; a miss reserves an eligible buffer, writes its old contents first if dirty, issues the device read, and marks the new contents valid when the transfer completes. A write modifies the buffer and marks it dirty. Under a write-back policy, a later flush or eviction sends it to the device; under write-through, completion also waits for the required device write. Dirty state differs from “currently in use”: a pinned or locked buffer cannot simply be reused while a request depends on it.
A buffer cache needs synchronization for concurrent readers, writers and in-flight transfers, and should avoid inconsistent independent copies of the same block. Explicit flushes and ordering are needed when durable storage is required; caching alone does not guarantee that an acknowledged in-memory update survives a crash. Replacement chooses among eligible buffers, preserving dirty data before reuse.
Use LRU replacement, or a modest recency-based approximation, for eligible buffer-cache entries. Unlike individual memory accesses, buffer cache lookups already pass through operating system code. Updating an LRU replacement list on each lookup is therefore practical: remove the accessed entry from its old position and put it at the most-recent end; choose the oldest unpinned entry as victim. A hash lookup plus a doubly linked recency list makes this bookkeeping constant time.
Good temporal locality favors retaining recently used blocks. FIFO page replacement's arrival-only criterion can evict a block used moments ago. CLOCK page replacement can save bookkeeping, but the difficulty of observing arbitrary memory references that motivates it is absent for software-mediated block accesses. Dirty victims require write-back, so a policy can favor an old clean buffer or arrange background cleaning without discarding recent hot data. A long one-pass scan can pollute pure LRU replacement; scan-resistant variants are useful refinements rather than a reason to ignore recency altogether.
Articles by others on the same topic
There are currently no matching articles.