Date: Thu, 17 Sep 1998 02:05:23 -0700 (PDT) From: dan@math.berkeley.edu (Dan Strick) To: freebsd-current@FreeBSD.ORG Cc: dan@math.berkeley.edu Subject: Re: Download of FreeBSD 3.0-SNAP Message-ID: <199809170905.CAA27537@math.berkeley.edu>
next in thread | raw e-mail | index | archive | help
> > 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
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?199809170905.CAA27537>