From owner-freebsd-hackers Thu Jan 30 19:47:36 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 7C2F037B401 for ; Thu, 30 Jan 2003 19:47:35 -0800 (PST) Received: from HAL9000.homeunix.com (12-233-57-224.client.attbi.com [12.233.57.224]) by mx1.FreeBSD.org (Postfix) with ESMTP id 0612F43F3F for ; Thu, 30 Jan 2003 19:47:35 -0800 (PST) (envelope-from dschultz@uclink.Berkeley.EDU) Received: from HAL9000.homeunix.com (localhost [127.0.0.1]) by HAL9000.homeunix.com (8.12.6/8.12.5) with ESMTP id h0V3lVNt011615; Thu, 30 Jan 2003 19:47:31 -0800 (PST) (envelope-from dschultz@uclink.Berkeley.EDU) Received: (from das@localhost) by HAL9000.homeunix.com (8.12.6/8.12.5/Submit) id h0V3lVi4011614; Thu, 30 Jan 2003 19:47:31 -0800 (PST) (envelope-from dschultz@uclink.Berkeley.EDU) Date: Thu, 30 Jan 2003 19:47:31 -0800 From: David Schultz To: Fergal Daly Cc: freebsd-hackers@FreeBSD.ORG Subject: Re: Random disk cache expiry Message-ID: <20030131034731.GB11445@HAL9000.homeunix.com> Mail-Followup-To: Fergal Daly , freebsd-hackers@FreeBSD.ORG References: <200301310127.38826.fergal@esatclear.ie> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <200301310127.38826.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 Thus spake Fergal Daly : > kientzle@acm.org (Tim Kientzle) wrote in message > news:... > > Personally, I think there's a lot of merit to _trying_ > > There's even more merit in only pretending to try... Welcome to my quotes file. > As you can see, the locking cache is always better than the random one and the > file doesn't have to be very big for it to be hugely better. 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. To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-hackers" in the body of the message