Page Replacement for Virtual Memory
Virtual memory becomes useful when physical memory becomes full, however at that point we need to figure some things out:
- page replacement: what pages are best to swap out to disk If a process needs more memory and is at maximum frame allocation, we can pick one of its own pages to replace. We could use a common replacement policy such as FIFO, random, or LRU.
- frame allocation: how many frames of physical memory does each process get?
We also don’t want physical memory to get completely full in case the OS needs some memory for internal use, i.e. to make progress on page replacement.
Page Replacement: Implementing LRU
Using an LRU replacement policy is a good idea because of locality of reference.
This graph shows memory addresses being accessed against time. However, we can’t actually implement LRU because of hardware limitations, we don’t get given any sort of timestamp to understand the last access.
The hardware sets the dirty bit whenever the page is written to and sets the used bit whenever the page in question is used.
Instead, we can make use of the used (sometimes referenced) bit. The OS periodically clears all used bits, so if the bit is set we know the page was used recently (just not how recently).
So, we need to pick a page, preferring those with a clear used bit. To break ties we can at best degenerate to random or FIFO. A common approach is ‘second-chance FIFO’, where we walk the list from oldest to newest, and if we see a non-used page we choose it. If we see a used page, we give it a second chance (clear its used bit and keep walking) which sends it to the back of the list.
To optimise this implementation, we use a circular list with a ‘current position’ pointer which we can pick up from each time we need to search. This is called Clock and avoids any expensive list manipulation.
Frame Allocation
Conceptually, each process has a set of pages that it is ‘using now’ that it needs to make uninterrupted progress over a small time interval. This is called the working set. The size of this set is called the working set size (WSS). To estimate the WSS, we count used bits after clearing them some time prior (say 100ms).
When all processes get less than their WSS, system throughput will drop to nearly zero, this is called thrashing: runnable threads plummet and the system is spending time waiting on I/O. So we should try to give processes as many WSS frames as possible not necessarily equal amounts of frames to each.
Complementary strategies to this exist for managing out-of-memory situations, this includes the Linux ‘OOM killer’.