Question

    Which of the following page replacement algorithms results in the lowest page-fault rate for a given reference string but is often impractical to implement in a real-world system? 

    A FIFO (First In First Out) Correct Answer Incorrect Answer
    B LRU (Least Recently Used) Correct Answer Incorrect Answer
    C Optimal Page Replacement Correct Answer Incorrect Answer
    D Second-Chance Algorithm Correct Answer Incorrect Answer
    E Clock Algorithm Correct Answer Incorrect Answer

    Solution

    The Optimal Page Replacement algorithm replaces the page that will not be used for the longest period in the future. It guarantees the lowest page-fault rate for any reference string because it makes perfect decisions based on future knowledge. However, it is impractical to implement in real-world systems because predicting the future sequence of page accesses is impossible. Despite this limitation, the Optimal algorithm serves as a benchmark against which other, more practical algorithms (such as LRU and FIFO) are measured. Why Other Options are Incorrect: A) FIFO: FIFO is easy to implement but often results in more page faults due to its simplistic approach of replacing the oldest page. B) LRU: LRU approximates Optimal in many cases by replacing the least recently used page but is not always perfect. D) Second-Chance Algorithm: This is a variant of FIFO that provides a "second chance" to pages with a reference bit set, but it is less efficient than LRU or Optimal. E) Clock Algorithm: A variation of the Second-Chance Algorithm that is more efficient but still not as good as the Optimal algorithm.

    Practice Next

    Relevant for Exams: