Could we use multiple stacks?

[Francois-Rene Rideau]

[Note: this belongs to tunes-lll@ens.fr, not tunes@ens.fr]

>>>:spc
>>:jecel
>:spc

>> 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.
>
Well, that's exactly what I called the high-priviledge threads
that could preempt the normal ones, and for which you wanted
me to call the system "preemptive" instead of "cooperative" !!!


>> 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.
>
So you agree at last!


>>    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.
>
Why is such new thread of control "more than just an interrupt" ???
If you need things to be done immediately, then that's precisely
what the interrupt is for. Else, I see no problem with a 5 ms delay.
Anyway, either your handling code is not preemptible,
hence interrupt-driven and cooperative,
or it is preemptible, and you have can have no timing warranty,
and your 10 us response requirement is moot.


>> 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.
>
Which is a stupid mix-up of semantically different things,
that forces the system programmer to add "NODELAY" flags to some calls,
while yielding execution in a way that will flush the cache when it is
most useful.
   Anyway, you don't quite answer our problem of allowing GC
if an instruction that does pointer manipulation is could be interrupted.
The GC just CANNOT work in such a possibility,
unless any such "critical section" is put between cli() sti()
calls, which is much more costly than cooperative threading.


>> 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/)).
>
This doesn't fail more on multiprocessors
than does the preemptive equivalent cli() ... sti().
See below.

>   How well does cooperative multitasking do in a multiprocessor box?
>
Very well, if you consider the processors as different nodes in
a network, that just can communicate through reliable hyper-fast
low-latency channels, so that object migration costs little.
Modelling the OS through fine-grained object migration
allows much more scalable behaviour than just the coarse-grained
migration that traditional OSes do with multiprocessor.


>> 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
>
You're thinking about parallel architectures.
Synchronizing with other CPUs is not harder with cooperative threads
than with preemptive ones. Cooperation has to do with time-shared
threads, not space-shared ones, and makes their synchronization trivial.
   What cooperation brings is that
you only have to synchronize *active* threads
to synchronize them all with low-level systemwide requirements,
and won't have to wake up every single sleeping thread for that;
surely higher-level requirements may involve higher-level constructs,
and cooperation won't modify anything about that.
   Anyway, cooperation *does* reduce synchronization time
for parallel architectures as well as for purely sequential ones,
and actually is all the more a win in parallel architectures,
where synchronization is the most important performance bottleneck
(think about systemwide GC again).


>> 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?
>
Preemption just prevents the difference from being made.
You cannot know if the register or memory region you're inspecting
is not in a transient state where what is a pointer and what isn't
cannot be determined.


>   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 YOU complained about GNU not imposing limits!
I wonder what kind of limits you propose were imposed!?


>> 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.
>
I hope you realize that doing this in a preemptible way
has a overhead much worse than cooperative multithreading.

--    ,                                         ,           _ v    ~  ^  --
-- Fare -- rideau@clipper.ens.fr -- Francois-Rene Rideau -- +)ang-Vu Ban --
--                                      '                   / .          --
Join the TUNES project for a computing system based on computing freedom !
                 TUNES is a Useful, Not Expedient System
WWW page at URL: "http://www.eleves.ens.fr:8080/home/rideau/Tunes/"