[Imprint][Data Privacy Statement][E-Mail]
Back to main index.
View the specification.
View theorem base summary,
View theorem base listing,
the used properties by spec,
the dependency list,
the symbol table,
enrich
DMSQ-proofs,
DQ-proofs
with
functions
content : reflist × heap → list;
ren : DMSQAction → DQAction;
abspc : DMSQGState × DMSQLState × DMSQPC → DQPC;
predicates
abs : DMSQState × DQState;
absls : DMSQGState × DMSQLState × DMSQPC × DQLState;
DMSQastep : DMSQState × DQAction × DMSQState;
DMSQinit : DMSQState;
DQinit : DQState;
variables
gs : DMSQGState;
ags : DQGState;
cs : DMSQState;
lsf : Tid → DMSQLState;
alsf : Tid → DQLState;
pcf : Tid → DMSQPC;
apcf : Tid → DQPC;
ls : DMSQLState;
als : DQLState;
pc : DMSQPC;
apc : DQPC;
aa : DQAction;
ca : DMSQAction;
q : list;
tid : Tid;
vs : heap;
ps : heap;
val : elem;
optval : OptElem;
nd : Node;
success : bool;
rvref : rvRef;
r : Ref;
rl : reflist;
axioms
DMSQinit-def:
DMSQinit(mkstate(gs, lsf, pcf))
↔ (∃ r, val.
r ≠ null ∧ gs.ps = ∅[r, mk(val, Some(dummytid), null)] ∧ gs.phead = r ∧ gs.vhead = r ∧ gs.vtail = r ∧ gs.orl = r ' ∧ gs.qrl = []
∧ gs.vs = gs.ps)
∧ gs.vrvHp = ∅ ∧ gs.prvHp = ∅ ∧ gs.vretRefs = (λ tid. null) ∧ gs.pretRefs = (λ tid. null) ∧ gs.owns = (λ r. None) ∧ pcf = (λ tid. idle)
∧ (∀ tid. lsf(tid).tid = tid);
comment: a predicate identical to the initial state of the automaton DMSQ (except lsf(tid).tid = tid was implicit);
DQinit-def: DQinit(mkstate(ags, alsf, apcf)) ↔ ags.queue = [] ∧ apcf = (λ tid. idle) ∧ (∀ tid. alsf(tid).tid = tid);
comment: a predicate identical to the initial state of the automaton DQ (except lsf(tid).tid = tid was implicit);
DMSQastep-def: DMSQastep(cs, aa, cs0) ↔ (∃ ca. ren(ca) = aa ∧ DMSQstep(cs, ca, cs0));
used for: ls, s;
ren-chooseE: ren(chooseE1(r, nd, success)) = τ;
used for: s, ls;
ren-chooseD: ren(chooseD2(rvref, optval0)) = τ;
used for: s, ls;
ren-invENQ: ren(invENQ(tid, val)) = InvEnq(tid, val);
used for: s, ls;
ren-invDEQ: ren(invDEQ(tid)) = InvDeq(tid);
used for: s, ls;
ren-retDEQ: ren(retDEQ(tid, optval)) = RetDeq(tid, optval);
used for: s, ls;
ren-retENQ: ren(retENQ(tid)) = RetEnq(tid);
used for: s, ls;
ren-callRUN: ren(callRUN(tid)) = callRun(tid);
used for: s, ls;
ren-doDeq: ren(doDeq(tid)) = DoDeq(tid);
used for: s, ls;
ren-doDeqEmpty: ren(doDeqEmpty(tid)) = DoDeqEmpty(tid);
used for: s, ls;
ren-doEnq: ren(doEnq(tid)) = DoEnq(tid);
used for: s, ls;
ren-tau: ren(τ) = τ;
used for: s, ls;
ren-CRASH: ren(globalCRASH) = globalCrash;
used for: s, ls;
ren-FLUSHHEAD: ren(globalFLUSHHEAD) = τ;
used for: s, ls;
ren-FLUSHVAL: ren(globalFLUSHVAL(r)) = τ;
used for: s, ls;
ren-checkEmp: ren(checkEmp(tid)) = CheckEmp(tid);
used for: s, ls;
abs-def:
abs(mkstate(gs, lsf, pcf), mkstate(mkgs(q), alsf, apcf))
↔ q = content(gs.qrl, gs.ps) ∧ (∀ tid. absls(gs, lsf(tid), pcf(tid), alsf(tid)) ∧ abspc(gs, lsf(tid), pcf(tid)) = apcf(tid));
absls-def:
absls(gs, ls, pc, als)
↔ ls.tid = als.tid
∧ ( pc = E1 ∨ pc = E2 ∨ pc = E3 ∨ pc = E4 ∧ ¬ ls.success ∨ pc = E5 ∨ pc = E6 ∨ pc = E7 ∨ pc = E8 ∨ pc = E9
∨ pc = E10 ∧ (ls.success → ls.lst = gs.vtail ∧ gs.ps[ls.lst].next = null) ∨ pc = E11 ∧ ls.lst = gs.vtail ∧ gs.ps[ls.lst].next = null
∨ pc = E13 ∨ pc = E14 ∨ pc = E15 ∨ pc = E16
→ ls.value = als.ival)
∧ ((pc = D10 ∨ pc = D11 ∨ pc = D12 ∨ pc = D13 ∨ pc = D14) ∧ ls.nxt = null → als.obsEmpty)
∧ (pc = D20 ∧ ls.success ∧ gs.ps[ls.nxt].deqID ≠ None ∨ pc = D21 ∧ gs.ps[ls.nxt].deqID ≠ None ∨ pc = D22 → als.oval = ls.optval)
∧ (pc = D15 ∨ pc = D23 ∨ pc = D24 ∨ pc = D6 ∧ ls.success ∨ pc = D34 → als.oval = gs.vrvHp[gs.vretRefs(ls.tid)]);
abspc-def:
abspc(gs, ls, pc)
= (pc = idle
⊃ idle
;(pc = ready
⊃ ready
;(pc = crashed
⊃ crashed
;( pc = E1 ∨ pc = E2 ∨ pc = E3 ∨ pc = E4 ∧ ¬ ls.success ∨ pc = E5 ∨ pc = E6 ∨ pc = E7 ∨ pc = E8 ∨ pc = E9
∨ pc = E10 ∧ (ls.success → ls.lst = gs.vtail ∧ gs.ps[ls.lst].next = null) ∨ pc = E11 ∧ ls.lst = gs.vtail ∧ gs.ps[ls.lst].next = null
∨ pc = E13 ∨ pc = E14 ∨ pc = E15 ∨ pc = E16
⊃ invEnq
;(pc = E10 ∨ pc = E11 ∨ pc = E12 ∨ pc = E4 ∨ pc = E13 ∨ pc = E17
⊃ resEnq
;( pc = D1 ∨ pc = D2 ∨ pc = D3 ∨ pc = D4 ∨ pc = D5 ∨ pc = D6 ∧ ¬ ls.success ∨ pc = D7 ∨ pc = D8 ∨ pc = D9 ∨ pc = D10 ∨ pc = D11
∨ pc = D12 ∨ pc = D13 ∨ pc = D14 ∨ pc = D16 ∨ pc = D17 ∨ pc = D18 ∨ pc = D19 ∨ pc = D20 ∧ (ls.success → gs.ps[ls.nxt].deqID = None)
∨ pc = D21 ∧ gs.ps[ls.nxt].deqID = None ∨ pc = D25 ∨ pc = D26 ∨ pc = D27 ∨ pc = D28 ∨ pc = D29 ∨ pc = D30 ∨ pc = D31 ∨ pc = D32
∨ pc = D33
⊃ invDeq
;resDeq
)
)
)
)
)
);
used for: ls;
content-base: content([], ps) = [];
used for: s, ls;
content-rec: content(r ' + rl, ps) = ps[r].val + content(rl, ps);
used for: s, ls;
end enrich