java一个正确同步的程序是否仍然允许数据竞争？（第一部分）

Question

JLS得出了两个结论：

• C1：如果一个程序没有数据争用，那么该程序的所有执行看起来都是顺序一致的：data-race-free => sequentially consistent
• C2：如果一个程序被正确同步，那么该程序的所有执行看起来都是顺序一致的：correctly synchronized => sequentially consistent

如果C1的倒数为真，那么我们可以得出结论：

• C3：如果程序正确同步，那么它就没有数据争用：correctly synchronized => data-race-free

但不幸的是，JLS中没有这样的声明，因此我得出了第四个结论：

• C4：一个程序可以正确地同步并且有数据竞争

但我对这种方法并不满意，我想得到一个证据，证明这个结论是正确的（或错误的），即使是以非正式的方式或以抽样的方式

首先，我认为显示包含数据竞争的多线程程序顺序一致执行的代码段有助于理解和解决此问题

经过认真考虑，我仍然找不到合适的样品。那么你能给我一个这样的代码段吗

Answer 1

http://rsim.cs.illinois.edu/Pubs/popl05.pdf

证据似乎是这样的：

假设一个正确同步程序的执行包含数据竞争，我们可以找到一个包含数据竞争的顺序执行，这违反了“正确同步程序”的定义[C1]

因此，执行不能包含数据竞争。[C3]由此可以证明执行顺序是一致的。[C2]

所以C3是真的，它被用来证明C2

Answer 2

字符串的哈希代码就是一个很好的例子：

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;
}

这里有一个数据竞争，因为散列可以由不同的线程写入和读取，并且没有先发生后关系（没有同步）

但是，程序是顺序一致的，因为线程不可能看到不是字符串的实际哈希代码的哈希代码（当线程执行哈希代码方法时，它可以看到0并重新计算确定性值，或者看到有效值）。这是因为int写是原子的

编辑

此（几乎）相同的代码被破坏，可能返回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)
}

由于（1）和（2）可以重新排序：（1）可以读取非空值，而（2）可以读取0。在第一个示例中，这不会发生，因为计算是在局部变量上进行的，返回值也是该局部变量，根据定义，该局部变量是线程安全的

编辑2

关于你的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).

因此，如果程序已正确同步：

• 所有的执行顺序都是一致的
• 所有顺序一致的执行都没有数据争用

因此我们可以得出结论，所有执行都没有数据竞争，因此程序也没有数据竞争

Answer 3

竞赛条件意味着让你的程序的输出取决于谁先到达某一特定点。例如，如果有两个线程：T1和T2，如果程序的输出是X，如果T1首先到达程序中的P点，那么程序的输出是Y，如果T2首先到达P点，那么就有一个争用条件

在伪代码中：

 Global variable i initialized to 6;
 Thread 1: 
       aquire(lock l)
             increment global variable i, i.e. i++;


 Thread 2: 
       aquire(lock l)
             double the value of global var i, i.e.: i*=2;

如果T1获得锁l启动，T2秒，i的值将为14 如果T2获得锁l启动，T1秒，i的值将为13