5

这是“多处理器编程的艺术”中两个线程的多文本实现

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() {}

他们指出，如果“一个线程先于另一个线程运行”，则此代码将死锁。任何人都可以描述没有发生死锁时交错执行的示例。

4

4 回答 4

2

我的理解可能存在缺陷，在这种情况下，希望有人可以澄清（cc @SonarJetLens）。

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

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

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

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

于 2017-02-25T03:37:48.213 回答
0

今天再次阅读后，我想我明白了“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 类是不合适的，因为如果只有一个线程它会死锁。（虽然不需要锁）

于 2019-07-05T11:23:35.477 回答
-1

基本上，一个线程将在 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 继续其临界区。ETC

于 2014-04-14T13:55:19.603 回答
-1

我也会尝试回答这个问题，尽管我是这个部门的新手。

考虑以下情况（A & B 是线程）：

writeA(victim=A) -> readA(victim != A) -> CSA

相似地

writeB(victim=B) -> readB(victim != B) -> CSB

现在考虑以下情况：

Case 1:当一个线程完全领先于另一个线程时，即A -> B

首先thread A启动时，它设置victim=A并等待，同时thread B无法启动，因为它正在等待线程 A 完成其对临界区的执行。从而thread A等待thread B改变victim而B等待thread A完成其CSA。因此，当两个线程等待两种不同的条件时，将发生死锁：

Thread A is waiting so that thread B sets victim=B whereas thread B is waiting so that thread A completes its critical section (CSA).

Case 2:当线程交错执行时。

在这种情况下，由于两个线程几乎同时启动（假设它们一次又一次地运行，可能在一个循环中），它们将交替设置牺牲品，因此当然允许彼此交替运行。

于 2018-01-18T05:58:01.263 回答