views:

629

answers:

8

I've just written a method that is called by multiple threads simultaneously and I need to keep track of when all the threads have completed, the code uses this pattern:

private void RunReport()
{
   _reportsRunning++;

   try
   {
       //code to run the report
   }
   finally
   {
       _reportsRunning--;
   }
}

This is the only place within the code that _reportsRunning's value is changed, and the method takes about a second to run.

Occasionally when I have more than six or so threads running reports together the final result for _reportsRunning can get down to -1, if I wrap the calls to _runningReports++ and _runningReports-- in a lock then the behaviour appears to be correct and consistant.

So, to the question: When I was learning multithreading in C++ I was taught that you didn't need to synchronize calls to increment and decrement operations because they were always one assembly instruction and therefore it was impossible for the thread to be switched out mid-call. Was I taught correctly, and if so how come that doesn't hold true for C#?

+16  A: 

Yes, a ++ operator is not atomic in C# (and I doubt if it is guaranteed to be atomic in C++) so your counting is subject to race conditions.

Use Interlocked.Increment and .Decrement

System.Threading.Interlocked.Increment(ref _reportsRunning);
try 
{
  ...
}
finally
{
   System.Threading.Interlocked.Decrement(ref _reportsRunning);
}
Henk Holterman
Thanks for the fast response. I've never seen those methods before - very helpful. Any idea if my lecturer was right to tell me that is is an atomic operation in C++?
Martin Harris
++ is not atomic in C++ as well.
aJ
It might haven been OK in som C++ implementations, but I wouldn't rely on it. In C# it is certainly not safe.
Henk Holterman
If your lecturer was referring to machine INCREMENT and DECREMENT instructions, it was correct. That is not guaranteed with `higher` level languages.
nik
C++ does not specify ANY atomic operations.
anon
Linux use atomic_t for supporting atomic integer operations. It is not atomic by default.
Here Be Wolves
don't know in C++, but in C on my intel mac, ++ increment is done with a single INCL operation <main+11>: incl -0x4(%rbp), which I guess is atomic (you cannot preempt a opcode execution). I would not put my hands on this, however, and I would lock anyway.
Stefano Borini
Stefano, right. Atomicity is the exception rather than the rule.
Henk Holterman
+2  A: 

No, you need to synchronize access. On Windows you can do this easily with InterlockedIncrement() and InterlockedDecrement(). I'm sure there are equivalents for other platforms.

EDIT: Just noticed the C# tag. Do what the other guy said. See also: http://stackoverflow.com/questions/680097/ive-heard-i-isnt-thread-safe-is-i-thread-safe

jeffamaphone
Thanks, that's answered the other half of my question, seems I was taught wrong (or more likely misunderstood). Shame I can't accept both answers... Sorry.
Martin Harris
@Martin: No worries! I'm not here for glory and the points. Just trying to help out.
jeffamaphone
+3  A: 

You were taught wrong.

There does exist hardware with atomic integer increment, so it's possible that what you were taught was right for the hardware and compiler you were using at the time. But in general in C++ you can't even guarantee that incrementing a non-volatile variable writes memory consecutively with reading it, let alone atomically with reading.

Steve Jessop
+3  A: 

Incrementing the int is one instruction but what about loading the value in the register?

That's what i++ effectively does:

  1. load i into a register
    • increment the register
    • unload the register into i

As you can see there are 3 (this may be different on other platforms) instructions which in any stage the cpu can context switch into a different thread leaving your variable in an unknown state.

You should use Interlocked.Increment and Interlocked.Decrement to solve that.

Shay Erlichmen
x86 does have memory versions of increment and decrement that do all 3 steps in one instruction. But they're not atomic - there is no guarantee that other CPU's will see the correct results if they are also modifying the value.
Michael
+12  A: 

So, to the question: When I was learning multithreading in C++ I was taught that you didn't need to synchronize calls to increment and decrement operations because they were always one assembly instruction and therefore it was impossible for the thread to be switched out mid-call. Was I taught correctly, and if so how come that doesn't hold true for C#?

This is incredibly wrong.

On some architectures, like x86, there are single increment and decrement instructions. Many architectures do not have them and need to do separate loads and stores. Even on x86, there is no guarantee the compiler will generate the memory version of these instructions - it'll likely load into a register first, especially if it needs to do several operations with the result.

Even if the compiler could be guaranteed to always generate the memory version of increment and decrement on x86, that still does not guarantee atomicity - two CPU's could modify the variable simultaneously and get inconsistent results. The instruction would need the lock prefix to force it to be an atomic operation - compilers never emit the lock variant by default since it is less performant since it guarantees the action is atomic.

Consider the following x86 assembly instruction:

inc [i]

If I is initially 0 and the code is run on two threads on two cores, the value after both threads finish could legally be either 1 or 2, since there is no guarantee that one thread will complete its read before the other thread finishes its write, or that one thread's write will even be visible before the other threads read.

Changing this to:

lock inc [i]

Will result in getting a final value of 2.

Win32's InterlockedIncrement and InterlockedDecrement and .NET's Interlocked.Increment and Interlocked.Decrement result in doing the equivalent (possibly the exact same machine code) of lock inc.

Michael
+1  A: 

Any kind of increment/decrement operation in a higher level language (and yes, even C is higher level compared to machine instructions) is not atomic by nature. However, each processor platform usually has primitives that support various atomic operations.

If your lecturer was referring to machine instructions, Increment and Decrement operations are likely to be atomic. Yet, that is not always correct on the ever increasing multi-core platforms of today, unless they guarantee coherency.

The higher level languages usually implement support for atomic transactions using low level atomic machine instructions. This is provided as the interlock mechanism by the higher level API.

nik
A: 

x++ probably isn't atomic, but ++x might be (not sure offhand, but if you consider the difference between post- and pre-increment it should be clear why pre- is more amenable to atomicity).

A bigger point is, if these runs take a second to run each, the amount of time added by a lock is going to be noise compared to the runtime of the method itself. It's probably not worth monkeying with trying to remove the lock in this case - you've got a correct solution with locking, that will likely not have a visible difference in performance from the non-locking solution.

kyoryu
A: 

On a single-processor machine, if one isn't using virtual memory, x++ (rvalue ignored) is likely to translate into a single atomic INC instruction on x86 architectures (if x is long, the operation is only atomic when using a 32-bit compiler). Also, movsb/movsw/movsl are atomic ways of moving a byte/word/longword; a compiler isn't apt to use those as the normal way of assigning variables, but one could have an atomic-move utility function. It would be possible for a virtual memory manager to be written in such a way that those instructions would behave atomically if a page fault occurs on the write, but I don't think that's normally guaranteed.

On a multi-processor machine, all bets are off unless one uses explicit interlocked instructions (invokable via special library calls). The most versatile instruction which is commonly available is CompareExchange. That instruction will alter a memory location only if it contains an expected value; it will return the value it had when it decided whether or not to alter it. If one wishes to "xor" a variable with 1, one could do something like (in vb.net)

  Dim OldValue as Integer
  Do
    OldValue = Variable
  While Threading.Interlocked.CompareExchange(Variable, OldValue Xor 1, OldValue)  OldValue

This approach allows one to perform any sort of atomic update to a variable whose new value should depend on the old value. For certain common operations like increment and decrement, there are faster alternatives, but the CompareExchange allows one to implement other useful patterns as well.

Important caveats: (1) Keep the loop as short as possible; the longer the loop, the more likely it is that another task will hit the variable during the loop, and the more time will be wasted each time that happens; (2) a specified number of updates, divided arbitrarily among threads, will always complete, since the only way a thread can forced to re-execute the loop is if some other thread has made useful progress; if some threads can perform updates without making forward progress toward completion, however, the code may become live-locked.

supercat