Conflicting threads on a local variable

Question

why is it, that in the following code, n doesn't end up being 0, it's some random number with a magnitude less than 1000000 each time, somtimes even a negative number?

static void Main(string[] args)
{
    int n = 0;

    var up = new Thread(() =>
        {
            for (int i = 0; i < 1000000; i++)
            {
                n++;
            }
        });

    up.Start();

    for (int i = 0; i < 1000000; i++)
    {
        n--;
    }

    up.Join();

    Console.WriteLine(n);

    Console.ReadLine();
}

Doesn't up.Join() force both for loops to finish before WriteLine is called?

I understand that the local variable is actually part of a class behind the scenes (think it's called a closure), however because the local variable n is actually heap allocated, would that affect n not being 0 each time?

Answer 1

If you don't want to use locks there are atomic versions of the increment and decrement opperators in the Interlocked class.

Change your code to the following and you will always get 0 for an answer.

static void Main(string[] args)
{
    int n = 0;

    var up = new Thread(() =>
        {
            for (int i = 0; i < 1000000; i++)
            {
                Interlocked.Increment(ref n);
            }
        });

    up.Start();

    for (int i = 0; i < 1000000; i++)
    {
        Interlocked.Decrement(ref n);
    }

    up.Join();

    Console.WriteLine(n);

    Console.ReadLine();
}

Answer 2

The n++ and n-- operations are not guaranteed to be atomic. Each operation has three phases:

1. Read current value from memory
2. Modify value (increment/decrement)
3. Write value to memory

Since both of your threads are doing this repeatedly, and you have no control over the scheduling of the threads, you will have situations like this:

• Thread1: Get n (value = 0)
• Thread1: Increment (value = 1)
• Thread2: Get n (value = 0)
• Thread1: Write n (n == 1)
• Thread2: Decrement (value = -1)
• Thread1: Get n (value = 1)
• Thread2: Write n (n == -1)

And so on.

This is why it is always important to lock access to shared data.

-- Code:

static void Main(string[] args)
{

    int n = 0;
    object lck = new object();

    var up = new Thread(() => 
        {
            for (int i = 0; i < 1000000; i++)
            {
                lock (lck)
                    n++;
            }
        });

    up.Start();

    for (int i = 0; i < 1000000; i++)
    {
        lock (lck)
            n--;
    }

    up.Join();

    Console.WriteLine(n);

    Console.ReadLine();
}

-- Edit: more on how lock works...

When you use the lock statement it attempts to acquire a lock on the object you supply it - the lck object in my code above. If that object is already locked, the lock statement will cause your code to wait for the lock to be released before continuing.

The C# lock statement is effectively the same as a Critical Section. Effectively it is similar to the following C++ code:

// declare and initialize the critical section (analog to 'object lck' in code above)
CRITICAL_SECTION lck;
InitializeCriticalSection(&lck);

// Lock critical section (same as 'lock (lck) { ...code... }')
EnterCriticalSection(&lck);
__try
{
    // '...code...' goes here
    n++;
}
__finally
{
    LeaveCriticalSection(&lck);
}

The C# lock statement abstracts most of that away, meaning that it's much harder for us to enter a critical section (acquire a lock) and forget to leave it.

The important thing though is that only your locking object is affected, and only with regard to other threads trying to acquire a lock on the same object. Nothing stops you from writing code to modify the locking object itself, or from accessing any other object. YOU are responsible for making your sure your code respect the locks, and always acquires a lock when writing to a shared object.

Otherwise you're going to have a non-deterministic outcome like you've seen with this code, or what the spec-writers like to call 'undefined behavior'. Here Be Dragons (in the form of bugs you'll have endless trouble with).

Answer 3

You need to join the threads earlier:

static void Main(string[] args)
    {
        int n = 0;

        var up = new Thread(() =>
        {
            for (int i = 0; i < 1000000; i++)
            {
                n++;
            }
        });

        up.Start();
        up.Join();

        for (int i = 0; i < 1000000; i++)
        {
            n--;
        }


        Console.WriteLine(n);

        Console.ReadLine();
    }

Answer 4

Yes, up.Join() will ensure that both of the loops end before WriteLine is called.

However, what is happening is that the both of the loops are being executed simultaneously, each one in it's own thread.

The switching between the two threads is done all the time by the operation system, and each program run will show a different switching timing set.

You should also be aware that n-- and n++ are not atomic operations, and are actually being compiled to 3 sub-operations, e.g.:

Take value from memory
Increase it by one
Put value in memory

The last piece of the puzzle, is that the thread context switching can occur inside the n++ or n--, between any of the above 3 operations.

That is why the final value is non-deterministic.