Re: Thread model

[Thomas Bushnell BSG]

On Wed, 2008-03-12 at 20:46 +0100, Neal H. Walfield wrote:
> At Wed, 12 Mar 2008 15:32:26 -0400,
> Thomas Bushnell BSG wrote:
> > On Tue, 2008-03-11 at 12:10 +0100, Neal H. Walfield wrote:
> > > What you are suggesting is essentially using a user-level thread
> > > package.  (Compacting a thread's state in the form of a closure is a
> > > nice optimization, but the model essentially remains the same.)  The
> > > main advantage to user-level thread package is that the thread memory
> > > is pagable and is thus less likely to exhaust the sparser kernel
> > > resources.  In the end, however, it suffers from the same problems as
> > > the current approach.
> > 
> > Cthreads does this.
> 
> Does what?  The cthread implementation found in hurd/libthreads uses
> one kernel thread per user thread.

The old Mach cthreads has a functional feature that multiplexes multiple
user threads on one or more kernel threads.  For the reasons I explain,
we turned this off.  

> > Still, the issue is the thread stacks; even if you are using multiplexed
> > user threads, each user thread still needs a user stack.
> 
> Yes, that is what I tried to say, sorry if it wasn't clear.  My
> suggestion was to use one thread per CPU and to make methods
> restartable so that should an RPC ever need to wait for a resource, we
> just add the message buffer to the object's wait queue (perhaps using
> push-back, e.g., reply to client: try message again using this
> capability, which identifies the wait queue).  When the object becomes
> unblocked, the message is requeued.

This is a risky strategy when there are complicated locks at stake, for
example, in something like diskfs_dir_rename.  Instead of holding one
lock and then waiting on the next (which requires its own proof that the
locking hierarchy is maintained), you hold one lock, try for the next,
and then release both and start over.  You need to prove that there are
no starvation problems, and it's very hard to prove that, because the
technique of a locking hierarchy is no longer sufficient.  There is one
case in diskfs like this (".." traversal), which required me to sort
through all the other multiple-lock cases in diskfs and be sure that
there was no starvation issue.

But, providing you get it right, the way to think about your savings is
this: the easy way stores the continuation as a stack to be resumed.
Your way has the continuation simply be a record of the whole
transaction, which is restarted from the beginning; now you only need to
save one message.

The clever way is to identify the particular things in the stack which
must be saved, and throw the rest away, and then restart the
continuation with the few things that really matter.  This is what the
kernel does internally; just look for "continuation" and you can see it.
You have to identify *each* blocking point, and make a continuation
structure for it, and so forth.  It's not too tough, you eventually just
start writing in explicit continuation passing style.  The code segment
gets bigger though. :)

Thomas