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 ][ [EMAIL PROTECTED] ][ [EMAIL PROTECTED] ] [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 ]
signature.asc
Description: Digital signature
_______________________________________________ vos-d mailing list vos-d@interreality.org http://www.interreality.org/cgi-bin/mailman/listinfo/vos-d
