Multi-threaded message passing scheme

Many smalltalk implementations lack of effective native threading support. And in rising era of multi-core CPUs something must be done to fill this gap.

The following model based on message passing threading. Any language, which based on message-passing can use such model.

What we need to know about objects?
- objects is a state, stored at some memory location. To interact with objects we send them a messages. A semantics, how message sent is under total control of the VM. To make object answer messages, developer defines methods, which can access receiver's state and can use this state to evaluate return result. Methods can also send messages to other objects and use their evaluation result for own needs.

To make safe use of native threads we need to define following restrictions:
- for any unique object in system only single method can access it's contents at single point of time.

Lets examine the structure of typical method evaluation scheme in message-passing language implementation:
1. lookup method for given message and receiver
2. enter method
3. evaluate result
4. exit method, return result

A result evaluation can be divided in steps consisting of following categories:
- manipulate receiver's contents
- send messages to other objects

Our goal is to prevent running two or more methods which access object contents at same point of time.
To ensure, that no other thread can manipulate receiver's contents we must mark receiver object as busy and make it free when we done manipulating.
For this, we must add a field, named 'busy' for each object in system. Object considered busy when some method accessing it's state and free if no methods currently accessing it's state.
Make note, that when we sending message to other object from within current method, we don't need to keep receiver object marked as busy, since we stop manipulating it's contents and waiting for return from other method.

But 'busy' property introduces too much overhead:
- to enter 'manipulation step' thread must check if receiver object is currently marked as busy and wait when it becomes free, then mark it as busy, perform manipulation and mark as free at the end.
Since such steps is rather atomic and performed with high frequency in running system, a locking/unlocking mechanism introduces too much overhead.

To avoid this i propose to use message queuing approach:
- messages instead of sent directly, are enqueued.
- a worker thread polls queue and enters enqueued method context to evaluate result.
- every object in system, instead of having 'busy' property, holds an active context reference, which, if not nil, indicates that object already take part in other method evaluation.

A typical worker thread is running on the following scheme:

1. fetch message context from queue
2. activate context (start/continue evaluating a method)

- when sending message from active context do following:

• lookup for method of receiver
• create new method context, set its parent to current
  
• check receiver's active context
• if receiver's active context is nil, choose thread which will be responsible for evaluating a message, set new context owner to chosen thread, set object's context to new context(write barrier).
• if receiver's active context is not nil, set new context owner to same owner of receiver's active context
  
• enqueue context to queue of its owner
• deactivate current context

- when returning from method

• store return result in parent context
• if receiver's active context same as current context, set it to nil (no write barrier)
• destroy current context
• enqueue parent context to its owner thread queue
  

3. goto step 1.

When thread queue is empty, thread is going to sleep, and wait for activation by different thread, or can be recycled.
For choosing new context owner thread a thread which creates new context can check if its own queue is non-empty (a more messages is pending to evaluate), and if so, pass ownership of new context to one of the sleeping threads or allocate new thread if its own queue grown too big.

Memory management/Garbage collector.

How GC must act in such environment?
A general principles is clear enough: collect garbage fast and effectively, without system wide locks.