Я пытаюсь воспроизвести тупик из книги Херлихи «Искусство многопроцессорного программирования» в TLA +. В следующем коде, когда поток хочет получить блокировку, он отмечает себя как жертву и продолжает работу только тогда, когда другой поток становится жертвой. Здесь возникает тупик, если не приходит другой поток.
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 отлично работает с Thread = {t1, t2}, где t1 и t2 - модельные значения.
Как заставить TLA сообщать о тупике?