multithreading - Bakery Algorithm max() 操作是否会出现死锁？

Question

如资源所述，Bakery 算法应该是无死锁的。但是当我试图理解伪代码时，我想到了一条可能引发死锁的行(据我所知)。

引用下面的代码，在 Lock() 函数中，我们有一行内容是

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

如果两个线程同时进入该状态，并且由于 max 不是原子的，两个标签将获得相同的值怎么办？

然后由于两个标签具有相同的值，因此具有该标签的两个线程将同时获得进入临界区的许可。不会出现死锁吗？

我尽力在这里解释问题。如果仍然不清楚，请发表评论。谢谢。

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?

首先，您可能指的是 race , 不是 deadlock .

但是，不，这里不会有比赛。如果你看，有条件

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

当发生这种情况时，线程实际上处于忙等待状态。

这意味着即使 label[i] 与 label[k] 相同(因为两者同时执行了 max)，编号较高的线程将推迟到编号较低的线程。

(可以说，这是算法的问题，因为它固有地优先考虑线程。)