Could we use multiple stacks?

Sean 'Captain Napalm' Conner spc@gate.net
Wed, 29 May 1996 17:42:51 -0400 (EDT)


  I'm going to respond to Fare on the tunes-lll list (not here, as per his
wishes).  It'll be some time before I do, as I feel we both have to calm
down a bit.

  Anyway ...

On some network somewhere in cyberspace, Jecel Assumpcao Jr transmitted:
> 
> > > 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.
> 
> Exactly my point! What Fare' seems to be talking about is
> something very much like this (I could be wrong) and you
> tell him that it is no longer cooperative.
> 
  A large part of the problem Fare and I are having is communication.  He
has claimed that I play word games with him, but I'm not.  I'm trying to
understand what he's saying, but he's using terms in unfamiliar and
unexpected contexts.

  Yes, technically, an interrupt "preempts" the execution of the current
"thread/process/continuation" but it exists in a different state (or
context) than a "thread/process/continuation" because (and here, I'm talking
about interrupts due to external (hardware) sources, not those issued by
software):

	1. it is executed asynchronously to the rest of the system (granted,
	   there may be a determinable amount of time between interruptions
	   (say, due to a clock) but it's still asynchronous "in context
	   of the system as a whole").

	2. it can't assume anything about its own state or context, so it
	   has to establish its own state or context (saving and loading of
	   registers, for instance)

  	3. They usually are written to finish running before the next
	   interrupt of its type is triggered again (for example, an
	   interrupt handler for a hardware timer that has been programmed
	   to send an interupt request (IRQ) every 10mSecs (milliseconds)
	   has to finish within 10mSecs (preferrably less though) or there
	   stands a chance for missing further IRQs).

  An interrupt does "preempt" the current execution unit, and when it's
done, the execution unit that was interrupted is resumed (although under a
preemptive system, that is not always true).

  So while an interrupt is an "execution unit" (i.e. is code run by the CPU)
there aren't many things availble to it due to its nature.  Which is why I
consider interrupts a different thing than threads/processes/continuations,
since the contexts between the two are different.

  Fare is calling an interrupt handler a "thread" (possibly, I don't know
for sure) whereas to me, they're two different things entirely.

> > > 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.
> 
> I hope you don't get the impression that I don't like preemptive
> systems (as many don't). In fact, almost all of the OSes I have
> written so far have been preemptive. But it doesn't automatically
> solve problems like the one you describe.
> 
  
> A preemptive system with dynamic priorities would have trouble
> with this too. A system with fixed priorities (like QNX) could
> handle this by having it run with the top priority. But what if
> you have *two* events with such requirements? We would have
> to give up on priority scheduling and go to deadline scheduling
> or some other such complication.
> 
  If I had two events with such stringint real time requirements I would
have to rethink what I'm actually trying to do.  In the case of two events
requiring a response time of 10uSecs, and given that the system CAN garentee
a response time of 10uSecs for one event, but not two, then I would ask
myself:

	What is the possibility of the two events happening at the same time
	(or within a certain time frame)?

	Do both events REALLY need to be serviced in 10uSecs?

  I might conclude that I either don't need the 10uSec response time, that
only one is really critical, or since both are very important, have a
separate machine handle each event.

  But you will have the same problems reguardless of preemptive or
cooperative.

> >   How well does cooperative multitasking do in a multiprocessor box?
> 
> I would say it wouldn't work at all. My Merlin OS handles a more
> limited case: distributed memory machines. It will run on SMP
> machines by treating them as having logically separate memories
> for each CPU and as being connected by an increadably fast
> network. This isn't the best use of the hardware, but I have
> to limit the complexity of my hardware model if I am ever
> going to finish this thing.
> 
> >   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)).
> 
> True, though I think these things are also too low level for us
> to be able to write bug free programs with them. In Merlin I have
> concurrent objects as the single construct for synchronization. 
> 
  And I contend that it'll always be impossible to have bug free code (and
here, I'm using bug in a very wide sense).  Remember, be careful of what you
wish for, since you might just get it (and what I'm talking about here is a
misspecification is a bug).

  And there's only so much you can do to protect the user/programmer from
himself.

> > 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)).
> 
> If you want your interrupt handler to be a full thread that
> runs in less than 10us, I don't see how you are going to avoid
> disabling further interrupts. 

  Not run withing 10uSecs, but have the system respond to the event (or I
should say, start to respond) within 10uSecs.

> I don't see what shared interrupts
> have to do with anything (you do have them on a PC: see what
> interrupts your COM1 and COM3 use, for example).
> 
  Actually, not much.

  But as far as a Pcompatible (IBM PC and PClone) interrupt sharing is not
possible using the ISA/EISA bus, due to the way they're implemented (yes,
COM1 and COM3 use the same IRQ, but try using them at the same time).

> >   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!).
> 
  And I should have made it more explicit that I was being sarcastic there.

> The similar MacOS did a trick, which caused Apple a lot of
> grief in 1987. I steal the lower 2 bits, so only have 30 bit
> addresses (which still span 4GB since they are long word
> addresses), integers and floats.
> 
  And while that's okay for pointers (since you get better performance using
aligned pointers (although at the expense of more memory) you do loose range
in integers and floats, and you still have the problem of short
integers/long floats.  

  -spc (There are tradeoffs in nearly anything you do with computers ... )