[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[tlaplus] Reproducing deadlock in TLA+



I'm trying to reproduce a deadlock from Herlihy's "The Art of Multiprocessor Programming" in TLA+. In the following code when a thread wants to acquire a lock it marks itself as a victim and proceed only when another thread becomes a victim. There is a deadlock here if another thread never comes.

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

The TLA+ spec is as follows:

```
------------------------------ 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 runs fine with Thread = {t1, t2} where t1 and t2 are model values.

How to make TLA to report a deadlock when one thread wants to lock but another one never comes?

--
You received this message because you are subscribed to the Google Groups "tlaplus" group.
To unsubscribe from this group and stop receiving emails from it, send an email to tlaplus+unsubscribe@xxxxxxxxxxxxxxxx.
To view this discussion on the web visit https://groups.google.com/d/msgid/tlaplus/402a01c0-ec1f-46e2-9d4a-36cb93dcb929%40googlegroups.com.