正确同步的程序是否仍允许数据竞争？(第一部分)

Question

JLS有两个结论:

• C1:如果一个程序没有数据竞争,那么程序的所有执行都将显示为顺序一致: data-race-free => sequentially consistent
• C2:如果程序正确同步,则程序的所有执行都将显示为顺序一致: correctly synchronized => sequentially consistent

如果C1的反面是真的,那么我们可以得出结论:

• C3:如果一个程序正确同步,那么它没有数据竞争: correctly synchronized => data-race-free

但不幸的是,JLS中没有这样的陈述,所以我得出了第四个结论:

• C4:程序可以正确同步并具有数据竞争.

但我对这种方法并不满意,并且想要证明这个结论是正确的(或错误的),即使是以非正式的方式或以样本的方式.

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

经过认真考虑,我仍然找不到合适的样品.那么请你给我这样的代码段吗？

Answer 1

一个很好的例子可能是String的哈希码:

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

as(1)和(2)可以重新排序:(1)可以读取非空值,而(2)读取0.这在第一个例子中不会发生,因为计算是在局部变量和返回上进行的value也是局部变量,根据定义,它是线程安全的.

编辑2

关于你的命题C4,我认为不可能:

当且仅当所有顺序一致的执行没有数据争用时,程序才能正确同步.

如果程序正确同步,则程序的所有执行都将显示为顺序一致(第17.4.3节).

因此,如果程序正确同步:

• 所有执行都按顺序显示.
• 所有顺序一致的执行都没有数据竞争

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