PintOS: The Day Memory Was Full

A new page needed to come in, and there was no frame left. A page is one piece of the virtual memory a program uses; a frame is the seat where that piece actually sits in RAM. When every seat is taken, someone has to leave. The page singled out to go is called the victim.

The problem looked simple, but two questions kept trailing it. Which page can leave at the smallest loss? And must the entire memory be walked, every time, to find that one page? This design began with those two questions.

Clearing One Seat

Eviction does not cost the same for every page. A page read from a file and never modified can simply be dropped — the original is still in the file, and rereading it is enough. A modified file page must first write its changes back to the file. An anonymous page, like stack or heap, has no backing file at all; its current contents must be preserved wholesale on the swap disk.

So the standard for a victim is not "the oldest page" but "the page cheapest to evict now and revive later." Pages were divided by kind and modification into cost classes: file clean, file dirty, anon, stack anon. When swap space runs low, the design grows one degree more cautious about choosing anonymous pages.

Putting State on a Single Coordinate

Opening frame structs one by one on every victim search means walking the whole of memory again each time. Too high a price for clearing one seat. So every frame was given a consecutive frame_id and seated in an array.

Detailed information, like the page address, stays in the frame struct. States that end in yes or no — in use? pinned? holding a file page? — were gathered separately into bitsets. One frame, one bit; that is the whole array.

frame_table_by_id[17]  → detailed info for frame 17
occupied_bits[17]      → currently in use?
pinned_bits[17]        → must not be moved right now?
file_bits[17]          → holding a file page?

Array or bitset, the same number means the same frame. The struct reads one chosen frame in depth; the bitset asks every frame the same question at once.

Building the Net

One bitset is one condition. Layer several at the same position with AND and NOT, and only the frames that pass every condition remain 1.

  valid
& occupied
& ~pinned
& ~evicting
& ~shared
──────────────────
frames safe to select

pinned marks a frame the kernel is working on and must not be touched; evicting marks one already claimed by another eviction. Frames shared by multiple pages are set aside as well. Past these required conditions, the net tightens toward unmodified file pages and pages untouched for a long while.

The speed comes from bundling. The states of 64 frames fold into a single 64-bit word and are filtered in one logical operation. A word cursor visits the words in turn; within each word, a bit cursor resumes from where it last stopped. To keep selection from clustering in one region, at most two candidates are scooped from each word.

Collection stops at 32. It is a ceiling that bounds the lookup cost of the next stage — not an optimum, but a working budget, set for now to observe where the balance sits between candidate spread and evaluation cost.

Asking Again at the Last Moment

Bitsets narrow the candidates fast, but they are only hints. Whether a page was just touched, whether its contents changed — these keep shifting while the program runs. So this judgment is deferred to the very end and made directly against the page table, for the remaining candidates only.

The CPU sets the accessed bit in the page table when a page is used, and the dirty bit when its contents change. If accessed is on at check time, the page is pushed back in priority and the bit is cleared. If it is still off at the next evaluation, only then is there ground to believe the page has sat unused for a while.

Each frame records observation_count, how many times it has been evaluated, and cold_miss_count, how many consecutive times it showed no trace of access. Choosing first among candidates with accumulated observations and enough repeated "no access" — that is the strict phase. When no such candidate exists and a frame is needed now, the relaxed phase lowers the bar, weighing access state, observation count, and storage cost together.

The Responsibility After the Choice

Choosing a victim does not mean the frame can be overwritten. Mark, save, unmap, detach — only then, reuse. First the evicting bit goes on. Inside the lock-serialized eviction path, this mark keeps the same frame from being picked up as a candidate again. Then swap_out() takes over the preservation each kind of page requires: anonymous pages are written to the swap disk, modified file pages are flushed back to their files.

Once saving is done, pml4_clear_page() erases the mapping between the old virtual address and the frame from the page table. From this moment, access to that address can no longer reach the frame directly; it returns through a page fault to the kernel's recovery path. Sever the last reference between page and frame, and the frame becomes a seat for a new page.

The whole passage was recorded in a trace log. Which word candidate 437 came from, whether it showed traces of access, how it became the victim as file clean. Whether the policy ran as intended was confirmed not by the code, but by this record.

The Maintenance Cost of Elegance

Every time the bitsets were layered, frames scattered across memory gathered into one candidate set. I rather liked that sight. The trouble is that the more a design pleases you, the harder its maintenance cost deserves to be examined.

In exchange for dense state storage and word-level checks, the frame metadata array must be reserved in advance, and every path that mutates state must be managed so struct and bitset never drift apart. The accuracy of the hints and the synchronization of a global structure are burdens this design took on.

Whether it is truly faster than a plain sequential scan can only be answered on real workloads and benchmarks. The filtering computation shrinks, but the cost of updating the bitsets and the quality of the collected candidates can overturn the result either way.

What I gained was not the conclusion that some data structure is always superior. It was the experience of turning a problem into a repeated question, choosing a data structure shaped like that question, and placing the efficiency and the complexity that choice brought onto the same scale. The bitset was not the answer. It was a choice that transcribed, into the shape of code, the question I kept asking.