Page replacement

One problem with modern page table memory systems is that the amount of memory used by all processes may exceed the amount of actual physical memory. Page replacement refers to schemes that keeps referenced pages in memory and puts others on disk. Then, they’re only swapped back to memory when they’re needed.

Mechanism

Some space on the disk is reserved for moving pages back and forth, called swap {space, files}. The OS needs to remember the disk address of a given page once it’s swapped out.

swap files

• used for replacements
• memory is pretty cheap and has high capacity. we might want to know when we need more memory than to just let a process run slowly (if more than available memory, we need to keep swapping. this is not performant. if we disable swapping, linux will OOM kill the process and we know we just need more memory in system)
• larger page sizes allow for speedups (2 MB, 1 GB)
  • trade off: more fragmentation for more TLB coverage

demand paging:

• use memory as a Cache for the filesystem

• map memory pages to filesystem blocks

• only load them into memory when they’re used through the page fault

• if the page doesn’t represent a file, we map it to swap space

• move it to disk if we need to use more physical memory

• number of pages used by a Process is called its working set

• if we can’t fit the working set into physical memory, the process will thrash, i.e., move entries in and out of cache. performance will suffer

All memory in user-mode can be swapped out. Not all memory in kernel-mode can be swapped out. There are two regions for dynamically allocated memory:

• The paged pool can be swapped out to a disk file.
• The non-paged pool can never be paged out to a disk file.

Replacement algorithms

We use certain algorithms (much like any caching scheme) to determine which pages we should swap out to disk.

• Optimal — replace the page that won’t be used for the longest.
  • This looks into the future, so isn’t implementable in practice.
  • Core idea is to maximise page hits.
• Random — replace a random page.
• FIFO — replace the oldest page first.
  • It turns out: more page frames (i.e., more memory) can cause more page faults. This is called Bélády’s anomaly.
  • This only holds for FIFO algorithms. For other algorithms, adding more memory (increasing the number of page frames) decreases the number of page faults.
• LRU — pick the least recently used page.
  • In practice, this is still not viable. The naïve implementation requires $\mathcal{O}(n)$ traversal. An optimised LRU implementation still requires $\mathcal{O}(1)\times 6$ pointer accesses per page reference. This adds quite a bit of contention with multiple processor machines.
• Clock — approximates LRU quite well. Used in practice.