Interlocked Class: read before write race condition problem

Question

using System;
using System.Threading;
using System.Threading.Tasks;

namespace InterlockedLearning
{
    class Program
    {
        static int sharedVariable = 0;

        static void Main()
        {
            Parallel.For(0, 1000000, Func1);
            Console.WriteLine("Thread{0} sharedVariable: {1}", Thread.CurrentThread.ManagedThreadId, sharedVariable);
            Console.Read();
        }

        public static void Func1(int val)
        {
            int i = Interlocked.CompareExchange(ref sharedVariable, 0, 0);
            if (i < 500000)
            {
                Interlocked.Increment(ref sharedVariable);
            }
        }
}

I am studying how to modify the above code so that the race condition problem does not happen again.

The above code result should be 500000, but the code's final result is 500001 if running several times. I think it may be caused by the checking condition.

I understand that it can be solved by simply using a lock, but I wonder if there are any non-blocking style methods to solve the problem.

Answer 1

The general pattern for updating a field using CompareExchange is (from MSDN):

int initialValue, computedValue;
do {
    // Save the current running total in a local variable.
    initialValue = totalValue;

    // Add the new value to the running total.
    computedValue = initialValue + addend;

    // CompareExchange compares totalValue to initialValue. If
    // they are not equal, then another thread has updated the
    // running total since this loop started. CompareExchange
    // does not update totalValue. CompareExchange returns the
    // contents of totalValue, which do not equal initialValue,
    // so the loop executes again.
} while (initialValue != Interlocked.CompareExchange(ref totalValue, computedValue, initialValue));

Adapting this to your scenario:

int initialValue, computedValue;
do
{
    initialValue = sharedVariable;
    if (initialValue >= 500000)
    {
        break;
    }
    computedValue = initialValue + 1;
} while (initialValue != Interlocked.CompareExchange(ref sharedVariable, computedValue, initialValue));

This says:

• Read the current value of the field.
• If the current value is >= 500000, we're done.
• Compute the new value by adding 1
• If the field hasn't changed since we read it, update it to the new computed value. If it has changed since we read it, there was a race, and we need to try again.

There's the possibility of a race, where we read the sharedVariable, then someone else increments it, then we compare against 500000, but that's OK. If it was >= 500000 before someone else incremented it, it's going to be >= 500000 after they incremented it, too.

Answer 2

I think it may be caused by the checking condition.

Yes, exactly, reading int i and then checking it is not atomic operation - imagine 2 threads (A and B) doing int i = Interlocked.CompareExchange(ref sharedVariable, 0, 0); (also why not just Interlocked.Read) getting 499999, performing check and then incrementing the value. For example:

• thread A reads sharedVariable = 499999
• thread A checks sharedVariable < 500000 (true)
• thread B reads sharedVariable = 499999
• thread B checks sharedVariable < 500000 (true)
• thread A increments sharedVariable (500000)
• thread B increments sharedVariable (500001)

I understand that it can be solved by simply using lock, but I wonder that if there are any non-blocking style method to solve the problem.

Not much that I can think of but for example you can decrement in case of overflow:

public static void Func1(int val)
{
    if (sharedVariable >= 500000) return;
    if (Interlocked.Increment(ref sharedVariable) > 500000)
    {
        Interlocked.Decrement(ref sharedVariable);
    }
}

Another option would be using CompareExchange in a cycle (see example in the docs).

P.S.

Highly recommend to check out the Deadlock Empire which will make understanding such cases much easier.