Questions: Buffer Pool Management and Cache Replacement Policies

Question 1

The buffer pool is full and the replacement policy selects a page to evict. The chosen page's dirty bit is set to 1. What must happen before the frame can be reused?

• A. Nothing extra — the dirty bit just indicates the page was recently accessed, not that it was modified
• B. The page must be written back to disk before the frame can be reused, incurring a write I/O
• C. The page is discarded immediately since dirty pages are invalid and the disk copy is authoritative
• D. The pin count must be decremented to zero before the dirty page can be written

Answer: (B)

The dirty bit tracks whether a page has been modified since it was read from disk. A dirty page has changes that exist only in memory — the disk copy is stale. Before the frame can be reused for a new page, the dirty page must be flushed to disk, incurring a write I/O. A clean page (dirty bit = 0) can be evicted instantly because the disk copy is still valid. This asymmetry is why the buffer manager tries to evict clean pages first and why background writer processes proactively flush dirty pages.

Question 2

A database buffer pool is running the clock algorithm. A frame's reference bit is currently 1 when the clock hand reaches it during eviction. What happens?

• A. The frame is immediately evicted because it was recently accessed and should be refreshed
• B. The reference bit is reset to 0, the clock hand moves on, and the frame gets a 'second chance'
• C. The frame's pin count is incremented to protect it from future eviction
• D. The frame is promoted to a special 'hot' list that the clock algorithm skips permanently

Answer: (B)

The clock algorithm approximates LRU with less bookkeeping. When the clock hand encounters a frame with reference bit = 1, it gives it a second chance: reset the bit to 0 and move on. Only when the hand returns to a frame and finds the bit still 0 (meaning no access occurred in the interim) does it evict that frame. This avoids LRU's expensive per-access list updates while still approximating recency — recently accessed pages have their bit reset to 1 before the hand can revisit them.

Question 3

LRU is the most commonly implemented replacement policy in real database buffer pools because it provides the best performance in most workloads.

• T. True
• F. False

Answer: False

Despite LRU's theoretical appeal, most real database systems use the clock algorithm (or variants like Clock-Pro or 2Q) rather than true LRU. The reason is overhead: LRU requires updating a precise access ordering on every page access — typically maintaining a doubly-linked list — which adds synchronization cost in concurrent systems. The clock algorithm approximates LRU's behavior with a single reference bit and no per-access list manipulation. Additionally, LRU performs poorly on sequential scans (where every page is accessed exactly once and then not again), and real systems often use special-purpose policies for scan patterns.

Question 4

A page with a pin count greater than zero cannot be evicted by any replacement policy, regardless of how long it has been in the buffer pool.

• T. True
• F. False

Answer: True

The pin count tracks how many active operations are currently using a page. If a transaction or query is in the middle of reading or writing a page, it pins the page to prevent the buffer manager from evicting it mid-operation. Any eviction algorithm — LRU, FIFO, clock — must skip pinned pages entirely. The pin count is decremented when the operation completes, at which point the page becomes eligible for eviction. This mechanism is essential for correctness: evicting a page an active operation depends on would cause data corruption or invalid memory references.

Question 5

Why does evicting a dirty page cost more than evicting a clean page, and how do database systems reduce this overhead?

Model answer: A dirty page has been modified in memory but not yet written to disk, so evicting it requires a write I/O to persist the changes — doubling the I/O cost compared to simply reading a new page in. A clean page's disk copy is still valid, so no write is needed. Database systems reduce this overhead through background writer processes that proactively flush dirty pages to disk during idle periods, so that when eviction is needed, more frames are already clean and can be evicted immediately.

The dirty bit is central to both correctness and performance. Without flushing dirty pages before eviction, updates would be permanently lost. But if every eviction required a write (flush) followed by a read (new page), the effective throughput would be halved. Background flushing decouples these two operations: dirty pages are written to disk asynchronously before they are urgently needed for eviction, so the eviction path is usually just a read, not a read-after-write.