From owner-freebsd-current  Thu Sep 17 02:05:56 1998
Return-Path: <owner-freebsd-current@FreeBSD.ORG>
Received: (from majordom@localhost)
          by hub.freebsd.org (8.8.8/8.8.8) id CAA28570
          for freebsd-current-outgoing; Thu, 17 Sep 1998 02:05:56 -0700 (PDT)
          (envelope-from owner-freebsd-current@FreeBSD.ORG)
Received: from math.berkeley.edu (math.Berkeley.EDU [128.32.183.94])
          by hub.freebsd.org (8.8.8/8.8.8) with ESMTP id CAA28548
          for <freebsd-current@FreeBSD.ORG>; Thu, 17 Sep 1998 02:05:45 -0700 (PDT)
          (envelope-from dan@math.berkeley.edu)
Received: (from dan@localhost)
	by math.berkeley.edu (8.8.7/8.8.7) id CAA27537;
	Thu, 17 Sep 1998 02:05:23 -0700 (PDT)
Date: Thu, 17 Sep 1998 02:05:23 -0700 (PDT)
From: dan@math.berkeley.edu (Dan Strick)
Message-Id: <199809170905.CAA27537@math.berkeley.edu>
To: freebsd-current@FreeBSD.ORG
Subject: Re: Download of FreeBSD 3.0-SNAP
Cc: dan@math.berkeley.edu
Sender: owner-freebsd-current@FreeBSD.ORG
Precedence: bulk
X-Loop: FreeBSD.ORG

> > I've seen assorted drive literature describing different caching 
> > policies on modern drives, and I think it's probably in our interest 
> > not to try too hard to outsmart the disk these days, as it's busy 
> > trying to outsmart us. 
> > 
> > If you really wanted to play games with the queue sorter, you might 
> > want to go for a minimal distance insertion policy rather than a strict 
> > ladder sort.  As Kirk pointed out, there's plenty of room for 
> > experimentation in this field. 8)
> 
> you can easily starve processes far from the insertion point using an
> algorithm like that, in fact you can almost DOS a machine unless some sort
> of quantum is invlolved to compromise locallity over time elapsed since a 
> read/write has been queued.

For all of these reasons, I favor a simple insertion sort by block
number using two lists of buffers not yet converted into I/O commands,
a "current" list and a "next" list.  A new buffer is inserted into the
"current" list provided that:

 1) The new buffer block number exceeds the first block number in the
    "current" list minus some small quantity (e.g. our best guess at the
    drive's cylinder size) intended to capture on average blocks in the
    current cylinder, and

 2) The number of buffers inserted into the "current" list since the
    "next" list last become nonempty has not exceeded some small
    number (e.g. 20) intended to encourage "fairness".

Otherwise the new buffer goes into the "next" list.  The goal of this
strategy is a simple compromise between the desires to maximize
throughput and to minimize maximum response time.

One other thing: hardware and circumstances permitting (I don't know
about typical PC DMA capabilities), similar I/O requests for
contiguous disk addresses should be coalesced.  This can be a
gigantic win.

I submit these ideas for consideration the next time someone decides
to overhaul the optimization code.

Dan Strick
dan@math.berkeley.edu

To Unsubscribe: send mail to majordomo@FreeBSD.org
with "unsubscribe freebsd-current" in the body of the message