How to prevent Deadlocks in Java using the Bakery Algorithm?

Question

Here is the code which is basically implements the Bakery Algorithm (in a class called Bakery) in order to protect the critical section in the Class Counter (from that class I will create my threads). The problem that I faced is that the program get stuck sometimes (and sometimes work perfectly i.e the counter variable is 20000 because there are 4 threads in my code). By the way Solution it is just an Interface contains the entrySection and the 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;
    }
}

I tried to implement the bakery Algorithm and expecting the counter variable to be 20000.

Answer 1

Like many approaches to mutual exclusion and related forms of thread synchronization, the Bakery algorithm depends on particularly strong memory semantics -- stronger than you can safely rely upon in most environments that have multiple concurrent execution units. Or even in some that don't.

In particular, as described on Wikipedia, Lamport's Bakery algorithm contains several potential data races, and unless those are forestalled, its behavior in Java is undefined. To make your implementation work reliably in Java, you need to fix data races involving

• the elements of Bakery.Choosing
• the elements of Bakery.Number
• Counter.count

You need to ensure that different threads will actually observe each others' writes to these, and that the reads and writes of any of them will not be reordered with respect to others of them. Presumably, the objective is that the Bakery algorithm itself should inherently provide the needed synchronization for accesses to Counter.count inside a critical section, and done right, it will. But that depends on ensuring correct memory semantics for all those array elements.

Using synchronized blocks or methods, or explicit locks, would moot the point of using the Bakery algorithm, so I imagine those are off the table. volatile was raised in comments on the question, but it does not serve here because only fields and variables can be volatile, whereas you need a safe way to access array (or List) elements.

A reasonably natural solution that doesn't stray too far from the conventional description of the algorithm would involve using arrays or Lists of atomic objects:

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
        }
    }

    // ...

There is a variety of methods for accessing and modifying the value held by each atomic object, but the simple get() and set() methods of these should do what you need. These provide the same memory semantics as volatile reads and volatile writes, respectively. (Some other access methods do not provide strong enough semantics.)