One common page replacement algorithm is the Least Recently Used (LRU) algorithm. The LRU algorithm replaces the page that has not been used for the longest time.
Let’s consider an example with a memory of four page frames and a sequence of page references: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5.
Initially, all page frames are empty:
|---|---|---|---|
| | | | |
|---|---|---|---|
When the first page reference (1) comes in, it is placed in the first frame:
|---|---|---|---|
| 1 | | | |
|---|---|---|---|
When the second page reference (2) comes in, it is placed in the second frame:
|---|---|---|---|
| 1 | 2 | | |
|---|---|---|---|
When the third page reference (3) comes in, it is placed in the third frame:
|---|---|---|---|
| 1 | 2 | 3 | |
|---|---|---|---|
When the fourth page reference (4) comes in, it is placed in the fourth frame:
|---|---|---|---|
| 1 | 2 | 3 | 4 |
|---|---|---|---|When the fifth page reference (1) comes in, it is already in memory, so there is no page fault:
|---|---|---|---|
| 1 | 2 | 3 | 4 |
|---|---|---|---|
When the sixth page reference (2) comes in, it is already in memory, so there is no page fault:
|---|---|---|---|
| 1 | 2 | 3 | 4 |
|---|---|---|---|
When the seventh page reference (5) comes in, all page frames are in use. The LRU page is the one that has not been used for the longest time, which is page 3. So, page 3 is replaced with page 5:
|---|---|---|---|
| 1 | 2 | 5 | 4 |
|---|---|---|---|
When the eighth page reference (1) comes in, page 1 is already in memory, so there is no page fault:
|---|---|---|---|
| 1 | 2 | 5 | 4 |
|---|---|---|---|
When the ninth page reference (2) comes in, page 2 is already in memory, so there is no page fault:
|---|---|---|---|
| 1 | 2 | 5 | 4 |
|---|---|---|---|
When the tenth page reference (3) comes in, page 3 is not in memory, and all page frames are in use. The LRU page is page 4, which has not been used for the longest time. So, page 4 is replaced with page 3:
|---|---|---|---|
| 1 | 2 | 5 | 3 |
|---|---|---|---|
When the eleventh page reference (4) comes in, page 4 is not in memory, and all page frames are in use. The LRU page is page 1, which has not been used for the longest time. So, page 1 is replaced with page 4:
|---|---|---|---|
| 4 | 2 | 5 | 3 |
|---|---|---|---|When the ninth page reference (5) comes in, page 5 is already in memory, so there is no page fault:
|---|---|---|---|
| 4 | 2 | 5 | 3 |
|---|---|---|---|