[Solved]: What's the difference between clock replacement & LRU replacement?

Problem Detail: 

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?

Thanks~

Asked By : Echo0831

Answered By : Rick Decker

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/53626

 Ask a Question

 Download Related Notes/Documents