From owner-freebsd-questions  Sun Jun  9 05:50:54 1996
Return-Path: owner-questions
Received: (from root@localhost)
          by freefall.freebsd.org (8.7.5/8.7.3) id FAA03551
          for questions-outgoing; Sun, 9 Jun 1996 05:50:54 -0700 (PDT)
Received: (from jmb@localhost)
          by freefall.freebsd.org (8.7.5/8.7.3) id FAA03535;
          Sun, 9 Jun 1996 05:50:53 -0700 (PDT)
From: "Jonathan M. Bresler" <jmb>
Message-Id: <199606091250.FAA03535@freefall.freebsd.org>
Subject: Re: Design & Implementation of 4.4BSD
To: jbarrm@panix.com (Barry Masterson)
Date: Sun, 9 Jun 1996 05:50:52 -0700 (PDT)
Cc: questions@freebsd.org
In-Reply-To: <Pine.BSF.3.91.960609083447.2892A-100000@jbarrm.dialup.access.net> from "Barry Masterson" at Jun 9, 96 08:36:19 am
X-Mailer: ELM [version 2.4 PL24]
Content-Type: text
Sender: owner-questions@freebsd.org
X-Loop: FreeBSD.org
Precedence: bulk

Barry Masterson wrote:
> 
> Hi,
> 
> I'm working my way thru the recently released book entitled
> "The Design and Implementation of the 4.4BSD Operating System",
> and have come across some algorithm code samples on pages 199 & 203:
> 
> disksort(dq, bp)
>     drive queue *dq;
>     buffer *bp;
> {
>     if (drive queue is empty) {
>         place the buffer at the front of the drive queue;
>         return;
>     }
>     if (request lies before the first active request) {
>         locate the beginning of the second request list;
>         sort bp into the second request list;
>     } else
>         sort bp into the current request list;
> }
> 
> I'm familiar with the basics of c/c++, perl, shell scripts, but this
> use of "the", "of", "into", "at" is something I've yet to see. It
> seems a little too human readable to be real code.
> 
> What language is this?  Are there other examples of this type of
> programming in the FreeBSD source code?

	its called "psuedo-code".  rather then present the actual source
	the authors are presenting the algorithm stripped of the details
	of data structures and pointer (etc....) that obscure the purpose
	of the code.  rather liek the difference between the blueprints
	and the building itself.

	the purpose of the code is to sort disk accesses by the position of
	the data on disk so that the heads walk the disk from edge to edge
	doing every I/O possible on each pass.  without this the heads 
	would shuttle from cylinder to cylinder in a rather random pattern.
	seeks are the longest component of disk access time.  the code
	minimizes seeks.

	the real code for ufs is in: /sys/ufs/ufs/ufs_disksubr.c:disksort()

	the comments matche the pseudo-code well.  take a look :)

jmb

ps.	this is one of the joys of FreeBSD--getting to see the real
	code
--
Jonathan M. Bresler           FreeBSD Postmaster             jmb@FreeBSD.ORG
FreeBSD--4.4BSD Unix for PC clones, source included. http://www.freebsd.org/