LinkedListChannel Tutorial and Implementation Discussion

This page illustrates the purpose and basic use of a LinkedListChannel and its specific implementation details. LinkedListChannel can be found in the DigitallyCreated.Utilities.Concurrency assembly.

Tutorial

A channel is simply a thread-safe queue, where multiple threads can enqueue (Put) and dequeue (Take) data from the queue in a safe manner. A common scenario for the use of channels would be where threads will take data off an input channel, process it, place the result onto an output channel, and then forget about the data before taking new data off the input channel and repeating. In this situation you can have a system that allows data to flow between threads, but at the same time structurally protects the data from being concurrently accessed (which could cause issues). If a channel is empty and a taker tries to take from it, the taker should wait until a putter places data onto the channel. This guarantees any taker that it will always receive some data off the channel.

You put and take data off a channel like so:

LinkedListChannel<MyData> channel = new LinkedListChannel<MyData>();
channel.Put(new MyData());
MyData data = channel.Take();

Implementation Discussion

Concurrency utilities are hard to implement correctly. These discussions illustrate how these utilities have been implemented and how they work, which should convince you that they're stable. Of course, if you see something I've missed, please do post an issue on the issue tracker.

This implementation of a channel (LinkedListChannel) can deal with thread interrupts and ensures that if they were to occur within the LinkedListChannel, they would not corrupt the internal state. This implementation does not support thread abortion.

See here for the code for LinkedListChannel.

The LinkedListChannel is an implementation that uses a custom linked list as its backing data structure. It has two locks, one for taking (_TakeLock) and one for putting (_PutLock). It manually implements a monitor wait/pulse system that causes takers to wait until the channel contains data before they are pulsed and are able to take their data and return.

This implementation uses a slightly strange version of a linked list, where the very first node in the list is not used and contains no data (_BlankFirst). The reason this is done is so it deals with the edge case of when the channel is empty. Because we have different locks for putters and takers, when the channel is empty we need a way of synchronising the putters and takers so that the takers blocks until something is put. To do this, we make the putters and takers not only acquire their _PutLock and _TakeLock, but they almost also acquire a lock against the node they are trying to access, which will be _BlankFirst in the case of takers, and _Last in the case of putters. This means when we come down to an empty channel _Last will be pointing to the same node as _BlankFirst and either a taker or a putter (but not both) is able to execute. However, when there are items in the channel, putters and takers will be acquiring locks against different nodes and therefore will be able to run concurrently without blocking each other.

When a taker acquires _BlankNode and finds the channel empty, it begins a Wait against _BlankNode. When a putter acquires _Last (which is pointing to the same object as _BlankNode) and finds the channel empty, it inserts a new node and pulses _Last, which causes the taker to wake up. Note that more than one taker can never be waiting on _BlankNode because as a taker waits, it also holds _TakeLock which blocks any other takers from trying to acquire _BlankNode.

Interrupts are handled correctly in both Put and Take. In both methods, interrupts at the locks are allowed to throw an exception as normal because at those points no action has been taken and therefore no special logic is needed. The potential interrupt at the taker's Wait also does not need to be handled because there is no need to pulse the lock if an interruption occurred. This is because there will never be anyone else waiting on that lock at the same time, since the thread waiting on that lock holds _TakeLock, thereby blocking all other takers.

Last edited Apr 1, 2010 at 8:17 AM by dchambers, version 1

Comments

No comments yet.