May a correct program be incorrectly synchronized?

Question

In answer of Does a correctly synchronized program still allow data race?(Part I), it gives us a good example: all executions of a program appear to be sequentially consistent, but it still has data race. It tells us why another direction of following conclusion in JLS is not true:

If a program has no data races, then all executions of the program will appear to be sequentially consistent.

Now take a look at another conclucsion in JLS:

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

According to this conclusion,above example is not correctly synchronized, so may a correct program be incorrectly synchronized?

Now **THAT**'s what I call "soon"! – Marko Topolnik Aug 22 '12 at 12:35 — Marko Topolnik, Aug 22 '12 at 12:35

score 2 · Accepted Answer · answered Aug 22 '12 at 12:37

You would probably need to define first what a correct program is (not easy). JCiP proposes (in a different context):

a program is correct if it conforms to its specifications.

Using that definition, the example provided is correct. However, it is not correctly synchronized (there is a data race on hash).

==> a correct program may be incorrectly synchronized, as proved by that example.

Peter Lawrey · Answer 2 · 2012-08-23T07:22:30.347

1

While this doesn't appear to answer the OP's question, I am keeping it for the comments.

You can get a number of race conditions using synchronized collections. e.g.

Vector<Integer> vector = ...
vector.add(1);

vector.set(0, 1 + vector.get(0));

Each method is synchronized and yet there is a race condition. This is because you can have threads T1 and T2 doing.

T1: int tmp1 = vector.get(0);
T2: int tmp2 = vector.get(0);
T1: vector.set(0, 1 + tmp1);
T2: vector.set(0, 1 + tmp2);

In this case tmp1 == tmp2 which is not normally the case.

To synchronize this correctly you would do the following to ensure you hold the lock the whole time.

synchronized(vector) {
    vector.set(0, 1 + vector.get(0));
}

edited Aug 23 '12 at 07:22

answered Aug 22 '12 at 12:37

Peter Lawrey

525,659
79
751
1,130

Peter, you are not demonstrating an instance of a *data race*, which is what OP is asking about. OP is really bent on the precise usage of terms, he's been reading and re-reading the JLS in the past days to the last letter :) – Marko Topolnik Aug 22 '12 at 12:39
@MarkoTopolnik Ok, can you tell what the difference between a `race condition` and a `data race` ? – Peter Lawrey Aug 22 '12 at 12:45
A *data race* is only a very narrow kind of a *race condition* involving conflicting inter-thread actions on non-volatile variables that are not ordered by the *happens-before*. In your code all accesses are ordered. – Marko Topolnik Aug 22 '12 at 12:51
Do you mean where you have `a = 3; b = 5;` and you see that `b = 5` before you see `a = 3` ? – Peter Lawrey Aug 22 '12 at 12:54
Thank you for clearing up that point, but I thought the question was " may a correct program be incorrectly synchronized?" – Peter Lawrey Aug 22 '12 at 12:56
The point is, **your program is correctly synchronized** as it **doesn't contain data races**. OP wants an incorrectly synchronized program, but that is still *correct*. – Marko Topolnik Aug 22 '12 at 12:57
@MarkoTopolnik It is correct in term of a data race, but still using synchronized incorrectly and fails the `sequentially consistent executions` test. – Peter Lawrey Aug 22 '12 at 13:00
2

Not according to the strict definitions of the JLS, which the OP has in mind. You in fact demonstrate the opposite of OP's request: a **correctly synchronized** program ([JLS 17.4.5](http://docs.oracle.com/javase/specs/jls/se7/html/jls-17.html#jls-17.4.5)) which is **incorrect**. – Marko Topolnik Aug 22 '12 at 13:10
1

BTW as your program is correctly synchronized, all its executions will appear to be sequentially consistent, even though the behavior will not be as intended (it will be incorrect from a requirements standpoint). – Marko Topolnik Aug 22 '12 at 13:11
@PeterLawrey, I have made further edit on your answer. Please don't roll it back but correct it, so readers like me and beginner can learn more from your modification. – newman Aug 23 '12 at 05:40
@PeterLawrey. I'm not sure whehter my understanding is correct or not, if it is not correct, please correct it. Your program is correct if call on vector.set() is atomic. As call on vector.set() like vector.set(0, 1 + vector.get(0)) is not atomic, this program is not correct. However, according to definition in JLS, this program is correctly synchronized. The reason why this program is not correct is that this program contains race condition, whereas it is out of the scope of JMM defined in JLS. Is my understanding correct? Thanks a lot. – newman Aug 23 '12 at 06:00
@newman That sounds right. Whether this is an example of incorrect synchronization is under question. IMHO its synchronized incorrectly but I don't know if that is what the author had in mind. – Peter Lawrey Aug 23 '12 at 07:21

May a correct program be incorrectly synchronized?

2 Answers2