Page Replacement Examples

Problem-01: 

A system uses 3 page frames for storing process pages in main memory. It uses the First in First out (FIFO) page replacement policy. Assume that all the page frames are initially empty. What is the total number of page faults that will occur while processing the page reference string given below-

4 , 7, 6, 1, 7, 6, 1, 2, 7, 2

Also calculate the hit ratio and miss ratio. 

Solution- 

Total number of references = 10

 

 From here,

Total number of page faults occurred = 6

 

Calculating Hit ratio- 

Total number of page hits

= Total number of references – Total number of page misses or page faults

= 10 – 6

= 4

 Thus, Hit ratio

= Total number of page hits / Total number of references

= 4 / 10

= 0.4 or 40% 

Calculating Miss ratio- 

Total number of page misses or page faults = 6

 Thus, Miss ratio

= Total number of page misses / Total number of references

= 6 / 10

= 0.6 or 60%

 

Alternatively,

Miss ratio

= 1 – Hit ratio

= 1 – 0.4

= 0.6 or 60%

 

Problem-02: 

A system uses 3 page frames for storing process pages in main memory. It uses the Least Recently Used (LRU) page replacement policy. Assume that all the page frames are initially empty. What is the total number of page faults that will occur while processing the page reference string given below-

4 , 7, 6, 1, 7, 6, 1, 2, 7, 2

Also calculate the hit ratio and miss ratio. 

Solution- 

Total number of references = 10 

 

From here,

Total number of page faults occurred = 6

 In the similar manner as above-

• Hit ratio = 0.4 or 40%
• Miss ratio = 0.6 or 60%

 

Problem-03: 

A system uses 3 page frames for storing process pages in main memory. It uses the Optimal page replacement policy. Assume that all the page frames are initially empty. What is the total number of page faults that will occur while processing the page reference string given below-

4 , 7, 6, 1, 7, 6, 1, 2, 7, 2

Also calculate the hit ratio and miss ratio. 

Solution-

Total number of references = 10

 

 

From here,

Total number of page faults occurred = 5 

In the similar manner as above-

• Hit ratio = 0.5 or 50%
• Miss ratio = 0.5 or 50%

 

To gain better understanding about Page Replacement Algorithms,

Problem-04: 

Consider a main memory with five page frames and the following sequence of page references: 3, 8, 2, 3, 9, 1, 6, 3, 8, 9, 3, 6, 2, 1, 3. which one of the following is true with respect to page replacement policies First-In-First-out (FIFO) and Least Recently Used (LRU)?

A. Both incur the same number of page faults
B. FIFO incurs 2 more page faults than LRU
C. LRU incurs 2 more page faults than FIFO
D. FIFO incurs 1 more page faults than LRU

Solution:

Number of frames = 5

FIFO

According to FIFO, the page which first comes in the memory will first goes out.

Number of Page Faults = 9
Number of hits = 6

LRU

According to LRU, the page which has not been requested for a long time will get replaced with the new one.

Number of Page Faults = 9
Number of Hits = 6

The Number of page faults in both the cases is equal therefore the Answer is option (A).