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