Concurrent Programming - Channel

From SwinBrain

A Channel is designed to allow threads to exchange data via a buffer (i.e. a queue). A Channel offers two main methods:

  • Put: which places data upon the Channel.
  • Take: which takes data from the Channel.

A typical behaviour for a Channel will cause it to block during Take operations when the Channel is empty. The Take action will wait forever if no data arrives, which in some cases is not acceptable. To extend the usability of this utility you can offer a version of Take which includes a time-out. This method provides a version of Take that is more "live", allow it to be used in cases where data may be placed upon the Channel, but a time-out is required.

  • Poll: looks for data for a given period of time, after which it gives up and times out.

Illustration

When the Channel is created it is empty. In this illustration a thread arrives to take data from the channel. In standard single-threaded applications a take operation on an empty queue would throw an exception. Because the application has only a single thread there is no way that the queue will ever have data if it doesn't have data at the moment. The situation is very different when you have a concurrent program (with multiple threads). In these cases it may be appropriate for the taking thread to wait for data to arrive. This is exactly the operation of the Channel. When taking the data from the Channel the thread will wait if the channel is currently empty.

These images illustrate this process. Firstly the thread arrives at the Channel and finds that it is empty (image 1). At this point the Channel blocks the taking thread (image 2). Other take threads may also arrive before any data is Put onto the channel (image 3).

The take thread checks if it can take.
The take thread waits for data.
More than one thread can wait.


At some point in the future another thread arrives to Put data onto the Channel. This thread will bring a single piece of data and place it upon the Channel. This thread then indicates to the waiting threads that data has arrived. The waiting threads will then be unblocked and one of them will receive the data. Different implementations can optimise this so that only one thread is woken, however the safest option is to wake all waiting threads

The following images illustrate this process. In the first image the Put thread is arriving with its data. The Put thread then gains access of the Channel and then places its data upon the channel (image 2). During this placing process the Put thread wakes the waiting Take threads. These cannot yet gain access to the Channel as the Put thread will currently have exclusive access (to ensure safety). When the Put thread leaves one of the Take threads can gain access to the channel. This access will be exclusive causing the other Take threads to block (image 3). The Take will then remove the data from the Channel and return with it (image 4). As all waiting threads were woken, the other thread will now gain access to the Channel (image 5), and then determine that it still needs to wait (image 6).

A thread arrives to put data onto the channel.
Put locks the Channel and places the data.
One Take thread gets access to the channel.
Take thread removes data.
Other threads check if there is data.
Threads must wait for data to arrive.


Timed Illustration

The timed version of the Take works as you would expect. If the data does not arrive in time then the Poll method returns without any data. Typically the Poll method needs to return two pieces of data:

  • The data received (if any), and
  • True if data was returned, False if the operation timed out.

Image 1 shows the Poll arriving and waiting for data. Image 2 shows the result of a Time-out. Image 3 shows the result of a successful take.

Poll being called on empty channel.
Time-out as no data arrived in time. Returns false, and null.
Success, returns true, and data.


Bounded Channel

The Bounded Channel is a variation of the channel where the there is only limited space. With this version the Put operations will block when the Channel is full.

The following images illustrate the operation of a Bounded Channel. When the Bounded Channel is full, a put thread will block waiting for space to place its data (image 1). When a Take thread arrives it will gain exclusive access to the Bounded Channel and then take the data (images 2, and 3). Once the Take thread leaves the Put thread can gain access to the Bounded Channel (image 4).

Put blocks waiting for a free space.
The taking thread arrives and gains exclusive access to the Bounded Channel.
The taking thread removes some data from the Channel and returns.
The putting thread can then gain access to the Channel.
Put thread can place data when there is space.


With the Bounded Channel the Put operation may now block indefinitely if no other thread takes data from the Channel. In some cases this behaviour is not acceptable. Just as we can add a Poll method to perform a timed take, we can also introduce a Offer method that performs a timed add.

The Offer method provides data to the Bounded Channel, which it must accept within the specified time (image 1). When the Offer times out, the Offer method returns false. When the Offer succeeds, the Offer method returns true.

The offer provides a timed version of the put method.
When the offer times out, it returns false.
When the offer succeeds, it returns true.