Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!water!watnot!watmath!clyde!cbatt!ihnp4!illusion!marcus
From: marcus@illusion.UUCP
Newsgroups: comp.os.minix
Subject: Re: Disk Scheduling (& note to Dr T.)
Message-ID: <108@illusion.UUCP>
Date: Mon, 2-Mar-87 00:14:51 EST
Article-I.D.: illusion.108
Posted: Mon Mar  2 00:14:51 1987
Date-Received: Tue, 3-Mar-87 00:16:17 EST
References: <236@inuxf.UUCP>
Reply-To: marcus@illusion.UUCP (Marcus Hall)
Organization: Magic Numbers Software, Bloomingdale, IL
Lines: 37

In article <236@inuxf.UUCP> matt@inuxf.UUCP (Matt Verner) writes:
>I am planning on adding true disk scheduling to MINIX as part of an over-all
>study of operating system efficiencies.  The existing method in MINIX is a 
>First-come-first-served pipeline with no disk i/o queue.  I would like to
>through out a straw man proposal for a method so that the alert among you
>folks can poke holes, make suggestions, etc.
...
>	2) Create a new procedure, say floppy_sched(), that examines the
>queued requestes for the shortest seek time request and issues a do_rdwt()
>for that request.
>	3) floppy_sched() then will prepare a return message for the proper
>process and send() a reply to that process.
>	4) floppy_sched() re-examines the queue and the process continues.

I would think that there is a potential performance problem here.  If two
processes are making requests for blocks at the same end of the disk and 
another is requesting blocks at the other end, the scheduler will service one
process then find the other process at the same end and work on it.  In the
meantime, the process that was just serviced requests the next block which
will be serviced next, etc.

The upshot of this is that the process that had requested a block at the
distant end of the disk will not be serviced until the processes that are
requesting `closer' blocks stop making requests.  This does optimize total
system throughput, but it puts a significant penalty on the one process
that had the misfortune to want a block that was too far from where the
head was currently working.

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.

marcus hall
..!ihnp4!illusion!marcus