[ On Sunday, December 8, 2002 at 20:57:06 (-0500), Roland Dowdeswell wrote: ]
> Subject: Re: CVS commit: syssrc/sys/kern 
>
> Now a long time ago I was thinking that it would be interesting
> for processes to be scheduled on a user by user basis.  This would
> also (although that was not the motivation at the time) take care
> of a user-level forkbomb.

Yes, under the standard UNIX scheduler, a single user can acquire a
large share of the system resources simply by running many processes.  A
fair share scheduler uses the recent history of CPU consumption by each
user or group of users to adjust process priorities.  As a result it can
restrict certain user or groups of users to specified percentages of
system resources when any competing users or groups are also demanding
those same resources.  Thus when competition for CPU usage is great a
fair share scheduler limits the number of CPU cycles that any one user
or group of users may consume.  Of course a good fair share scheduler
has the option of never preventing any process from running when there
are idle CPU cycles, regardless of the owner's allocation.

>  Charles Hannum suggested a multi-level
> scheduler to me in reference to this discussion, and there is prior
> art as a patch by Rik van Riel to the Linux kernel that does
> this[3,4].  There is another implementation of a multi-level
> scheduler for linux on sourceforge[5].

Don't forget the first such fair share scheduler for UNIX (that I know
of, and apparently that the author knew of at the time of publication
too):

   G. J. Henry, "The Fair Share Scheduler", AT&T Bell Laboratories
   Technical Journal, Vol.63 No.8, pp. 1845-1858, Oct. 1984.  (also
   appears in UNIX System Readings and Applications Volume II, Prentice
   Hall, 1987, ISBN 0-12-939845-7, which is a full reprint of BSTJ
   Vol.63 No.8)

Also somewhat related, especially in context of multi-user student
systems where fork-bombs might be quite common:

	http://www.cs.usyd.edu.au/~piers/papers/Share/share.html

and of course there's the present state of the art in a widly used
commercial system:

	http://docs.sun.com/db/doc/816-0222/6m6nmlsug?a=view

> Please note that this email is just a few minutes of looking around
> on google and isn't actually a proper search for prior art.  There
> is a lot of information in the literature about schedulers and
> whatnot and if we are going to look into any of these strategies
> we should read it and determine what the best strategy is.

Yes the literature is literally littered with timesharing system
scheduler discussion!

-- 
								Greg A. Woods

+1 416 218-0098;            <g.a.woods@ieee.org>;           <woods@robohack.ca>
Planix, Inc. <woods@planix.com>; VE3TCP; Secrets of the Weird <woods@weird.com>