4

Possible Duplicate:
Are incrementers / decrementers (var++, var--) etc thread safe?

Can you describe for me, at the assembly code level, why incrementing a value from two different threads is not considered safe on a single core machine?

Peter Cordes
  • 328,167
  • 45
  • 605
  • 847
Dejas
  • 3,511
  • 4
  • 24
  • 36
  • For multi-core machines especially, see [Can num++ be atomic for 'int num'?](https://stackoverflow.com/q/39393850). It does mention that `num++` can compile to multiple instructions, but spends more time on how even a single instruction isn't atomic wrt. other threads unless it's a special atomic RMW instruction. – Peter Cordes May 14 '20 at 14:10

7 Answers7

11

Consider the instructions that might be generated for a statement like i++. Of course this will depend upon your architecture/instruction set, but it will probably be something along the lines of:

LOAD    @i, r0    ;load the value of 'i' into a register from memory
ADD     r0, 1     ;increment the value in the register
STORE   r0, @i    ;write the updated value back to memory

Now consider how multithreading would be implemented in an operating-system, regardless of how many cores the machine has. At the most basic level, the OS is going to need some facility to interrupt the execution of the current thread, save its state, and perform a context switch to a different thread. The OS has no automatic way of knowing which instructions inside of a user thread should be treated as an atomic operation, and has the ability to initiate a context switch between any two instructions.

So what happens if the OS performs a context switch from one thread to the other between LOAD and ADD? Let's say that i started out with a value of 0, so r0 will be set to 0 when the first thread gets swapped out. The OS will save this value as part of that thread's state. Now the second thread runs, and performs the same LOAD statement. The value in memory is still 0, so r0 gets 0 loaded into it again. The thread increments the value and writes it back to memory, setting the value of i to 1. Now the first thread resumes execution, and the operating-system restores the value of r0 to 0 as part of its context switch. The first thread now performs its increment, setting r0 to 1, and the value of 1 gets stored in i again. Now the value of i is incorrect because two increments have been applied, but the value has only increased by 1.

So in a nutshell, even though i++ is a single statement in a high-level language, it generates multiple assembly-language instructions, and those instructions will not be treated as atomic by the operating-system/runtime environment unless you add extra synchronization logic around them.

aroth
  • 54,026
  • 20
  • 135
  • 176
  • Thanks @aroth. I was a little confused about whether, when the OS resumed the first thread, it would invalidate R0's contents and reread from memory or not. It's now clear to me that R0 will be whatever the value R0 used to be irrespective of what other threads may have done. – Dejas May 19 '11 at 01:40
  • 3
    On x86 this can actually be done in a single instruction, e.g "inc [eax]" where eax is the register pointing to the memory containing "i". This assumes "i" is even stored in memory (not optimized away to registers only), and that the compiler chooses to use an "inc" instruction. So, basically you can't rely on this even on architectures with single instruction memory increments. – John Ripley May 19 '11 at 01:47
  • Note that this question is about single-core machines specifically. `inc dword [eax]` *is* atomic wrt. other threads on a single core machine (or with all threads pinned to the same CPU, or between a thread and a signal handler that runs in the same thread). Because interrupts (and thus context switches) can only happen before or after an instruction, not during. On a multi-core machine it's of course not thread-safe without `lock inc dword [eax]`. [Can num++ be atomic for 'int num'?](https://stackoverflow.com/q/39393850) – Peter Cordes Nov 06 '22 at 02:36
9

i++ has three operations:

  • Fetch i into a register
  • Increment the register
  • Write it back to i

In between these operations, the thread might be interrupted by the scheduler so that a different thread can run (and modify i).

SLaks
  • 868,454
  • 176
  • 1,908
  • 1,964
  • ok, so, just to make sure I understand, if some thread has the contents of a memory address in a register and that thread is switched out and back in we will not update that value in the register with the current contents of that memory address but instead use whatever value was in that register prior to the switch? – Dejas May 19 '11 at 01:33
  • @Dejas: Of course. Registers aren't linked to memory locations. – SLaks May 19 '11 at 01:36
  • Thanks. I thought the OS might be smart enough to track what the origin of R0's contents was and as such invalidate R0 when the first thread resumed. – Dejas May 19 '11 at 01:42
  • 1
    @Dejas: Smart enough? Doing that would break code all over the place and make context-switching much more expensive. – Brian May 19 '11 at 14:50
2

Your question is tagged assembler but asks about i++. You have no guarantee that an i++ in your C code will compile to a single instruction that changes memory. If you have multiple threads that load i from memory with one instruction, increments it with another and writes it back to memory with a third, a thread switch between the first and third of those can cause some updates to i to be lost.

Baffe Boyois
  • 2,120
  • 15
  • 15
1

Thread one reads the old value

Timer interrupt goes off

Kernel resumes thread two

thread 2 reads old value

thread two increments it

thread two writes it

timer goes off

kernel resumes thread 1

thread one increments

thread one stores

now you're one behind.

bmargulies
  • 97,814
  • 39
  • 186
  • 310
1

If the processor does not have a single instruction that can increment the contents of a memory location, the compiler would have to do something like generating:

 load      location, registerA
 increment registerA
 store     registerA, location

So even if any single instruction is atomic, the sequence is not. And even if there is a single

increment location

instruction there is no guarantee a compiler would use it. For example, the compiler might have done some optimizing and is using a register to hold some frequently-used value, only storing it back to memory at times mandated by any sequencing rules in the compiler's language's memory model.

QuantumMechanic
  • 13,795
  • 4
  • 45
  • 66
1

The sequence of the instructions executed from 2 threads on a single core cannot be predicted. The following is a possible sequence, when both threads attempt to do i++, but the effect is equivalent to doing i++ once:

load i        # thread 1
system interrupt
load i        # thread 2, now i++ in thread 1 is not complete
increment i   # thread 2
store i       # thread 2
system interrupt
increment i   # thread 1, sees the same un-incremented older value that was loaded before thread 1 was interrupted.
store i
Binita Bharati
  • 5,239
  • 1
  • 43
  • 24
Chang Peng
  • 1,052
  • 8
  • 14
  • This would be clearer if you wrote it as `increment register` or `temporary` or something, to make it clear you're incrementing the value from the load-result, *not* incrementing the shared memory location `i`. – Peter Cordes Nov 06 '22 at 02:33
0

What stops the system from descheduling one thread between the time it read the value and the time it wrote the value? Sure, it is less likely to happen, but on standard operating systems the kernel could get an interrupt at any time and decide that the other thread deserves to run. At that point, both threads would have read the same value and both will increment identically. However, the second thread could run for another time slice, incrementing thousands of times, and then when the first thread gets rescheduled, would zap all of the forward progress by the second thread by writing the stale value.

Seth Robertson
  • 30,608
  • 7
  • 64
  • 57