From mboxrd@z Thu Jan 1 00:00:00 1970 From: Werner Almesberger Subject: Re: barriers vs. reads Date: Thu, 24 Jun 2004 09:16:53 -0300 Sender: linux-fsdevel-owner@vger.kernel.org Message-ID: <20040624091653.S1325@almesberger.net> References: <20040623214845.A21586@almesberger.net> <20040624003944.B21586@almesberger.net> <20040624080008.GA22997@MAIL.13thfloor.at> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Return-path: Received: from almesberger.net ([63.105.73.238]:22276 "EHLO host.almesberger.net") by vger.kernel.org with ESMTP id S264002AbUFXMRD (ORCPT ); Thu, 24 Jun 2004 08:17:03 -0400 Received: from almesberger.net (vpnwa-home [10.200.0.2]) by host.almesberger.net (8.11.6/8.9.3) with ESMTP id i5OCGw416788 for ; Thu, 24 Jun 2004 05:16:58 -0700 Received: (from werner@localhost) by almesberger.net (8.11.6/8.11.6) id i5OCGrZ24693 for linux-fsdevel@vger.kernel.org; Thu, 24 Jun 2004 09:16:53 -0300 To: linux-fsdevel@vger.kernel.org Content-Disposition: inline In-Reply-To: <20040624080008.GA22997@MAIL.13thfloor.at>; from herbert@13thfloor.at on Thu, Jun 24, 2004 at 10:00:08AM +0200 List-Id: linux-fsdevel.vger.kernel.org Herbert Poetzl wrote: > by verifying those eight cases for correctness, you > can conclude, that the sum of N such cases will give > the correct number of overlaps (with a given test > range); verification itself is simple: Thanks (very nice drawings, btw.) ! Yes, now that I see it written down, I also see how we can generalize that to a proof for any number of (a,b) ranges. Cool ! So this means that we have a solution to detect overlaps that shouldn't be significantly slower than, say tree+hash as used in the anticipatory scheduler. One problem is that this approach doesn't tell us where the overlapping requests are, only that there are somewhere out there. Thanks, - Werner -- _________________________________________________________________________ / Werner Almesberger, Buenos Aires, Argentina wa@almesberger.net / /_http://www.almesberger.net/____________________________________________/