geoff@desint.UUCP (Geoff Kuenning) (10/11/84)
(Discussing the UCSD load-control mechanism) >The real advantage to this approach is >that kernel based approaches can not easily distinguish between a vi and a >compile, causing interactive jobs to become unuseable. > Keith Muller Gee, when I was in college (early 70's) our big CDC 6500 ran a "kernel" scheduler that did a real good job at that, on a dynamic basis (i.e., a big vi operation like a huge global substitution ran at "background" priority). The scheduler had multiple layers: an input queue for batch jobs, a "pool" of 40 potentially runnable jobs, and 7 "control points" (read partitions) for jobs actually in memory and available for CPU usage. (The limit of 7 processes in memory would have been far too small had we not had slowish core for swapping, especially since 3 were permanently occupied by system processes). Borrowing an idea that worked really well at Purdue, most processes ran under a fairly standard priority-adjustment scheme, where I/O improved priority and CPU usage decreased it. However, any job that blocked for *terminal* I/O got a short-term and big boost in priority when that I/O completed. (The length that the priority boost lasts depends on CPU speed--I think we used a few CPU seconds. The idea is to pick a number more than what an editor usually needs before it reads more from the terminal, but less than the amount of time taken by your typical compile.) Once this limit expired, process priority dropped drastically and becomes subject to the standard scheduling algorithms. The other trick was to have a scheduler that was smart about picking the 40 potentially-runnable jobs and about bringing the 7 into memory. The biggest improvement in a Unix system (where it is hard to control the number of potentially-runnable jobs without something like the UCSD load-control system) would come from tuning the swapping scheduler better. A swap takes a large amount of time; you want to make that time pay off by picking a process that will stay out for a long time, so that the amount of time spent swapping is small by comparison. In addition, you would like to pick a process that is consuming a lot of the resource you need--memory, I/O, or CPU--which requires better per-process statistics (especially on I/O rates) than most Unixes keep. Even the best scheduler cannot be perfect. Ours had operator commands to change process priorities and lock them into or out of memory. Many is the time I have seen a good operator clear up a thrashing system by either forcing an offending process to completion or by swapping it out until the load level had dropped. Now if we could only package good old Toshio and ship him with each 4.2 system...:-) -- Geoff Kuenning First Systems Corporation ...!ihnp4!trwrb!desint!geoff
henry@utzoo.UUCP (Henry Spencer) (10/14/84)
The problem with being smart about giving higher priority to processes
that do terminal i/o is that all sorts of interesting programs start
sprouting unnecessary terminal i/o. I know of one large, hard-crunching
compiler [name deleted to protect the guilty] which put out a NUL to
the terminal each time it read a line of source, to keep its priority
nice and high. Argh.
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.
--
Henry Spencer @ U of Toronto Zoology
{allegra,ihnp4,linus,decvax}!utzoo!henryach@pucc-h (Stephen Uitti) (10/19/84)
A side note to giving priority to processes that do terminal I/O. Many systems reset your priority to Max after a sleep. I've seen programs that first check to see if the load is high, and if so, every 30 seconds or so will sleep for a second. The result is that you sleep (you probably wouldn't have run then anyway) then run at higher priority. You'd be amazed sometimes how much real time improvement there is. Steve Uitti
guy@rlgvax.UUCP (Guy Harris) (10/19/84)
> The problem with being smart about giving higher priority to processes > that do terminal i/o is that all sorts of interesting programs start > sprouting unnecessary terminal i/o. I know of one large, hard-crunching > compiler [name deleted to protect the guilty] which put out a NUL to > the terminal each time it read a line of source, to keep its priority > nice and high. Argh. This tactic was used on MULTICS; however, MULTICS gave higher priority to processes blocking on terminal input, not to all processes doing terminal I/O (so if you just did a lot of writes to the terminal, it didn't help). What was done there was to interrupt the job; this didn't kill it, it gave you a subshell *under* the interrupted job. You then told that subshell to continue the interrupted job; since this was all taking place in one process, the interrupted job benefited from the priority boost given to the subshell which initially blocked reading a command from your terminal. Guy Harris {seismo,ihnp4,allegra}!rlgvax!guy
geoff@desint.UUCP (Geoff Kuenning) (10/19/84)
Henry Spencer writes: >The problem with being smart about giving higher priority to processes >that do terminal i/o is that all sorts of interesting programs start >sprouting unnecessary terminal i/o. I know of one large, hard-crunching >compiler [name deleted to protect the guilty] which put out a NUL to >the terminal each time it read a line of source, to keep its priority >nice and high. Argh. > >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. Programs that try to outsmart schedulers can be a serious problem. But I wasn't talking about rewarding terminal output. It is terminal *input* that drives user's perceptions of response times, and thus that is the only way to get a big priority kick. Naturally, nobody wants to 'babysit' a compute-bound program by giving it a CR every second or so to keep it going (especially since a proper implementation would ensure that only blocking reads gave the priority boost). -- Geoff Kuenning First Systems Corporation ...!ihnp4!trwrb!desint!geoff
tim@callan.UUCP (Tim Smith) (10/20/84)
In article <161@desint.UUCP> ...!ihnp4!trwrb!desint!geoff (Geoff Kuenning) says: > >Programs that try to outsmart schedulers can be a serious problem. >But I wasn't talking about rewarding terminal output. It is terminal >*input* that drives user's perceptions of response times, and thus >that is the only way to get a big priority kick. Naturally, nobody >wants to 'babysit' a compute-bound program by giving it a CR every >second or so to keep it going (especially since a proper >implementation would ensure that only blocking reads gave the >priority boost). Isn't this what auto-repeat and chewing gum are for? -- Tim Smith ihnp4!wlbr!callan!tim or ihnp4!cithep!tim
rpw3@redwood.UUCP (Rob Warnock) (10/24/84)
+--------------- | > 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@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*)
crp@stcvax.UUCP (Charlie Price) (10/25/84)
> >Programs that try to outsmart schedulers can be a serious problem. >But I wasn't talking about rewarding terminal output. It is terminal >*input* that drives user's perceptions of response times, and thus >that is the only way to get a big priority kick. Naturally, nobody >wants to 'babysit' a compute-bound program by giving it a CR every >second or so to keep it going (especially since a proper >implementation would ensure that only blocking reads gave the >priority boost). I was a surprise to me, but people ARE willing to "babysit" a running program if it helps their response. A couple years ago, some folks in a sibling group here at STC were doing something that took a long time and ran on one of the corporate IBM (or lookalike -- we have both) machines. I have personally NEVER seen an IBM mainframe that wasn't massively overloaded and this one was no exception. The mythology they related was that typing "enter" raised your priority and they claim that experience confirmed this. They would "babysit" a terminal and hit enter every few minutes FOR AN ENTIRE DAY so that their job would finish during the day. Garg!!!! Sad, but true. -- Charlie Price {hao ihnp4 decvax philabs sdcrdcf}!stcvax!crp (303) 673-5698 USnail: Storage Technology Corp - MD 3T / Louisville, CO / 80028
rcd@opus.UUCP (Dick Dunn) (10/26/84)
> The problem with being smart about giving higher priority to processes > that do terminal i/o is that all sorts of interesting programs start > sprouting unnecessary terminal i/o... > 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 ...Lately it occurs to me what a long, strange trip it's been.
jack@vu44.UUCP (Jack Jansen) (10/30/84)
About babysitting: If you send a signal to a process in unix,
it has it's runflag set (at least, it did in V6. I didn't use
the trick in V7 or anything else yet). So, if your program did
a lot of computing, you just ignore SIGINT, and put something
heavy with a 1cm**2 base (your girlfriend, standing on one
high-heeled shoe?) on the DEL key. Wow. Your program runs at least
twice as fast.....
Jack Jansen, {seismo|philabs|decvax}!mcvax!vu44!jack
or ...!vu44!htsa!jack
"Only the great masters of style ever succeed in being obscure"
Oscar Wilde, 1894.
"Most unix(tm) programmers are great masters of style"
Jack Jansen, 1984.