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, not a deadlock。

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

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

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

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

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

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

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

algorithm

concurrency

multithreading

deadlock

locking