memory-managementpagingpage-replacement

What breaks a tie in Optimal Page Replacement?


Assume we have 3 frames for a process with values (1,7,0). Now assume that the remaining references in the string reference for that process are : 4,6,7. For the reference 4 , a page fault will occur and only 7 is present in the future , so which frame should be replaced here , 1 or 0 ? Do I apply FIFO to break this tie or I can select any of them to replace ?


Solution

  • Optimal means you have all future information, so if two pages were truly never to be used again you could pick either and be fine. However if you wanted to do an LRU or FIFO to break the tie, it would be fine (i.e. wouldn't matter).

    What would be interesting is thinking about optimal applied globally and not just to a single process. If we assume other processes might touch 1 or 0 later, that could be part of the future information used to make the optimal choice. Optimal decision-making would also become more complicated if multiple cpus are touching memory concurrently as well.