2
$\begingroup$

This may not make a difference in the end, but not knowing is driving me insane. When using the Optimal algorithm for page replacement, if you need to put something new into a frame and you have more than one frame that will not be used again, how does it prioritize which one to replace? In other words, if you have three frames and you enter in 1, 1, 2, 3, and neither 1 or 2 ever appears again, which one gets bumped when you try to put in 4?

Does it go by FIFO and kick out 1, does it go by most used and kick out 2 or does it go by least recently used and kick out 1?

$\endgroup$
2
  • $\begingroup$ Do you know 1 and 2 will never be used again? How do you obtain that knowledge? In general, there is no optimal page replacement algorithm because you want to drop those with the smallest probability of beeing used in the future, and in general, one cannot obtain knowledge about the future from looking at the past. $\endgroup$
    – Rainer P.
    Mar 6 '16 at 21:43
  • $\begingroup$ I know that the optimal algorithm is impossible in practice, but I'm referring to the theoretical optimal that's taught in class. So in this case, we're imagining that it is possible to know the future and what's coming. This is a purely what-if question $\endgroup$ Mar 6 '16 at 22:01
2
$\begingroup$

The optimal algorithm uses whatever is optimal (or one of the optimal possibilities, in case there are several), i.e. whatever produces the least page faults. There isn't necessarily any simpler description of its behavior, though there might be. In general, it depends on the problem; for this specific problem, I don't know whether a simple description exists, though there is probably a simple algorithm that finds an optimal sequence.

FIFO, most used and LRU are heuristics that are useful for the online version; it's not necessarily true that they can be used in any shape or form to obtain optimal page replacement sequences (but you might be able to describe rules for obtaining an optimal sequence using them; I just don't know).

$\endgroup$
2
$\begingroup$

Wikipedia says

'The Optimal Page Replacement Algorithm cannot be implemented in a general purpose operating system because it is impossible to compute reliably how long it will be before a page is going to be used, except when all software that will run on a system is either known beforehand and is amenable to static analysis of its memory reference patterns, or only a class of applications allowing run-time analysis. Despite this limitation, algorithms exist that can offer near-optimal performance — (i.e. less page faults).'

Hence, it is an ideal algorithm for page replacements and causes the least no. of page faults to occur. So, you should not be worried about which frame will be popped out if more than two frames are not used in near future because as you mentioned, it does not matter (since no. of page faults will remain the same no matter which one you pop out) and you cannot implement it in real life. Moreover, this algorithm can be used to compare the efficiency of other algorithms.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.