jump to navigation

E Concurrency model 21 March 2008

Posted by Matthew Fulmer in Uncategorized.
trackback

The E Language has an interesting and very nice concurrency model. It is related to the Croquet/Tweak messaging model. This is an outline of it. I also made an animated demo of how promises work

Objects

  • Everything is an OBJECT.
  • Every object is associated with exactly one MAILBOX

There are two ways to initiate an action:

  • CALL a METHOD of an object (synchronous, immediate)
  • SEND a MESSAGE to an object (asynchronous, eventual)

Calling a method:

  • Pauses the currently executing method
  • Runs the called method until it completes
  • Returns the computation result to the calling method
  • Resumes executing the calling method

Sending a message:

  • Creates a message object
  • Places the message the receiver object’s mailbox
  • Returns a PROMISE to the sending method

A message knows about:

  • The promise created when the message was sent
  • The object that will receive the message (the receiver)
  • The method to call
  • The arguments to the method

Promises

  • A promise has a private mailbox
  • Messages sent to a promise will merely be stuffed in its private mailbox
  • A promise will turn into the return value of its associated message when it completes (the promise RESOLVES)
  • A promise will put the messages in it’s private mailbox on the public mailbox when it resolves

A thread executes the following loop until terminated:

  • take the earliest message from an object’s mailbox
  • call the method named in the message
  • when the method finishes, resolve its promise with the method’s return value

A method CANNOT wait for a promise to resolve, or for any other event. It may only place messages in a promise’s mailbox, to be run after the promise resolves. Thus, waiting is impossible, and, therefore, deadlock is impossible.

A thread, the group of objects associated with that thread, and the mailbox associated with those objects, is collectively called a VAT (called “Islands” in Tweak). Vats are the basic unit of concurrency in E. The number of active vats is the upper bound on the number of methods that are executing at once.

A vat is:

  • A thread
  • A mailbox
  • A group of objects

All objects belong to exactly one vat

  • a message sent to an object is enqueued in the object’s vat’s mailbox (unless the receiver is a promise)
  • a method called on an object is executed in the context of the object’s vat’s thread
  • an object can call methods of another object only if the callee object and the calling object are in the same vat (and therefore the methods execute in the same thread)
  • an object can send a message to any object it knows about, no matter if it is in the local vat, in another vat, or is a promise

A vat’s thread is only ever processing one message at any time, and it runs to completion. And since an object may only be in one vat, it’s state is only ever being touched by at most one thread. Hence, memory contention is not present, and locking is not necessary. Locking is impossible anyway, as waiting is impossible.

Keywords:

  • Object: An entity with state and behavior
  • Method: A unit of behavior defined on an object
  • Call: To execute a method in the current thread synchronously
  • Message: A request to execute a method at some point in the future
  • Mailbox: A queue for messages that have not yet been serviced
  • Send: To place a message in an object’s mailbox
  • Vat: A set of objects all sharing one thread and mailbox
  • Promise: A handle for an object that has not been computed yet, since it is the result of a message that has not yet been serviced
  • Resolve: To turn a promise into the object it was standing-in for. This happens when the message associated with the promise completes

This model is somewhat simplified. It does not address:

  • Exception handling
  • Broken promises
  • Pass-by-copy objects
  • Global message ordering

For more information, see chapter 3 of the Walnut book. For a discussion of how this concurrency model aids security as well, read Mark Miller’s thesis, or the Walnut book

Advertisements

Comments»

1. Mark - 21 March 2008

Really good explanation. Thanks!

2. Ron Welch - 21 March 2008

Nice work. I am hoping that you will expound on the relationship to Croquet’s TeaTime at some point….

3. Toby - 21 March 2008

Another good reference is Mark Miller’s Phd Thesis

4. Counterrevolution - 21 June 2008

Somehow i missed the point. Probably lost in translation 🙂 Anyway … nice blog to visit.

cheers, Counterrevolution!

5. Three ways to Parallelize a Raytracer « And I thank God for… - 8 July 2008

[…] well the approach maps to the E Concurrency model , which I also call the vat model, […]


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: