在TLA+中重现死锁

Question

我正在尝试用TLA+重现Herlihy的“多处理器编程的艺术”中的一个死锁。在下面的代码中，当一个线程想要获取一个锁时，它会将自己标记为牺牲品，并仅在另一个线程成为牺牲品时才继续。如果另一个线程再也没有出现，这里就会出现死锁。

class LockTwo implements Lock {
  private int victim;

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

  public void unlock() {}
}

TLA+规范如下：

------------------------------ MODULE LockTwo ------------------------------

CONSTANT Thread

VARIABLE victim, owner, wasVictim

Null == CHOOSE v: v \notin Thread

Init == 
  /\ victim = Null
  /\ owner = [t \in Thread |-> FALSE]
  /\ wasVictim = [t \in Thread |-> FALSE]

TypeOK == 
  /\ victim \in Thread \cup {Null}
  /\ owner \in [Thread -> BOOLEAN]
  /\ wasVictim \in [Thread -> BOOLEAN]

BecomeVictim(t) ==
  /\ wasVictim[t] = FALSE
  /\ owner[t] = FALSE
  /\ victim' = t
  /\ wasVictim' = [wasVictim EXCEPT ![t] = TRUE]
  /\ UNCHANGED owner

AcquireLock(t) ==
  /\ wasVictim[t] = TRUE
  /\ victim # t
  /\ owner' = [owner EXCEPT ![t] = TRUE]
  /\ wasVictim' = [wasVictim EXCEPT ![t] = FALSE]
  /\ UNCHANGED victim

ReleaseLock(t) ==
  /\ owner[t] = TRUE
  /\ owner' = [owner EXCEPT ![t] = FALSE]
  /\ UNCHANGED <<victim, wasVictim>>

Next ==
  \E t \in Thread: BecomeVictim(t) \/ AcquireLock(t) \/ ReleaseLock(t)

MutualExclusion ==
  \A t1, t2 \in Thread: (t1 # t2) => ~ (owner[t1] /\ owner[t2])

EventualSuccess ==
  \A t \in Thread: (victim = t) ~> owner[t]

Spec == Init /\ [][Next]_<<victim, owner, wasVictim>> /\ EventualSuccess

=============================================================================

TLA spec在Thread = { t1，t2}时运行良好，其中t1和t2是模型值。

如何让TLA上报死锁？

Answer 1

请看莱斯利·兰波特在半官方谷歌小组上的回答：https://groups.google.com/forum/#!topic/tlaplus/rp5cE4IzEnM

(镜像：http://discuss.tlapl.us/msg03229.html)