denbeste@cc5.bbn.com.BBN.COM (Steven Den Beste) (08/19/87)
> Now some substance: Most time-slice mutlti-tasking operating systems > guarantee that every ready-to-run job will get a chance to run, at > least once a time-interval (often a second.) This has the effect of > slowing down interactive performance: the interactive application > doesn't get all of the processor, so there is a lag in its response to > user input. OK, I don't like "my computer can beat up your computer" discussions any more than anyone else, so I will confine myself to theoretical discussions. First I'd like to point out that when multi-tasking, not every job is actually run-bound. The typical multi-tasking system maintains several queues with process control blocks. One is used to hold PCB's which aren't currently active, another to hold PCB's whose jobs are ready to run (usually known as the READY queue) and there will be an additional queue for each system resource (usually I/O devices) which a process may need but not be able to get. In many such systems, these queues are sorted by priority - particularly the run queue. (This is more-or-less how pSOS does it. pSOS is a helluva fine product.) On each time slice, the task switcher takes the item from the front of the run queue and moves it to the back (of its priority level) and takes the next one and lets it run. This takes the same amount of time unrelated to how many PCB's there are - so system overhead doesn't increase with a larger number of tasks. If there are several tasks operating at the same priority level, they each get an equal share of the machine, as you would expect. In this case, each operates slower than they would if they owned the machine. If there are several tasks which are READY, but one has a higher priority than any of the others, then it AND ONLY IT runs continuously. On each time slice the task switcher turns it on again. There lies the key to solving Mr. Oster's objection. Suppose I have an editor and a compilation running simultaneously. The editor is set to a higher priority than the compiler, but spends most of its time I/O bound. The user is examining the screen and not hitting the keys. On each time slice, the only task which is ready to run is the compiler, so it runs full tilt. The Editor is stuck on the I/O queue for the keyboard. The user hits a key - causing an interrupt. The interrupt handler takes the key, puts it in the key-press queue, and moves the Editor from the Keyboard queue to the READY queue. Note that it retains its higher priority. On the next time-slice, the task switcher gives the Editor a chance to run. It continues to be the only task at its priority which needs to run until it finishes handling the keystroke and goes I/O bound again, at which point it moves off of the READY queue back to the I/O queue for the keyboard. At that point, the compiler kicks in again and runs full tilt. (There can be variations on this theme if the keystroke causes other I/O - it may move the editor onto the disk queue, or the screen queue, or who knows what. Let's keep it simple for this discussion, though.) The practical effect of this is that the user of the editor gets exactly the same performance as he would if the compiler wasn't running - for the the following reason: If there isn't a low-priority task waiting to eat the CPU cycles which the editor doesn't need, the system has one which will, usually called "IDLE" or some such. The scenario described above is EXACTLY the same if the editor is the only task running, except that for "compiler" substitute "idle process". In some systems the task-switcher is invoked immediately after the READY queue is changed instead of waiting for the next time slice. This is what pSOS does; I don't know which approach the Amiga uses. All of this assumes that the user sets up the priorities correctly. On some systems it is done automatically by making any process which comes off an I/O queue be slightly higher priority for a couple of slices. Here we get into the black magic of scheduling algorithms, and risk losing our souls to some dark anti-deity. The Amiga does not do this automatically, but there is a command which allows it to be done manually. > Amiga fans can help not by explaining why multi-tasking is good, but > by explaining how the Amiga can do multi-tasking without suffering > from the interactive response problems that plague Unix, VMS, and that > plagued the Lisa. Most of the problems that plague UNIX and VMS come from the fact that often the number of highest-priority tasks which are READY are in total larger than the available memory - so even to service the READY queue requires memory swapping. The Amiga (and OS9, too, for that matter) avoids this by simply requiring that all tasks be memory resident at all times. If an MMU is available for the A2000 in the future, this requirement will probably still be maintained - so virtual memory shouldn't affect performance. This isn't a particularly major restriction with memory prices so low these days... Any remaining problems with interactive response can be handled by making any non-interactive tasks low priority on the Amiga. With regards to the LISA, I honestly don't know enough about it to be able to say what its problems are. I was able to run multi-tasking on my 900 Khz 6809-based Color Computer with OS9 quite reasonably with the maximum-possible-memory 64K, so I suspect that the LISA's problems came from bad design or bad implementation, not from any inherent difficulty in multi-tasking per se. > --- David Phillip Oster --My Good News: "I'm a perfectionist." > Arpa: oster@dewey.soe.berkeley.edu --My Bad News: "I don't charge by the hour." > Uucp: {seismo,decvax,...}!ucbvax!oster%dewey.soe.berkeley.edu I have only one more comment: The presence of the capability of multi-tasking does not mandate its use. If a machine has it it can still be used in single-task mode if nothing else will do. If a machine is single-task, then multi-tasking cannot be used. Multi-tasking is not a solution to every problem, but it is a solution to many problems. It is an option I am glad I have on my Amiga. -- Steven C. Den Beste Bolt Beranek & Newman, Cambridge MA denbeste@bbn.com (ARPA or CSNET or UUCP) harvard!bbn.com!denbeste (UUCP) I don't think BBN cares what I think about this stuff.
daveb@geac.UUCP (Brown) (08/20/87)
In article <407@cc5.bbn.com.BBN.COM> denbeste@cc5.bbn.com.BBN.COM (Steven Den Beste) writes: >Most of the problems that plague UNIX and VMS come from the fact that often >the number of highest-priority tasks which are READY are in total larger than >the available memory - so even to service the READY queue requires memory >swapping. The Amiga (and OS9, too, for that matter) avoids this by simply >requiring that all tasks be memory resident at all times. It is interesting that Unix's papa, Multics, refused to schedule tasks to use up "spare cycles" if by doing so the working set of the programs then running would be unable to stay in core (source: Organic). This is the paged-machine equivalent of requiring all runnable programs be core resident. --dave -- David Collier-Brown. {mnetor|yetti|utgpu}!geac!daveb Geac Computers International Inc., | Computer Science loses its 350 Steelcase Road,Markham, Ontario, | memory (if not its mind) CANADA, L3R 1B3 (416) 475-0525 x3279 | every 6 months.
rbl@nitrex.UUCP ( Dr. Robin Lake ) (08/21/87)
In article <407@cc5.bbn.com.BBN.COM> denbeste@cc5.bbn.com.BBN.COM (Steven Den Beste) writes: > >> Now some substance: Most time-slice mutlti-tasking operating systems >> guarantee that every ready-to-run job will get a chance to run, at >> least once a time-interval (often a second.) This has the effect of >> slowing down interactive performance: the interactive application >> doesn't get all of the processor, so there is a lag in its response to >> user input. > >OK, I don't like "my computer can beat up your computer" discussions any more >than anyone else, so I will confine myself to theoretical discussions. First I'd >like to point out that when multi-tasking, not every job is actually >run-bound. ..... Excellent discussion of task-switching resource sharing eliminated for brevity .... What Steve describes reminds me of the histories of both DEC and IBM operating systems. (Please excuse any errors of an ageing mind! :-} ) DEC originally had RSX-11-A, about 800 bytes of priority task-sharing control that managed well-behaved memory-resident programs. Then followed enhancements that allowed memory protection, programs called from disk, checkpointing, and maybe even not-well-behaved programs. IBM went along much the same path, from a single job run to completion, to multiple jobs in memory, each in a fixed size partition, to operator-controlled memory partitions, to dynamic allocation. MVS even today looks a lot like a fast batch processing stream to the user. If we extrapolate from history, perhaps the Mac will proceed along the same lines. Sure, some additional memory management hardware might be needed, but at least the box is open now! Rob Lake (It's really BP America Research, Development and Technical Service now) decvax!mandrill!nitrex!rbl > Steven C. Den Beste > Bolt Beranek & Newman, Cambridge MA > denbeste@bbn.com (ARPA or CSNET or UUCP) > harvard!bbn.com!denbeste (UUCP) >
barnett@vdsvax.steinmetz.UUCP (Bruce G Barnett) (08/21/87)
In article <407@cc5.bbn.com.BBN.COM> denbeste@cc5.bbn.com.BBN.COM (Steven Den Beste) writes: |All of this assumes that the user sets up the priorities correctly. On some |systems it is done automatically by making any process which comes off an I/O |queue be slightly higher priority for a couple of slices. Here we get into the |black magic of scheduling algorithms, and risk losing our souls to some dark |anti-deity. At the risk of my soul :-), here is what I understand of UN*X's algorithm. On UN*X System V, the system clock ticks 50-100 times a second. For each tick: If the current running job isn't blocked - it doesn't reschedule. If is does block ( waiting for I/O), the next job in the ready-to-run queue starts off. The current job gets a counter incremented, indicating CPU usage, or number of slices the task has used for the last 8 seconds. The priority is based on priority = CPU USAGE / 2 + base-level-priority Once a second: The CPU USAGE for each job is divided by two. It also re-computes the priorities of the tasks, and reschedules them if necessary. So it should be obvious that: Interactive tasks get high priority. CPU-bound tasks are scheduled by a round-robin mechanism. If a job gets 100% of the CPU ( i.e. 100 ticks) for 1 second, and is idle for eight seconds, the CPU usage after the decaying period drops to 0 ( divide 100 by 2, eight times) The scheduler penalizes CPU-bound jobs in favor of I/O intensive jobs. This provides `reasonable' sharing of resources, without the user writing any special `hooks' into the code. Also the user rarely has to change priorities. -- Bruce G. Barnett <barnett@ge-crd.ARPA> <barnett@steinmetz.UUCP>
bryce@COGSCI.BERKELEY.EDU (Bryce Nesbitt) (08/22/87)
In article <> barnett@steinmetz.UUCP (Bruce G Barnett) writes: >In article <> denbeste@cc5.bbn.com.BBN.COM (Steven Den Beste) writes: > > At the risk of my soul :-), here is what I understand of UN*X's algorithm... > [read the article for the description] > ...So it should be obvious that: > > Interactive tasks get high priority. No, it should be clear that lightly used interactive tasks get high priority. If your interactive task is a CPU hog, it will get a low priority. Based on CPU usage, it is impossible to determine which task the user is waiting for. This is why my "Auto-pri" toy asks Intuition. Intuition is the Amiga's user interface; it knows. Auto-pri's problem is that it sets the priority .5 too high :-). I really need to dig into the scheduler to make it work the way I want. Oh, since so many of you asked... Auto-pri will be posted to the net when it's ready. (comp.{sources,binaries}.amiga) >This provides `reasonable' sharing of resources, without the user >writing any special `hooks' into the code. On a single-user machine like the Amiga, on which you *know* which is the interactive task, I contend that a hook is ok. For a multi-user computer I would not have the same opinion. ----- |\ /| . Ack! (NAK, EOT, SOH) {o O} . ( " ) bryce@cogsci.berkeley.EDU -or- ucbvax!cogsci!bryce U "Success leads to stagnation; stagnation leads to failure."