Implement Swapping: Write Pages to Swap File

Topic Overview

Disk as Overflow Memory

Swapping moves cold pages to a swap file or partition, freeing physical frames for hotter data. On access, a major page fault reads the page back. Thrashing happens when reclaim cost exceeds useful work.

Swap Slot Management

Kernel swap path:

• Pick victim page with clock or LRU approximation
• Write frame to swap slot, mark PTE swapped
• On fault, read slot back into new frame

For example, a workstation with 8 GB RAM running 12 GB of idle browser tabs may keep working sets in RAM while cold tabs live in swap slot 4421.

Why This Matters in Production

Linux's kswapd daemon and its two-list active/inactive LRU approximation , a more scalable cousin of the victim selection you implement here , decide which pages get written to swap the moment memory pressure hits. Get victim selection wrong and you reproduce thrashing, the exact failure mode where a server burns more cycles swapping pages than serving requests.

Debugging Checklist

Before you call the implementation done, walk failure modes on purpose. Test empty structures, single-element edge cases, maximum concurrency, and errno paths that must not crash the program. OS code usually fails in production when happy-path tests pass but invariants break under contention or memory pressure.

Implementation Notes

Keep structures small and name fields after kernel counterparts when possible. That lets you read man pages and kernel source side by side while you work. Print observable events during development; remove noisy logs once tests pass reliably.

For This Exercise

You will implement a swap file backend and fault-in path for evicted pages. This exercise requires tracking page fault types (minor vs major) before and after swap pressure.

Your Task

Simulate swapping. There are only N physical frames. When they are all in use and a new page is needed, the kernel evicts the least recently used page. A page whose only up-to-date copy is in RAM must first be written to a swap slot (a swap-out). A page that was swapped in and hasn't been modified since still has a valid copy in its slot, so it can just be dropped, which is the cheap case. Touching a swapped-out page later causes a major fault that reads it back.

Input

cCopy
Loading…

Rules

• Hit: the page is resident. Update its LRU time; a write marks it dirty.
• Fault: take the lowest free frame. If none is free, evict first:
  • the victim is the resident page with the oldest last access (every access, hit or fault, counts);
  • if the victim is clean and has a swap copy, just drop it;
  • otherwise swap it out: to its existing slot if it has one (the old copy is stale), else to the lowest free slot. With no free slot, the access fails: out of swap space (nothing changes).
• A page never touched before becomes a zero page (minor fault). It counts as dirty, since no copy exists anywhere.
• A page with a swap slot is swapped in (major fault). It is clean after a read and dirty after a write, and it keeps its slot.

Output

cCopy
Loading…

The eviction note is appended to the fault line that caused it.

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. Per page: resident flag, frame, swap slot (or none), dirty flag and last-access time. Plus a frame bitmap and a slot bitmap.
2. Never write a clean page that already has a valid swap copy. That saved write is why swap-ins keep their slot.

Hidden tests cover a page rewritten after being swapped in (swapped out again to its same slot), running out of swap space, free releasing both a frame and a slot, and a scan larger than RAM repeated twice (LRU's worst case).