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

编程入门行业动态更新时间:2024-10-08 22:56:28

本文介绍了正确同步的程序是否仍允许数据竞争？（第一部分）的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！问题描述

JLS有两个结论：

C1：如果程序没有数据争用，那么程序的所有执行都将完成似乎是顺序一致的： data-race-free =>顺序一致
C2：如果程序正确同步，那么程序的所有执行都将按顺序一致：正确同步=>顺序一致

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

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

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

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

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

但不幸的是，JLS中没有这样的声明，所以我得到了到第四个结论：

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

C4：程序可以正确同步并具有数据竞争。

但我对这种方法并不满意，并希望得到一个证据，证明这个结论是真的（或错误的），即使在非正式的方式或样本方式。

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?

推荐答案

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

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

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

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.

编辑

这（几乎）相同的代码被破坏并且可以返回0的哈希码：

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

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

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.

编辑2

关于你的命题C4，我不认为是可能的：

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

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

如果程序正确同步，则程序的所有执行都将显示为顺序一致（第17.4.3节）。

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: