Load control and intelligence in schedulers

[Rob Warnock]

+---------------
| > I'm not saying it can't be done well, just that care is needed.  Terminal
| > input should be considered much more significant than output, for purposes
| > of scheduling.
| OK, but be careful to distinguish actual (requested) input--something from
| the keyboard which satisfies an outstanding read from the program.
| Otherwise you give the users (rather than programs) a way to kick the
| priority--just bang on the return key every now and then.
| -- Dick Dunn	{hao,ucbvax,allegra}!nbires!rcd		(303)444-5710 x3086
+---------------

As John Nagle <jbn at wdl1.UUCP> points out, the schedulers which give snappy
response often give a quantum of run time and a priority, but note that
(at least in the 5.07 TOPS-10 scheduler) the priority and quantum are
reset ONLY when CHANGING queues. The transitions which INCREASE priority
are those from some kind of wait to the corresponding wait-satisfied run
queue. On the other hand, exhausting the quantum run time of a run queue
shifts one to a different run queue with a DECREASE in priority, and often
(as John pointed out) an increase in quantum of run time. Now (in TOPS-10),
the interesting transition was from tty-input-wait (a "wait" queue, like UNIX
"sleep(address)") to tty-input-wait-satisified (a "run" queue, one of several).
This transition gave the job VERY high priority, but only for 1/30 sec.

As I recall, the run queues and quantums (from highest priority down) were
something like this:

high-->	tty-input-wait-satisfied	1/30 sec.
	disk-I/O-wait-satisfied		1/30 sec.
	misc-I/O-wait-satisfied		1/30 sec. <-- includes tty OUTPUT
	processor-queue-#1		1/2 sec.
	processor-queue-#2		2 sec.
low-->	processor-queue-#3		2 sec.

If your job exhausted the 1/30 sec. quantum for TIWS without blocking, it
would drop onto the end of PQ1, and any other jobs waiting to run in TIWS,
DIOWS, IOWS, or for that matter, PQ1, would run first. If you got to run
and used up another 1/2 sec., you would drop to PQ2, ... then PQ3. (From
PQ3 you just go to the tail of PQ3, so CPU-bound jobs were round-robin.)

Note that the ONLY way to get into the tty-input-wait-satisified queue was
to have been in the tty-input-wait queue, which means the job had BLOCKED
on an input read. Type-ahead did nothing but put the characters into the
"tty chunks" ("c-lists"), and if there was a line (or whatever) there when
the job went for it, it got it and continued without blocking. So in order
to get a "kick" in priority, you HAD to wait for the job to block. If you
"banged on the return key every now and then", you could make it worse than
if you carefully waited and responded to each prompt.

Occasional output also had no effect on your priority, since in order
to block (and hence to wake up into I/O-wait-satisfied) you had to fill
the terminal output queue (or at least exhaust your quota). A couple of
characters wouldn't affect your priority, since the queues were quite large.

Historical curiosity:
In fact, on the KA-10 processor with early versions of the O/S, you COULDN'T
block on output to a 9600 baud terminal, because the tty line discipline
(named SCNSER) couldn't PROCESS 960 chars/sec.! (...although the interrupt
code and the terminal could.) So 2400 baud terminals could actually get better
service when listing a long file, if there were also several CPU-bound jobs
in the system.  (It was later fixed, but that's another story.)

Incidently, the TOPS-10 system ("job"-oriented) was usually thought to be
able to support about twice as many users ON THE SAME HARDWARE as TOPS-20
or Tenex ("process"-oriented systems), especially on smaller systems such
as the DECsystem-2020 (a "2901" bit-slice machine). My personal subjective
experience is that TOPS-10 was the snappiest operating system I have ever
used, but I would not give up the convenience of pipes and redirection to
have it back.  (It DID have "job control" like Berkeley's, sort of. You could
stop a job, "detach" it, log in again, do something, detach, attach to the
earlier job, continue it, etc. But it was clumsy by comparison.)

Rob Warnock

UUCP:	{ihnp4,ucbvax!amd}!fortune!redwood!rpw3
DDD:	(415)572-2607	(*new*)
Envoy:	rob.warnock/kingfisher
USPS:	510 Trinidad Ln, Foster City, CA  94404	(*new*)