在下面的论文中，我在第4页（836）上找到了一个相当简单的n进程互斥算法：
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()返回布尔值的方法来实现它，该方法指示该进程是否成功获取了锁（即到达第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 and Lynch算法（可能会帮助您考虑问题）：

我是过程，我和其他人（过程）排成一排。当我想进入关键部分时，请执行以下操作：

• 3/4：只要有人举手，我就会向左看，并保持双手放下。
• 5：如果我左边没有人举手，我举起我的
• 6：我再次检查左边的人是否同时举起了手。如果是这样，我放下我的脚，然后重新开始。否则，我会举手。
• 7：我右边的每个人都先走，所以我往右边看，等到看不到任何举手。
• 8：一旦我右边没有人举起手来，我就可以进入临界区。
• 1：完成后，我将手放回原处。

对我来说似乎很可靠…不确定为什么它不能可靠地工作…