如何使用 Bakery 算法防止 Java 中的死锁？

Question

这里的代码基本上实现了 Bakery 算法（在一个名为 Bakery 的类中），以保护类计数器中的关键部分（我将从该类中创建我的线程）。我面临的问题是程序有时会卡住（有时工作正常，即计数器变量为 20000，因为我的代码中有 4 个线程）。顺便说一下解决方案，它只是一个包含entrySection和exitSection的接口。

public class Main {
 public static void main(String[] args) throws InterruptedException {
     int threadNumbers = 4;
     
     Bakery solution = new Bakery(threadNumbers);

     ArrayList<Counter> threads = new ArrayList<Counter>();

     for(int i =0; i<threadNumbers;i++){
         threads.add(new Counter(i,solution));
     }
     for(int i =0; i<threadNumbers;i++){
         threads.get(i).start();
     }
     for(int i =0; i<threadNumbers;i++){
         
         threads.get(i).join();
     }
     System.out.println(Counter.counter);
 }
}
public class Counter extends Thread{
    static int counter;
    int id;
    private final Bakery solution;
    int count = 0;

    public Counter(int id,Bakery solution) {
        this.id= id;
        this.solution = solution;
    }
    @Override
    public void run(){
        for (int i=0;i<5000;i++){
            this.solution.entrySection(this);
             counter++;
             System.out.println(counter);
            this.solution.exitSection(this);

        }

    }
}
public class Bakery implements Solution{
    boolean[] Choosing;
    int[] Numbers;
    Bakery(int n){
        Choosing = new boolean[n];
        Numbers = new int[n];
        for(int i=0;i<n; i++) {
            Choosing[i] = false;
            Numbers[i] = 0;
        }
    }
    @Override
    public void entrySection(Counter c) {
        Choosing[c.id] = true;
        int max = Numbers[0];
        for (int i = 1; i < Numbers.length; i++) {
            int currentNumber = Numbers[i];
            if (currentNumber > max) {
                max = currentNumber;
            }
        }
        Numbers[c.id] = max + 1;
        Choosing[c.id] = false;
        for(int i=0;i<Numbers.length; i++) {
            while(Choosing[i]){}
            while ((Numbers[i] != 0) && ((Numbers[i] < Numbers[c.id]) || ((Numbers[i] == Numbers[c.id]) && (i < c.id)))) {}
        }
    }
    @Override
    public void exitSection(Counter c) {
        Numbers[c.id] = 0;
    }
}

我尝试实现面包店算法并期望计数器变量为 20000

Answer 1

与许多互斥方法和相关形式的线程同步一样，Bakery 算法依赖于特别强大的内存语义——比您在具有多个并发执行单元的大多数环境中可以安全依赖的语义更强大。或者甚至在一些没有的地方。

特别是，正如维基百科上所述，Lamport 的 Bakery 算法 包含几个潜在的数据竞争，除非这些被预先阻止，否则它在 Java 中的行为是未定义的。为了使您的实现在 Java 中可靠地工作，您需要修复涉及的数据争用

• Bakery.Choosing

的元素

• Bakery.Number

的元素

• Counter.count

您需要确保不同的线程实际上会观察彼此对这些线程的写入，并且其中任何线程的读取和写入不会相对于其他线程重新排序。据推测，目标是 Bakery 算法本身应该本质上为访问关键部分内的

Counter.count

提供所需的同步，并且做得正确的话，它会的。但这取决于确保所有这些数组元素的内存语义正确。

使用

synchronized

块或方法，或者显式锁，会失去使用 Bakery 算法的意义，所以我想这些都是不可能的。

volatile

是在对该问题的评论中提出的，但它在这里不起作用，因为只有字段和变量可以是

volatile

，而您需要一种安全的方法来访问数组（或

List

）元素。

一个相当自然的解决方案，不会偏离算法的传统描述太远，涉及使用数组或

List

的原子对象：

public class Bakery implements Solution{
    AtomicBoolean[] choosing;
    AtomicInteger[] numbers;

    Bakery(int n){
        choosing = new AtomicBoolean[n];
        numbers = new AtomicInteger[n];
        for(int i = 0; i < n; i++) {
            choosing[i] = new AtomicBoolean();  // defaults to false
            numbers[i] = new AtomicInteger();   // defaults to 0
        }
    }

    // ...

有多种方法可以访问和修改每个原子对象所持有的值，但是这些简单的

get()

和

set()

方法应该可以满足您的需要。它们分别提供与

volatile

读取和

volatile

写入相同的内存语义。 （一些其他访问方法不提供足够强大的语义。）