Halting Problem

Emulating Newsqueak's channels in C#

We'll look at some of the threading related mechanisms provided by .NET, and we'll do that by trying to emulate some ideas from a little known programming language called Newsqueak.

Tekst dostępny także po polsku

December 2007

Newsqueak

Every language which supports concurrency provides constructs for synchronization between different threads of execution (thread don't have to correspond to OS threads). In Newsqueak (not related to Squeak, a Smalltalk implementation) that mechanism is called channels. Let's look at a simple example:

c = chan of int;
c = mk();

In the first line we declare c as a channel for sending and receiving integers. The second creates the channel and initializes it (assume mk() works similarly to new keyword in C#). It's time to use the channel and send some data.

c <-= 3;

// meanwhile, in a different thread
int x <-= c;

First, we send the number 3 to c. When a variable of type chan is on the left hand side of the <-= operator, we put data into the channel. When it is on the right hand side, we receive data from the channel. So now the variable x is set to 3.

Communication via channels is completely synchronous. A thread that sends data blocks until someone tries to pull the data out of the channel. When the receiving thread tries to receive data, it blocks until some other thread actually sends any data. Obviously, no thread can receive and send data to itself through the same channel. A channel blocks until we get data out of it. There is no buffer for storing multiple values in a channel.

Thanks to channels Newsqueak allows us to acquire results from functions executing concurrently to the current thread. If we have a function foo, which takes arguments x and y, we can create a new thread with begin.

begin foo(x, y)

If we have a channel defined somewhere inside foo, we can communicate with the newly created thread. Of course, for two way communication we need two channels.

Putting it all together, let's look at a simple application of channels.

void Counter(c: chan of int)
{
    int n = 1;
    for(;;)
    {
        c <-= n++;
    }           
}

nat := mk(chan of int);
begin Counter(nat);
int n;
for(;;)
{
    n <-= nat;
    print("%d\n", n);
}

After this short presentation of the Newsqueak language, we can try to recreate that functionality in C#.

EventWaitHandle

To avoid typical synchronization problems, we can use some of the classes in Systems.Threading namespace. One of them is EventWaitHandle. Although it is not the most efficient way, we can emulate Newsqueak's channels with its help. EventWaitHandle allows threads to communicate with signaling.

Channel implementation

We will create a Channel class containing two public methods: Send and Receive. The most important elements of that class will be two instances of type EventWaitHandle. Their Set and WaitOne methods do the whole work. Thread calling WaitOne blocks until another thread signals it is ready by calling Set on the same EventWaitHandle object.

The default constructor of Channel class creates both EventWaitHandle objects in the following way:

sendIt = new EventWaitHandle(false, EventResetMode.AutoReset);
waitForData = new EventWaitHandle(false, EventResetMode.AutoReset);

Value of the first argument, false, means that the created object won't be signaling readiness (when the argument is set to true, the constructors calls Set after creating the object). The second argument specifies the mode in which this EventWaitHandle instance operates. When multiple threads call WaitOne on the same object, a queue forms. AutoReset means that every time we call Set, exactly one of waiting threads will unblock (the first from the queue).

Let's see the code of mentioned public methods of our channel. Remember that, each one of the methods will be called from a different thread.

public void Send(T packet) 
{
    waitForData.WaitOne();
    lock (locker) { data = packet; }
    sendIt.Set();
}

public T Receive()
{
    T packet;
    waitForData.Set();
    sendIt.WaitOne();
    lock (locker)
    {
        packet = data;
        data = default(T);
    }
    return packet;
}

Before sending data we check, if any other thread signaled that it wants to receive data. Such signal is sent in Receive method, by calling Set on the private member waitForData. We won't be able to send anything if there's no receiver. Analogical situation takes place when receiving data.

Send and Receive use a lock, which guarantees that our thread is the only one having access to a particular piece of data. Thanks to locks we can prevent situations like the following:

class Race{
    public float x = NumberFactory.X;
    public float y = SomeCalculation();

    public void Divide(){
        if(y != 0) {
            // now another thread does this: y = 0
            float result = x/y;
        }
    }
}

The "check for zero and then divide" consists of two operations (actually, there's even more going underneath) and we have no guarantee that some other thread won't modify y between them. Putting the dangerous fragment of code into a lock gives us what we really wanted.

lock(someObject)
{
    // the code from  above goes here
}

Everything between the curly braces can be accessed only by the current thread. Only one thread can put a lock on someObject and if it's already locked, other threads have to wait (of course, too much waiting can be a problem too).

Example

We will use the Channel class to implement Eratosthenes prime sieve, a simple algorithm for computing prime numbers. It works the following way: from the set of all natural numbers we choose the smallest number greater than one, which is 2, then we "throw out" all its multiplies. Of all the numbers that remained, we choose the smallest one (this time it's number 3) and once again we throw out all its multiplies. Repeating the procedure will give us successive prime numbers.

The idea for implementation, as well as the concept of channels, was taken from Rob Pike's on Google Video. Code looks similarly, even we we take the differences between Newsqueak and C# into consideration. That actually was the goal, because the original looked very clean.

Channel<int> chan = Sieve();
// print first 100 prime numbers
for (int i = 0; i < 100; i++)
{
    Console.WriteLine("{0}", chan.Receive());
}

Sieve method returns a channel from which we extract successive primes and print them on the screen. At first, in the above loop we get data directly from Counter method, which is called in a new thread. Counter's implementation is analogous to the Newsqueak version presented earlier, with the little difference that we start counting from 2 (do you see why?).

static public Channel<int> Sieve()
{
    Channel<int> c = new Channel<int>();
    new Thread(Counter).Start(c);
    Channel<int> prime = new Channel<int>();
    new Thread(delegate()
    {
        int p;
        Channel<int> newChan;
        for (; ; ) {
            p = c.Receive();
            prime.Send(p);
            newChan = new Channel<int>();
            FilterArg arg = new FilterArg();
            arg.Prime = p;
            arg.Listener = c;
            arg.Sender = newChan;
            new Thread(Filter).Start(arg);
            c = newChan;
        }
    }).Start();
    return prime;
}

Sieve starts a new thread and in it inside an infinite loop we chain together filters (Filter method), which filter out multiplies of a certain number (given as an argument). To start a new thread we crate an object of type Thread giving an instance of one of the following delegates:

public delegate void ThreadStart();
public delegate void ParametrizedThreadStart(Object obj);

In our example we pass an anonymous delegate. After creating a Thread instance, we just have to call its Start method.

After the whole "machinnery" is started, in the infinite loop we receive number 2 - the smallest integer at that moment - and we send it further (at this stage, it is printed on the screen). Then a thread is started, filtering out all multiplies of 2. From now on, every number, before "appearing" in the loop in Main, travels from Counter to the filter thread. Successive iterations of the loop contained in Sieve add new filters: for multiplies of 3, 5 and so on (those numbers come from channel c).

It's worth noticing, that nowhere in the code, despite creating lots of new threads, can we see locks. Original implementation also has this property, and the help of channels we were able duplicate it.

Notes

Once more I emphasize, that the idea of channels and usage example was inspired (read ripped) from Rob Pike's talk, which I strongly recommend to see. To know more about Newsqueak, take a look at slides from a lecture titled "Construction of Concurrent Systems Software" (PDF: 1, 2, 3). The Channel class is just an exercise to familiarize yourself with EventWaitHandle. We're not able to reproduce all of Newsqueak in C# (eg. everything in Newsqueakis passed by value, which is not the way one usually does things in C#) and that wasn't my goal.

Marginalia

Download the Channel class and examples as a VS2005 Solution

Update: May 2010: I wrote a small followup to the article on my blog, taking .NET 4.0 into consideration.

Created: December 2007