4.2bsd kernel auto-nicing, scheduling

[Guy Harris]

> Priority boosts are given for socket input, terminal input (specific to
> mode)...

Unfortunately, the terminal mode doesn't tell you as much as you might
think.  The distinction between screen editors and programs like "more" is
*not* that the former run in RAW mode and the latter run in CBREAK mode. The
bulk of "full-screen" programs run in CBREAK mode on systems running
V7-descended terminal drivers; there is no way to distinguish between "vi"
and "more" simply on the basis of the mode it puts the terminal into.
(EMACS may put the terminal into RAW mode, but that's because it was the
only way to get an 8-bit data path to use with terminals with META keys that
turn the 8th bit on.  If it merely wanted to disable XON/XOFF flow control,
it could have set the start and stop characters to '\377'.)  It would also
be interesting to see what effect treating programs running in RAW mode as
screen editors would have on programs like "uucico" (which are the sort of
programs RAW mode was intended for - programs which want a raw 8-bit data
path for data transfer, not screen editors).

Furthermore, the System V driver has a cleaner "ioctl" interface; you don't
have all-inclusive mode bits like RAW and CBREAK, you have particular
processing operations which you turn on and off.  It's not clear how you'd
distinguish between RAW and CBREAK mode in this context.  (The scheduler
work in that paper is not just of interest to 4.[23]BSD users; all UNIX
variants since V7 use similar schedulers with similar deficiencies.)

It would be better to attempt to come up with a classification of processes
as "extremely interactive", "very interactive", and "interactive" based on
some measure independent of the details of the terminal driver's "ioctl"s,
rather than an *ad hoc* classification based on the mode the author of the
program the process is running chose to use.  (The current scheme gives an
incentive to rewrite EMACS to use CBREAK mode wherever possible, since you
get a bigger priority boost when a read completes than you do in RAW mode.)

A first cut at this might be based on the real time, or process virtual
time, interval between blocking reads from the terminal, with longer
intervals giving rise to greater priority boosts.  This seems to match the
intent of the RAW/CBREAK/cooked split, as described in the paper: "extremely
interactive" processes, which do only a little work between keystrokes (e.g.
a screen editor updating the current line) get small boosts; "very
interactive" processes, which do more work between keystrokes (e.g. "more",
or "ed", or even "vi" or EMACS, when used as a file browser) getting larger
boosts; and "interactive" processes, which do large amounts of work between
keystrokes (e.g., a shell) getting still larger boosts.  (Note that a
process can provide a different sort of interactive response at different
times, depending on what sort of work it's doing in response to keystrokes;
a screen editor can get different priority boosts depending on whether the
user is typing text in or doing an interactive global search and replace.)

This area of the new scheduler needs more work.  The requirements weren't
really stated; what was the rationale for the three-way classification of
processes, and why give the most interactive processes the least boost?
(For instance, is it intended that an interactive process should always get
placed at approximately the same priority relative to its "priority-max"
when it wakes up from a terminal I/O wait, so that a process which does
little work between terminal I/O waits needs a smaller boost than a process
which does a fair bit of work, since it has had fewer quantum expirations
and has had its priority lowered fewer times?)  The choices sound
reasonable, but I'm curious why those were the choices made.

Also, is there a danger of starvation with this scheduler?  Could several
people banging away at screen editors keep their process' priorities at
their "priority-max", with the risk that there could always be at least one
of those processes eligible to run, thus locking out all other processes?
On a large system with many users logged in, it seems possible that enough
users could be typing at any given time that one might always be eligible to
run.  This might actually be what is desired, but if there are situations
where it is not desired some mechanism (perhaps some form of "aging") will
have to be provided to prevent it.
-- 
	Guy Harris
	{ihnp4, decvax, seismo, decwrl, ...}!sun!guy
	guy at sun.arpa	(yes, really)