在Java中实施Burns和Lynch的互斥算法：由于指令重新排序会有问题吗？
在下面的论文中，我在第4页（836）找到了一个相当简单的n进程互斥算法：
Burns和Lynch的“使用不可分割读写的相互排斥”
program Process_i; type flag = (down, up); shared var F : array [1..N] of flag; var j : 1..N; begin while true do begin 1: F[i] := down; 2: remainder; (* remainder region *) 3: F[i] := down; 4: for j := 1 to i-1 do if F[j] = up then goto 3; 5: F[i] := up; 6: for j := 1 to i-1 do if F[j] = up then goto 3; 7: for j := i+1 to N do if F[j] = up then goto 7; 8: critical; (* critical region *) end end. 我喜欢它，因为它的内存使用量很少，并且goto应该允许我在一个方法enterCriticalRegion()中实现它，该方法返回一个布尔值，指示进程是否成功获取锁（即到达第8行）或者是否触及了goto和需要稍后再试，而不是忙着等待。 （在我的案例中，公平和饥饿并不是真正的问题）
我尝试在Java中实现它并通过让一堆线程尝试快速连续进入关键区域来测试它（看起来很长，但它主要是注释）：
import java.util.concurrent.atomic.AtomicInteger; public class BurnsME { // Variable to count processes in critical section (for verification) private static AtomicInteger criticalCount = new AtomicInteger(0); // shared var F : array [1..N] of flag; private static final boolean[] F = new boolean[10000]; // Some process-local variables private final int processID; private boolean atLine7; public BurnsME(int processID) { this.processID = processID; this.atLine7 = false; } /** * Try to enter critical region. * * @return T - success; F - failure, need to try again later */ public boolean enterCriticalRegion() { // Burns Lynch Algorithm // Mutual Exclusion Using Indivisible Reads and Writes, p. 836 if (!atLine7) { // 3: F[i] down F[processID] = false; // 4: for j:=1 to i-1 do if F[j] = up goto 3 for (int process=0; process<processID; process++) if (F[process]) return false; // 5: F[i] = up F[processID] = true; // 6: for j:=1 to i-1 do if F[j] = up goto 3 for (int process=0; process<processID; process++) if (F[process]) return false; atLine7 = true; } // 7: for j:=i+1 to N do if F[j] = up goto 7 for (int process=processID+1; process1) { System.err.println("TWO PROCESSES ENTERED CRITICAL SECTION!"); System.exit(1); } // 8: critical region return true; } /** * Leave critical region and allow next process in */ public void leaveCriticalRegion() { // Reset state atLine7 = false; criticalCount.decrementAndGet(); // Release critical region lock // 1: F[i] = down F[processID] = false; } //=============================================================================== // Test Code private static final int THREADS = 50; public static void main(String[] args) { System.out.println("Launching "+THREADS+" threads..."); for (int i=0; i<THREADS; i++) { final int threadID = i; new Thread() { @Override public void run() { BurnsME mutex = new BurnsME(threadID); while (true) { if (mutex.enterCriticalRegion()) { System.out.println(threadID+" in critical region"); mutex.leaveCriticalRegion(); } } } }.start(); } while (true); } }
出于某种原因，互斥validation（通过AtomicInteger）在几秒钟后仍然失败并且程序退出并显示消息TWO PROCESSES ENTERED CRITICAL SECTION! 。
算法和我的实现都是如此简单，我有点困惑为什么它不工作。
Burns / Lynch算法有问题吗（怀疑它）？ 或者我在某个地方犯了一些愚蠢的错误，我只是没有看到？ 或者这是由一些Java指令重新排序引起的？ 后者似乎对我不太可能，因为每次任务后都会有潜在的return ，因此不应与任何其他任务交换，不是吗？ 或者Java中的数组访问不是线程安全的吗？
快点：
这是我如何可视化Burns和Lynch算法（可能有助于思考这个问题）：
我是这个过程，我和其他人（流程）站在一起。 当我想进入关键部分时，我会执行以下操作：
- 3/4：只要有人伸出手，我就向左看并保持手。
- 5：如果左边没有人举手，我就放了
- 6：我再次检查左边是否有人举起手来。 如果是这样，我把我放回去重新开始。 否则，我举起手来。
- 7：我右边的每个人都先行，所以我向右看，等到我看不到任何举手。
- 8：一旦我右边没有人举起手，我就可以进入关键部分了。
- 1：当我完成后，我把手放回去了。
对我来说似乎很坚固……不确定为什么它不能可靠地工作……
在java内存模型中，您无法保证对F [i]的写入对于稍后从其读取的另一个Thread可见。
这种可见性问题的标准解决方案是将共享变量声明为volatile，但在这种情况下，F是一个数组，写入/读取到F [i]不会更改F的值。
不可能声明一个“volatile of volatile ……”，但是可以将F声明为AtomicIntegerArray并使用compareAndSet以primefaces方式更改数组内容而不必担心Thread-visibility。