Воспроизведение тупика в TLA +

Я пытаюсь воспроизвести тупик из книги Херлихи «Искусство многопроцессорного программирования» в 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 сообщать о тупике?


person neverov    schedule 13.11.2019    source источник


Ответы (1)


См. Ответ Лесли Лэмпорта в полуофициальной группе Google: https://groups.google.com/forum/#!topic/tlaplus/rp5cE4IzEnM

(Зеркало: http://discuss.tlapl.us/msg03229.html)

person M.K.    schedule 16.11.2019