Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Path: utzoo!watmath!clyde!burl!ulysses!allegra!mit-eddie!think!harvard!seismo!ut-sally!pyramid!pesnta!epimass!jbuck From: jbuck@epimass.UUCP (Joe Buck) Newsgroups: net.unix-wizards Subject: Re: 4.2bsd kernel auto-nicing, scheduling Message-ID: <172@epimass.UUCP> Date: Fri, 7-Mar-86 23:35:53 EST Article-I.D.: epimass.172 Posted: Fri Mar 7 23:35:53 1986 Date-Received: Mon, 10-Mar-86 08:21:51 EST References: <1014@brl-smoke.ARPA> <856@inset.UUCP> <3311@sun.uucp> Reply-To: jbuck@epimass.UUCP (Joe Buck) Organization: Entropic Processing, Inc., Cupertino, CA Lines: 37 In article <3311@sun.uucp> guy@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