Paul Tarvydas  <tarvydas@visualframeworksinc.com> wrote:
+---------------
| At the assembler level, I think that I have to save less state than the
| process-based method.  Preemption requires that every cpu register be saved
| on the stack and that the stack pointer be changed.  My method needs to
| save an index in a state variable.  The rest of registers don't need to be
| saved (because, (a) either the unit of work has been completed (getting
| out) and only the "next state" needs to be saved, or (b) a hardware
| interrupt has occurred and the hardware does (at least some of) the saving
| for me).
+---------------

This sounds similar to the approach I took when designing the kernel
of the "WSched" multi-tasking communications operating system for
the DEC PDP-8 [augmented with DCA's proprietary "Bus Window" MMU]
back at Digital Communications Associates (DCA) in Atlanta in 1972.

The entire O/S ran with interrupts *off*[1], but by fiat [enforced
during design reviews!] each task was required to execute one
"@SERVICE" macro[2] at *least* once every 200 machine cycles[3]
and at least once per trip through every data-dependent loop
[such as traversing an arbitrary-length linked list]. This ensured
that the scheduler ["event dispatcher" in modern parlence] got a
chance to re-prioritorize things at least every 200 cycles (~250 us)
if a new event had arrived from the outside world [such as a user-
typed character]. The *only* state preserved by the "@SERVICE" macro
was the current PC and the current "Bus Window" mapping ["page table
base pointer", in modern parlence].

Newly-arrived events were linked to the end of the list (task queue)
associated with their priority, and contained the PC of the task
responsible for servicing them. A task pre-empted by an "@SERVICE"
became an new "event" whose "task" was simply to return to the PC
after the "@SERVICE" which pre-empted it. Task scheduling was thus
trivial -- simply run the first task on the highest-priority non-empty
task queue. [There were only 3 or 4 priorities, hence only 3 or 4
task queues]

This design [plus the "Bus Window", which made manipulating the
8-word "chunks" which were the basic units of allocation *much*
easier] was *extremely* efficient -- average CPU consumption to
get a character into and *out* of the system was only ~100 us
(or ~83 cycles) -- and we were able to keep over a hundred local
user terminals plus several remote terminal-concentrator network
lines serviced using a cheap, "slow", little PDP-8... much to the
consternation of the competition [DEC themselves!] who were using
the more expensive, much faster, "obviously better" DEC PDP-11 CPU
for the same job.  ;-}


-Rob

[1] Except that the "@SERVICE" macro[2] turned interrupts on for
    exactly *one* instruction as a cheap way to poll the common bus
    interrupt request line. It was cheaper even than testing for
    "any interrupt" then conditionally calling the scheduler, since
    the interrupt hardware did both the test & the "call" for us.

[2] Using the "8BAL" macro pre-processor [think "m4", but nicer syntax].
    "@SERVICE" was defined as "ION; CLA; IOF", and tested whether
    anyone was pulling on the Omnibus's interrupt request line. The
    ION (Interupt ON) instruction had a one-cycle delay built into it
    [for reasons having to do with the PDP-8's instruction set], which
    was why the CLA (CLear Accumulator) was there, and "@SERVICE" was
    thus *documented* to clear the AC [which was often needed on the
    PDP-8 anyway].

[3] The DEC PDP-8's instuction set was very simple, and programmers
    could trivially manually count machine cycles taken by instructions,
    as there were only a handful of different cases: basic instructions
    were one cycle; memory-reference added a cycle; indirection during
    memory-reference added a cycle; "auto-incrementing" during indirection
    added a cycle, and storing back into memory added a cycle. [The only
    instruction that could do *all* of those was "ISZ @FOO", where "FOO"
    was one of the eight same-page magic auto-incrementing locations
    (locations #o10-#o17), and cost 5 cycles.]

    Well, actually, on the PDP-8/e reading from memory took 1.2 us
    and writing took 1.4 us, so technically there were *two* possible
    cycle lengths, but we didn't need to be that precise and so didn't
    bother with the difference.  ;-}

-----
Rob Warnock			<rpw3@rpw3.org>
627 26th Avenue			<URL:http://rpw3.org/>
San Mateo, CA 94403		(650)572-2607