How is it possible for some threads to never execute?

Question

int x = 0 // global shared variable
T1: for (i=0; i++; i<100) x++;
T2: x++ // no loop, just one increment

T1 and T2 are separate threads. I am told the final value of x can be ANYTHING from the values of 1 and 101. How is this possible? I am wondering how this could possibly just be 1.

Obviously, something fails in the execution sequence, but I'm wondering what.

Assuming an arbitrary language – Ryan Shocker Mar 22 '16 at 18:22 — Ryan Shocker, Mar 22 '16 at 18:22

score 6 · Accepted Answer · edited May 23 '17 at 12:00

6

x++ is not atomic operation (at least in most languages), this operation actually works like this:

tmp = x;
tmp = tmp + 1;
x = tmp;

now assume next execution order:

T2: tmp = x; // tmp is 0
T1: run all loop iterations, finally x is 100
T2: tmp = tmp+1; x = tmp; // x is 1

to get any other number, imagine next order:

T1: started loop, at some point x is 45
T2: tmp = x; // tmp is 45
T1: finished loop, x is 100
T2: tmp = tmp+1; x = tmp; // x is 46

edited May 23 '17 at 12:00

Community

1
1

answered Mar 22 '16 at 18:24

Iłya Bursov

23,342
4
33
57

Thanks! So, how is it possible to end at some number, say 46? – Ryan Shocker Mar 22 '16 at 18:32
Thanks a lot, appreciate it! – Ryan Shocker Mar 22 '16 at 18:41

score 0 · Answer 2 · edited May 23 '17 at 12:00

0

~~The reason for this behavior is memory caching.~~ Since threads can be executed on independent cpu's following situation is possible:

T1: loads x value
T2: loads x value
T1: runs loop 10 times (T1_x=10)
T2: increments (T2_x=1)
T1: saves value 10 to memory
T2: saves value 1 to memory

This is why you need thread synchronization. You can read more here: Mutex example / tutorial?

Thank you @Lashane for correction.

edited May 23 '17 at 12:00

Community

1
1

answered Mar 22 '16 at 18:34

Michal Partyka

49
4

what is memory caching? – Iłya Bursov Mar 22 '16 at 18:37
CPU has a very fast built in memory called cache. Each modern CPU used in a PC has it. Take [Intel web page](http://ark.intel.com/products/family/75023/4th-Generation-Intel-Core-i7-Processors#@All) as an example. You can find more info here https://en.wikipedia.org/wiki/CPU_cache – Michal Partyka Mar 22 '16 at 18:46
you want to say - that for CPUs without cache - we will not be able to get 1? – Iłya Bursov Mar 22 '16 at 18:49
before answer please read [how cpu cache actually works](https://en.wikipedia.org/wiki/Cache_coherence) and why it is not the case here – Iłya Bursov Mar 22 '16 at 18:50
even for single cpu - situation with 1 at the end is possible – Iłya Bursov Mar 22 '16 at 19:08
Dear @Lashane, I agree - the reason for this behavior is thread preemption. But can you explain the low level mechanics of the tmp variable from your example? I think we both agree, that one of possibilities is that the value is stored in CPU register, when context is switched. Is this the only possible reason for tmp existence? – Michal Partyka Mar 22 '16 at 19:18
for low level - right, tmp variable can be well known register (like ax/eax for x86), also some [risc cpus does not control pipeline execution](https://en.wikipedia.org/wiki/Instruction_pipelining#Workarounds) (it is up to developer/compiler), for high-level - java works as stack machine, so it could "pop" old value before any modifications by other thread and store it in ordinary ram – Iłya Bursov Mar 22 '16 at 19:31

How is it possible for some threads to never execute?

2 Answers2