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

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

如果一个线程完全领先于另一个线程，即

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 继续执行其临界区。ETC