[lkml]   [2000]   [Sep]   [17]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
SubjectRe: An elevator algorithm (patch)

On Sun, 17 Sep 2000, Rik van Riel wrote:

> On 17 Sep 2000, Peter Osterlund wrote:
> > Andrea Arcangeli <> writes:
> >
> > > While the queue is plugged or with things like SCSI your logic
> > > change won't work because in such case if your request is lower the
> > > lowest in the queue, you can put it at the head of the queue and you
> > > have no way to know where your "tmp1" was placed so you can't make
> > > any assumption (that's why the current code makes sense).
> >
> > I still don't think the current code makes sense.
> [snip examples]
> Indeed, it's obvious that your code will give better
> results (and it's more readable too). I like it...
> > The new patch is also not unfair to requests near the end of the
> > disk. The current kernel code can starve those requests a very
> > long time if the request queue never becomes empty.
> This is a very very big problem, which definately needs
> to be addressed ASAP. I've witnessed this starvation happen
> a couple of times and it's a really big problem...
> > The only disadvantage I can see is that the new patch doesn't
> > handle consecutive insertions in O(1) time, but then again, the
> > pre-latency elevator code didn't do that either. Is this really
> > important? How long can the request queue be? Apparently we gain
> > more by avoiding disk seeks than we lose by wasting some CPU
> > cycles during request insertion.
> Well DUH. ;)
> A disk seek takes ~10 milliseconds on a modern drive,
> that's about an /eternity/ as far as the CPU is concerned.

This was under MS/DOS 10 years ago probably.

Nowadays you can connect 30 disks of about 4 ms average seek time to a
single Ultra 160 2 channels 64 bit 66MHz PCI controller. With appropriate
benchmarks that gain advantage of disk prefetching, you can easily observe
30,000 short IOs per seconds and even more (15000 per channel). This
happens using no more than 3 disks per BUS.

For real work, with disks actually seeking, such an possible system should
probably be capable of performing more than 6000 IOs per seconds (That's
theory from me, since I never saw such a system :-) ).
This gives some margin for wasting CPU cycles but far less than you seem
to assume, in my opinion.

> Anyone who thinks saving on CPU time is worth it for
> something as critical to disk seeks as the elevator code
> should be locked up inside a microVAX ;)

Not wasting uselessly CPU cycles is still worth it, in my opinion.


To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to
Please read the FAQ at

 \ /
  Last update: 2005-03-22 12:38    [W:0.083 / U:0.664 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site