Concurrency issue: parallel writes

Question

One day I was trying to get a better understanding of threading concepts, so I wrote a couple of test programs. One of them was:

using System;
using System.Threading.Tasks;
class Program
{
    static volatile int a = 0;

    static void Main(string[] args)
    {
        Task[] tasks = new Task[4];

        for (int h = 0; h < 20; h++)
        {
            a = 0;
            for (int i = 0; i < tasks.Length; i++)
            {
                tasks[i] = new Task(() => DoStuff());
                tasks[i].Start();
            }
            Task.WaitAll(tasks);
            Console.WriteLine(a);
        }
        Console.ReadKey();
    }

    static void DoStuff()
    {
        for (int i = 0; i < 500000; i++) 
        {
            a++;
        }
    }
}

I hoped I will be able to see outputs less than 2000000. The model in my imagination was the following: more threads read variable a at the same time, all local copies of a will be the same, the threads increment it and the writes happen and one or more increments are "lost" this way.

Although the output is against this reasoning. One sample output (from a corei5 machine):

2000000
1497903
1026329
2000000
1281604
1395634
1417712
1397300
1396031
1285850
1092027
1068205
1091915
1300493
1357077
1133384
1485279
1290272
1048169
704754

If my reasoning were true I would see 2000000 occasionally and sometimes numbers a bit less. But what I see is 2000000 occasionally and numbers way less than 2000000. This indicates that what happens behind the scenes is not just a couple of "increment losses" but something more is going on. Could somebody explain me the situation?

Edit: When I was writing this test program I was fully aware how I could make this thrad safe and I was expecting to see numbers less than 2000000. Let me explain why I was surprised by the output: First lets assume that the reasoning above is correct. Second assumption (this wery well can be the source of my confusion): if the conflicts happen (and they do) than these conflicts are random and I expect a somewhat normal distribution for these random event occurences. In this case the first line of the output says: from 500000 experiments the random event never occured. The second line says: the random event occured at least 167365 times. The difference between 0 and 167365 is just to big (almost impossible with a normal distribution). So the case boils down to the following: One of the two assumptions (the "increment loss" model or the "somewhat normally distributed paralell conflicts" model) are incorrect. Which one is and why?

Answer 1

The behavior stems from the fact that you are using both the volatile keyword as well as not locking access to the variable a when using the increment operator (++) (although you still get a random distribution when not using volatile, using volatile does change the nature of the distribution, which is explored below).

When using the increment operator, it's the equivalent of:

a = a + 1;

In this case, you're actually doing three operations, not one:

1. Read the value of a
2. Add 1 to the value of a
3. Assign the result of 2 back to a

While the volatile keyword serializes access, in the above case, it's serializing access to three separate operations, not serializing access to them collectively, as an atomic unit of work.

Because you're performing three operations when incrementing instead of one, you have additions that are being dropped.

Consider this:

Time    Thread 1                 Thread 2
----    --------                 --------
   0    read a (1)               read a (1)
   1    evaluate a + 1 (2)       evaluate a + 1 (2)
   2    write result to a (3)    write result to a (3)

Or even this:

Time    a    Thread 1               Thread 2           Thread 3
----    -    --------               --------           --------
   0    1    read a                                    read a
   1    1    evaluate a + 1 (2)
   2    2    write back to a
   3    2                           read a
   4    2                           evaluate a + 1 (3)
   5    3                           write back to a
   6    3                                              evaluate a + 1 (2)
   7    2                                              write back to a

Note in particular steps 5-7, thread 2 has written a value back to a, but because thread 3 has an old, stale value, it actually overwrites the results that previous threads have written, essentially wiping out any trace of those increments.

As you can see, as you add more threads, you have a greater potential to mix up the order in which the operations are being performed.

volatile will prevent you from corrupting the value of a due to two writes happening at the same time, or a corrupt read of a due to a write happening during a read, but it doesn't do anything to handle making the operations atomic in this case (since you're performing three operations).

In this case, volatile ensures that the distribution of the value of a is between 0 and 2,000,000 (four threads * 500,000 iterations per thread) because of this serialization of access to a. Without volatile, you run the risk of a being anything as you can run into corruption of the value a when reads and/or writes happen at the same time.

Because you haven't synchronized access to a for the entire increment operation, the results are unpredictable, as you have writes that are being overwritten (as seen in the previous example).

What's going on in your case?

For your specific case you have many writes that are being overwritten, not just a few; since you have four threads each writing a loop two million times, theoretically all the writes could be overwritten (expand the second example to four threads and then just add a few million rows to increment the loops).

While it's not really probable, there shouldn't be an expectation that you wouldn't drop a tremendous amount of writes.

Additionally, Task is an abstraction. In reality (assuming you are using the default scheduler), it uses the ThreadPool class to get threads to process you requests. The ThreadPool is ultimately shared with other operations (some internal to the CLR, even in this case) and even then, it does things like work-stealing, using the current thread for operations and ultimately at some point drops down to the operating system at some level to get a thread to perform work on.

Because of this, you can't assume that there's a random distribution of overwrites that will be skipped, as there's always going to be a lot more going on that will throw whatever order you expect out the window; the order of processing is undefined, the allocation of work will never be evenly distributed.

If you want to ensure that additions won't be overwritten, then you should use the Interlocked.Increment method in the DoStuff method, like so:

for (int i = 0; i < 500000; i++)
{
    Interlocked.Increment(ref a);
}

This will ensure that all writes will take place, and your output will be 2000000 twenty times (as per your loop).

It also invalidates the need for the volatile keyword, as you're making the operations you need atomic.

The volatile keyword is good when the operation that you need to make atomic is limited to a single read or write.

If you have to do anything more than a read or a write, then the volatile keyword is too granular, you need a more coarse locking mechanism.

In this case, it's Interlocked.Increment, but if you have more that you have to do, then the lock statement will more than likely be what you rely on.

Answer 2

I don't think it's anything else happening - it's just happening a lot. If you add 'locking' or some other synch technique (Best thread-safe way to increment an integer up to 65535) you'll reliably get the full 2,000,000 increments.

Each task is calling DoStuff() as you'd expect.

private static object locker = new object();

static void DoStuff()
{
    for (int i = 0; i < 500000; i++)
    {
        lock (locker)
        {
            a++;
        }
    }
}

Answer 3

Try increasing the the amounts, the timespan is simply to short to draw any conclusions on. Remember that normal IO is in the range of milliseconds and just one blocking IO-op in this case would render the results useless.

Something along the lines of this is better: (or why not intmax?)

     static void DoStuff()
     {
        for (int i = 0; i < 50000000; i++) // 50 000 000
           a++;
     }

My results ("correct" being 400 000 000):

63838940
60811151
70716761
62101690
61798372
64849158
68786233
67849788
69044365
68621685
86184950
77382352
74374061
58356697
70683366
71841576
62955710
70824563
63564392
71135381

Not really a normal distribution but we are getting there. Bear in mind that this is roughly 35% of the correct amount.

I can explain my results as I am running on 2 physical cores, although viewed as 4 due to hyperthreading, which means that if it is optimal to do a "ht-switch" during the actual addition atleast 50% of the additions will be "removed" (if I remember the implementation of ht correctly it would be (ie modifying some threads data in ALU while loading/saving other threads data)). And the remaining 15% due to the program actually running on 2 cores in parallell.

My recommendations

• post your hardware
• increase the loop count
• vary the TaskCount
• hardware matters!