4.2bsd kernel auto-nicing, scheduling

[Joe Buck]

In article <3311 at sun.uucp> guy at sun.uucp (Guy Harris) writes:
>> Some fairly viable work has been done on SHARE scheduling on UNIX
>> in Australia.  You should check it out.  It actually uses some
>> algorithms, and was even designed.
>what do you mean by "algorithms" here?  Over here, we tend to think
>"algorithm" as meaning any procedure of the sort executed by a computer,
>whether it's well thought-out or specified or not.  You may think of
>auto-nicing as a hack (I certainly do), but by my definition the procedure
>that implements it certainly qualifies as an algorithm....

I don't believe it!  I, a mere mortal, get to correct Guy Harris :-).
Though you frequently see the word "algorithm" associated with schedulers,
they are not because they don't terminate (at least they aren't supposed
to).  Knuth (who is "over here") lists the following properties of algorithms:

Finiteness: 	always terminates in a finite number of steps
Definiteness:	each step is precisely defined
Input:		zero or more inputs
Output:		one or more outputs
Effectiveness:	"... all of the operations to be performed ... can in
		 principle be done exactly and in a finite length of
		 time ... using pencil and paper"

Knuth uses the term "computational method" to describe things that lack
finiteness.

Other writers besides Knuth also give finiteness as a criterion.  No one
seems to require that the algorithm be particularly efficient or
well-designed.  But I'd go along with the original writer (I don't know
who he was) up to a point: OSes that have been hacked until they work,
sort of, may lack definiteness.  Sure, there is a definite sequence of
instructions being executed, but who knows what it is.

Of course, the function that decides the next process to be executed at
a given time is (I hope!) an algorithm.
-- 
- Joe Buck <ihnp4!pesnta!epimass!jbuck>