[vos-d] s5 concurrency (design part 2)

[Peter Amstutz]

On Wed, Apr 11, 2007 at 06:20:21PM +0200, Karsten Otto wrote:

> Ok, I get it. What you say sounds exactly like the Simula coroutine  
> concept, where you use an exchange jump to switch between multiple  
> stacks. This is not necessarily the same as user-level threads, in  
> particular when blocking I/O is involved.

You're right, it's a bit different from user threads, although what I 
have in mind could be handled reasonably well by creating a user thread 
for every vobject ahead of time.  Then a sending a message would involve 
more or less pushing the call into the target's message queue and then 
explicitly yielding to the target.

However, I realized after writing the email that that any solution which 
results in blocking the sender due to the target blocking isn't the 
right behavior.  The sender may be able to handle the message as an 
asynchronous call (since it gets a future back) so it's not fair to 
block it -- indeed that's the whole point of being able to switch tasks.

So, we want to be able to save state and return to the immediate caller 
(not the toplevel event loop, as I said in my previous email).  
Unfortunately the unix swapcontext() isn't really appropriate in this 
case, because it saves the entire stack (which includes the caller's 
stack, and caller's caller's stack, etc...) and we're really only 
interested in just the stack for the current vobject.

> Digging around a bit I found http://en.wikipedia.org/wiki/Coroutine
> which explains this nicely, lists a few libraries, and even mentions  
> the Actor model (duh) :-)
> You probably know this page already, but I thought I'd mention it  
> anyway just in case.

On further research, I'm coming around to the conclusion that there 
simply doesn't exist a good implementation of coroutines or user threads 
in C/C++.

So I think a futures-based, continuation-passing style is going to be 
the way to go, with blocking waits not permitted.  Instead, we'll focus 
on the more tractable goal of providing a good API for 
psudeo-continuations in C/C++ (boost may be helpful here) as well as 
hopefully ensuring that design allows bindings for lanaguages that do 
have coroutines/continuations can take advantage of it.

I should also note that the other side of this is that a method can be 
marked "CPU_INTENSIVE" or "BLOCKING", which will cause VOS to always 
execute the method in a different thread from the sender.  The goal of 
all of this is that, since we will be doing message passing internally 
to the application and as well as across language/network boundaries, to 
be efficient and avoid context switch overhead when the method being 
called is trivial.

On a related note, I started thinking a lot about user 
threads/microthreading/continuations etc in part from reading a couple 
of developer blog entries on how Linden Labs acomplished it in their 
server.  They have an interesting challenge (which we will eventually 
also have to deal with) which is that they need to support many 
thousands of scripts running simultaneously on a simulator, and the 
scripts come from untrusted sources that can do obnoxious things like 
spin in an infinite loop and never return.  Operating system threads 
arn't suitable due to overhead (and possibly also due to synchronization 
requirements with the physics simulation) so it has to be a user-level 
thread strategy.  However, users can't be trusted to have their code 
ever yield (or even ever end).  So, they force the issue.  The scripts 
are compiled for the .NET virtual machine, but before they are allowed 
to run, a gatekeeper inserts explicit yields into the bytecode at 
strategic points (branching points being the obvious target, if I had to 
guess).  This results in each script periodically checking to see if it 
has run out its timeslice, and when that happens it explicit yields to 
the next thread without the need for preemptive scheduling.

-- 
[   Peter Amstutz  ][ tetron at interreality.org ][ peter.amstutz at gdit.com ]
[Lead Programmer][Interreality Project][Virtual Reality for the Internet]
[ VOS: Next Generation Internet Communication][ http://interreality.org ]
[ http://interreality.org/~tetron ][ pgpkey:  pgpkeys.mit.edu  18C21DF7 ]

-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
Url : http://www.interreality.org/pipermail/vos-d/attachments/20070411/9a2b8da3/attachment.pgp