java - Burns和Lynch在Java中实现互斥算法 : Could there be issues due to instruction reordering?

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() 方法中实现它，该方法返回一个 boolean 值，指示进程是否成功获取锁(即到达第 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)在几秒钟后一直失败，程序退出并显示消息 两个进程进入关键部分!。

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

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

速记:

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

我就是进程，我和其他人(进程)站成一排。当我想进入临界区时，我执行以下操作:

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

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

Answer 1

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

这种可见性问题的标准解决方案是将共享变量声明为 volatile，但在这种情况下 F 是一个数组，写入/读取 F[i] 不会改变 F 的值。

声明一个“volatiles 数组...”是不可能的，但是可以将 F 声明为 AtomicIntegerArray 并使用 compareAndSet以原子方式更改数组内容，而不必担心线程可见性。