Which page do you throw out of memory?
Page replacement is the choice of which page to remove from memory when a new page must come in and every frame is full. A good choice avoids slow trips to the disk, so programs stay quick.
Two simple rules, first in first out and least recently used, show how the choice is made.
By the end of this lesson
Note
I can simulate FIFO and LRU page replacement and count the page faults.
Key words
| Word | What it means | Example |
|---|---|---|
| Page fault | a request for a page that is not in memory | |
| Reference string | the list of pages a program asks for, in order | 1, 2, 3, 1 |
| FIFO | first in first out: remove the page that arrived earliest | |
| LRU | least recently used: remove the page unused for longest | |
| Swap | disk space used as spare memory | |
| Hit | a request for a page that is already in memory |
The cells students fill in are left blank in this preview.
A page fault is a missing page
Memory holds only some pages of each process. The rest wait on the disk, in a place called swap.
When a process asks for a page that is not in a frame, that is a page fault. The system must fetch the page from the disk. A disk is thousands of times slower than memory, so every fault costs real time.
If every frame is full, the system must also choose a page to remove.
Read the fault and swap counters since boot
grep -E '^(pswpin|pswpout|pgfault) ' /proc/vmstatShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Read how eagerly Linux uses swap
cat /proc/sys/vm/swappinessShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
FIFO removes the page that arrived first
First in, first out keeps the pages in the order they arrived. When a frame is needed, the oldest page goes.
It is easy to build, because it is a plain queue. It ignores how often a page is used. The table follows the reference string 1, 2, 3, 1, 4, 1, 2, 5, 1, 2 with three frames.
Worked example: FIFO with three frames
| Asks for | Result | Frames after, oldest first |
|---|---|---|
| 1 | fault | 1 |
| 2 | fault | 1, 2 |
| 3 | fault | 1, 2, 3 |
| 1 | hit | 1, 2, 3 |
| 4 | fault, 1 removed | 2, 3, 4 |
| 1 | fault, 2 removed | 3, 4, 1 |
| 2 | fault, 3 removed | 4, 1, 2 |
| 5 | fault, 4 removed | 1, 2, 5 |
| 1 | hit | 1, 2, 5 |
| 2 | hit | 1, 2, 5 |
| Total | 7 faults |
The cells students fill in are left blank in this preview.
LRU removes the page unused for longest
Least recently used guesses that a page used a moment ago will be used again soon. It removes the page that has gone unused the longest.
On every hit the page moves to the newest end of the list. The same string now gives fewer faults, because page 1 is kept while it is in use.
Worked example: LRU with three frames
| Asks for | Result | Frames after, least recent first |
|---|---|---|
| 1 | fault | 1 |
| 2 | fault | 1, 2 |
| 3 | fault | 1, 2, 3 |
| 1 | hit | 2, 3, 1 |
| 4 | fault, 2 removed | 3, 1, 4 |
| 1 | hit | 3, 4, 1 |
| 2 | fault, 3 removed | 4, 1, 2 |
| 5 | fault, 4 removed | 1, 2, 5 |
| 1 | hit | 2, 5, 1 |
| 2 | hit | 5, 1, 2 |
| Total | 6 faults |
The cells students fill in are left blank in this preview.
A common mistake
Warning
Many people think LRU never does worse than FIFO. On many strings it does better, but not on all of them. Take the string 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 with three frames. FIFO has 9 faults and LRU has 10. Every rule is a guess about the future.