Date: Mon, 3 Feb 2003 23:58:24 +0000 From: Fergal Daly <fergal@esatclear.ie> To: David Schultz <dschultz@uclink.Berkeley.EDU> Cc: freebsd-hackers@FreeBSD.ORG Subject: Re: Random disk cache expiry Message-ID: <200302032358.24268.fergal@esatclear.ie> In-Reply-To: <20030131034731.GB11445@HAL9000.homeunix.com> References: <200301310127.38826.fergal@esatclear.ie> <20030131034731.GB11445@HAL9000.homeunix.com>
next in thread | previous in thread | raw e-mail | index | archive | help
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 statistic= s,=20 that sounds hard. In many cases, the application knows in advance what th= e=20 access pattern will be. I think someone else in the thread has suggested=20 having hints attached to the file as one option and I think the app itsel= f=20 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.=20 You could end up using a lot of memory storing the access pattern and a l= ot=20 of effort encoding things as FSAs. Also the FSA has to be able to pick no= t=20 just the block that won't be used for the longest time but it also has to= =20 pick a block that is actually in memory and for a more general access pat= tern=20 this is not necessarily easy. Coping with reading a file straight through, several times is relatively=20 common and can be encoded very easily and without much memory and assumin= g=20 the file is not being accessed non-sequentially by another process, then=20 picking the correct block is easy. Anyway, it's all academic for me really as I don't even run BSD and altho= ugh I=20 can write it when I have to, I don't find C anywhere near as much fun as=20 Perl. I just thought it was an interesting question. I should probably go= and=20 get my coat now ;-) F To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-hackers" in the body of the message
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?200302032358.24268.fergal>