Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!water!watnot!watmath!clyde!cbatt!ihnp4!ptsfa!lll-lcc!seismo!ut-sally!husc6!bacchus!mit-eddie!jbs
From: jbs@mit-eddie.UUCP
Newsgroups: comp.os.minix
Subject: Re: Disk Scheduling (& note to Dr T.)
Message-ID: <5004@mit-eddie.MIT.EDU>
Date: Mon, 2-Mar-87 02:34:25 EST
Article-I.D.: mit-eddi.5004
Posted: Mon Mar  2 02:34:25 1987
Date-Received: Tue, 3-Mar-87 19:53:25 EST
References: <236@inuxf.UUCP> <108@illusion.UUCP>
Reply-To: jbs@eddie.MIT.EDU (Jeff Siegal)
Organization: MIT, EE/CS Computer Facilities, Cambridge, MA
Lines: 24

In article <108@illusion.UUCP> marcus@illusion.UUCP (Marcus Hall) writes:
>Unix implements a so-called `elevator algorithm' which attempts to order
>requests so that the closest block IN THE CURRENT MOVEMENT DIRECTION is
>serviced next, if there are none, then the direction is reversed.  This
>tends to sweep the head across the disk more than is absolutely necessary,
>and so it is sub-optimal in a global sense, but it does insure that all
>requests will be serviced without undue delay.

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.  The
usefulness of this depends on the seek time of the device as compared
to the amount of time spent waiting in the I/O queue.

Another alternative is a "fairness" count.  This is the maximum number
of requests allowed to be processed after a given request is received,
but before that request is serviced.  You then use minimal head
movement to select requests until the fairness count is expired, then
thatrequest is serviced regardless of head position.

Jeff Siegal