[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,
automaton specification
DQ
using Node-heap, optelem,
list-last
variables
queue : list;
obsEmpty : bool;
ival : elem;
value : elem;
oval : OptElem;
tid : Tid;
state variables
queue : list;
local state variables
tid : Tid;
obsEmpty : bool;
ival : elem;
oval : OptElem;
thread id tid;
external labels idle,
ready,
crashed,
invEnq,
resEnq,
invDeq,
resDeq;
special actions CheckEmp(. .tid : Tid)
| DoDeq(. .tid : Tid)
| DoDeqEmpty(. .tid : Tid)
| DoEnq(. .tid : Tid)
| InvDeq(. .tid : Tid)
| InvEnq(. .tid : Tid;. .val : elem)
| RetDeq(. .tid : Tid;. .optval : OptElem)
| RetEnq(. .tid : Tid)
;
initial state
queue = [] ∧ pcf = (λ tid. idle)
declarations
Crash:
Crash(; pcf)
global
{ pcf := λ tid. (pcf(tid) = idle ⊃ idle;crashed)
}
;
Run:
idle :- Run()
atomic
{ return :- ready
}
;
INVENQ:
ready :- INVENQ(value; ival)
atomic with InvEnq(tid, value)
{ ival := value; return :- invEnq
}
;
DOENQ:
invEnq :- DOENQ(ival; queue)
atomic with DoEnq(tid)
{ queue := queue + ival; return :- resEnq
}
;
RETENQ:
resEnq :- RETENQ()
atomic with RetEnq(tid)
{ return :- ready
}
;
INVDEQ:
ready :- INVDEQ(; obsEmpty)
atomic with InvDeq(tid)
{ obsEmpty := false; return :- invDeq
}
;
CHECKEMP:
invDeq :- CHECKEMP(queue; obsEmpty)
atomic with CheckEmp(tid)
precondition queue = [];
{ obsEmpty := true; return :- invDeq
}
;
doDeqEmpty:
invDeq :- DODEQEMPTY(obsEmpty; oval)
atomic with DoDeqEmpty(tid)
precondition obsEmpty;
{ oval := Empty; return :- resDeq
}
;
doDeq:
invDeq :- DODEQ(; oval, queue)
atomic with DoDeq(tid)
precondition queue ≠ [];
{ oval := Val(queue.head), queue := queue.tail; return :- resDeq
}
;
retDeq:
resDeq :- RETDEQ(oval; optval)
atomic with RetDeq(tid, oval)
{ optval := oval; return :- ready
}
;
end automaton specification ;;; END
------------------------------------------------
base =
enrich
Node-heap,
optelem,
list-last
with
variables
queue : list;
obsEmpty : bool;
ival : elem;
value : elem;
oval : OptElem;
tid : Tid;
end enrich
pc =
data specification
DQPC = crashed
| idle
| invDeq
| invEnq
| ready
| resDeq
| resEnq
;
variables
pc : DQPC;
end data specification
gs =
data specification
using base
DQGState := mkgs(. .queue : list)
;
variables
gs : DQGState;
queue : list;
end data specification
ls =
data specification
using base
DQLState := mkls(. .tid : Tid;
. .obsEmpty : bool;
. .ival : elem;
. .oval : OptElem;
. .value : elem;
. .optval : OptElem)
;
variables
ls : DQLState;
tid : Tid;
obsEmpty : bool;
ival : elem;
oval : OptElem;
value : elem;
optval : OptElem;
end data specification
state =
data specification
using pc, localstate,
globalstate
DQState := mkstate(. .gstate : DQGState;. .lsf : Tid → DQLState;. .pcf : Tid → DQPC)
;
variables
s : DQState;
lsf : Tid → DQLState;
pcf : Tid → DQPC;
gstate : DQGState;
end data specification
action =
data specification
using base
data types
DQAction = CheckEmp(. .tid : Tid)
| DoDeq(. .tid : Tid)
| DoDeqEmpty(. .tid : Tid)
| DoEnq(. .tid : Tid)
| InvDeq(. .tid : Tid)
| InvEnq(. .tid : Tid;. .val : elem)
| RetDeq(. .tid : Tid;. .optval : OptElem)
| RetEnq(. .tid : Tid)
| callRun(. .tid : Tid)
| globalCrash
| τ
;
variables
a : DQAction;
tid : Tid;
val : elem;
optval : OptElem;
end data specification
step =
enrich
state,
action
with
functions
lstepf : DQGState × DQLState × DQPC × DQAction → DQLState;
gstepf : DQGState × DQLState × DQPC × DQAction → DQGState;
pcstepf : DQGState × DQLState × DQPC × DQAction → DQPC;
predicates
DQstep : DQState × DQAction × DQState;
pre : DQGState × DQLState × DQPC × DQAction;
lstep : DQGState × DQLState × DQPC × DQAction × DQGState × DQLState × DQPC;
DQGInv : DQGState;
DQLInv : DQGState × DQLState × DQPC;
DQInv : DQGState × (Tid → DQLState) × (Tid → DQPC);
procedures Run : ;
INVENQ elem : elem nonfunctional ;
DOENQ elem : list nonfunctional ;
RETENQ : ;
INVDEQ : bool nonfunctional ;
CHECKEMP list : bool nonfunctional ;
DODEQEMPTY bool : OptElem nonfunctional ;
DODEQ : OptElem × list nonfunctional ;
RETDEQ OptElem : : OptElem ;
Crash : (Tid → DQPC) nonfunctional ;
axioms
DQInv: DQInv(gs, lsf, pcf) ↔ DQGInv(gs) ∧ (∀ tid. lsf(tid).tid = tid ∧ DQLInv(gs, lsf(tid), pcf(tid)));
DQGInv: DQGInv(gs) ↔ true;
DQLInv: DQLInv(gs, ls, pc) ↔ true;
DQstep:
DQstep(mkstate(gs, lsf, pcf), a, mkstate(gs0, lsf0, pcf0))
↔ (∃ tid, ls, pc. lstep(gs, lsf(tid), pcf(tid), a, gs0, ls, pc) ∧ lsf0 = lsf(tid; ls) ∧ pcf0 = pcf(tid; pc))
∨ a = globalCrash ∧ ⟨Crash(; pcf)⟩ (gs0 = gs ∧ lsf0 = lsf ∧ pcf0 = pcf);
lstep:
lstep(gs, ls, pc, a, gs0, ls0, pc0)
↔ pre(gs, ls, pc, a) ∧ ls0 = lstepf(gs, ls, pc, a) ∧ gs0 = gstepf(gs, ls, pc, a) ∧ pc0 = pcstepf(gs, ls, pc, a);
pre-resDeq: pre(gs, ls, resDeq, a) ↔ a = RetDeq(ls.tid, ls.oval);
pre-invEnq: pre(gs, ls, invEnq, a) ↔ a = DoEnq(ls.tid);
pre-resEnq: pre(gs, ls, resEnq, a) ↔ a = RetEnq(ls.tid);
pre-ready: pre(gs, ls, ready, a) ↔ (∃ value. a = InvEnq(ls.tid, value)) ∨ a = InvDeq(ls.tid);
pre-idle: pre(gs, ls, idle, a) ↔ a = callRun(ls.tid);
pre-invDeq:
pre(gs, ls, invDeq, a) ↔ a = CheckEmp(ls.tid) ∧ gs.queue = [] ∨ a = DoDeqEmpty(ls.tid) ∧ ls.obsEmpty ∨ a = DoDeq(ls.tid) ∧ gs.queue ≠ [];
pre-crashed: pre(gs, ls, crashed, a) ↔ false;
used for: s, ls;
lstepf-idle-Run: lstepf(gs, ls, idle, callRun(ls.tid)) = ls;
used for: s, ls;
lstepf-ready-INVENQ: lstepf(gs, ls, ready, InvEnq(ls.tid, value)) = ls.ival:= value;
used for: s, ls;
lstepf-invEnq-DOENQ: lstepf(gs, ls, invEnq, DoEnq(ls.tid)) = ls;
used for: s, ls;
lstepf-resEnq-RETENQ: lstepf(gs, ls, resEnq, RetEnq(ls.tid)) = ls;
used for: s, ls;
lstepf-ready-INVDEQ: lstepf(gs, ls, ready, InvDeq(ls.tid)) = ls.obsEmpty:= false;
used for: s, ls;
lstepf-invDeq-CHECKEMP: lstepf(gs, ls, invDeq, CheckEmp(ls.tid)) = ls.obsEmpty:= true;
used for: s, ls;
lstepf-invDeq-DODEQEMPTY: lstepf(gs, ls, invDeq, DoDeqEmpty(ls.tid)) = ls.oval:= Empty;
used for: s, ls;
lstepf-invDeq-DODEQ: lstepf(gs, ls, invDeq, DoDeq(ls.tid)) = ls.oval:= Val(gs.queue.head);
used for: s, ls;
lstepf-resDeq-RETDEQ: lstepf(gs, ls, resDeq, RetDeq(ls.tid, ls.oval)) = ls.optval:= ls.oval;
used for: s, ls;
gstepf-resDeq-RETDEQ: gstepf(gs, ls, resDeq, RetDeq(ls.tid, ls.oval)) = gs;
used for: s, ls;
gstepf-invEnq-DOENQ: gstepf(gs, ls, invEnq, DoEnq(ls.tid)) = gs.queue:= (gs.queue + ls.ival);
used for: s, ls;
gstepf-resEnq-RETENQ: gstepf(gs, ls, resEnq, RetEnq(ls.tid)) = gs;
used for: s, ls;
gstepf-ready: gstepf(gs, ls, ready, a) = gs;
used for: s, ls;
gstepf-idle-Run: gstepf(gs, ls, idle, callRun(ls.tid)) = gs;
used for: s, ls;
gstepf-invDeq-CHECKEMP: gstepf(gs, ls, invDeq, CheckEmp(ls.tid)) = gs;
used for: s, ls;
gstepf-invDeq-DODEQEMPTY: gstepf(gs, ls, invDeq, DoDeqEmpty(ls.tid)) = gs;
used for: s, ls;
gstepf-invDeq-DODEQ: gstepf(gs, ls, invDeq, DoDeq(ls.tid)) = gs.queue:= gs.queue.tail;
used for: s, ls;
pcstepf-idle-Run: pcstepf(gs, ls, idle, callRun(ls.tid)) = ready;
used for: s, ls;
pcstepf-ready-INVENQ: pcstepf(gs, ls, ready, InvEnq(ls.tid, value)) = invEnq;
used for: s, ls;
pcstepf-invEnq-DOENQ: pcstepf(gs, ls, invEnq, DoEnq(ls.tid)) = resEnq;
used for: s, ls;
pcstepf-resEnq-RETENQ: pcstepf(gs, ls, resEnq, RetEnq(ls.tid)) = ready;
used for: s, ls;
pcstepf-ready-INVDEQ: pcstepf(gs, ls, ready, InvDeq(ls.tid)) = invDeq;
used for: s, ls;
pcstepf-invDeq-CHECKEMP: pcstepf(gs, ls, invDeq, CheckEmp(ls.tid)) = invDeq;
used for: s, ls;
pcstepf-invDeq-DODEQEMPTY: pcstepf(gs, ls, invDeq, DoDeqEmpty(ls.tid)) = resDeq;
used for: s, ls;
pcstepf-invDeq-DODEQ: pcstepf(gs, ls, invDeq, DoDeq(ls.tid)) = resDeq;
used for: s, ls;
pcstepf-resDeq-RETDEQ: pcstepf(gs, ls, resDeq, RetDeq(ls.tid, ls.oval)) = ready;
used for: s, ls;
end enrich