Page Eviction Algorithms

When a page fault occurs (data that is not in RAM needs to be loaded into RAM) and our RAM is full, we must decide on a page to evict from RAM to make room for the new page. There are several approaches to how we might want to evict pages.

Page Eviction Strategy #1: First In, First Out

The most basic strategy for evicting a page is simple: evict the page that has been in memory the longest. More generally, we call this a first in, first out or FIFO page eviction strategy.

To illustrate how this works, consider a series of page accesses:

At each step, we check if the page is already loaded into RAM. If the page is not already loaded into RAM, a page fault will occur and the data will be loaded into an available spot in RAM. If needed, the oldest page will be evicted.

• Page 17 is requested and is not in RAM. A page fault occurs and its loaded into RAM[0]. (We will denote a page fault by making the square bold where is was loaded.)

• Page 33 is requested and is not in RAM. A page fault occurs and its loaded into RAM[1].

• Page 40 is requested and is not in RAM. A page fault occurs and its loaded into RAM[2].

• Page 17 is already in RAM and can be accessed without a page fault.

• Page 43 is requested and is not in RAM. A page fault occurs and its loaded into RAM[3].

• Page 8 is requested and is not in RAM. A page fault occurs and the oldest page is evicted – Page 17 is evicted from RAM[0] and replaced with Page 8.

• Page 99 is requested and is not in RAM. A page fault occurs and the oldest page is evicted – Page 33 is evicted from RAM[1] and replaced with Page 99.

• Page 33 is requested and is not in RAM. (This is a really sad, as we just evicted Page 33!) Since it’s not in RAM, a page fault occurs and we evict the oldest page (Page 40) from RAM[2] and load in Page 33.

• Page 99 is already in RAM! :)

• Finally, Page 17 is now a RAM and one final page fault occurs.

Summary

After the ten page accesses, this is our full page table/RAM access diagram:

• A page faults occurred when the cell is outlined in a bold,
• A page access occurred when the cell is highlighted

Analysis

When using the FIFO page eviction strategy, we saw we needed eight page faults when accessing the pages in this access pattern. Since a page fault is an expensive operation (loading 4 KiB of data from storage into RAM), our goal is to minimize the number of page faults.

Page Eviction Strategy #2: Least Recently Used (LRU)

Another second strategy to explore is to examine how recently page page was used (accessed) instead of simply how long the page has been in RAM. By doing this, a frequently used page should be able to stay in RAM for a long time as long as it’s continually used.

Using the same memory access sequence, we can fill in the table the same way:

[…after all of the accesses…]

Analysis

On this memory sequence, LRU resulted in a different layout of pages within RAM but still had 8 page faults. We would need to explore more samples, and longer access patterns, to understand if LRU would outperform FIFO on this system.

However, what’s the best we can do?

Page Eviction Strategy #3: Optimal (OPT)

As we explore more strategies, we should explore what the optimal scenario would look like. Consider what would be the optimal eviction strategy:

• We want to evict the page that is used furthest in the future among all of the pages in RAM.
• This requires us know the future (impossible in the real world!) but will provide us the ability to find the best-case solution.

Using the same memory access sequence, we can fill in the table the same way:

[…after all of the accesses…]

Analysis

Using an optimal approach, we find we require six page faults even if we can know the future.

Page Eviction Strategy #4: Not Recently Used (NRU)

A new strategy we can explore begins to add more complexity. We want to capture the idea of how recently used is the page? To do that:

• When a page is used (accessed), set the recentlyUsed bit to 1.
• When a page needs to be evicted, evict a page least recently used page that has the recentlyUsed bit set to 0. If no pages have the recentlyUsed bit set to 0, set all pages recentlyUsed bit to 0 and evict the least recently used page.

Using the same memory access sequence, we can fill in the table the same way. Except that we will add an ! when the recentlyUsed bit is 0 and the page is in danger of being evicted:

[…after all of the accesses…]

Page Eviction Strategy #5: Least Frequently Used (LFU)

A final strategy we can explore captures the idea of how frequently used is the page?

In addition to storage the page, we will store the useCount. When evicting a page, we will evict the page with minimal value of useCount; in the case of a tie, we will evict the page that was least recently used:

[…after all of the accesses…]