On Friday 31 January 2003 03:47, David Schultz wrote: > You have found an optimal replacement algorithm for the case of > repeated sequential reads. In fact, if you know in advance what > the access pattern is going to be, it is *always* possible to find > an optimal replacement algorithm. Specifically, you always > replace the block in the cache that will not be used for the > longest time in the future. > > If you want the system to always cache the right thing in the > general case, the only hint you would need to provide the system > is a reference string specifying the predicted access pattern. > (If I were to do this, my first reaction would be to encode it as > an FSA.) If that proves to be infeasible, I'm sure there are ways > to approximate the same thing. The hard parts, I think, would be > teaching the VM system to use the new information, and gathering > statistics from which you form your hints.
I wouldn't even begin to try and deduce the access pattern from statistics, that sounds hard. In many cases, the application knows in advance what the access pattern will be. I think someone else in the thread has suggested having hints attached to the file as one option and I think the app itself should be able to signal it's intention to repeatedly read the file. I think trying to encode generalised access patterns is maybe not such a win. You could end up using a lot of memory storing the access pattern and a lot of effort encoding things as FSAs. Also the FSA has to be able to pick not just the block that won't be used for the longest time but it also has to pick a block that is actually in memory and for a more general access pattern this is not necessarily easy. Coping with reading a file straight through, several times is relatively common and can be encoded very easily and without much memory and assuming the file is not being accessed non-sequentially by another process, then picking the correct block is easy. Anyway, it's all academic for me really as I don't even run BSD and although I can write it when I have to, I don't find C anywhere near as much fun as Perl. I just thought it was an interesting question. I should probably go and get my coat now ;-) F To Unsubscribe: send mail to [EMAIL PROTECTED] with "unsubscribe freebsd-hackers" in the body of the message
