What's "sequentially consistent executions are free of data races"?

Question

In JLS, §17.4.5. Happens-before Order, it says that

A program is correctly synchronized if and only if all sequentially consistent executions are free of data races.

It only give us definition about "sequentially consistent", it does not give us definition about "sequentially consistent executions". Only after knowing about what is "sequentially consistent executions", we may make further discussion about the topic.

So what's "sequentially consistent executions" and what's "sequentially consistent executions are free of data races"?

Mullin

Answer 1

An execution has a very simple formal definition: it is simply a total ordering on the set of all memory actions that is under consideration.

A sequentially consistent execution is represented by any total ordering on actions which is sequentially consistent.

The term "free of data races" is also precisely defined by the JLS.

Note that the JLS does not require sequential consistency. In fact, the whole formalism of happens-before exists in order to define precisely the terms under which sequentially inconsistent executions can maintain an illusion of sequential consistency.

Damaraland

Would you please give me an example about sequentially consistent executions in which it contains data race? Thanks a lot. – Mullin

This is very simple: global int i is written by thread t1, then read by t2. t2 reads the value written by t1 so the execution is sequentially consistent. However, there is no happens-before ordering between these actions so there's a data race. Note that happens-before doesn't come about automatically, just because there's a time ordering of these events. – Damaraland

Thanks for your reply. one step further, could you please give me such an example: all sequentially consistent executions of a program is data race free, but the normal execution of such program contains data race. Thanks a lot. – Mullin

I have to go, see you next day. – Mullin

There is no such an example, which is precisely the point of it all: a properly synchronized program can be sequentially inconsistent without introducing a data race. That's the basis for all compiler optimizations. – Damaraland

Answer 2

sequentially consistent executions means basically that each read operation on a variable sees the last write operation on that variable, no matter on which thread or processor the read/write operations are performed.

However, the JLS does not guarantee sequential consistency out of the box. Programmers have to achieve this consistency by proper synchronisation. Without synchronisation, threads may see inappropriate data, e.g. data that is being modified by another thread at the same time. This is called "data race".

Cedar

I'm confused about your answer, so may I modify your definition as follows: sequentially consistent executions means basically ... on that variable in program order. If I'm not right, please point out. – Mullin

sequentially consistent executions means basically that each read operation on a variable sees the last write operation on that variable in a total execution order which is consistent with program order. Am I right? – Mullin

Yes, that's basically the definition of §17.4.3 – Cedar

Because there is a total order for all operations, operations in same thread obey program order, operations in different thread obey total order. I heard from someone said that sequentially consistent executions is just execution in a single CPU computer. I'm not sure whether it is true or not. So what's your opinion? – Mullin

This is not true. Even with a single CPU there's multithreading and a possibility of data races. – Damaraland

Sequentially consistent ordering is quite precisely defined. To put it more bluntly, it is every interleaving of actions by various threads such that the actions of each thread individually maintain that thread's program order, plus the requirement that each read action always observes the nearest preceding write action. – Damaraland

Also note that most real-world executions are not sequentially consistent, but the extent to which they fail at it is precisely controlled by the happens-before relationship, so as not to cause observable bugs. – Damaraland

@MarkoTopolnik, different threads also obey a total order, so it just like execution in a uni-processor computer. Am I right? – Mullin

@MarkoTopolnik, because my english is not good enough, please check whether my understanding is right: in "which they fail at it", "they" means "most real-world executions", "it" means "sequentially consistent". Thanks a lot. – Mullin

Yes, you got it right. Clarifying some more: an execution order is always a total order. That order may, however, fail to be sequentially consistent. Also, the execution order is not necessarily consistent with the program order. – Damaraland

@MarkoTopolnik, you said that an execution order is always a total order, so how about execution order of two threads? – Mullin

@MarkoTopolnik, I agree with your last two conclusions, but not the first: an execution order is always a total order. So could you please explain your first conclusion in more detail? Thanks a lot. – Mullin

Let's quote the JLS: "A set of actions is sequentially consistent if all actions occur in a total order (the execution order) that is consistent with program order". So you see that excution order is indeed a total order. – Damaraland

But this is true only when there is a sequentially consistent. – Mullin

That is irrelevat. Concentrate on the words "total order (the execution order)"---that means that execution order is defined as a total order. The only thing that is open is that the actions may not occur in a total order, which would mean that there is no execution order. I don't think any such thing is really implied, though. – Damaraland

If there is no execution order, how does a program execute? – Mullin

I have to go, see you next day. – Mullin

For future reference: a read needs to see the most recent write before it in the happens-before order and not in the real-time order. Keep in mind that reads/writes can be skewed under SC and do not need to respect the real-time order. – Extremely

Answer 3

To ensure that two actions are free of a data race, you must establish a happens-before relationship between the two actions using any of the five conditions specified in §17.4.5 and recapitulated in Memory Consistency Properties. Once you do that, your program is correctly synchronized with respect to those two actions. All executions of that program will appear to be sequentially consistent, and you can safely ignore any re-ordering permitted in §17.4.3. Programs and Program Order.

Retread

would you please give me an example about sequentially consistent executions in which it contains data race? Thanks a lot. – Mullin

Contrast Example 17.4.5-1. Happens-before Consistency with Example 17.4.8-1. Happens-before Consistency Is Not Sufficient. – Retread

I have to go, see you next day. – Mullin

Answer 4

1) Sequential Consistent executions (by def.): the result of any execution is the same as if the operations of all the processors were executed in some sequential order, and the operations of each individual processor appear in this sequence in the order specified by its program

2) Data Race is a situation when concurrent operations accesses a shared memory location, of which at least one is a write.

3) So if the executions do not appear sequentially consistent their result will differ from the program result or would demonstrate the unexpected behavior. And such executions we don't want.

4) If to suppose that there is a seq. con. execution which is not free of a data race, then it means that there exists another fork of this seq. con. execution which reorders accesses in data race point and leads to the different program result. And then, these executions are not sequentially consistent with the program, or

5) the program allows seq. con. executions to have counterintuitive behaviors and unexpected results, and thus, is not correctly synchronized.

Virgo