0
$\begingroup$

I'm going through 'Operating Concepts' by Silberschatz, Galvin and Gagne (The Dinosaur Book) and it mentions the Second-Chance Algorithm (not enhanced) as an improvement on the FIFO replacement algorithm.

My question is, is there ever a case where this algorithm would perform better than, say, the Least Recently Used algorithm or even something like the Farthest-in-Future Algorithm? The book describes how the algorithm works but doesn't offer a lot of information on when it would be useful, other than just in improving 'FIFO'.

To add to this, is there ever a case where 'second chance' would out preform LRU? I'm assuming the answer is yes, as no algorithm is perfect for every situation.

Improve this question
$\endgroup$
2
  • $\begingroup$ (What does the book state about Farthest-in-Future?) Try to construct examples where one algorithm performs better than the other. If you don't succeed, present how far you got and where/why/how you see yourself stuck. $\endgroup$
    – greybeard
    Commented May 2, 2020 at 18:35
  • $\begingroup$ That's partially what brought up the question. I've been running comparisons on SCR and LRU and haven't been able to find a case where SCR preforms better but have found many where FIFO outperforms LRU, even though SCR is an optimization of FIFO. $\endgroup$
    – selfstudy777
    Commented May 2, 2020 at 19:34

1 Answer 1

Reset to default
3
$\begingroup$

Farthest-in-future is optimal, second chance can't be better. Second chance is a way to approximate LRU when the required hardware (access times, sort them) isn't available. Both try to approximate the optimal strategy, there certainly can be cases where one or the other is better.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ Technically, farthest-in-future is only optimal if the cost of miss is constant. Disk storage favors spatial locality in the disk (two reads close in time to the same cylinder will typically be faster). Hybrid storage (flash+disk) gives two extremely different latencies and throughputs. Prefetchable access patterns cost less than unpredictable random accesses. The ability to overlap latencies effects the impact of a 'page miss' just as memory level parallelism effects the impact of a cache miss. Such is probably outside the scope of the question. $\endgroup$
    – user4577
    Commented May 2, 2020 at 17:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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