Java中用Bakery算法避免死锁：程序偶发卡顿问题排查

我实现了Bakery算法（封装在Bakery类中），用于保护Counter类的临界区（基于该类创建线程）。当前问题是程序有时会卡住，但有时能正常运行（此时计数器变量为20000，因为代码中有4个线程）。Solution是一个仅包含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;
    }
}

问题原因分析 #

• 共享变量可见性缺失：Choosing和Numbers数组没有用volatile修饰，线程无法及时感知其他线程对这些变量的修改。比如某个线程修改了Choosing[i]为false，其他线程可能一直读取到旧的true值，导致while(Choosing[i])无限循环，程序卡住。
• 计数器变量可见性隐患：Counter类中的static int counter未加volatile，主线程可能无法及时看到所有线程更新后的最终值，不过这不是卡顿的核心原因。

解决方案 #

核心是确保共享变量的线程可见性，修改如下：

1. 修改Bakery类的数组修饰符

给Choosing和Numbers数组添加volatile，确保线程间变量修改的即时可见：

public class Bakery implements Solution{
    volatile boolean[] Choosing;
    volatile 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;
    }
}

2. 优化Counter类的计数器变量

给static int counter添加volatile，确保主线程能及时获取最终计数结果：

public class Counter extends Thread{
    static volatile 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);

        }

    }
}

说明 #

添加volatile后，线程每次读取变量时都会直接从主内存获取最新值，写入时也会立即刷新到主内存，避免了因缓存不一致导致的无限循环问题，程序就能稳定运行并得到预期的20000结果。

内容的提问来源于stack exchange，提问作者Oualid Laib