GATE CSE 2001 | Question: 1.21

Question

Consider a virtual memory system with FIFO page replacement policy. For an arbitrary page access pattern, increasing the number of page frames in main memory will

• A. always decrease the number of page faults
• B. always increase the number of page faults
• C. sometimes increase the number of page faults
• D. never affect the number of page faults

Comments

Consider the following reference string:

1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 

Case-1: If the system has 3 frames, the given reference string on using FIFO page replacement algorithm yields a total of 9 page faults. The diagram below illustrates the pattern of the page faults occurring in the example.

Case-2: If the system has 4 frames, the given reference string on using FIFO page replacement algorithm yields a total of 10 page faults. The diagram below illustrates the pattern of the page faults occurring in the example.

It can be seen from the above example that on increasing the number of frames while using the FIFO page replacement algorithm, the number of page faults increased from 9 to 10.

 

Source : https://www.geeksforgeeks.org/beladys-anomaly-in-page-replacement-algorithms/

---

Belady’s anomaly : More physical memory doesn’t always mean fewer faults.

---

Source: Galvin 9th edition, chapter 9(9.4.2)

Answer 1

Answer is (C).

Belady anomaly is the name given to the phenomenon in which increasing the number of page frames results in an increase in the number of page faults for certain memory access patterns. This phenomenon is commonly experienced when using the First in First Out (FIFO) page replacement algorithm

Answer 2

ans is C.

Belady's anomaly.

Answer 3

Due to belady's anomaly, the Increase in number of frames does not always implies Less page faults in memory. It occurs in FIFO and FIFO Based replacement techniques which are Non stack based algorithms.

Ans is (C).

Other algorithms which shows belady's anomaly are :
1. Random Page replacement
2. Second chance LRU approximation when all of the Reference bits are 1.

Answer 4

Its belady's anamoly. Here by increasing the no of page frames we expect the page fault to decrease but it actually increases. this happens extensively in FIFO but not in optimal, lru, lfu etc.. Hope u all like this answer

Answer 5

As usual we know that increases of page frames  the page faults rate decreases but in FIFO suffers from belady anamoly , so sometimes it increases the page fault along the increases of the frames .