4.2bsd kernel auto-nicing, scheduling (long)

[Jeff Straathof]

In article <3303 at sun.uucp> guy at sun.UUCP writes:
>... there is no way to distinguish between "vi"
>and "more" simply on the basis of the mode it puts the terminal into.

True that they both operate in CBREAK mode, but "vi" does a lot more input
than "more" does, that's how the difference in priorities arises.

>(EMACS may put the terminal into RAW mode, but that's because ...

Good point about EMACS.  Dividing interactive processes on the basis of mode
was just a choice.  With the current implementation of the scheduler, it is
simple to disregard the mode by making the various boost values for terminal
input equal.

>It would also be interesting to see what effect treating programs running in
>RAW mode as screen editors would have on programs like "uucico"...

"Uucico" can definitely be a problem.  What will probably be required of
it is a voluntary call to setminmax() to lower its priority.  I haven't done
it yet but probably will.  Thanks to Chris Torek for originally pointing it
out to me and thanks to Guy for pointing it out to everyone else.

>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.

I have never worked with System V so don't know the answer.  I might not
know the answer even if I had worked with it.  The key with this scheduler
is that some of the boosting has been moved to the terminal driver.  The
implementation makes it easy to change the criteria for receiving terminal
input boosts.  I considered several different ones and chose just one to
implement.  I've got others in mind though.

>(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.)

Glad to here others agree.

>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.

Perhaps it would, but remember that whatever the mode the author chooses he
gets no boost unless he does the input.  That fact is more important than
the ad-hoc mode classifications.

>(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.)

Any full screen editor, regardless of the mode in which it operates, does
so much input that it stays in the top levels of the run queue in the current
implementation.

>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...

Not really.  A scheduler-buster could then compile the file between inputs,
something we wanted to avoid.

>... "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.)

Once an editor begins to do a global search-and-replace, it becomes less
of an interactive process by my classifications.  The other editor users
should get quicker service if they are just doing inserts when you are doing
your global replace.  You should still get much quicker service than the
remaining processes because you started out in that top level and won't
drop many levels before requiring input again.  For all of this to work,
the scheduler should be tuned properly.

Boosts for "extremely" interactive processes are small because they get so
many of them.  It probably doesn't matter what the amount is as long as it
is bigger than 0.  Boosts for the "very" interactive processes that do things
like file browsing and news reading are larger because fewer of them occur and
more cpu service is required to get the next batch (perhaps a screenful) of
output prepared.  If they didn't get the larger boost, they might fall into the
lower levels with the compilers and not give the user the small response time
for which we were looking.  Boosts for interactive processes like shells are
larger to give the command it might fork a chance to show its interactive
nature.  If the child, or the process itself, isn't interactive it will drop
through the levels quickly.

My intentions might be met by just giving an equal boost for any type of
terminal input and letting the quantum sizes to the rest.

>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, ...

I just wanted to try to properly assign priorities among the interactive
processes themselves as the paper stated.  There are several different methods
of doing this each with tradeoffs between effectiveness and cost.  I chose
the 'mode method' because I thought it would be fairly effective and because
it would incur very little cost.

>...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.

Correct.  Perhaps my explanation of the differing boost amount should go
here. Sorry about leaving all of it out of the paper.

>...is there a danger of starvation (by many editors) with this scheduler...

Definitely.  We thought about it beforehand but didn't know the answer.  We
firmly believed the effort had enough potential merit to at least try out.
The scheduler does maintain a small and stable response time for interactive
processes regardless of system load (determined by use only).  Obviously
something has to give during peak hours, and it's the troffs and compilers
that do.  Though they won't get starved if the machine is powerful enough,
they will if it isn't.

>...(having editors lock out others)... might actually be what is desired...

It was what was desired by us.  The goals of the new scheduler placed
interactive responsiveness as the most important.  Not having that particular
responsiveness during peak hours was a major motivation for the research.
I suspect that users will learn about the best times to compile and about
the best times to look their code over twice before compiling.  As it stood
before, the best time to compile was always now!  That policy was getting
quite aggrivating.

>... 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.

If you want to avoid that situation, tune the scheduler that way.  Make the
priority boosts smaller for terminal input, make the quantum sizes at the top
of the queue smaller, and make the quantum expiration bump larger.  All of that
might not work if you have so many editors running, but then your machine
might not be powerful enough to handle the workload people are placing on it.
Interactive responsiveness was our major goal, and avoiding a form of "aging"
in BSD was what provoked this good discussion some time ago.

The design of the scheduler is quite simple.  I imagine that it is discussed
in most introductory OS books.  The simplicity unvails cases like uucico
that break the intentions, but the simplicity also provides opportunities for
experimentation and success.  Many ideas people have about scheduling can
be tried out with simple modifications to this implementation.  One I will
try next is that of the "base+boost" method.

Good tools for measuring the performance of such schedulers are a must, and
they are what I am working on now (along with preparing everything for
distribution, argh).  Once I get everything done, the results will be made
available.

Thanks to Guy Harris for his comments.

-- 
Spoken: Jeff Straathof 	ARPA:	jeff at mimsy.umd.edu	Phone: +1-301-454-7690
CSNet:	jeff at umcp-cs 	UUCP:	seismo!umcp-cs!jeff
USPS: Comp Sci Dept, Lab for Parallel Comp, Univ of Md, College Park, MD 20742