GATE CSE 2009 | Question: 9, ISRO2016-52

Question

In which one of the following page replacement policies, Belady's anomaly may occur?

• A. FIFO
• B. Optimal
• C. LRU
• D. MRU

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/

---

A.FIFO : Bélády’s anomaly is the name given to the phenomenon where increasing the number of page frames results in an increase in the number of page faults for a given memory access pattern.

Answer 1

Answer : A) FIFO

How/Why?
Page Replacement algorithms suffer from Belady’s anamoly if :

• They do not follow the stack based algorithm.

Reference :-

• https://stackoverflow.com/questions/5263988/why-lru-doesnt-suffer-beladys-anomaly
• https://stackoverflow.com/questions/31801098/how-can-beladys-anamoly-be-avoided

Since MRU, LRU & Optimal Replacement Algo follow Stack Algo, hence they are not affected by Belady's Anamoly.

Comments

Reference:- Galvin, chapter 9, Question 9.4 of Exercise Solutions (https://codex.cs.yale.edu/avi/os-book/OS9/practice-exer-dir/9-web.pdf).

---

Is this correct ?

Second chance behaves like FIFO when all the reference bits are 1 during current epoch.

Answer 2

It is (A).

http://en.wikipedia.org/wiki/B%C3%A9l%C3%A1dy%27s_anomaly

Answer 3

In computer storage, Bélády's anomaly is 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.

So, ans is (A)FIFO

Answer 4

 GOAL:

We’ll use the same page reference string with 3 frames and then 4 frames, and show that more frames cause more page faults — this is Belady’s Anomaly.

---

 Page Reference String:

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

---

Case 1: Using 3 Frames with FIFO

Step	Reference	Frame State	Page Fault?
1	1	1 _ _	Yes
2	2	1 2 _	Yes
3	3	1 2 3	Yes
4	4	2 3 4	Yes
5	1	3 4 1	Yes
6	2	4 1 2	Yes
7	5	1 2 5	Yes
8	1	1 2 5	No
9	2	1 2 5	No
10	3	2 5 3	Yes
11	4	5 3 4	Yes
12	5	3 4 5	Yes

 Total Page Faults = 9

---

Case 2: Using 4 Frames with FIFO

Step	Reference	Frame State	Page Fault?
1	1	1 _ _ _	Yes
2	2	1 2 _ _	Yes
3	3	1 2 3 _	Yes
4	4	1 2 3 4	Yes
5	1	1 2 3 4	No
6	2	1 2 3 4	No
7	5	2 3 4 5	Yes
8	1	3 4 5 1	Yes
9	2	4 5 1 2	Yes
10	3	5 1 2 3	Yes
11	4	1 2 3 4	Yes
12	5	2 3 4 5	Yes

Total Page Faults = 10

---

Conclusion:

• 3 frames → 9 page faults

• 4 frames → 10 page faults ❗

So, we increased memory but got more page faults — this is Belady’s Anamoly

Answer 5

Option:( A) FIFO

Belady's anomaly is the problem which occur when we increase the frame size and still the page fault increases

Answer 6

Quite a simple question.

Answer is option A