Java 中 Burns 和 Lynch 的实现互斥算法：指令重新排序会不会有问题？

Question

我在以下论文的第 4 (836) 页找到了一个相当简单的 n 进程互斥算法：
"Mutual Exclusion Using Indivisible Reads and Writes" by Burns and 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() 中实现它 returns 一个布尔值，指示进程是否成功获取锁 (即到达第 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; process<F.length; process++) 
            if (F[process]) return false;

        // Verify mutual exclusion
        if (criticalCount.incrementAndGet()>1) {
            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);
    }
}

由于某种原因，互斥验证（通过 AtomicInteger）在几秒钟后一直失败，程序退出并显示消息 TWO PROCESSES ENTERED CRITICAL SECTION!。

算法和我的实现都非常简单，我有点困惑为什么它不起作用。

难道Burns/Lynch算法有问题（怀疑）？还是我在某个地方犯了一些我只是没有看到的愚蠢错误？或者这是由某些 Java 指令重新排序引起的？后者对我来说似乎不太可能，因为每个赋值后面都有一个潜在的 return，因此不应该与任何其他赋值交换，不是吗？或者 Java 中的数组访问不是线程安全的？

顺便提一句：

以下是我如何可视化 Burns 和 Lynch 算法（可能有助于思考这个问题）：

我是进程，我和其他人（进程）站成一排。当我想进入临界区时，我执行以下操作：

3/4：我向左看，只要有人举手，我的手就一直向下。
5：如果我左边没有人举手，我就举手
6：我再次检查我左边是否有人同时举手。如果是这样，我把我的放回去重新开始。否则，我会举手。
7：我右边的每个人都先走，所以我向右看，等到没有人举手。
8：等我右边没人举手了，我就可以进入临界区了
1：完成后，我把手放回去。

对我来说似乎很可靠...不知道为什么它不能可靠地工作...

Answer 1

在 java 内存模型中，您无法保证对 F[i] 的写入对稍后从中读取的另一个线程可见。

这种可见性问题的标准解决方案是将共享变量声明为volatile，但此时F是数组，write/reads到F[i]不改变F的值。

无法声明 "array of volatiles ..."，但可以将 F 声明为 AtomicIntegerArray 并使用 compareAndSet 以原子方式更改数组内容，而无需担心线程可见性。

Java 中 Burns 和 Lynch 的实现互斥算法：指令重新排序会不会有问题？

Implementing Mutual Exclusion Algorithm by Burns and Lynch in Java: Could there be issues due to instruction reordering?

java

algorithm

multithreading

mutual-exclusion