Virtual Memory Page Replacement Algorithms

Consider the following virtual page reference sequence: page 1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3. This indicates that these particular pages need to be accessed by the computer in the order shown. Consider each of the following 4 algorithm-frame combinations:

For each of the 4 combinations below move from left to right as the virtual page numbers are requested in sequence. Place each virtual page into one of the frames by writing in its number (initially while empty frames remain, load them from top down). When all frames are already occupied by other pages, select a victim page to displace according to the page replacement algorithm in use (LRU or FIFO) and mark the event with an F for Fault. (Do not count a fault when loading a missing page at a time when there is a frame unoccupied, in other words on the first 3 or 4 loads.) When finished, compute the total number of page faults.

Please work carefully.

THREE Page Frames

Least-recently-used (LRU) method:

1 2 3 4 2 1 5 6 2 1 2 3

 

 
 

 

 
 

 

 
 

 

 

 

 

 
 

 

 
 

 

 
 

 

 
 

 

 
 

 

 
 

 

 
 

Number of page faults for LRU/3:                     

 

First-in-First-out (FIFO) method:

1 2 3 4 2 1 5 6 2 1 2 3

 

 
 

 

 
 

 

 
 

 

 
 

 

 
 

 

 
 

 

 
 

 

 
 

 

 
 

 

 
 

 

 
 

 

 
 

Number of page faults for FIFO/3:                     

 

FOUR Page Frames

Least-recently-used (LRU) method:

1 2 3 4 2 1 5 6 2 1 2 3

 

 
 
 

 

 
 
 

 

 
 
 

 

 
 
 

 

 
 
 

 

 
 
 

 

 
 
 

 

 
 
 

 

 
 
 

 

 
 
 

 

 
 
 

Number of page faults for LRU/4:                     

 

First-in-First-out (FIFO) method:

1 2 3 4 2 1 5 6 2 1 2 3

 

 
 
 

 

 
 
 

 

 
 
 

 

 
 
 

 

 
 
 

 

 
 
 

 

 
 
 

 

 
 
 

 

 
 
 

 

 
 
 

 

 
 
 

Number of page faults for FIFO/4: