来自“多处理器编程的艺术”的LockTwo

Question

下面是“多处理器编程的艺术”中两个线程的mutext实现。

private int victim;
// thread-local index, 0 or 1

public void lock() {
  int i = ThreadID.get();
  victim = i;                 // let the other go first
  while (victim == i) {}      // spin
}
public void unlock() {}

他们指出，如果“一个线程在另一个线程之前运行”，该代码就会死锁。有人能描述一个没有死锁发生时的交错执行的例子吗？

Answer 1

我可能在理解上有缺陷，在这种情况下，希望有人可以澄清(cc @SonarJetLens)。

在一个线程完全在另一个线程之前运行的情况下，例如，线程A获得锁并等待，因为它是受害者。它会无限期地等待，直到线程B出现并将自己设置为受害者，从而让A通过它的临界区。在这种情况下，我没有看到任何死锁发生:根据定义，死锁是指任何线程都没有取得任何进展。

但是，考虑线程A从未尝试重新获取锁的情况。在这种情况下，线程B将无限期地等待，永远无法到达它的临界区。对我来说，这看起来更像是饥饿，这意味着线程B是饥饿的，并且永远无法获得线程。

如果程序在那里结束，那么线程A通过执行它的临界区已经取得了一些“进展”，而线程B没有，因此没有死锁。然而，存在饥饿，因为线程B试图获取锁，但从未成功，因此与饥饿自由的定义相矛盾。

我希望这是有意义的，我没有在这里犯任何术语或定义错误，我真的希望有人澄清:)。

Answer 2

今天再次阅读之后，我想我明白了“LockTwo类是不够的，因为如果一个线程在另一个线程之前运行completely，它就会死锁”。

如果线程A和B被序列化，这意味着线程B等待线程A完成，那么线程A将永远不会通过"LockTwo“获得锁，根据定义，这是一个死锁：Freedom from Deadlock: If some thread attempts to acquire the lock, then some thread will succeed in acquiring the lock.。

更明显的是，如果作者写道“LockTwo类是不够的，因为如果只有一个线程，它就会死锁。(尽管不需要锁)。”

Answer 3

基本上，一个线程将停滞在while循环中等待，直到另一个线程进入lock()并更改牺牲品字段的值。

如果一个线程完全在另一个线程之前运行，即

thread A writes victim = A -> 
thread A reads Victim != A -> 
thread A do Critical Section -> 
thread B writes victim = B -> 
thread B reads Victim != B -> 
thread B do Critical Section

这将导致死锁，因为事件thread B writes victim = B必须在thread A reads Victim != A之前出现，否则事件线程A读取Victim != A将无限期地阻塞。

交错操作可以防止死锁，因为例如，当线程B写入victim = B，允许A完成并返回其临界区时，线程B现在在while循环中等待，直到执行victim != B。当线程A重新进入锁并更改牺牲品，或者另一个线程C进入锁并更改牺牲品时，线程B将从while循环返回，允许B继续到其临界区。等