Can there be a deadlock in Bakery Algorithm max() operation?

Question

As resources stated, Bakery algorithm is supposed to be deadlock free. But when I tried to understand the pseudocode, I came up with a line which could raise a deadlock (according to my knowledge).

Reffering to the code below, in Lock() function, we have a line saying

label[i] = max( label[0], ..., label[n-1] ) + 1;

What if two threads come to that state at the same time and since max is not atomic, two labels will get the same value?

Then since two labels have to same value, both threads with that labels will get the permission to go for the critical section at the same time. Wouldn't that occur a deadlock?

Tried myself best to explain the problem here. Comment if it is still not clear. Thanks .

class Bakery implements Lock {
 volatile boolean[] flag;
 volatile Label[] label;

 public Bakery (int n) {
  flag = new boolean[n];
  label = new Label[n];

  for (int i = 0; i < n; i++) {
   flag[i] = false; label[i] = 0;
  }

 public void lock() {
  flag[i] = true;
  label[i] =max(label[0], ...,label[n-1])+1;
  while ( $ k flag[k] && (label[i],i) > (label[k],k);
 }    
}

public void unlock() {
flag[i] = false;
}

Answer 1

Then since two labels have to same value, both threads with that labels will get the permission to go for the critical section at the same time. Wouldn't that occur a deadlock?

To begin with, you probably mean a race, not a deadlock.

However, no, there won't be a race here. If you look, there's the condition

(label[i],i) > (label[k],k)

and while this happens, the thread effectively busy-waits.

This means that even if label[i] is the same as label[k] (as both performed the max concurrently), the thread numbered higher will defer to the thread numbered lower.

(Arguably, this is a problem with the algorithm, as it inherently prioritizes the threads.)