As title. When we want to request following page numbers 2,4,4,2,5,2,1,1,3,1, is clock replacement better? What are the advantages and disadvantages of them?


  • $\begingroup$ This would depend on the number of page frames there are. $\endgroup$ – Rick Decker Feb 26 '16 at 1:39
  • $\begingroup$ @Rick Decker Thanks for helping with that. If the buffer pool with 3 pages and the requests are above. What's the difference between them? $\endgroup$ – Echo0831 Feb 26 '16 at 3:13
  • 2
    $\begingroup$ What are your thoughts? What research have you done? We expect you to do a significant amount of research and self-study before asking, and to show us in the question what you've tried and what your thoughts are. $\endgroup$ – D.W. Feb 26 '16 at 3:34

Coincidentally, for your reference string, both LRU and CLOCK replacement strategies generate the same number of page faults, five if you count all frame loads, including the first three to initially fill the buffer. In addition, both algorithms generate page faults at the same times. Of course, this won't be the general situation. I assume you know how each works; if not let me know and I'll edit this answer.

Every operating system text I have on my shelf includes a discussion on the relative performance of various page replacement algorithms, so there's where you'll find more extensive comparisons than would fit here. Some empirical studies show that in general there's reason to assert that MIN (a.k.a OPTIMAL) generates the fewest page faults (in fact, MIN is provably optimal), followed by LRU, CLOCK, and FIFO, in that order. In terms of implementation, MIN is, of course, impossible, since it requires knowledge of the future$^*$, LRU is somewhat difficult to do, basic CLOCK is fairly easy (and can be improved with relatively little effort), and FIFO is easiest.

$^*$ If I had a time machine, I certainly wouldn't waste my time including it in the hardware to support MIN. I'd buy lottery tickets and/or play the stock market.

  • $\begingroup$ In some restricted cases the system is simple enough (and has periodic behaviour), and it is possible to "know" the future. $\endgroup$ – vonbrand Feb 27 '16 at 20:38

Please consider that operating system texts show examples with a few frames and a few dozen references, while my PC here has 8 GiB RAM, i.e., 2 million 4 KiB frames, and does millions of memory references a second. And that isn't a large machine by any stretch.

It can be proved that OPT is optimal. For performance of any other method, the only way to evaluate that is by using real reference strings, as real references show very different behaviours, and the behaviours are very hard to model accurately enough. The behaviour is irregular enough that exact mathematical analysis is out of the question.


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.