search
Log In
16 votes
4k views

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

  1. FIFO
  2. Optimal
  3. LRU
  4. MRU
in Operating System
edited by
4k views
0

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/

4 Answers

17 votes
 
Best answer

edited by
6 votes

In computer storageBé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 (FIFOpage replacement algorithm.

So, ans is (A)FIFO

4 votes
 Answer : A) FIFO

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

  • They do not follow the stack based algorithm.

Reference :-

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


edited by
0 votes
Option:( A) FIFO

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

Related questions

77 votes
16 answers
1
22.1k views
Frames of $\text{1000 bits}$ are sent over a $10^6$ $\text{bps}$ duplex link between two hosts. The propagation time is $\text{25 ms}$. Frames are to be transmitted into this link to maximally pack them in transit (within the link). What is the minimum number of bits ... numbers distinctly? Assume that no time gap needs to be given between transmission of two frames. $I=2$ $I=3$ $I=4$ $I=5$
asked Sep 22, 2014 in Computer Networks Kathleen 22.1k views
20 votes
8 answers
2
5.9k views
$S \to aSa \mid bSb\mid a\mid b$ The language generated by the above grammar over the alphabet $\{a,b\}$ is the set of: all palindromes all odd length palindromes strings that begin and end with the same symbol all even length palindromes
asked Sep 22, 2014 in Theory of Computation Kathleen 5.9k views
5 votes
4 answers
3
5.1k views
Determine the number of page faults when references to pages occur in the following order: 1, 2, 4, 5, 2, 1, 2, 4 Assume that the main memory can accommodate 3 pages and the main memory already has the pages 1 and 2, with page one having brought earlier than page 2. (LRU page replacement algorithm is used) 3 5 4 None of these
asked Jul 5, 2016 in Operating System habedo007 5.1k views
29 votes
3 answers
4
4.2k views
A hard disk has $63$ sectors per track, $10$ platters each with $2$ recording surfaces and $1000$ cylinders. The address of a sector is given as a triple $\langle c, h, s \rangle$, where $c$ is the cylinder number, $h$ is the surface number and $s$ is the sector number. Thus, the ... is $\langle 0, 15, 31 \rangle$ $\langle 0, 16, 30 \rangle$ $\langle 0, 16, 31 \rangle$ $\langle 0, 17, 31 \rangle$
asked Apr 23, 2016 in Operating System jothee 4.2k views
...