Discussion
The optimal page replacement algorithm is
Answer: D
Correct answer: a theoretical benchmark that cannot be implemented in practice
The optimal algorithm, sometimes called OPT or MIN, evicts the page that will not be used for the longest time in the future. It provably yields the lowest possible page-fault rate. It cannot be implemented, because it requires knowledge of the future reference string. Its value is as a benchmark: a trace of a real program can be replayed afterwards, when the future is known, to establish the best achievable fault rate, and a practical algorithm is then judged by how close it comes. That comparison is how LRU earns its reputation. LRU is the mirror image of optimal, looking backwards where optimal looks forwards, and on programs with good locality the past predicts the future well enough that it performs within a small margin. It is also a stack algorithm and so immune to Belady’s anomaly. FIFO, by contrast, is simple but performs poorly and can exhibit that anomaly - which is why real systems use clock or second-chance approximations of LRU instead.
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development