Lock Isn't Stopping Duplicates

Question

I am having a problem with my Lock() critical section of the code. The situation is that my output is containing duplicates, I can't have that! Below you can see the code that replicates my situation. I am really dumb founded by my situation, excuse me if I am missing something really silly...

private static object theLock = new object();
private static int currentNumber = 0;

. . .

static void Main(string[] args)
{
    for (int i = 0; i < 30; i++)
        CreateAndRunWorker();
}

. . .

private static void CreateAndRunWorker()
{
    BackgroundWorker worker = new BackgroundWorker();
    worker.DoWork += new DoWorkEventHandler(TheWorkToBeDone);
    worker.RunWorkerCompleted += new RunWorkerCompletedEventHandler(TheWorkAfterWork);
    worker.RunWorkerAsync();
}

. . .

private static void TheWorkToBeDone(object sender, DoWorkEventArgs e)
{
    OutputNum();
}

. . .

private static void TheWorkAfterWork(object sender, RunWorkerCompletedEventArgs e)
{
     CreateAndRunWorker();
}

. . .

private static void OutputNum()
{
    lock (theLock)
    {
        currentNumber++;
        Console.WriteLine(currentNumber);
    }
}

The above is being called by 25 background workers from a Main() function. The lock and counter are initialized globally. The output contains duplicate numbers. How?

Answer 1

You are probably running into some cache effects for local caches on unrelated cores. The issue at hand is the int itself isn't declared or updated in a way that would ensure the local cache is kept up to date. You could address this in a couple ways:

Fixing your implementation

private static readonly object theLock = new object();
private static volatile int currentNumber = 0; // note the addition of "volatile"

private static void OutputNum()
{
    lock (theLock)
    {
        currentNumber++;
        Console.WriteLine(currentNumber);
    }
}

The volatile keyword is important to force all locally cached references to that number to read the same. There are corner cases in the micro-optimizations where executing things out of order can cause a race condition on certain chip architectures. The lock is still required to protect from increment race conditions though.

The readonly keyword is important to prevent your lock object from ever getting overwritten during run time. Once initialized the instance of the readonly lock object can never be changed. If you do change the instance of the lock object, you will have a short period of time where two threads can access the counter variable at the same time.

Getting rid of the lock

If you use the Interlocked.Increment function you can get the effect of what you want without using locks at all.

private static volatile int currentNumber = 0;

private static void OutputNum()
{
    int localRef = Interlocked.Increment(ref currentNumber);
    Console.WriteLine(localRef);
}

This removes the lock completely, keeps the solution more performant since there is less lock contention, but retains all the safety.

IMPORTANT: Use the value returned from Interlocked.Increment for future work in the same method since that won't change from another thread accessing the same code and changing the value before the Console.WriteLine() can execute.

Understanding Why This Works

1. The CLR performs optimizations and recompiles code at runtime. The volatile keyword ensures the optimizations don't include accessing your counter. (https://msdn.microsoft.com/en-us/library/x13ttww7.aspx)
2. If the lock instance ever changes during runtime, you will have a brief moment where you can have a race condition. One thread locked on the old object while another is locked on the new object. Always declare your lock objects so that they cannot change. If it's a static object, then static readonly or const is what you want. If it's a field inside an object meant to protect one instance, declare the lock as readonly. The readonly keyword ensures the instance can never change for the life of the containing scope. (https://msdn.microsoft.com/en-us/library/acdd6hb7.aspx)
3. Interlocked.Increment performs an atomic change that is guaranteed safe across all running cores. If your critical section of code is simply incrementing a counter, this method relieves the system of needing a heavy lock. Just use the return value for the rest of the method so that it stays constant for that scope. (https://msdn.microsoft.com/en-us/library/dd78zt0c(v=vs.110).aspx)

For a good summary of the subject, see https://stackoverflow.com/a/154803/476048

For academic purposes the same problems and solutions exist in Java. The APIs are just a little different.