Could we use multiple stacks?

[Sean 'Captain Napalm' Conner]

On some network somewhere in cyberspace, Jecel Assumpcao Jr transmitted:
> 
> Sean 'Captain Napalm' Conner wrote:
> >   Example:  My Real-Time requirements require that the handler for event A
> > is executed within 10uSecs (10 microseconds).  Event sequence as follows:
> > 
> >         Thread B just passed a "check point".  It won't get to the next
> >         "check point" until another 50uSecs.
> > 
> >         Event A happens.  I have 10uSecs (or less) to handle this situation,
> >         or something bad happens.
> > 
> >   I can't just stop Thread B, because that would be ... oh ...
> > PREEMPTION, now wouldn't it?  Or do you get around that by calling some
> > special code in Thread B that causes it to PREEMPT itself?  Oh, real
> > COOPERATIVE there.
> 
> You are just being dogmatic, here. 

  I suppose I am.

> Look at the Macintosh OS,
> for example. There is a lot of preemption there - when you
> move a mouse, when a disk block comes in, etc. 

  Okay, although I tend to call those interrupts.

> Why is it
> called a cooperative OS, then? Because:
> 
>    1) the preempting task *must* always return to the
>       preempted task, never to another one
> 
  Interrupted task.  Okay.

>    2) the preempting task can only use a very restricted
>       subset of system services
> 
> A device driver is divided into two parts: a time critical
> one that is scheduled preemptively and the rest, which is
> scheduled cooperatively. So a responsive cooperative OS
> only needs to yield every 5 ms or so, not every 10 us!
> 
  But (playing Devil's Advocate here) my hypothetical Real Time requirements
of 10uSecs is more than just an interrupt.  A whole new thread of control
has to be switched in to deal with the situation, not wait for the current
thread to give up control, as it were.

> A popular method of dealing with GC in a cooperative system
> is to push a word on the stack with each call that has a
> 1 bit for each register that contains a live pointer at that
> point. Since a GC can only occur as a result of a call
> (with an implicit yield), the GC has all the information
> it needs about all the stacks in the system. In a preemptive
> system, the GC may be invoked between *any* two instructions.
> This makes scanning the stack much more challanging.
> 
  I address this in another post.  A "system" call can do an implicit
"yeild" in a preemptive system as well.

> >   To even hope for a response time of XuSecs in a cooperative system, you'll
> > have to insert checks every X/2usecs (assuming you can), which doubles the
> > overhead.
> 
> A cooperative system has many downsides, but one advantage is
> that every program segment between system calls (yield points)
> is a critical region. 

  This fails in a multiprocessor system, which are becoming more popular (in
fact, there's at least one "PC" now out that contains two processors right
in the box (http://www.be.com/)).

  How well does cooperative multitasking do in a multiprocessor box?

> In a preemptive OS you will have to
> create the critical region yourself by surrounding the code
> with DisableInterrupt() and EnableInterrupt() or a higher
> level construct. 

  Come tomarrow, even DisableInterrupt()/EnableInterrup() won't even cut it
and you (and I) will have to use higher level constructs (like semaphores or
mutexes (which is the same as a semaphore, only with a worse sounding
name)).

> It is not at all hard to delay interrupts
> by more than 10 us on such a system. The only way to get
> as good a response time as we have in a cooperative system
> is on a CPU with multiple interrupt levels, where we can
> mask the timer interrupt while letting others preempt
> even a critical region.
> 
  I don't quite follow.  The 80x86 gets around this by using an external
interrupt controller.  But even on a system WITH one interrupt level, the
handler can leave interrupts disabled until the cause of the interrupt is
determined, then re-enable them.  It's only the poor hardware design of the
PC that disallows sharing of interrupts (although the newer busses (PCI) fix
this, it'll be a few years before this becomes used)).

> >   And garbage collection is going through memory looking for allocated
> > memory that no longer is referenced, and freeing it.  A secondary objective
> > may be to compact the memory so that free space is coalessed into one block,
> > but that doesn't seem to be mandatory.
> 
> Great definition. The problem is finding out what "no longer is
> referenced" if you look at a bit pattern and don't know
> if it is a pointer or an integer!
> 
  Which is a problem, isn't it?

  I know that Emacs got around this by using the upper 8 bits of a pointer
for GC.  At least, until computers started using more than 16M of memory
(way to go, rms!).

> Most copying GCs don't need indirect pointers at all. Since
> they sweep through the whole memory, they can fix every
> reference to some object that moved. 
> 
  The trick then, is in keeping tabs on all references.

  -spc (Oh these damn computers with their finite speed and memory!  If
	only they ran faster than the speed of light with infinite
	memory!)