www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Shared and race conditions

reply Wanderer <d-wanderer hitbts.com> writes:
I'm trying to simulate a race condition in D with the following 
code:

(https://run.dlang.io/is/RfOX0I)

```
import std.stdio;
import core.thread;
import std.concurrency;

shared struct IdGen(T)
{
     T id;

     this(T start)
     {
         id = start;
     }

     T next()
     {
         id = id.next();
         return id;
     }
}

struct MyId
{
     uint num;

     shared MyId next()
     {
         return MyId(num + 1);
     }
}

static void getId(shared IdGen!(MyId)* g)
{
     writeln("next: ", g.next());
     writeln("next: ", g.next());
}

void main()
{
     MyId start = {0};
     auto g = IdGen!(MyId)(start);

     auto num = 12;
     for (auto i = 0; i < num; i++)
     {
         spawn(&getId, &g);
     }

     thread_joinAll();
     writeln("Done");
}
```

But all I get is correct IDs without any sign of a race (i.e. 
duplicate ids).
Does compiler add synchronization for `shared` data?
Nov 29 2017
next sibling parent reply Michael <michael toohuman.io> writes:
On Wednesday, 29 November 2017 at 16:13:13 UTC, Wanderer wrote:

 I'm trying to simulate a race condition in D with the following 
 code:

 (https://run.dlang.io/is/RfOX0I)

 ```
 import std.stdio;
 import core.thread;
 import std.concurrency;

 shared struct IdGen(T)
 {
     T id;

     this(T start)
     {
         id = start;
     }

     T next()
     {
         id = id.next();
         return id;
     }
 }

 struct MyId
 {
     uint num;

     shared MyId next()
     {
         return MyId(num + 1);
     }
 }

 static void getId(shared IdGen!(MyId)* g)
 {
     writeln("next: ", g.next());
     writeln("next: ", g.next());
 }

 void main()
 {
     MyId start = {0};
     auto g = IdGen!(MyId)(start);

     auto num = 12;
     for (auto i = 0; i < num; i++)
     {
         spawn(&getId, &g);
     }

     thread_joinAll();
     writeln("Done");
 }
 ```

 But all I get is correct IDs without any sign of a race (i.e. 
 duplicate ids).
 Does compiler add synchronization for `shared` data?


I unfortunately cannot answer your question but I am noticing 
that running the code with DMD gives you an unordered sequence of 
IDs, but running with DMD-nightly gives you a sequence in the 
correct order. I wonder what has changed to do with threads that 
causes this difference between compiler versions.
Nov 29 2017
next sibling parent Michael <michael toohuman.io> writes:
On Wednesday, 29 November 2017 at 16:19:05 UTC, Michael wrote:

 On Wednesday, 29 November 2017 at 16:13:13 UTC, Wanderer wrote:

 [...]


 I unfortunately cannot answer your question but I am noticing 
 that running the code with DMD gives you an unordered sequence 
 of IDs, but running with DMD-nightly gives you a sequence in 
 the correct order. I wonder what has changed to do with threads 
 that causes this difference between compiler versions.


Just to add to this, the page here:
https://tour.dlang.org/tour/en/multithreading/synchronization-sharing
does suggest that the compiler will automatically create critical 
sections when it can i.e. wrapping a section in

synchronized {
     importStuff();
}
Nov 29 2017
prev sibling parent Wanderer <d-wanderer hitbts.com> writes:
On Wednesday, 29 November 2017 at 16:19:05 UTC, Michael wrote:

 On Wednesday, 29 November 2017 at 16:13:13 UTC, Wanderer wrote:

 [...]


 I unfortunately cannot answer your question but I am noticing 
 that running the code with DMD gives you an unordered sequence 
 of IDs, but running with DMD-nightly gives you a sequence in 
 the correct order. I wonder what has changed to do with threads 
 that causes this difference between compiler versions.


The "unordered" output is completely fine, as I assume runtime 
does not guarantee the order of execution of logical threads 
(order is different between ldc and dmd as well).
Nov 29 2017
prev sibling next sibling parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 11/29/17 11:13 AM, Wanderer wrote:

 I'm trying to simulate a race condition in D with the following code:


[snip]


 But all I get is correct IDs without any sign of a race (i.e. duplicate 
 ids).
 Does compiler add synchronization for `shared` data?


Using the compiler switch -vcg-ast, I see no synchronization of these 
methods.

Races are by definition unpredictable. What has to happen in your case 
is one of 2 things:

1. The thread context switches out after the next() call, but before the 
assignment. This is very very unlikely given the small number of 
instructions the thread executes (the OS isn't about to context switch 
out a thread it just switched into execution mode).
2. Two threads running on separate cores both assign at the exact same 
time, and they race on the data, one overwriting the other in memory.

Note that executing 12 threads in concurrency isn't going to be a very 
stressful case for this race. Yes, it's probably more than the cores on 
your machine, but it's also a very small number of threads.

Note also that even when there is a possibility of a race, it may be a 
long time before you see any errant behavior. I'd try more threads, and 
run the whole test in a loop. At the end of each loop iteration (after 
all the threads are completed), verify that the number has incremented 
by the correct amount. Stop only after it sees a race has happened.

You may run for minutes until you see a race. You may never see one. 
That's the nature of the thing :)

-Steve
Nov 29 2017
next sibling parent reply Wanderer <d-wanderer hitbts.com> writes:
On Wednesday, 29 November 2017 at 16:33:50 UTC, Steven 
Schveighoffer wrote:

 On 11/29/17 11:13 AM, Wanderer wrote:

 [...]


 [snip]


 [...]


 Using the compiler switch -vcg-ast, I see no synchronization of 
 these methods.

 [...]


That's what I assume, I was just lucky not to see a race.
Thanks for `-vcg-ast` switch! Really helpful, and it answered my 
questions as no syncronization code was added.
Nov 29 2017
parent Steven Schveighoffer <schveiguy yahoo.com> writes:
On 11/29/17 11:46 AM, Wanderer wrote:

 On Wednesday, 29 November 2017 at 16:33:50 UTC, Steven Schveighoffer wrote:

 On 11/29/17 11:13 AM, Wanderer wrote:

 [...]


 [snip]


 [...]


 Using the compiler switch -vcg-ast, I see no synchronization of these 
 methods.

 [...]


 
 That's what I assume, I was just lucky not to see a race.
 Thanks for `-vcg-ast` switch! Really helpful, and it answered my 
 questions as no syncronization code was added.


FYI, I ran this about 15 times, finally got one:

Stevens-MacBook-Pro:testd steves$ ./testshared
next: MyId(1)
next: MyId(2)
next: MyId(3)
next: MyId(4)
next: MyId(5)
next: MyId(6)
next: MyId(7)
next: MyId(8)
next: MyId(9)
next: MyId(10)
next: MyId(11)
next: MyId(12)
next: MyId(12) <=== race
next: MyId(13)
next: MyId(14)
next: MyId(15)
next: MyId(16)
next: MyId(17)
next: MyId(18)
next: MyId(19)
next: MyId(20)
next: MyId(21)
next: MyId(22)
next: MyId(23)
Done

-Steve
Nov 29 2017
prev sibling parent reply Michael <michael toohuman.io> writes:
On Wednesday, 29 November 2017 at 16:33:50 UTC, Steven 
Schveighoffer wrote:

 On 11/29/17 11:13 AM, Wanderer wrote:

 [...]


 [snip]


 [...]


 Using the compiler switch -vcg-ast, I see no synchronization of 
 these methods.

 [...]


Any idea what has changed in DMD-nightly to retain the correct 
ordering of IDs?
Nov 29 2017
parent Steven Schveighoffer <schveiguy yahoo.com> writes:
On 11/29/17 11:51 AM, Michael wrote:

 On Wednesday, 29 November 2017 at 16:33:50 UTC, Steven Schveighoffer wrote:

 On 11/29/17 11:13 AM, Wanderer wrote:

 [...]


 [snip]


 [...]


 Using the compiler switch -vcg-ast, I see no synchronization of these 
 methods.

 [...]


 
 Any idea what has changed in DMD-nightly to retain the correct ordering 
 of IDs?


No idea. Perhaps it was another factor, as machine busyness could affect 
the ordering.

The ordering of when the ids are fetched is pretty much the same (as 
long as no race has happened). It's really the printing of the ids that 
might be affected.

-Steve
Nov 29 2017
prev sibling next sibling parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 11/29/17 11:13 AM, Wanderer wrote:

 I'm trying to simulate a race condition in D with the following code:
 
 (https://run.dlang.io/is/RfOX0I)


One word of caution, I think the running of your code on run.dlang.io is 
cached. Refreshing doesn't make it re-run.

https://run.dlang.io/is/k0LhQA

-Steve
Nov 29 2017
next sibling parent Wanderer <d-wanderer hitbts.com> writes:
On Wednesday, 29 November 2017 at 17:03:42 UTC, Steven 
Schveighoffer wrote:

 On 11/29/17 11:13 AM, Wanderer wrote:

 I'm trying to simulate a race condition in D with the 
 following code:
 
 (https://run.dlang.io/is/RfOX0I)


 One word of caution, I think the running of your code on 
 run.dlang.io is cached. Refreshing doesn't make it re-run.

 https://run.dlang.io/is/k0LhQA

 -Steve


I was using this just for the reference, as I've noticed caching 
as well.
Thanks Steve, for spending time and actually hitting a race!
Nov 29 2017
prev sibling parent Michael <michael toohuman.io> writes:
On Wednesday, 29 November 2017 at 17:03:42 UTC, Steven 
Schveighoffer wrote:

 On 11/29/17 11:13 AM, Wanderer wrote:

 I'm trying to simulate a race condition in D with the 
 following code:
 
 (https://run.dlang.io/is/RfOX0I)


 One word of caution, I think the running of your code on 
 run.dlang.io is cached. Refreshing doesn't make it re-run.

 https://run.dlang.io/is/k0LhQA

 -Steve


Ah good catch.
Nov 29 2017
prev sibling next sibling parent Jacob Carlborg <doob me.com> writes:
On 2017-11-29 17:13, Wanderer wrote:

 I'm trying to simulate a race condition in D with the following code:


I'm not sure what your end goal is but perhaps you could try to see if 
the LLVM thread sanitizer [1] can be used with LDC. The thread sanitizer 
can identify race conditions even though they're not actually triggered [2].

It can be quite difficult to simulate a race condition because x86 has 
an almost strong memory model.

[1] https://clang.llvm.org/docs/ThreadSanitizer.html
[2] https://developer.apple.com/videos/play/wwdc2016/412/ 16:00

-- 
/Jacob Carlborg
Nov 30 2017
prev sibling parent reply Kagamin <spam here.lot> writes:
On Wednesday, 29 November 2017 at 16:13:13 UTC, Wanderer wrote:

 static void getId(shared IdGen!(MyId)* g)
 {
     writeln("next: ", g.next());
     writeln("next: ", g.next());
 }


writeln synchronizes on stdout, so your code is mostly 
serialized, good example of a very subtle race condition.
Dec 04 2017
parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 12/4/17 4:09 AM, Kagamin wrote:

 On Wednesday, 29 November 2017 at 16:13:13 UTC, Wanderer wrote:

 static void getId(shared IdGen!(MyId)* g)
 {
     writeln("next: ", g.next());
     writeln("next: ", g.next());
 }


 
 writeln synchronizes on stdout, so your code is mostly serialized, good 
 example of a very subtle race condition.


Well, this is just why you don't see output items that are mixed lines 
(i.e. "nenext: 1\nxt: 2\n" instead of "next: 1\nnext: 2\n")

The next calls are not synchronized.

-Steve
Dec 04 2017
parent reply Kagamin <spam here.lot> writes:
A lock on stdout works as a barrier: threads may hit it 
simultaneously, but pass it one by one in a queue with a time gap 
between them.
Dec 04 2017
parent Kagamin <spam here.lot> writes:
Uh, a bottleneck, not a barrier.
Dec 04 2017