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

[Peter Amstutz]

Okay, in following up with Ken's question, let me talk a little bit 
about s5 concurrency.  Warning, long, fairly detailed writeup follows.

In s4, the threading model is essentially wide open.  There is a thread 
pool fed by the "task queue", and all incoming requests, updates and 
notification callbacks are serviced by creating a Task object and adding 
it to the task queue.  This meant all code can potentially be called 
reentrantly, and need to be protected accordingly.  Since most calls are 
potentially blocking, asynchronous tasks are spun off into separate 
threads by assigning them to the task queue.  This means that the burden 
of serializing callbacks that act on non-threadsafe code (Crystal Space, 
WxWidgets) falls on the application.

Unsuprisingly, these scheme turns out to be fairly difficult to program 
for.  There are locks everywhere, the Crystal Space plugin is a mess of 
asynchronous code fragments, there are race conditions, and there's at 
least one known (but not yet debugged) deadlock in the ircbridge code 
which is why the demo world on interreality.org is nonresponsive half 
the time.

The essential problem is that the vobject model in s4 doesn't include 
computation: how the flow of control is transferred between parts of the 
program.  While the data semantics of vobjects were pretty well defined, 
we didn't understand at the time the need to also define the computation 
semantics -- we were stuck in the object-oriented notion of "message 
passing" == "synchronously calling a method".  As noted above, for an 
openended framework like VOS, that's not good enough.

So, a key goal in the s5 design process is to introduce a computational 
model.  Having thought it through and done some research, I determined 
that the Actor Model (http://en.wikipedia.org/wiki/Actor_model) is the 
closest to what we're trying to do, and so serves as a basis going 
forward as we turn it into a concrete design.

The key features of the actor model are:
 - Each actor executes independently of other actors
 - Actors can send asynchronous messages to other actors
 - Actors can execute behavior based on received messages
 - Actors can create other actors
 - Actors have no shared state

Now, replace "Actor" with "Vobject" and you have a pretty good 
description of how s4 VOS already works when talking to remote sites.  
The problem is, s4 VOS does't do this internally, which leads to a 
"leaky abstraction" when code written to work on local vobjects is made 
to access remote vobjects, as well all the other problems of 
shared-state concurrency outlined above.

Thus, in s5 we will establish each vobject-actor as a logically 
independent thread of control, and work primarily through message 
passing both within the local process as well as over the network.  This 
approach was popularized by the Erlang language (http://erlang.org/) and 
is often referred to as "Erlang-style concurrency."  However, unlike 
Erlang, we're not trying to get into the programming language business, 
instead the strategy is to add this functionality via libraries or 
bindings to the "VOS kernel" into existing, popular programming 
languages.

I should note at this point that a naive implementation of actors would 
create one operating system thread (or process!) for each actor, so you 
may get the impression that this is inefficient.  This is not what we 
intend to do at all, and instead propose the following optimization:

Observe that in the common case, at any given point in time most 
vobjects are idle.  Thus, we don't need a thread for every single 
vobject.  Instead, we "bind" a vobject to a thread on demand, allow it 
to execute, and then "unbind" it when we're done.  Binding a vobject is 
similar to acquiring a normal mutual exclusion lock, with the key 
difference that it can continue to accumulate pending asynchronous 
message.

A thread may have many vobjects bound to it.  This is crucial for tasks 
such as working with single-threaded code like WxWidgets or Crystal 
Space, as it allows for a fine-grained vobject-based representation but 
while requests are automatically marshaled and serialzed into a single 
thread.

To avoid excessive context switches, if a vobject is unbound, then it 
may be bound to the current thread and the request executed 
synchronously.  The decision to whether to execute the request 
synchronously is based on whether the method handler is "fast" or 
"slow".  A "fast" method does not block waiting for any other vobject, 
does not consume an inordinate amount of CPU time, and does not block on 
I/O from the operating system.  A "slow" method is any method that 
doesn't fit that criteria and is typically spun out into a separate 
thread.  Presently the determination of "fast" and "slow" has to be made 
by the programmer, although it may be possible to determine it 
automatically via some kind of code scanning or validation in future 
scripting langugaes.  If the vobject is bound to another thread, then 
the message is placed in the vobject's queue and executed later.

All method calls with present only an asynchronous interface.  The call 
will return a "future" (also known as a "promise" in the E language) 
which is a handle representing the progress and outcome of the 
computation.  The caller can then do a number of things with it:
 - ask if the computation is completed
 - block until the computation completes
 - block until all results are known for a set of computations
 - get the result, if completed
 - get the error, if failed
 - get the progress of the computation
 - register a continuation to be executed when the computation completes
 - register a continuation to be executed when all results must be known 
for a set of computations
 - register a continuation to be executed every N seconds when progress 
has occurred

I anticipate that the preferred pattern will be to pipeline as many 
requests as possible, return to the caller, and later handle the results 
in continuations (essentially callbacks) as they come in.  This permits 
very lightweight, interleaved execution even with thousands of actors.

Something I'm contemplating would be the use of user-level threads 
(using make/swapcontext() on Unix, and either get/setThreadContext() or 
the fibers API on Windows) when calling the blocking calls above.  This 
would simplify user code a lot, as the user would not need to manage 
context and could avoid splitting an algorithm across function 
bounderies (which might otherwise be necessary to ensure that that 
control flow resumes in the proper place.)

The last thing I want to talk about here is transactions.  Because 
vobjects are relatively fine grained, there will be cases where it makes 
sense to do a read-modify-update action on several vobjects at once 
without anyone seeing the intermediate results.  To this without the 
possibility for deadlock will probably require a centralized lock 
manager, but otherwise seems straightforward: bind a set of vobjects to 
a particular actor, checkpoint their state (for rollbacks) and disallow 
outgoing messages to objects not part of the transaction that could 
change anyone else's state (like change notifications) until the 
transaction is completed.  With a proper model for expressing these 
state changes, we could develop more general change tracking into a 
version control capability.

I think that about sums it up my current thinking on concurrency.  
There's a couple of other things I'm mulling over (process migration 
being one) but for the most part I believe what I've outlined here 
consists of a pretty thorough runtime/concurrency model that hopefully 
hits the sweet spot of power, ease of use, ability to scale across 
multiple cores and processors, and ability to interface with 
non-threadsafe code.  Finally, the pure message passing/actor model 
greatly facilitates cross-language method calls (scripting!) which I 
will discuss in my next s5 design email.

-- 
[   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/20070404/82f9b18b/attachment.pgp