Does a correctly synchronized program still allow data race?(Part I)

Question

There are two conclusions from JLS:

• C1: If a program is free of data races, then all executions of the program will appear to be sequentially consistent: data-race-free => sequentially consistent
• C2: If a program is correctly synchronized, then all executions of the program will appear to be sequentially consistent: correctly synchronized => sequentially consistent

If the converse of C1 is true, then we can conclude that:

• C3: If a program is correctly synchronized, then it is free of data races: correctly synchronized => data-race-free

But unfortunately, there is no such statement in the JLS, so I get to the fourth conclusion:

• C4: A program can be correctly synchronized and have data races.

But I am not satisfied with this approach and want to get a proof that this conclusion is true (or false), even in an informal way or in sample way.

First of all, I think a code segment that shows a sequentially consistent execution of a multi-threaded program that contains a data race is helpful to understand and resolve this problem.

After serious consideration, I still can not find a proper sample. So would you please give me such a code segment?

Answer 1

A good example could be String's hashcode:

private int hash; // Default to 0

public int hashCode() {
    int h = hash;
    if (h == 0 && count > 0) {
        int off = offset;
        char val[] = value;
        int len = count;

        for (int i = 0; i < len; i++) {
            h = 31*h + val[off++];
        }
        hash = h;
    }
    return h;
}

There is a data race here as hash can be written and read by different threads and there is no happens-before relationship (no synchronization).

However the program is sequentially consistent because it is impossible for a thread to see a hashcode which is not the actual hashcode of the string (when a thread executes the hashcode method, it can either see 0 and recalculate the value, which is deterministic, or it sees a valid value). This works because int writes are atomic.

EDIT

This (almost) same code is broken and could return a hashcode of 0:

public int hashCode() {
    if (hash == 0 && count > 0) { //(1)
        int h = hash;
        int off = offset;
        char val[] = value;
        int len = count;

        for (int i = 0; i < len; i++) {
            h = 31*h + val[off++];
        }
        hash = h;
    }
    return hash; //(2)
}

as (1) and (2) could be reordered: (1) could read a non null value while (2) would read 0. That can't happen in the first example because the calculation is made on the local variable and the return value is also that local variable, which, by definition, is thread safe.

EDIT 2

Regarding your proposition C4, I don't think it is possible:

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

If a program is correctly synchronized, then all executions of the program will appear to be sequentially consistent (§17.4.3).

So if a program is correctly synchronized:

• all the executions appear sequentially consistent.
• all sequentially consistent executions are free of data races

So we can conclude that all executions are free of data races and therefore the program is free of data races.