Running out of memory

What the OS does when RAM runs out.

Swap space

When RAM is full, the OS moves some pages out to an area on disk called swap space. If a program touches a page that is in swap space, a page fault happens and the OS brings the page back. Disk is far slower than RAM, so this costs a long wait.

Choosing a page to evict

When RAM is full, a page must leave: it is evicted. The best choice is the page that will be needed furthest in the future. This optimal choice needs the future, so the OS guesses. A bad guess causes another slow page fault.

LRU and FIFO

LRU (least recently used) evicts the page that has gone unused the longest. Pages used recently are often used again soon, so LRU usually guesses well. FIFO (first in, first out) evicts the page that came into RAM first, like a queue. It is simpler to track, but it may evict a page that is still used all the time.

The clock algorithm

Exact LRU must note the time of every memory use, which costs too much. So the hardware sets a use bit to 1 whenever a page is used. Pages sit in a circle with a hand. To evict, the hand checks each page: if the bit is 1, it sets it to 0 and moves on; if the bit is 0, it evicts that page. Pages used lately get a second chance.

Thrashing

When programs need more pages than fit in RAM, each fault evicts a page someone needs next. The CPU waits on the disk and almost no work gets done: thrashing. The fix is to run fewer programs or add RAM. Linux may stop one big process to save the rest, with its out-of-memory killer.

Remember

• Swap space holds pages that don't fit in RAM.
• The optimal choice needs the future, so the OS guesses.
• LRU usually beats FIFO.
• Clock is a cheap guess at LRU, using one bit per page.
• Thrashing means too little RAM for the work.