.NET 4.0+

Thread-Safe Stacks with ConcurrentStack<T>

by Richard Carr, published at http://www.blackwasp.co.uk/ConcurrentStack.aspx

.NET 4.0 introduced several thread-safe collection types that can be used in parallel code without manual thread synchronisation. The ConcurrentStack<T> class is one such collection. It allows the creation of thread-safe, last-in, first-out stacks.

Stacks and Parallelism

In an earlier article I described the ConcurrentQueue<T> class, which allows you to create thread-safe queues without adding lock statements to synchronise threads and avoid race conditions. A similar class exists that you can use to create last-in, first-out (LIFO) stacks. This is the generic class, ConcurrentStack<T>.

To demonstrate the use of ConcurrentStack<T>, we'll first create an example that uses the simpler Stack<T> type. We'll omit lock statements to introduce a concurrency bug.

To begin, create a new console application project. Add the following two using directives to the top of the Program class's file:

using System.Threading;
using System.Collections.Concurrent;

We can now define the Program class using the code below. This is similar to the Queue<T> example from the previous article. First a stack is initialised and populated with all of the integer values between one and one million. Every value is then popped from the stack and summed. The process continues until an exception is thrown when the stack is exhausted.

We should expect that the final total is 500,000,500,000. However, we are using two parallel tasks to process the stack and the basic Stack<T> is not thread-safe. This leads to race conditions and an incorrect result when using a computer with more than one processor core.

class Program
{
    static long _total;
    static Stack<int> _stack;
 
    static void Main()
    {
        IEnumerable<int> numbers = Enumerable.Range(1, 1000000);
        _stack = new Stack<int>(numbers);
        _total = 0;
 
        Task task1 = Task.Run(() => ProcessStack());
        Task task2 = Task.Run(() => ProcessStack());
 
        Task.WaitAll(task1, task2);
 
        Console.WriteLine("Total: {0}", _total);
    }
 
    static void ProcessStack()
    {
        try
        {
            while (true)
            {
                Interlocked.Add(ref _total, _stack.Pop());
            }
        }
        catch (InvalidOperationException) { }
    }
}

/* EXAMPLE OUTPUT

518360798399

*/

NB: As with the example in the ConcurrentQueue<T> article, you could solve this problem with the lock statement. However, the ConcurrentStack<T> class makes it much simpler.

ConcurrentStack<T>

To resolve the above problem without adding lock statements we can use the ConcurrentStack<T> class. You can add items to this type of stack in the same manner as for a standard stack, either by providing a source sequence at instantiation or using the Push method. However, the class does not include a corresponding Pop method to extract an item from the top of the stack. Instead you use TryPop.

With TryPop, if the stack contains an item it is returned via an output parameter and the return value for the method is true. If the stack is empty, the method returns false. This approach is necessary for multithreaded code. If you were to check that the stack contained an item before reading it, it's possible that another thread could empty the stack before Pop was called.

You can also look at the next item in a concurrent stack without removing it from the collection using TryPeek. This method has a similar syntax to TryPop; it returns a Boolean indicating if the operation was successful and if a value is present in the stack it is provided via an output parameter. As the stack may be read by multiple threads, you should not use TryPeek and expect a following call to TryPop to return the same value, or even to return a value at all.

To correct the previous code so that the summation is correct we need to make a couple of changes. Firstly, the stack type is changed to ConcurrentStack<int>. Next, the ProcessStack method is updated to use TryPop. We can also control the while loop's execution according to the result of the TryPop call, meaning that we are no longer using exceptions for flow of control.

The updated Program class is as follows:

class Program
{
    static long _total;
    static ConcurrentStack<int> _stack;

    static void Main()
    {
        IEnumerable<int> numbers = Enumerable.Range(1, 1000000);
        _stack = new ConcurrentStack<int>(numbers);
        _total = 0;

        Task task1 = Task.Run(() => ProcessQueue());
        Task task2 = Task.Run(() => ProcessQueue());

        Task.WaitAll(task1, task2);

        Console.WriteLine("Total: {0}", _total);
    }

    static void ProcessQueue()
    {
        int value;

        while (_stack.TryPop(out value))
        {
            Interlocked.Add(ref _total, value);
        }
    }
}

/* OUTPUT

500000500000

*/