Page Cache: A Buffer Pool with LRU Eviction

Reading a page from disk costs thousands of times more than reading it from memory. A database therefore keeps a buffer pool: a fixed number of in-memory slots (frames) holding recently used pages, between the B-tree and the disk. After this lesson your pool answers reads from memory when it can, goes to disk when it must, decides which page to throw out when full, and never loses a change.

Hit, miss, load

Every READ of page p is one of:

• hit: p is in the pool. Return it; it is now the most recently used page.
• miss, page on disk: count a miss, make room if the pool is full, load p as the most recently used page and return it.
• miss, no such page: count a miss and answer NOT_FOUND. Nothing is loaded.

Which page to evict: least recently used

Pages used recently are likely to be used again soon (the root of a B-tree is read by every search), so when the pool is full the victim is the page untouched for the longest. The simplest exact structure is a list ordered from least to most recently used: a touch moves a page to the end, the victim is taken from the front. Real systems use a hash map plus a linked list to make touches O(1); the order they implement is the same.

capacity 3        order (LRU -> MRU)
read 1,2,3        1 2 3
read 1 (hit)      2 3 1
read 4 (miss)     evict 2:  3 1 4

Dirty pages and write-back

A WRITE changes the cached copy only. The page is now dirty: memory and disk disagree. If the pool dropped it silently, the change would vanish, so evicting a dirty page first writes it back to disk. A clean page can be dropped for free. Writes put the new contents in the pool without reading the old ones from disk (the whole page is replaced), so a write is neither a hit nor a miss.

CACHE FLUSH writes back every dirty page, in ascending page number, and reports how many (OK flushed=<n>). Afterwards those pages are clean, so flushing again writes nothing.

Pinning

A page that is in use (an operation is walking it) must not be evicted from under the caller. CACHE PIN <id> raises a pin count and CACHE UNPIN <id> lowers it. The victim is the least recently used page whose pin count is 0. If every page is pinned, the pool cannot make room: ERR all pages pinned, and nothing changes. Pins nest: two pins need two unpins. Pinning does not change recency.

Commands

Every eviction counts one eviction; every page copied to disk (on eviction or flush) counts one writeback.

Common mistakes

• Not refreshing recency on a hit. The victim then depends on load order, not use.
• Dropping a dirty page without writing it. DISK READ after the eviction must show the new data.
• Evicting a pinned page, or counting an eviction when nothing could be evicted.
• Counting writes as hits. Only reads feed the hit counter.

Your exercise

The starter parses the commands and prints statistics and the list. You implement write_back, evict_one, make_room, read_page, write_page and flush_all. The mistake to avoid: choosing the victim by insertion order instead of last use.