[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,

Specification DurQ
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