Which of the following page replacement algorithms can exhibit Belady’s Anomaly ?
First-In, First-Out (FIFO)
Belady's Anomaly is the counter-intuitive situation in which giving a process more page frames actually produces more page faults. It appears only in FIFO page replacement.
The reason lies in what FIFO uses to choose a victim. FIFO evicts whichever page arrived earliest, which has nothing to do with whether that page is about to be needed again. Because the set of pages FIFO keeps with three frames is not guaranteed to be a subset of what it keeps with four, adding a frame can change the eviction order for the worse. The classic reference string 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 gives nine faults with three frames but ten with four.
The other algorithms are immune because they are stack algorithms: the pages held with \(n\) frames are always a subset of those held with \(n+1\) frames, so faults can never increase when frames are added. LRU chooses by least recent use, MRU by most recent use, and OPT by the furthest future reference.
Hence, the answer is First-In, First-Out (FIFO).
Important Questions from Operating Systems
A collection of software that manages computer hardware resources and provides common services for computer programs is
In the context of computers, what is Ubuntu?
- The smallest unit of memory in a computer is
Match the columns.
List-I
List-II
(a)
Linux user interface
i.
Row of buttons, often near the top of an application window that control software functions
(b)
Word processing
softwareii.
GNOME
(c)
Icon
iii.
MS-Word
(d)
Toolbar
iv.
Small graphical representation of a
program, features or fileInner most layer of operating system which is always present in main memory is known as ______.
