Assignment - 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:

Print a copy of this page. For each of the 4 combinations, below, move from left to right as the virtual page numbers are requested in sequence. Put each virtual page into one of the frames by writing its number there (initially while empty frames remain, load them from top down). When all frames are already occupied by other pages, choose the right page to displace according to the applicable algorithm (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, total the number of page faults and write it in where indicated.

Submit the printout. The assignment will be graded on 8 items: the 4 final page configuration figures at the extreme right (correct or incorrect), and the 4 page fault totals written (correct or incorrect). 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: