From owner-freebsd-hackers Mon Feb 3 15:56:46 2003 Delivered-To: freebsd-hackers@freebsd.org Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id 12A1837B405 for ; Mon, 3 Feb 2003 15:56:44 -0800 (PST) Received: from wonka.esatclear.ie (wonka.esatclear.ie [194.145.128.5]) by mx1.FreeBSD.org (Postfix) with ESMTP id B8F6143E4A for ; Mon, 3 Feb 2003 15:56:42 -0800 (PST) (envelope-from fergal@esatclear.ie) Received: from whizzo.loc (x-airlock036.esatclear.ie [213.202.164.36]) by wonka.esatclear.ie (8.9.3/8.9.3) with ESMTP id XAA12536; Mon, 3 Feb 2003 23:56:26 GMT Content-Type: text/plain; charset="iso-8859-1" From: Fergal Daly To: David Schultz Subject: Re: Random disk cache expiry Date: Mon, 3 Feb 2003 23:58:24 +0000 User-Agent: KMail/1.4.3 Cc: freebsd-hackers@FreeBSD.ORG References: <200301310127.38826.fergal@esatclear.ie> <20030131034731.GB11445@HAL9000.homeunix.com> In-Reply-To: <20030131034731.GB11445@HAL9000.homeunix.com> MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Message-Id: <200302032358.24268.fergal@esatclear.ie> Sender: owner-freebsd-hackers@FreeBSD.ORG Precedence: bulk List-ID: List-Archive: (Web Archive) List-Help: (List Instructions) List-Subscribe: List-Unsubscribe: X-Loop: FreeBSD.ORG 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