Messages in this thread | | | Date | Wed, 31 Mar 1999 23:59:13 +0200 (MEST) | From | Ricardo Galli Granada <> | Subject | Re: buffer cache behavior on memory-constrained systems (fwd) |
| |
> >also, i think the page LRU approach is a clever way to solve the buffer > >reclamation problem. do you know how close to optimal (in terms of > > Very happy to hear that ;). > > >keeping the most used buffers in memory, and expelling the least used > >ones) it is? > > It should be optimal according to my instinct, but I didn't do math on > it... > > Andrea Arcangeli
According to empirical results (I doubt there is any analytic demonstration) that you can find in any good OS book, LRU is the algorithm which is most closed the OPT algorithm (select the page wich will be used more far away in the future) for page replacement.
LRU is exactly the "opposite" to OPT, it reverts future to past. If you believes in programs' locality* (in space and time), you should believe in LRU. Problems arise with your understanding of "least". How do you measure it? (I am going to take a look to Andrea's code, I can learn a lot). Do you timestamp the last referece to every page? What's the resolution? Do you maintain an ordered list of pages according to their timestamp? If not, you may get closer to CLOCK, which is in fact a "second chance" FIFO.
Andrea, can you give some pointers to the kernel files where you play around this?
* I believe this is normally true for no bloating software written in C or Pascal, but I really doubt it's still true for a C++ program ;-)
-- Ricardo Galli
- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.rutgers.edu Please read the FAQ at http://www.tux.org/lkml/
| |