[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
DurQ
using Node-heap, optelem,
list-last
variables
queue : list;
ival : elem;
value : elem;
oval : OptElem;
tid : Tid;
state variables
queue : list;
local state variables
tid : Tid;
ival : elem;
oval : OptElem;
thread id tid;
external labels idle,
ready,
crashed,
invEnq,
resEnq,
invDeq,
resDeq;
special actions ADoDeq(. .tid : Tid)
| ADoEnq(. .tid : Tid)
| AInvDeq(. .tid : Tid)
| AInvEnq(. .tid : Tid;. .val : elem)
| ARetDeq(. .tid : Tid;. .optval : OptElem)
| ARetEnq(. .tid : Tid)
;
initial state
queue = [] ∧ pcf = (λ tid. idle)
declarations
Crash:
ACrash(; pcf)
global
{ pcf := λ tid. (pcf(tid) = idle ⊃ idle;crashed)
}
;
ARun:
idle :- ARun()
atomic
{ return :- ready
}
;
AINVENQ:
ready :- AINVENQ(value; ival)
atomic with AInvEnq(tid, value)
{ ival := value; return :- invEnq
}
;
ADOENQ:
invEnq :- ADOENQ(ival; queue)
atomic with ADoEnq(tid)
{ queue := queue + ival; return :- resEnq
}
;
ARETENQ:
resEnq :- ARETENQ()
atomic with ARetEnq(tid)
{ return :- ready
}
;
AINVDEQ:
ready :- AINVDEQ()
atomic with AInvDeq(tid)
{ return :- invDeq
}
;
ADODEQ:
invDeq :- ADODEQ(; oval, queue)
atomic with ADoDeq(tid)
{ if queue = [] then oval := Empty else oval := Val(queue.head), queue := queue.tail; return :- resDeq
}
;
ARETDEQ:
resDeq :- ARETDEQ(oval; optval)
atomic with ARetDeq(tid, oval)
{ optval := oval; return :- ready
}
;
end automaton specification ;;; END
------------------------------------------------
base =
enrich
Node-heap,
optelem,
list-last
with
variables
queue : list;
ival : elem;
value : elem;
oval : OptElem;
tid : Tid;
end enrich
pc =
data specification
DurQPC = crashed
| idle
| invDeq
| invEnq
| ready
| resDeq
| resEnq
;
variables
pc : DurQPC;
end data specification
gs =
data specification
using base
DurQGState := mkgs(. .queue : list)
;
variables
gs : DurQGState;
queue : list;
end data specification
ls =
data specification
using base
DurQLState := mkls(. .tid : Tid;
. .ival : elem;
. .oval : OptElem;
. .value : elem;
. .optval : OptElem)
;
variables
ls : DurQLState;
tid : Tid;
ival : elem;
oval : OptElem;
value : elem;
optval : OptElem;
end data specification
state =
data specification
using pc, localstate,
globalstate
DurQState := mkstate(. .gstate : DurQGState;. .lsf : Tid → DurQLState;. .pcf : Tid → DurQPC)
;
variables
s : DurQState;
lsf : Tid → DurQLState;
pcf : Tid → DurQPC;
gstate : DurQGState;
end data specification
action =
data specification
using base
data types
DurQAction = ADoDeq(. .tid : Tid)
| ADoEnq(. .tid : Tid)
| AInvDeq(. .tid : Tid)
| AInvEnq(. .tid : Tid;. .val : elem)
| ARetDeq(. .tid : Tid;. .optval : OptElem)
| ARetEnq(. .tid : Tid)
| callARun(. .tid : Tid)
| globalACrash
| τ
;
variables
a : DurQAction;
tid : Tid;
val : elem;
optval : OptElem;
end data specification
step =
enrich
state,
action
with
functions
lstepf : DurQGState × DurQLState × DurQPC × DurQAction → DurQLState;
gstepf : DurQGState × DurQLState × DurQPC × DurQAction → DurQGState;
pcstepf : DurQGState × DurQLState × DurQPC × DurQAction → DurQPC;
predicates
DurQstep : DurQState × DurQAction × DurQState;
pre : DurQGState × DurQLState × DurQPC × DurQAction;
lstep : DurQGState × DurQLState × DurQPC × DurQAction × DurQGState × DurQLState × DurQPC;
DurQGInv : DurQGState;
DurQLInv : DurQGState × DurQLState × DurQPC;
DurQInv : DurQGState × (Tid → DurQLState) × (Tid → DurQPC);
procedures ARun : ;
AINVENQ elem : elem nonfunctional ;
ADOENQ elem : list nonfunctional ;
ARETENQ : ;
AINVDEQ : ;
ADODEQ : OptElem × list nonfunctional ;
ARETDEQ OptElem : : OptElem ;
ACrash : (Tid → DurQPC) nonfunctional ;
axioms
DurQInv: DurQInv(gs, lsf, pcf) ↔ DurQGInv(gs) ∧ (∀ tid. lsf(tid).tid = tid ∧ DurQLInv(gs, lsf(tid), pcf(tid)));
DurQGInv: DurQGInv(gs) ↔ true;
DurQLInv: DurQLInv(gs, ls, pc) ↔ true;
DurQstep:
DurQstep(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 = globalACrash ∧ ⟨ACrash(; 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 = ARetDeq(ls.tid, ls.oval);
pre-invEnq: pre(gs, ls, invEnq, a) ↔ a = ADoEnq(ls.tid);
pre-resEnq: pre(gs, ls, resEnq, a) ↔ a = ARetEnq(ls.tid);
pre-ready: pre(gs, ls, ready, a) ↔ (∃ value. a = AInvEnq(ls.tid, value)) ∨ a = AInvDeq(ls.tid);
pre-idle: pre(gs, ls, idle, a) ↔ a = callARun(ls.tid);
pre-invDeq: pre(gs, ls, invDeq, a) ↔ a = ADoDeq(ls.tid);
pre-crashed: pre(gs, ls, crashed, a) ↔ false;
used for: s, ls;
lstepf-idle-ARun: lstepf(gs, ls, idle, callARun(ls.tid)) = ls;
used for: s, ls;
lstepf-ready-AINVENQ: lstepf(gs, ls, ready, AInvEnq(ls.tid, value)) = ls.ival:= value;
used for: s, ls;
lstepf-invEnq-ADOENQ: lstepf(gs, ls, invEnq, ADoEnq(ls.tid)) = ls;
used for: s, ls;
lstepf-resEnq-ARETENQ: lstepf(gs, ls, resEnq, ARetEnq(ls.tid)) = ls;
used for: s, ls;
lstepf-ready-AINVDEQ: lstepf(gs, ls, ready, AInvDeq(ls.tid)) = ls;
used for: s, ls;
lstepf-invDeq-ADODEQ: lstepf(gs, ls, invDeq, ADoDeq(ls.tid)) = (gs.queue = [] ⊃ ls.oval:= Empty;ls.oval:= Val(gs.queue.head));
used for: s, ls;
lstepf-resDeq-ARETDEQ: lstepf(gs, ls, resDeq, ARetDeq(ls.tid, ls.oval)) = ls.optval:= ls.oval;
used for: s, ls;
gstepf-resDeq-ARETDEQ: gstepf(gs, ls, resDeq, ARetDeq(ls.tid, ls.oval)) = gs;
used for: s, ls;
gstepf-invEnq-ADOENQ: gstepf(gs, ls, invEnq, ADoEnq(ls.tid)) = gs.queue:= (gs.queue + ls.ival);
used for: s, ls;
gstepf-resEnq-ARETENQ: gstepf(gs, ls, resEnq, ARetEnq(ls.tid)) = gs;
used for: s, ls;
gstepf-ready: gstepf(gs, ls, ready, a) = gs;
used for: s, ls;
gstepf-idle-ARun: gstepf(gs, ls, idle, callARun(ls.tid)) = gs;
used for: s, ls;
gstepf-invDeq-ADODEQ: gstepf(gs, ls, invDeq, a) = (gs.queue = [] ⊃ gs;gs.queue:= gs.queue.tail);
used for: s, ls;
pcstepf-idle-ARun: pcstepf(gs, ls, idle, callARun(ls.tid)) = ready;
used for: s, ls;
pcstepf-ready-AINVENQ: pcstepf(gs, ls, ready, AInvEnq(ls.tid, value)) = invEnq;
used for: s, ls;
pcstepf-invEnq-ADOENQ: pcstepf(gs, ls, invEnq, ADoEnq(ls.tid)) = resEnq;
used for: s, ls;
pcstepf-resEnq-ARETENQ: pcstepf(gs, ls, resEnq, ARetEnq(ls.tid)) = ready;
used for: s, ls;
pcstepf-ready-AINVDEQ: pcstepf(gs, ls, ready, AInvDeq(ls.tid)) = invDeq;
used for: s, ls;
pcstepf-invDeq-ADODEQ: pcstepf(gs, ls, invDeq, ADoDeq(ls.tid)) = resDeq;
used for: s, ls;
pcstepf-resDeq-ARETDEQ: pcstepf(gs, ls, resDeq, ARetDeq(ls.tid, ls.oval)) = ready;
used for: s, ls;
end enrich