Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!henry
From: henry@utzoo.UUCP (Henry Spencer)
Newsgroups: comp.os.minix
Subject: Re: Disk Scheduling
Message-ID: <7740@utzoo.UUCP>
Date: Wed, 4-Mar-87 14:54:55 EST
Article-I.D.: utzoo.7740
Posted: Wed Mar  4 14:54:55 1987
Date-Received: Wed, 4-Mar-87 14:54:55 EST
References: <236@inuxf.UUCP> <108@illusion.UUCP>, <5004@mit-eddie.MIT.EDU>
Organization: U of Toronto Zoology
Lines: 24

> > Unix implements a so-called `elevator algorithm'...
>
> A disadvantage of this is that disk blocks in the middle of the disk
> end up being serviced twice as fast (frequently) as blocks at either
> edge.  An alternative here (again, sub-optimal globally in the
> interests of "equality") is to service all the requests while moving
> in one direction, and then sweep back to the first outstanding request
> and service outstanding requests in the same direction...

In fact, this algorithm -- the "one-way elevator" algorithm -- is the one
used by all modern variants of Unix that I'm familiar with.  I think V6 was
the last version that used a two-way elevator.  V7 used a one-way elevator
with the added complication of giving writes priority over reads (except
that the code as shipped had a bug that ended up reversing the priority,
which had various annoying effects under heavy load...).  The more recent
variants that I've looked at have all used simple one-way elevator.

(As a side note, I vaguely recall that Berkeley came up with a clever
justification for putting reads before writes, apparently never considering
that it might simply be a buggy implementation of a writes-before-reads
strategy.  I asked DMR, he confirmed that it was a bug.)
-- 
"We must choose: the stars or	Henry Spencer @ U of Toronto Zoology
the dust.  Which shall it be?"	{allegra,ihnp4,decvax,pyramid}!utzoo!henry