visit QP web site
go to Contents pagego to Installation pagereload this pageread about this and other CMP booksgo to Resources page
Exercises by Chapter

Chapter1
Exercise 1.1
Exercise 1.2
Exercise 1.2

Chapter 2
Exercise 2.1
Exercise 2.2
Exercise 2.3
Exercise 2.4

Chapter 3
Exercise 3.1
Exercise 3.2
Exercise 3.3
Exercise 3.4
Exercise 3.5
Exercise 3.6
Exercise 3.7
Exercise 3.8
Exercise 3.9
Exercise 3.10

Chapter 4
Exercise 4.1
Exercise 4.2
Exercise 4.3
Exercise 4.4
Exercise 4.5
Exercise 4.6
Exercise 4.7
Exercise 4.8
Exercise 4.9
Exercise 4.10
Exercise 4.12
Exercise 4.13
Exercise 4.14
Exercise 4.15

Chapter 5
Exercise 5.1
Exercise 5.2
Exercise 5.3
Exercise 5.4
Exercise 5.5
Exercise 5.6
Exercise 5.7
Exercise 5.8
Exercise 5.9
Exercise 5.10
Exercise 5.11
Exercise 5.12

Chapter 6
Exercise 6.1
Exercise 6.2
Exercise 6.3
Exercise 6.4
Exercise 6.5
Exercise 6.6
Exercise 6.7

Chapter 7
Exercise 7.1

Chapter 8
Exercise 8.1

Chapter 9
Exercise 9.1
Exercise 9.2
Exercise 9.3
Exercise 9.4

Chapter 10
Exercise 10.1
Exercise 10.2
Exercise 10.3
Exercise 10.4
Exercise 10.5
Exercise 10.6
Exercise 10.7
Exercise 10.8
Exercise 10.9
Exercise 10.10

Appendix A
Exercise A.1
Exercise A.2
Exercise A.3
Exercise A.4
Exercise A.5
Exercise A.6


Few things are harder to put up with than a good example.
— Mark Twain

This document contains the answers to all exercises scattered throughout the book. The convention of referring to the directories and files on the CD-ROM is <CD>:\, where <CD> is the drive letter of the CD-ROM drive on your machine. Alternatively, if you choose to install the software on your hard disk, <CD>: represents the complete path where you installed the software (e.g., C:\QP).

Most of the exercises contain hyperlinks to the source code or Microsoft Visual C++ projects. All these links use the relative paths, so they work directly on the CD-ROM, and also after installation to your hard-disk. Please note, however, that if you elect not to install certain software components (e.g., C++ with multiple inheritance), then the corresponding hyperlinks won't work when you browse this page from your hard-disk.


Chapter 1

Exercise 1.1 The Visual Basic calculator application is located in the directory <CD>:\Resources\VB. This directory contains three files: the executable Calc.exe, the Visual Basic source Calc.frm, and the Visual Basic 4.0 DLL Vb40032.dll necessary to execute the application. 

Some sequences of events that cause erroneous behavior of the Visual Basic calculator include (adopted from [Horrocks 99]):

  • Start application, '3', '-', '-', '1', '-'. At this point application crashes with an error indicating a runtime type mismatch.
  • Start application, '1', '-', '-', '%'. At this point application crashes with an error indicating a runtime type mismatch.
  • Start application, '2', '*', '2', '%', '%', '='. From this point on, the calculator will not perform any operations unless you click the Cancel button.
Back to Top

Exercise 1.2 The Quantum Calculator application is located in directory <CD>:\Cpp\Qcalc (C++ version), and <CD>:\C\Qcalc (the C version), The executables are <CD>:\Cpp\Qcalc\Release\calc.exe, and <CD>:\C\Qcalc\Release\calc.exe, respectively. The Quantum Calculator handles unary '-' and '+' only in states "begin" and "opEntered". In state "begin" the unary '-' causes transition to "negated1", whereas in "opEntered" to "negated2". The unary '+' is simply ignored in both these states.

Back to Top

Exercise 1.3 States "ready", "operand1", and "operand2" are composite (i.e., they contain substates). In UML statecharts, such states can become part of so called active configuration (see Chapter 2), but they can never become active directly — you will never see these states in the Quantum Calculator state-display. By the way, state "calc" is also composite and cannot become directly active either.

Back to Top

Chapter 2

Exercise 2.1 The following diagram shows the complete calculator statechart after "fleshing out" the internal structure of states "operand1" and "operand2" from Figure 2.7(b). Please note that at this stage the calculator cannot yet handle negative numbers and the Cancel Entry "CE" button.

Back to Top

Exercise 2.2 This version of the Quantum Calculator application is located in directory <CD>:\Cpp\Qcalc0. The executables is <CD>:\Cpp\Qcalc0\Release\Qcalc0.exe.

Back to Top

Exercise 2.3 The following diagram shows the refactored part of statechart from Figure 2.9. States "begin" and "result" inherit common transition from their superstate "ready". You can compare this fragment with the complete Quantum Calculator statechart from Figure 1.3 in Chapter 1.

Back to Top

Exercise 2.4 The following diagram shows adding electron spin as orthogonal region to the hydrogen atom statechart from Figure 2.10. The "coulomb" orthogonal region contains the whole statechart from Figure 2.10 as a sub-machine. States "spinUp" and "spinDown" in the "spin" orthogonal region use entry actions to set the spin quantum number s to + and -, respectively.

Back to Top

Chapter 3

The code pertaining to Chapter 3 is located in the directories: <CD>:\Cpp\Cparser (the C++ version), and <CD>:\C\Cparser (the C version). Each of these directories contains a VC++ workspace cparser.dsw, which in turn contains several VC++ projects.

Exercise 3.1 Examples of test harnesses for the C-comment parser state machine are provided in files <CD>:\Cpp\Cparser\Test1.cpp and <CD>:\C\Cparser\Test1.c for C++ and C versions, respectively. The following code fragment illustrates the main points:

#include "cparser1.h"    // include the C-comment parser declarations 
static CParser1 cparser;          // instantiate C-comment parser FSM 
 
int main(int argc, char *argv[]) { 
   . . . 
   cparser.init();                  // trigger the initial transition 
   while ((ch = fgetc(f)) != EOF) {    // read characters from a file 
       int sig; 
       switch (ch) {   // translate the characters into signal events 
       case '/': sig = SLASH_SIG; break; 
       case '*': sig = STAR_SIG;  break; 
       default:  sig = CHAR_SIG;  break; 
       } 
       cparser.dispatch(sig);      // dispatch the signals to the FSM 
       ++n;  
   } 
   . . . 
}
Back to Top

Exercise 3.2 In C, you can declare the CParser1 "class" as follows:

typedef struct CParser1 CParser1;           /* CParser1 class type */ 
struct CParser1 {              /* attributes of the CParser1 class */ 
   enum State state__;            /* private scalar state-variable */ 
   long commentCtr__;         /* private comment character counter */ 
}; 
                                  /* methods of the CParser1 class */ 
#define CParser1Init(me_) \ 
   ((me_)->commentCtr__ = 0, CParser1Tran(me_, CODE))  
void CParser1Dispatch(CParser1 *me, unsigned const sig); 
#define CParser1Tran(me_, target_) ((me_)->state__ = target_) 
#define CParser1GetCommentCtr(me_) ((me_)->commentCtr__)

Please note the use of the conventions described in Section A.1 of Appendix A. Every class "method" starts with the class name prefix (CParser1 in this case) "mangled" with the method name. Additionally, every method takes the pointer to the attribute structure as the first argument named me. Inline methods are implemented as preprocessor macros. The complete source code and executable image are available from the accompanying CD-ROM as a VC++ v6.0 project <CD>:\Cpp\Cparser\Cparser1.dsp.

Back to Top

Exercise 3.3 The alternative structure of the dispatch() method might look as follows:

void CParser1::dispatch(unsigned const sig) { 
   switch (myState) { 
   case CODE:    code(sig);    break; 
   case SLASH:   slash(sig);   break; 
   case COMMENT: comment(sig); break; 
   case STAR:    star(sig);    break; 
   } 
} 
 
void CParser1::code(unsigned const sig) { . . . } 
void CParser1::slash(unsigned const sig) { . . . } 
void CParser1::comment(unsigned const sig) { . . . } 
void CParser1::star(unsigned const sig) { . . . }

Where the state-handler methods code(), slash(), comment(), and star() contain only one level of switch that uses sig as the discriminator.

Back to Top

Exercise 3.4 The executable image and the complete source code and are available from the accompanying CD-ROM as VC++ v6.0 project <CD>:\Cpp\Cparser\Cparser2.dsp. The following listing illustrates the use of "C+" macros CLASS() and SUBCLASS() (see Appendix A) to declare the generic StateTable class and the specific CParser2 state machine subclass:

/* generic "event processor" ... */ 
struct StateTable;                          /* forward declaration */ 
typedef void (*Action)(struct StateTable *);  /* pointer-to-member */ 
CLASS(Tran) 
   Action action; 
   unsigned nextState; 
METHODS 
END_CLASS 
 
CLASS(StateTable) 
   Tran const *table__; 
   unsigned nSignals__; 
   unsigned nStates__; 
   unsigned state__; 
METHODS 
   StateTable *StateTableCtor(StateTable *me, Tran const *table,  
                              unsigned nStates, unsigned nSignals); 
   void StateTableDispatch(StateTable *me, unsigned const sig); 
   void StateTableDoNothing(StateTable *me); 
END_CLASS 
 
/* specific Comment Parser state machine ... */ 
SUBCLASS(CParser2, StateTable)           /* CParser2 state machine */ 
   long commentCtr__;                 /* comment character counter */ 
METHODS 
   CParser2 *CParser2Ctor(CParser2 *me); 
   void CParser2Init(CParser2 *me);               /* initial tran. */ 
   #define CParser2GetCommentCtr(me_) ((me_)->commentCtr__) 
   void CParser2A1(CParser2 *me);                 /* action method */ 
   void CParser2A2(CParser2 *me);                 /* action method */ 
END_CLASS

The following code fragment shows the definition of the StateTableDispatch() method:

void StateTableDispatch(StateTable *me, unsigned const sig) { 
   register Tran const *t = me->table__ +  
                            me->state__*me->nSignals__ + sig;  
   (t->action)(me); 
   me->state__ = t->nextState; 
}
Back to Top

Exercise 3.5 The complete code for this exercise is available from <CD>:\Cpp\Cparser\Cparser7.dsp (C++ version) and <CD>:\C\Cparser\Cparser7.dsp (C version). The following listing shows the modified StateTable class. Note that the state table stores now only Actions, that is, pointers-to-member functions:

class StateTable { 
public: 
   typedef void (StateTable::*Action)(); 
   StateTable(Action const *table, unsigned nSta, unsigned nSig) 
      : myTable(table), myNsignals(nSig), myNstates(nSta) {} 
   void dispatch(unsigned const sig) { 
      register Action const a =*(myTable + myState*myNsignals + sig); 
      (this->*(a))(); 
   } 
   void doNothing() {} 
protected: 
   void tran(unsigned target) { myState = target; } 
protected: 
   unsigned myState; 
private: 
   Action const *myTable; 
   unsigned myNsignals; 
   unsigned myNstates; 
}; 
 
// specific Comment Parser state machine ... 
enum Event {                        // enumeration for CParser events 
   CHAR_SIG, STAR_SIG, SLASH_SIG, MAX_SIG 
}; 
enum State {                        // enumeration for CParser states 
   CODE, SLASH, COMMENT, STAR, MAX_STATE 
}; 
class CParser7 : public StateTable {        // CParser2 state machine 
public: 
   CParser7() : StateTable(&myTable[0][0], MAX_STATE, MAX_SIG) {} 
   void init() { myCommentCtr = 0; myState = CODE; } // initial tran. 
   long getCommentCtr() const { return myCommentCtr; } 
private:                                         // action methods... 
   void codeOnSLASH() { tran(SLASH); }  
   void slashOnCHAR() { tran(CODE);  } 
   void slashOnSTAR() { myCommentCtr += 2; tran(COMMENT); } 
   . . . 
private: 
   static Action const myTable[MAX_STATE][MAX_SIG]; 
   long myCommentCtr;                    // comment character counter 
}; 
 
StateTable::Action const CParser7::myTable[MAX_STATE][MAX_SIG] = { 
   {&StateTable::doNothing,  
    &StateTable::doNothing,  
    static_cast<StateTable::Action>(&CParser7::codeOnSLASH) }, 
    . . . 
};
Back to Top

Exercise 3.6 The complete code for the "State" design pattern is available from <CD>:\Cpp\Cparser\Cparser3.dsp (C++ version) and <CD>:\C\Cparser\Cparser3.dsp (C version). The following code snippet shows the C-declaration of the abstract CParserState class and one of its specific subclasses (CodeState):

struct CParser3;             /* Context class, forward declaration */ 
SUBCLASS(CParserState, Object)                   /* abstract State */ 
VTABLE(CParserState, Object) 
   void (*onCHAR)(CParserState *me, struct CParser3 *ctxt, char ch); 
   void (*onSTAR)(CParserState *me, struct CParser3 *ctxt); 
   void (*onSLASH)(CParserState *me, struct CParser3 *ctxt); 
METHODS 
   CParserState *CParserStateCtor(CParserState *me); 
END_CLASS 
 
SUBCLASS(CodeState, CParserState)         /* concrete State "code" */ 
VTABLE(CodeState, CParserState) 
METHODS 
   CodeState *CodeStateCtor(CodeState *me);   
END_CLASS

Note that the CParserState superclass introduces virtual methods onCHAR(), onSTAR(), and on-SLASH(), which are not repeated in the subclass' VTABLE. 

Perhaps the most tricky part of the C implementation is proper initialization of the VTABLES and VPTRs (something that C++ compilers do behind the scenes). The following code fragment shows the definition of CodeState class VTABLE and the constructor:

BEGIN_VTABLE(CodeState, CParserState) 
   VMETHOD(CParserState, onSLASH) =  
      (void (*)(CParserState *, CParser3 *))CodeStateOnSLASH__; 
END_VTABLE 
 
CodeState *CodeStateCtor(CodeState *me) { 
   CParserStateCtor(&me->super_);          /* construct superclass */ 
   VHOOK(CodeState);                /* hook on the CodeState class */ 
   return me; 
}
Back to Top

Exercise 3.7 The complete code for this exercise is available from <CD>:\Cpp\Cparser\Cparser8.dsp (C++ version) and <CD>:\C\Cparser\Cparser8.dsp (C version). The following code fragment shows the most important modifications with respect to the implementation described in Section 3.4 of Chapter 3:

class CParser8;                 // Context class, forward declaration 
class CParserState {                                // abstract State 
public: 
   virtual void dispatch(CParser8 *context, unsigned sig, char ch) {} 
}; 
 
class CodeState : public CParserState {      // concrete State "code" 
public: 
   virtual void dispatch(CParser8 *context, unsigned sig, char ch); 
}; 
 
. . . 
class CParser8 {                                     // Context class 
   . . . 
   void dispatch(unsigned sig, char ch) { 
      myState->dispatch(this, sig, ch); 
   } 
};

The CParserState abstract class declares only one virtual method dispatch() with the most general signature. Subsequently all concrete states override this method. The context class CParser8 delegates all signal events to the dispatch() method of the current state.

Back to Top

Exercise 3.8 The complete code for the "Optimal FSM" design pattern is available from <CD>:\Cpp\Cparser\Cparser4.dsp (C++ version) and <CD>:\C\Cparser\Cparser4.dsp (C version). The following code fragment illustrates the alternative C implementation of a state-handler that uses a table look-up instead of the switch statement:

static void CParser4commentOnCHAR(CParser4 *me) { 
   ++me->commentCtr__;              /* count the comment character */ 
} 
static void CParser4commentOnSTAR(CParser4 *me) { 
   TRAN(CParser4star);                     /* transition to "star" */ 
} 
static void CParser4commentOnSLASH(CParser4 *me) { 
   ++me->commentCtr__;              /* count the comment character */ 
} 
void CParser4comment(CParser4 *me, unsigned const sig) { 
   static const void (*lookup[])(CParser4 *) = { 
      CParser4commentOnCHAR, 
      CParser4commentOnSTAR, 
      CParser4commentOnSLASH 
   }; 
   REQUIRE(sig <= SLASH_SIG);           /* signal must be in range */ 
   (*lookup[sig])(me);        /* rapidly dispatch without 'switch' */ 
}
Back to Top

Exercise 3.9 The following code shows a typical implementation of a state machine based on function pointers, but still using a scalar state variable as an index into a jump table (the code fragment comes literally from the article [Gomez 00]):

typedef enum {GEAR_DOWN = 0, WTG_FOR_TKOFF, RAISING_GEAR,  
              GEAR_UP, LOWERING_GEAR} State_Type; 
void InitializeLdgGearSM() { printf("Hi"); } 
void GearDown() {} 
void WtgForTakeoff() {} 
void RaisingGear() {} 
void GearUp() {}  
void LoweringGear() {} 
 
/* This table contains a pointer to the function to call  
   in each state.*/ 
void (*state_table [])()= { GearDown, WtgForTakeoff, RaisingGear,  
                            GearUp, LoweringGear }; 
State_Type curr_state; 
 
main() { 
   InitializeLdgGearSM(); 
   /* The heart of the state machine is this one loop. The function 
   corresponding to the current state is called once per iteration.*/ 
   while (1) { 
      state_table [curr_state ](); 
      /* Do other functions, not related to this state machine. */ 
   } 
};

The following assembly output corresponds to the emphasized line within the while(1) loop:

00401025  mov   eax,[00406A84]         ; get curr_state into register 
0040102A  call  dword ptr [eax*4+406030h]       ; jump to the handler

This code invokes a state-handler function through a table lookup. As you can see, the indirection through the table requires additional assembly instructions compared to the direct function-pointer dereferencing (Section 3.6 in Chapter 3). The other disadvantages of this approach include: enumerating states, declaring the jump table, and initializing the jump table. All these steps are unnecessary in the "Optimal FSM" technique.

Back to Top

Exercise 3.10 Counting comment blocks cannot be implemented in the entry action to "comment" state because this sate is entered potentially many times from the "star" state. For example, the following comment block causes three entries to the "comment" state: /* compute: (*p)*(*q) */. Figure 4.4. in Chapter 4 shows two examples of HSMs for the C-comment parser. Counting the number of entries into the composite "comment" state in either of the HSMs indeed provides the number of complete comment blocks. Exercise 4.8 shows a concrete implementation.

Back to Top

Chapter 4

Exercise 4.1 The "Quantum FSM" QFsm class is part of the Quantum Framework (QF). You can find the declaration for this class in <CD>:\Cpp\QF\Include\qfsm.h and the implementation in <CD>:\Cpp\QF\Source\qfsm.cpp (the C version in <CD>:\C\QF\Include\qfsm.h and <CD>:\C\QF\Source\qfsm.c). Here is the C++ declaration of the QFsm class:

class QFsm {                       // Finite State Machine base class 
public: 
   typedef void (QFsm::*QFsmState)(QEvent const *); 
   QFsm(QFsmState initial) { myState = initial; }             // Ctor 
   void init(QEvent const *e = 0) { (this->*myState)(e); } 
   void dispatch(QEvent const *e) { (this->*myState)(e); } 
   QFsmState getState() const { return myState; } 
   static char const *getVersion(); 
protected: 
   void tran(QFsmState target) { myState = target; } 
   #define QFSM_TRAN(target_) tran((QFsmState)target_) 
private: 
   QFsmState myState;                             // the active state 
};

And here is the "C+" version:

typedef void (*QFsmState)(struct QFsm *, QEvent const *); 
 
SUBCLASS(QFsm, Object)  /* Quantum Finite State Machine base class */ 
   QFsmState state__;                          /* the active state */ 
VTABLE(QFsm, Object) 
METHODS 
/* public methods */ 
   #define QFsmInit(me_, e_) ((*(me_)->state__)((me_), (e_)))  
                                               /* "inline" methods */ 
   #define QFsmDispatch(me_, e_) (*(me_)->state__)((me_), (e_)) 
   #define QFsmGetState(me_) ((me_)->state__) 
 
/* protected methods */ 
   QFsm *QFsmCtor_(QFsm *me, QFsmState initial);           /* Ctor */ 
   void QFsmXtor_(QFsm *me);                               /* Xtor */ 
   #define QFSM_TRAN(target_) \ 
      (((QFsm *)me)->state__ = (QFsmState)(target_)) 
                               /* static methods (no "me" pointer) */ 
   char const *QFsmGetVersion(void); 
END_CLASS

The C-comment parser implementation based on the QFsm class is available from <CD>:\Cpp\Cparser\Cparser5.dsp (C++), and <CD>:\C\Cparser\Cparser5.dsp (C).

Back to Top

Exercise 4.2 The alternative design of the QHsm class looks as follows:

class QHsm { 
   . . . 
   QHsm();                                            // default Ctor 
   virtual void initial() = 0;     // pure virtual initial transition 
   . . . 
};

Note that the QHsm constructor no longer needs to take the initial-pseudostate argument. The init() method invokes the initial() transition as follows (compare with Listing 4.8 in Chapter 8):

void QHsm::init() { 
   REQUIRE(myState == Q_STATE_CAST(top))      // HSM not executed yet 
   register QState s = myState;        // save myState in a temporary 
   initial();                          // top-most initial transition 
   ASSERT(s ==           // initial transition must go one level deep 
             Q_STATE_CAST((this->*myState)(&pkgStdEvt[Q_EMPTY_SIG])); 
   s = myState;                               // update the temporary 
   (this->*s)(&stdEvt[Q_ENTRY_SIG]);            // enter the substate 
   while ((this->*s)(&stdEvt[Q_INIT_SIG]) == 0) {    // init handled? 
      ASSERT(s ==        // initial transition must go one level deep 
             Q_STATE_CAST((this->*myState)(&pkgStdEvt[Q_EMPTY_SIG])); 
      s = myState; 
      (this->*s)(&stdEvt[Q_ENTRY_SIG]);         // enter the substate 
   } 
}

Overall, in C++ using pure virtual initial transition seems more natural and elegant, especially be-cause the price for the virtual table has already been paid (QHsm has a virtual destructor). However, introduction of polymorphism into the C implementation is more involved and probably not justified only for the initial transition.

Back to Top

Exercise 4.3 The previous QHsm class (Exercise 4.2) can be extended as follows:

class QHsm { 
   . . . 
   virtual void onUnhandled(QEvent const *e) {} 
   QState top(QEvent const *e) {                     // the top state 
      if (e->sig >= Q_USER_SIG) { 
         onUnhandled(e);      // user policy for the unhandled events 
      } 
      return 0; 
    } 
   . . . 
};

The virtual method onUnhandled() implements the policy for dealing with unhandled events. The default is to do nothing, but clients can override this default in the subclasses of QHsm. The top state-handler invokes onUnhandled() only for user signals. As before, top() always returns 0.

Back to Top

Exercise 4.4 The complete source code and executable image for the annotated HSM example is available from directory <CD>:\Cpp\QHsmtst (C++ version) and <CD>:\C\QHsmtst (C version). You can use either implementation to execute the test.

Back to Top

Exercise 4.5 The source code and executable image for the modified statechart is available as project <CD>:\Cpp\QHsmtst\QHsmtst2.dsp (C++ version). The modifications involve cutting-and-pasting the transition 'e' from "s0" to "s2" and changing target state-handler of transition 'f' in state "s1".

Back to Top

Exercise 4.6 The source code and executable image for the modified statechart is available as project <CD>:\Cpp\QHsmtst\QHsmtst3.dsp (C++ version). The reason for the failing assertion in the initial transition in "s2" is crossing two levels of nesting (the current QHsm implementation allows only one). The second assertion fails because the "top" state cannot be a target of a state transition.

Exercise 4.7 The following listing contrasts side-by-side "ROOM linear form" ([Selic+ 94]) definition of the "s21" state from Figure 4.3 in Chapter 4 and the s21() state-handler method:
 

ROOM Linear Form State-handler Method
state s21: 
  vars: {(myFoo)} 
  entry action: {  
    printf("s21-ENTRY;"); 
  } 
  exit action: { 
    printf("s21-EXIT;"); 
  } 
  substates: {(s211)} 
   
 
  transitions: { 
    {transition b: 
      triggered by: (B_SIG,,true)
      action: {printf("s21-B;");}
      destination: state s211 }
    {transition h:
      triggered by:{H_SIG,,!myFoo}
      action: {printf("s21-H;");
               myFoo = 1; } 
      destination: state s21 }
  } 
QSTATE QHsmTst::s21(QEvent *e) {
   switch (e->sig) { 
   case Q_ENTRY_SIG:  
      printf("s21-ENTRY;");
      return 0; 
   case Q_EXIT_SIG: 
      printf("s21-EXIT;"); 
      return 0; 
   case Q_INIT_SIG: 
      printf("s21-INIT;"); 
      Q_INIT(&QHsmTst::s211);
      return 0; 
   case B_SIG: 
      printf("s21-B;"); 
      Q_TRAN(&QHsmTst::s211);
      return 0; 
   case H_SIG: 
      if (!myFoo) { 
         printf("s21-H;");
         myFoo = 1; 
         Q_TRAN(&QHsmTst::s21);
         return 0; 
      } 
      break; 
   } 
   return (QSTATE)&QHsmTst::s2;
}

As you can see, the state-handler implementation is quite similar to the "ROOM linear form" that has been specifically invented to capture state machines as succinctly as possible. Point to remember here is that state-handler methods not only implement a state machine but also are one of the most com-pact textual representations (documentation) of the state model.

Back to Top

Exercise 4.8 The following listing shows the declaration of the hierarchical C-comment parser from Figure 4.4(b) in Chapter 4:

class CParser6 : public QHsm {                        // C-parser HSM 
   long myCommentCtr;                    // comment character counter 
   long myCommBlkCtr;                        // comment block counter 
   void initial(QEvent const *e);              // initial pseudostate 
   QState code(QEvent const *e);                        // code state 
      QState slash(QEvent const *e);                   // slash state 
   QState comment(QEvent const *e);                  // comment state 
      QState star(QEvent const *e);                     // star state 
public: 
   CParser6() : QHsm((QPseudoState)initial) {}                // Ctor 
   long getCommentCtr() const { return myCommentCtr; } 
   long getCommBlkCtr() const { return myCommBlkCtr; } 
};

The hierarchical state-handler CParser6::comment() counts number of comments blocks in its entry action as follows:

QSTATE CParser6::comment(QEvent const *e) { 
   switch (e->sig) { 
   case Q_ENTRY_SIG: 
      ++myCommBlkCtr;                      // count number of entries 
      return 0; 
   case STAR_SIG: 
      Q_TRAN(&CParser6::star);                // transition to "star" 
      return 0; 
   case CHAR_SIG: 
   case SLASH_SIG: 
      ++myCommentCtr;                  // count the comment character 
      return 0;  
   } 
   return (QSTATE)&CParser6::top; 
}

You can find the complete implementation on the accompanying CD-ROM in the VC++ 6.0 projects <CD>:\Cpp\CParser\CParser6.dsp (C++ version) and <CD>:\C\CParser\CParser6.dsp (C version).

Back to Top

Exercise 4.9 The "is-in-state" query QHsmIsIn() is implemented as follows (C version):

int QHsm::isIn(QState state) { 
   register QState s; 
   for (s = myState; s; s = TRIGGER(mySource, Q_EMPTY_SIG)) { 
      if (s == state) {                       // do the states match? 
         return !0;                       // match found, return true 
      } 
   } 
   return 0;                          // no match found, return false 
}

This routine performs identical state traversal as dispatch(), except it sends only "empty signals" to the state-handlers. You can find the C++ version of the "is-in-state" query in <CD>:\Cpp\Source\Qhsm.cpp.

Back to Top

Exercise 4.10 The complete source code and executable image for this version of QHsmTst class are avail-able as the following VC++ v6.0 projects <CD>:\Cpp\QHsmtst\QHsmtst2.dsp (C++ version).

Back to Top

Exercise 4.12 You need to insert the "active-state" instrumentation "hook" in the following points: (1) as the last instruction of method QHsm::init() (Listing 4.8), (2) as the last instruction of method QHsm::tranStat() (Listing 4.11), and (3) as the last instruction of method QHsm::tran() (Listing 4.10). The "hook" may for instance, consist of a call to a virtual method QHsm::onActiveState().

Back to Top

Exercise 4.13 The complete C implementation of the QHsm class is available as part of the C version of the Quantum Framework (QF). You can find it on the accompanying CD-ROM in the files: <CD>:\C\Qf\Include\Qhsm.h and <CD>:\C\Qf\Source\Qhsm.c.

Back to Top

Exercise 4.14 The complete source code and executable image for the "C+" version of the test state machine is available as the VC++ v6.0 project located in <CD>:\C\QHsmtst\QHsmtst.dsp.

Back to Top

Exercise 4.15 The complete source code and executable image for the "C+" version of the Quantum Calculator is available as the VC++ v6.0 project located in <CD>:\C\QCalc\Calc.dsp.

Back to Top

Chapter 5

The code pertaining to Chapter 5 is located in the directories: <CD>:\Cpp\Qpattern (the C++ version), and <CD>:\C\Qpattern (the C version). Each of these directories contains a VC++ workspace qpattern.dsw, which in turn contains several VC++ projects.

Exercise 5.1 The C implementation of the "Ultimate Hook" state pattern is provided in the file <CD>:\C\Qpattern\hook.c. The following code fragment illustrates the main points:

SUBCLASS(UltimateHook, QHsm)      /* UltimateHook subclass of QHsm */ 
METHODS 
   UltimateHook *UltimateHookCtor(UltimateHook *me);       /* Ctor */ 
   void UltimateHook_initial(UltimateHook *me, QEvent const *e); 
   QSTATE UltimateHook_generic(UltimateHook *me, QEvent const *e); 
     QSTATE UltimateHook_specific(UltimateHook *me, QEvent const *e); 
   QSTATE UltimateHook_final(UltimateHook *me, QEvent const *e); 
END_CLASS 
 
UltimateHook *UltimateHookCtor(UltimateHook *me) { 
   QHsmCtor_(&me->super_,(QPseudoState)&UltimateHook_initial); 
   return me; 
} 
void UltimateHook_initial(UltimateHook *me, QEvent const *e) { 
   Q_INIT(&UltimateHook_generic); 
} 
. . . 
QSTATE UltimateHook_specific(UltimateHook *me, QEvent const *e) { 
   switch (e->sig) { 
   case Q_ENTRY_SIG: printf("specific:entry;"); return 0; 
   case Q_EXIT_SIG:  printf("specific:exit;");  return 0; 
   case A_SIG:       printf("specific:A;");     return 0; 
   } 
   return (QSTATE)&UltimateHook_generic; 
} 
static UltimateHook test;    /* instantiate the UlitmateHook class */ 
static const QEvent testQEvt[] = {  
   { A_SIG, 0, 0 }, { B_SIG, 0, 0 }, { C_SIG, 0, 0 }, { D_SIG, 0, 0 } 
}; 
main() { 
   . . . 
   UltimateHookCtor(&test);                  /* explicit Ctor call */ 
   QHsmInit((QHsm *)&test, 0);      /* take the initial transition */ 
   for (;;) { 
      char c; 
      printf("\nSignal<-"); 
      c = getc(stdin);  
      getc(stdin);                                 /* discard '\n' */ 
      if (c < 'a' || 'd' < c) { 
         c = 'd';                                          /* exit */ 
      } 
      QHsmDispatch((QHsm *)&test, &testQEvt[c - 'a']); 
   } 
   return 0; 
}

The emphasized elements of this implementation include declaration and implementation of the constructor, explicit call to the superclass' constructor, instantiation of the class, explicit invocation of the constructor, taking the initial transition and dispatching events.

Back to Top

Exercise 5.2 To change the frequency of generating the DATA_READY event, you need to modify the guard of the WM_TIMER internal transition in the "polling" state as follows:

QSTATE Sensor::polling(QEvent const *e) { 
   switch (e->sig) { 
   . . . 
   case WM_TIMER: 
      SetDlgItemInt(mainWnd, IDC_POLL, ++myPollCtr, FALSE); 
      if ((myPollCtr & 0x7) == 0){  // post DATA_READY every 8th time 
         PostMessage(mainWnd, WM_COMMAND, DATA_READY, 0); 
      } 
      return 0; 
   . . . 
}

The "Reminder" state pattern implementation is provided as a VC++ project located in <CD>:\Cpp\Qpattern\reminder.dsp.

Back to Top

Exercise 5.3 The translation of the C++ code (located in <CD>:\Cpp\Qpattern\reminder.cpp) to C is straightforward. Perhaps the only significant difference from the C++ implementation is the necessity of calling the constructor SensorCtr() explicitly, as shown in the following code snippet:

int WINAPI WinMain(...) { 
   . . . 
   SensorCtor(&app);           /* construct the Sensor application */ 
   . . . 
}

The C version of the "Reminder" state pattern is provided as a VC++ project located in <CD>:\C\Qpattern\reminder.dsp.

Back to Top

Exercise 5.4 The complete source code and executable image for the "Deferred Event" state pattern are available as the following VC++ projects <CD>:\Cpp\Qpattern\defer.dsp (C++ version) and <CD>:\C\Qpattern\defer.dsp (C version). The Windows timer is not leaked, because the TERMINATE signal triggers a state transition out of the "operational" state. Such a transition always involves guaranteed cleanup through executing exit actions from the substates, such as "receiving" and "authorizing".

Back to Top

Exercise 5.5 The translation of the C++ code (located in <CD>:\Cpp\Qpattern\defer.cpp) to C is straightforward. Again, as in the Exercise 5.3 you should explicitly call the TServerCtor() constructor in the WinMain() method. The C version of the "Deferred Event" state pattern is provided as a VC++ project located in <CD>:\C\Qpattern\defer.dsp.

Back to Top

Exercise 5.6 Deferring the TERMINATE signal involves instantiating the "Deferred Event" state pattern for the second time in the TServer statechart. Here are the augmented class and state diagrams (added elements are shown in boldface):

You can find this version of the TServer statechart in the VC++ project <CD>:\Cpp\Qpattern\defer1.dsp.

The test plan for the deferred handling of the TERMINATE signal involves testing three scenarios. The first is the check that the application terminates immediately when it is idle (not processing any re-quests). The second scenario involves posting the transaction request, and terminating the application before the end of processing. The application should not close immediately, but wait until the processing ends. The final scenario involves quickly posting two transaction requests (so that the second is deferred), and then shortly thereafter terminating the application. The application should process both transaction requests before closing down.

Back to Top

Exercise 5.7 The hierarchical version of the Alarm state machine class looks as follows (note the use of the "Device Mode" idiom):

The following pseudocode highlights the most interesting elements of the Alarm statechart implementation:

void Alarm::initial(QEvent const *e) { 
   . . . 
   Q_INIT(&Alarm::alarm); 
} 
 
QSTATE Alarm::alarm(QEvent const *e) { 
   switch (e->sig) { 
   case Q_INIT_SIG: Q_INIT(&Alarm::on);  return 0; 
   case IDC_ON: 
      if (alarm time valid) { 
         . . . 
         Q_TRAN(&Alarm::on);                   // "Device Mode" idiom 
      } 
      . . . 
      return 0; 
   case IDC_OFF: 
      . . . 
      Q_TRAN(&Alarm::off);                     // "Device Mode" idiom 
      return 0; 
   } 
   return (QSTATE)&Alarm::top; 
} 
 
QSTATE Alarm::on(QEvent const *e) { 
   switch (e->sig) { 
   case TIME_SIG: 
      if (((TimeEvt *)e)->currentTime == myAlarmTime) { 
         Beep(1000, 20); 
         PostMessage(myHwnd, WM_COMMAND, ALARM_SIG, 0);     // notify 
      } 
      return 0; 
   } 
   return (QSTATE)&Alarm::alarm; 
} 
QSTATE Alarm::off(QEvent const *e) { 
   return (QSTATE)&Alarm::alarm; 
}

You can find this version of the Alarm statechart in the VC++ project <CD>:\Cpp\Qpattern\comp1.dsp.

Back to Top

Exercise 5.8 The complete source code and executable image for this version of the "Orthogonal Component" state pattern are available as the following VC++ v6.0 projects <CD>:\Cpp\Qpattern\comp.dsp (C++ version) and <CD>:\C\Qpattern\comp.dsp (C version).

Back to Top

Exercise 5.9 In C, you declare the Alarm and AlarmClock classes as follows:

SUBCLASS(Alarm, QFsm)   // subclass the QFsm class (non-hierarchical) 
   unsigned alarmTime__; 
   HWND hWnd__;                                   /* window handle */ 
METHODS 
   Alarm *AlarmCtor(Alarm *me); 
   void Alarm_initial(Alarm *me, QEvent const *e); 
   void Alarm_on(Alarm *me, QEvent const *e); 
   void Alarm_off(Alarm *me, QEvent const *e); 
END_CLASS 
 
SUBCLASS(AlarmClock, QHsm)  // subclass the QHsm class (hierarchical) 
   unsigned currentTime__; 
   Alarm alarm__;                    /* Alarm orthogonal component */ 
   BOOL isHandled__; 
   HWND hWnd__;                                   /* window handle */ 
METHODS 
   AlarmClock *AlarmClockCtor(AlarmClock *me); 
   void AlarmClock_initial(AlarmClock *me, QEvent const *e); 
   QSTATE AlarmClock_timekeeping(AlarmClock *me, QEvent const *e); 
      QSTATE AlarmClock_mode12hr(AlarmClock *me, QEvent const *e); 
      QSTATE AlarmClock_mode24hr(AlarmClock *me, QEvent const *e); 
   QSTATE AlarmClock_final(AlarmClock *me, QEvent const *e); 
END_CLASS

The container AlarmClock is responsible for constructing its component(s) explicitly:

AlarmClock *AlarmClockCtor(AlarmClock *me) { 
   QHsmCtor_(&me->super_, (QPseudoState)&AlarmClock_initial); 
   AlarmCtor(&me->alarm__);             /* construct the component */ 
   return me; 
}

Also, you must not forget to invoke the container's constructor explicitly:

int WINAPI WinMain(HINSTANCE hInst, HINSTANCE hPrevInst, 
                   PSTR cmdLine, int iCmdShow) 
{ 
    . . . 
    AlarmClockCtor(&app);  /* construct the AlarmClock application */ 
    DialogBox(hInst, MAKEINTRESOURCE(IDD_DIALOG), NULL,  
              alarmClockDlg);                   
    return 0;          /* exit application when the dialog returns */ 
}

The complete C implementation of the "Orthogonal Component" state pattern is provided as a VC++ v6.0 project <CD>:\C\Qpattern\comp.dsp.

Back to Top

Exercise 5.10 Applying the Singleton design pattern to the AlarmClock class involves adding the static instance() method and protecting the constructor:

class AlarmClock : public QHsm { 
public: 
   static AlarmClock *instance();        // Singleton accessor method 
private: 
   AlarmClock() : QHsm((QPseudoState)initial) {}      // private Ctor 
   . . . 
   HWND myHwnd;         // the main window handle (shared with Alarm) 
   friend class Alarm; 
};

Usually, the container class (AlarmClock) grants friendship to the components (Alarm). The AlarmClock::instance() method can be implemented as follows:

AlarmClock * AlarmClock::instance() {           // Singleton accessor 
   static AlarmClock app; 
   return &app; 
}

Subsequently, all accesses to the sole AlarmClock instance are through the instance() method. In particular the Alarm component can access (share) the AlarmClock::myHwnd attribute as follows:

void Alarm::on(QEvent const *e) { 
   switch (e->sig) { 
   case TIME_SIG: 
      if (((TimeEvt *)e)->currentTime == myAlarmTime) { 
         Beep(1000, 20); 
         PostMessage(AlarmClock::instance()->myHwnd,  
                     WM_COMMAND, ALARM_SIG, 0);             // notify 
      } 
      return; 
   . . . 
   } 
}

The sharing of container attributes simplifies the components, which now don't need to maintain the shared elements (e.g., the component Alarm doesn't need to keep and initialize the window-handle myHwnd). On the flip side, however, data sharing couples the components to a concrete container—the components cannot be easily reused with a different container.

This version of the "Orthogonal Component" state pattern is available as the VC++ project <CD>:\Cpp\Qpattern\comp2.dsp.

Back to Top

Exercise 5.11 The complete source code and executable image for the "Transition to History" state pattern is available as the VC++ v6.0 project <CD>:\Cpp\Qpattern\history.dsp.

Back to Top

Exercise 5.12 The translation of the C++ code (located in <CD>:\Cpp\Qpattern\history.cpp) to C is straightforward. As always in C, you should explicitly call the ToasterOvenCtor() constructor in the main() method. The C version of the "Transition to History" state pattern is provided as a VC++ project located in <CD>:\C\Qpattern\history.dsp.

Back to Top

Chapter 6

Exercise 6.1 The Visual Basic calculator application is located in the directory <CD>:\Resources\VB. This directory contains three files: the executable Calc.exe, the Visual Basic source Calc.frm, and the Visual Basic 4.0 DLL Vb40032.dll necessary to execute the application (see also Exercise 1.1 in Chapter 1).

Back to Top

Exercise 6.2 The complete source code and executable image for the enhanced Quantum Calculator are available as the following VC++ v6.0 projects: <CD>:\Cpp\Qcalc2\Calc2.dsp (C++ version).

Back to Top

Exercise 6.3 You add an entry action to the operator2() state handler in the usual way (see Exercise 6.2 for the location of the source files):

QSTATE Calc2::operand2(QEvent const *e) { 
   switch (e->sig) {
   case Q_ENTRY_SIG: 
      Beep(1000, 20); 
      return 0; 
   case IDC_PERCENT: 
   . . . 
   } 
   return Calc1::operand2(e);        // let Calc1 handle other events 
}
Back to Top

Exercise 6.4 Removing the keyword virtual in line 6 of Listing 6.3 disables the virtual mechanism in the invocation of the pointer-to-member function (i.e., both invocations end up calling Foo::g()). The following machine-language output is almost identical to the output in Section 6.1.1, except now function Foo::f() returns the address of Foo::g() instead of the virtual thunk as before.

; Foo::g() 
00401010   push        406040h        ; stack address of "Foo::g()\n" 
00401015   call        004010B0       ; call printf() 
0040101A   pop         ecx 
0040101B   ret 
 
; Bar::g() 
00401020   push        40604Ch        ; stack address of "Bar::g()\n" 
00401025   call        004010B0       ; call printf() 
0040102A   pop         ecx 
0040102B   ret 
 
; main() 
00401090   mov         ecx,4068E8h    ; grab address of foo 
00401095   call        dword ptr ds:[4068E4h] ; call via pointer h 
0040109B   mov         ecx,4068E0h    ; grab address of bar 
004010A0   jmp         dword ptr ds:[4068E4h] ; call via pointer h 
 
; Foo::f() 
00401B96   mov         eax,[00406E14] 
00401B9B   test        eax,eax 
00401B9D   je          00401BA1 
00401B9F   call        eax 
00401BA1   push        406020h 
00401BA6   push        406014h 
00401BAB   call        00401C7E 
00401BB0   push        406010h 
00401BB5   push        406000h 
00401BBA   call        00401C7E 
00401BBF   add         esp,10h 
00401BC2   ret

In this case early binding occurs in both method invocations within main(), because the pointer-to-member function h holds now address of Foo::g() (and not the vcall thunk).

The code pertaining to this test is available as the VC++ v6.0 projects: <CD>:\Cpp\Ptm_test\test.dsp (virtual version) and <CD>:\Cpp\Ptm_test\test2.dsp (non-virtual version).

Back to Top

Exercise 6.5 The C implementation of the enhanced Quantum Calculator is available in the VC++ v6.0 project <CD>:\C\Qcalc2\Calc2.dsp. The following code fragment illustrates adding an entry action to the Calc2_operand2() state handler (see also Exercise 6.3):

QSTATE Calc2_operand2(Calc2 *me, QEvent const *e) { 
   switch (e->sig) { 
   case Q_ENTRY_SIG: 
      Beep(1000, 20); 
      return 0; 
   case IDC_PERCENT: 
      . . .} 
   } 
                                   /* let Calc handle other events */ 
   return Calc1_operand2((Calc1 *)me, e);  
}
Back to Top

Exercise 6.6 The complete source code and executable image for the enhanced Quantum Calculator are available as the following VC++ v6.0 projects: <CD>:\Cpp\Qcalc2\Calc2.dsp (C++ version) and <CD>:\C\Qcalc2\Calc2.dsp (C version). You can use either version to replace the macro Q_TRAN() with Q_TRAN_DYN().

Back to Top

Exercise 6.7 The MI-compatible version of the Quantum Framework (QF) is located in the directory <CD>:\CppMI. In particular, the QHsm class is declared in the header file <CD>:\CppMI\Qf\include\qhsm.h, and defined in <CD>:\CppMI\Qf\source\qhsm.cpp. Please note that this implementation is completely separated from the rest of the C++ code.

The modified class QHsm is declared as follows:

class QHsm {      // MI-compatible Quantum Hierarchical State Machine 
public: 
   class CQState { // "functor" class encapsulating pointer-to-member 
   public: 
      typedef CQState (QHsm::*QState)(QEvent const *); 
      . . . 
      CQState operator()(QHsm *hsm, QEvent const *e) {  
         return hsm->callMemberFn(myPtMF, e, hsm); 
      } 
   private: 
      QState myPtMF;          // pointer-to-member function attribute 
   }; 
   friend class QHsm::CQState; 
 
public: 
   typedef QHsm::CQState CQSTATE; 
   #define QSTATE_SC(fn) CQState(static_cast<CQState::QState>(fn)) 
 
      // the following macro should be placed in *each* derived class 
   #define Q_DEFINE_CALL_MEMBER_FN(class_) \ 
      virtual CQState callMemberFn(CQState::QState fn, \ 
                                   QEvent const *e, QHsm *hsm)\ 
      {\ 
         class_ *c = static_cast<class_*>(hsm); \ 
         return (c->*fn)(e); \ 
      } 
   void init();                         // execute initial transition 
   void dispatch(QEvent const *e);                  // dispatch event 
   int isIn(CQState state) const;              // "is-in-state" query 
   static char const *getVersion(); 
 
protected: 
   QHsm(CQState::QState initial);                             // Ctor 
   virtual ~QHsm();                   // pure virtual (abstract) Xtor 
   virtual CQState callMemberFn(CQState::QState fn,   // pure virtual 
                                QEvent const *e, QHsm *hsm) = 0; 
   struct Tran {                        // protected inner class Tran 
      CQState myChain[8]; 
      unsigned short myActions;    // action mask (2-bits for action) 
   }; 
   CQState top(QEvent const*) { return 0; } //the "top" state-handler 
   CQState getState() const { return myState; } 
   void tran(CQState target);             // dynamic state transition 
   void tranStat(Tran *t,CQState target);  // static state transition 
   void init_(CQState target) { 
       myState = target; 
   } 
   #define Q_INIT(target_) \ 
      init_(CQState(static_cast<CQState::QState>(target_))) 
   #define Q_TRAN(target_) if (1) { \ 
      static Tran t_; \ 
      tranStat(&t_, CQState(static_cast<CQState::QState>(target_)));\ 
   } else ((void)0) 
   #define Q_TRAN_DYN(target_) tran((CQState)(target_)) 
private: 
   void tranSetup(Tran *t, CQState target); 
private: 
   CQState myState;                               // the active state 
   CQState mySource;              // source state during a transition 
};

To test MI, you can derive the enhanced Quantum Calculator Calc2 from multiple base classes, for example:

class TestBase { 
public: 
   virtual ~TestBase() {} 
}; 
 
class Calc2 : public Calc1, public TestBase {               // use MI 
protected: 
   Q_DEFINE_CALL_MEMBER_FN(Calc2)            // Define callMemberFn() 
   virtual CQSTATE operand2(QEvent const *e); 
};

Please note the invocation of the Q_DEFINE_CALL_MEMBER_FN() macro inside the Calc2 class. You can find the MI-compatible Quantum Calculator in the directory <CD>:\CppMI\Qcalc2\.

Back to Top

Chapter 7

Exercise 7.1 The probability of a deadlock in the traditional DPP implementation from Section 8.1.1 depends on many factors. Perhaps the three most important are: the likelihood of a context switch between acquiring the left fork and acquiring the right fork, the frequency of context switches, and how long a philosopher thinks compared to how long it eats. To increase the likelihood of the deadlock, you can for instance, enforce a context switch between acquiring the left fork and the right fork. On Microsoft Windows, you can achieve it by calling Sleep(0) (refer to the Microsoft Win32 API documentation).

The following screen capture shows an example of a debug session. The console in the background shows a deadlocked DPP application. Please note that all philosophers report the "hungry" status. To debug the application, you first need to break into the running program (remember, a deadlocked application is still "executing"). In the Microsoft Developer Studio, you can use the Debug/Break menu or a shortcut button on the toolbar. Subsequently, you can inspect the state of the philosopher threads through the menu Debug/Threads, which opens the "Threads" window shown in the screen capture. By double clicking on each thread, you can find out the code location at which it stopped. As expected, all philosopher threads are stopped at the yellow arrow in the source window "dpp.c".

Click to see bigger

You can find the source code corresponding to this example in the directory <CD>:\C\dpp\.

Back to Top

Chapter 8

Exercise 8.1 The following state diagram shows in heavy line the new elements added to the "Reminder" state pattern example from Chapter 5:

And here are the changes to the code (compare to Listing 5.2 in Chapter 5):

QSTATE Sensor::polling(QEvent const *e) { 
   switch (e->sig) { 
   case Q_ENTRY_SIG: SetTimer(myHwnd, 1, 500, 0);  return 0; 
   case Q_EXIT_SIG:  KillTimer(myHwnd, 1);         return 0; 
   . . . 
   case EXCEPTION: Q_TRAN(&Sensor::fault); return 0; 
   } 
   . . . 
   return (QSTATE)&Sensor::top; 
} 
QSTATE Sensor::busy(QEvent const *e) { 
   switch (e->sig) { 
   case Q_ENTRY_SIG: 
      SetDlgItemText(myHwnd, IDC_STATE, "busy"); 
      try { 
         faulty(); 
      } 
      catch (...) { 
         PostMessage(myHwnd, WM_COMMAND, EXCEPTION, 0); 
      } 
      return 0; 
   . . . 
   } 
   return (QSTATE)&Sensor::processing; 
} 
QSTATE Sensor::fault(QEvent const *e) { 
   switch (e->sig) { 
   case Q_ENTRY_SIG: 
      SetDlgItemText(myHwnd, IDC_STATE, "fault"); 
      return 0; 
   case TERMINATE: Q_TRAN(&Sensor::final);  return 0; 
   } 
   return (QSTATE)&Sensor::top; 
}

The state-based exception handling mechanism performs the cleanup of the Windows timer, because the transition from "polling" to "fault" triggered by the EXCEPTION event causes execution of exit actions. Among others the exit action from state "polling" cleans up the timer.

You can find the source code pertaining to this example in the VC++ v6.0 project <CD>:\Cpp\Qpattern\reminder1.dsp.

Back to Top

Chapter 9

Exercise 9.1 The following listing illustrates system initialization and hooking the timer ISR for On Time RTTarget-32:

enum { TIMER_IRQ = 0 }; 
 
int main() { 
   static RTInterruptGate rtt32ISR;        // to save original vector 
   RTSaveVector(RTIRQ0Vector + TIMER_IRQ, &rtt32ISR); 
   RTSetIntVector(RTIRQ0Vector + TIMER_IRQ, asmISR);   // hook asmISR 
   RTEnableIRQ(TIMER_IRQ);             // tell PIC to enable this IRQ 
 
   QF::init(...); 
   QF::poolInit(...); 
   activeA.start(...); 
   . . . 
   for (;;) { 
      QF::background();                      // background processing 
      if (_kbhit()) {                             // any key pressed? 
         break;                                          // terminate 
      } 
   } 
   QF::cleanup(); 
   RTDisableIRQ(TIMER_IRQ); 
   RTRestoreVector(RTIRQ0Vector + TIMER_IRQ, &rtt32ISR); 
   return 0; 
}

You can see saving the timer-tick ISR through RTSaveVector() followed by setting new vector through RTSetIntVector(). The latter function stores the address of the specified handler directly in the interrupt descriptor table (IDT). Therefore, the handler must save/restore all registers it uses and must be terminated with an IRETD instruction. The following code (copied from the sample application SerInt distributed with On Time RTOS-32) does just that:

__declspec(naked) void asmISR(void) {  // low-level interrupt handler 
   __asm { 
      push  eax            ; save all registers which may be changed 
      push  edx            ; by C/C++ code 
      push  ecx 
      push  ds 
      push  es 
      cld                  ; required by C/C++ run-time system 
      mov   ax, cs         ; data selector comes right after 
      lea   eax, [eax+8]   ; code selector (ES = DS = CS + 8) 
      mov   ds, ax         ; initialize default data segment 
      mov   es, ax 
      call  ISR            ; call 'C' Handler 
      pop   es             ; restore registers 
      pop   ds 
      pop   ecx 
      pop   edx 
      pop   eax 
      iretd                ; interrupt return 
   } 
}

Finally, the C-portion of the ISR handler looks as follows:

static void __cdecl ISR(void) {//high-level Interrupt Service Routine 
   QF::tick();                     // invoke the time-tick QF handler 
   RTIRQEnd(TIMER_IRQ);              // tell the PIC that we are done 
}

The directory <CD>:\Cpp\Qdpp\RTT32 contains source code and executable example of a fore-ground/background RTTarget-32 application.

Back to Top

Exercise 9.2 The following code fragment elevates the priority of the main thread to the THREAD_PRIORITY_TIME_CRITICAL level:

THREAD_PRIORITY_TIME_CRITICAL level:
int main() { 
   . . . 
   SetThreadPriority(GetCurrentThread(), 
                     THREAD_PRIORITY_TIME_CRITICAL); 
   for (;;) { 
      Sleep(10); 
      QF::tick(); 
      . . . 
   } 
   . . . 
}
Back to Top

Exercise 9.3 This QF port (which I call RTK32A) does not use the built-in RTKernel-32 mailboxes or memory pools. Instead, it uses the portable QEqueue and QEpool classes. The following listing shows the public-scope include file qf_rtk32a.h:

#ifndef qf_rtk32a_h 
#define qf_rtk32a_h 
 
#include <rtk32.h> 
 
// RTK-32A-specific event queue and thread types 
#define QF_OS_EVENT(x_)  RTKSemaphore  x_; 
#define QF_EQUEUE(x_)    QEQueue       x_; 
#define QF_THREAD(x_)    RTKTaskHandle x_; 
#define Q_STATIC_CAST(type_, expr_) static_cast<type_>(expr_) 
 
#include "qevent.h" 
#include "qhsm.h" 
#include "qequeue.h"                     // RTK-32A needs event-queue 
#include "qepool.h"                       // RTK-32A needs event-pool 
#include "qactive.h" 
#include "qtimer.h" 
#include "qf.h" 
 
#endif                                                 // qf_rtk32a_h

Please note the inclusion of qequeue.h and qepool.h interfaces, the use of QEQueue as the event queue data type, and RTKSemaphore for blocking active object threads on empty queue. The package-scope header file for the RTK32A port is defined as follows:

#ifndef port_h 
#define port_h 
 
#include "qf_rtk32a.h" 
#include "qfpkg.h" 
 
// RTK-32A-specific critical section operations 
#define QF_PROTECT()          __asm{cli} 
#define QF_UNPROTECT()        __asm{sti} 
#define QF_ISR_PROTECT() 
#define QF_ISR_UNPROTECT() 
 
// RTK-32A-compiler-specific cast 
#define Q_STATE_CAST(x_)      reinterpret_cast<QState>(x_) 
 
// RTK-32A-specific event queue operations 
#define QF_EQUEUE_INIT(q_) \ 
   ((q_)->myOsEvent = RTKCreateSemaphore(ST_BINARY, 0, "")) 
#define QF_EQUEUE_CLEANUP(q_) RTKDeleteSemaphore(&(q_)->myOsEvent) 
#define QF_EQUEUE_WAIT(q_) \ 
   QF_UNPROTECT(); \ 
   do { \ 
      RTKWait((q_)->myOsEvent); \ 
   } while ((q_)->myFrontEvt == 0);\ 
   QF_PROTECT() 
#define QF_EQUEUE_SIGNAL(q_) \ 
   QF_UNPROTECT(); \ 
   RTKSignal((q_)->myOsEvent) 
#define QF_EQUEUE_ONEMPTY(q_) 
 
// RTK-32A-specific event pool operations 
#define QF_EPOOL              QEPool 
#define QF_EPOOL_INIT(p_, poolSto_, nEvts_, evtSize_) \ 
   (p_)->init(poolSto_, nEvts_, evtSize_);  
#define QF_EPOOL_GET(p_, e_)  ((e_) = (p_)->get()) 
#define QF_EPOOL_PUT(p_, e_)  ((p_)->put(e_)) 
 
         // the following constant may be bumped up to 15 (inclusive) 
         // before redesign of algorithms is necessary  
enum { QF_MAX_ACTIVE = 15 }; 
 
#endif                                                      // port_h

This header file illustrates the alternative method of disabling and enabling interrupts (through the inline assembly) and otherwise is analogous to the package-scope header file for the Win32 port. The only difference is the use of RTKernel-32 binary semaphore instead of the Win32 event.

Other aspects of this QF port (defined in the rtk32a.cpp file) are also analogous to the Win32 port. The complete source code is available in directory <CD>:\Cpp\Qf\RTK32A.

Back to Top

Exercise 9.4 The following steps describe how to prepare the host and target for cross-platform development with On Time RTOS-32:

  • Install the On Time RTOS-32 Evaluation Kit by executing <CD>:\OnTime\RTOS-32.exe. Please read the readme.html file installed in the target directory.
  • In the On Time RTOS-32 Evaluation Kit Start Menu group, click on Debug Monitor Configuration to configure the Monitor. Select the desired ports for the host-target communication. Click OK and follow the program's instructions to create a Monitor boot diskette.

    Click to see bigger


  • Connect your host PC with the target PC using a suitable cable on the selected ports. If you have selected a serial COM ports, a NULL modem cable is required. For parallel ports, a parallel Laplink or Interlink cable is required.
  • Boot the target PC with the Monitor Boot Diskette. The Debug Monitor should display a copyright message on the target's screen.
  • To enable building QF applications you also need to define the environment variable RTTARGET and append %RTTARGET%\bin to the execution PATH. On Microsoft Windows 95/98 you need to add the following two lines to autoexec.bat:
    set RTTARGET=<target directory>\RTOS-32
    PATH=%RTTARGET%\bin;%PATH%
    
    On Microsoft Windows NT/2000 you need to define the environment variable and the path in the corresponding System dialog box.

The following steps describe how to execute the Hello sample application under the Microsoft Developer Studio:

  • Click on one of the "Hello" demo in folder Visual Studio Demos in the On Time RTOS-32 Start menu group. This will start Visual Studio through the On Time RTOS-32 remote debug shell Dbgshell.exe and the selected demo project workspace file is loaded. You must use the shortcut to use the Visual Studio integrated debugger!
  • The workspace contains two projects. The Hello project (Win32 .exe) to build the respective demo program. The project named Target converts the Win32 executable to an On Time RTOS-32 binary by running it through the locator. Use menu Build/Set Active Configuration… to select Target-Win32 Debug.
  • To compile, link, and locate the Hello demo project, select Build from the Visual Studio menu or press F7.
  • To run the demo program under the control of the Visual Studio debugger, use any method to start a normal debug session (e.g., from the Visual Studio menu, select Build, Start Debug, Step Into). If you are prompted to enter the name of the executable to debug, enter Debug\Hello.exe. Visual Studio will remember the name and not ask again.
  • The demo projects all define both a Debug and a Release configuration, but only the Debug configurations can be built successfully with this Evaluation Kit. Release configurations are included for documentation purposes only.
Back to Top

Chapter 10

Exercise 10.1 You modify the signal definitions as follows:

enum DPPSignals { 
   HUNGRY_SIG = Q_USER_SIG,//sent by philosopher when becoming hungry 
   DONE_SIG,                  // sent by philosopher when done eating 
   EAT0_SIG,                // sent by Table to let philosopher 0 eat 
   EAT1_SIG,                // sent by Table to let philosopher 1 eat 
   EAT2_SIG,                // sent by Table to let philosopher 2 eat 
   EAT3_SIG,                // sent by Table to let philosopher 3 eat 
   EAT4_SIG,                // sent by Table to let philosopher 4 eat 
   TIMEOUT_SIG, // timeout philosophers use to end thinking or eating 
   MAX_SIG 
};

Consequently, you need to change the Philosopher statechart in the following two steps:

You change the subscription in the initial pseudostate to subscribe only to the specific eat permission:

void Philosopher::initial(QEvent const *) { 
   QF::subscribe(this, EAT0_SIG + myNum); 
   Q_INIT(&Philosopher::thinking); 
}

You change the event processing in the "hungry" state:

QSTATE Philosopher::hungry(QEvent const *e) { 
   TableEvt *pe; 
   switch (e->sig) { 
   . . . 
   case EAT0_SIG: 
   case EAT1_SIG: 
   case EAT2_SIG: 
   case EAT3_SIG: 
   case EAT4_SIG: 
      ASSERT(e->sig == EAT0_SIG + myNum); 
      Q_TRAN(&Philosopher::eating); 
      return 0; 
   }  
   return (QSTATE)&Philosopher::top; 
}

Please note that you now don't need to guard the transition to the "eating" state, because the signal conveys permission to eat for the specific philosopher. The code asserts that indeed the permission pertains to this philosopher.

The changes to the Table active object are all localized in the "serving" state:

QSTATE Table::serving(QEvent const *e) { 
   unsigned n, m; 
   QEvent *pe; 
   switch (e->sig) { 
   case HUNGRY_SIG: 
      . . . 
      if (myFork[m] == FREE && myFork[n] == FREE) { 
         myFork[m] = myFork[n] = USED; 
         pe = Q_NEW(QEvent, EAT0_SIG + n); 
         QF::publish(pe); 
         printf("Philospher %1d is eating\n", n); 
      } 
      . . .  
      return 0; 
      . . .  
   }  
   return (QSTATE)&Table::top; 
}

Please note that you can use a generic event QEvent without parameters instead of the specific TableEvt.

The complete source code and executable image for this variation of the DPP solution is available as a VC++ v6.0 project: <CD>:\Cpp\Qdpp2\Win32\Qdpp.dsp.

Back to Top

Exercise 10.2 You can intercept the generic EAT_SIG and assert the following condition in the eating() state handler:

QSTATE Philosopher::eating(QEvent const *e) { 
   switch (e->sig) { 
   . . . 
   case EAT_SIG: 
      ASSERT(((TableEvt *)e)->philNum != myNum); 
      return 0; 
   . . . 
   }  
   return (QSTATE)&Philosopher::top; 
}
Back to Top

Exercise 10.3 The complete source code and executable image for the DOS version of the QF DPP application is available from directory <CD>:\Cpp\Qdpp\Dos (C++ version) and <CD>:\C\Qdpp\Dos (C version). There is also a version for the Borland 3.1 DOS compiler in the directories: <CD>:\Cpp\Qdpp\Borland (C++ version) and <CD>:\C\Qdpp\Borland (C version). You can use either implementation to execute the test. You can run the application in a Windows console.

Back to Top

Exercise 10.4 The complete source code and executable image for the Windows version of the QF DPP application is available from directory <CD>:\Cpp\Qdpp\Win32 (C++ version) and <CD>:\C\Qdpp\Win32 (C version). You can use either implementation to execute the test.

Back to Top

Exercise 10.5 The complete source code and executable image for the RTKernel-32 version of the QF DPP application is available from directory <CD>:\Cpp\Qdpp\Rtk32 (C++ version) and <CD>:\C\Qdpp\Rtk32 (C version). You can use either implementation to execute the test. Please refer to Exercise 9.4 for instructions how to prepare host and target environment for cross-debugging with On Time RTOS-32. Remember to launch the Developer Studio through the On Time dbgshell.exe utility.

Back to Top

Exercise 10.6 Accessing the screen from concurrently executing Philosopher threads involves sharing a common resource (the screen). Even if the printf() facility is reentrant (as it is in most RTOSes), the underlying printf() implementation typically uses a mutex. As described in Section 8.4.1 in Chapter 8, mutexes can lead to priority inversions.

Back to Top

Exercise 10.7 A standard pseudo-random generator (such as the rand() facility from the C standard library) uses a static random seed (initialized with srand()). The random seed is an example of a shared resource. Often the rand() facility is not reentrant, and even if it is protected with a mutex, you run the risk of priority inversions (see Exercise 10.6).

An alternative to sharing the standard rand() facility among all Philosopher threads is to implement a truly reentrant pseudo-random-number generator that takes an external random seed (as a parameter) and does not need any mutual exclusion protection. Each Philosopher instance can have a separate random seed (as an attribute), which avoids sharing the common random seed.

Back to Top

Exercise 10.8 The following screen shot demonstrates the empirical method of determining event queue size for an active object.



Click to see bigger


The QDPP application (the version located in <CD>:\Cpp\Qdpp\Rtk32a) has been executed for several minutes. It has been then stopped at the breakpoint shown in the source window. The Watch window has been used to inspect the event queue of the Table active object (aTable instance in this case). As you can see, the high-water mark (myNmax) is 0, which means that no events have been ever deposited in the ring buffer. As you recall from Section 9.3.3 in Chapter 9, the QEQueue class uses the ring buffer only when the queue utilization goes beyond one event. The empirical measurement of myNmax = 0 indicates that the queue utilization never exceeded one, which is consistent with the static analysis.

Back to Top

Exercise 10.9 The following table summarizes empirically-determined event queue utilization in the QDPP application (RTK32A version):
 

Active object Priority High-water Mark
(myNmax)
Queue Utilization
(myNmax + 1)
aPhil[0]
1
2
3
aPhil[1]
2
2
3
aPhil[2]
3
1
2
aPhil[3]
4
1
2
aPhil[4]
5
0
1
aPhil[5]
6
0
1
aTable
7
0
1

As you can see, the event queue utilization of lower priority active objects never exceeds the queue utilization of the higher-priority ones.

Back to Top

Exercise 10.10 To statically estimate the event-pool size you can just add up all event queue utilizations from Exercise 10.9 (12) plus the number of active objects (6), which totals 18 events.

The following is an example of a runtime snapshot of the event pool used in the QDPP application (the RTK32A version):

LocPoolPtr[1]->myFree   0x4001FED8 
               mEvtSize 8 
               myNtot   25 
               myNfree  24 
               myNmin   22

The empirically-determined event pool utilization is thus myNtot - myNmin = 3. As you can see, the empirical value (3) is much lower than the static analysis result (18), because the event production and consumption are highly correlated in the QDPP application (e.g., they all happen at a time tick).

Back to Top

Appendix A

Exercise A.1 The following table correlates a "C+" class declaration with the "C+" macros:
 

"C+" class declaration "C+" macro definition
CLASS(QHsm) 
 
 
   QState state__; 
   QState source__; 
METHODS 
   QHsm *QHsmCtor_(QHsm *me, 
         QPseudoState initial);
   void QHsmXtor(QHsm *me); 
   . . . 
END_CLASS
#define CLASS(name_)          \
   typedef struct name_ name_;\
   struct name_ { 
 
 
#define METHODS };
 
 
 
 
#define END_CLASS

Back to Top

Exercise A.2 A pointer to member function of class QHsm taking no arguments (other than me) and returning void is defined as follows:

typedef void                                        /* return type */ 
          (*QPseudoState)             /* name of pointer-to-member */
             (struct QHsm *); /* class the function is a member of */
Back to Top

Exercise A.3 A pointer to member function of class QHsm taking immutable pointer to QEvent (QEvent const *) and returning QPseudoState (see Exercise A.2) is defined as follows:

typedef QPseudoState                                /* return type */ 
          (*QState)                   /* name of pointer-to-member */
             (struct QHsm *,  /* class the function is a member of */ 
              QEvent const *);        /* rest of the argument list */
Back to Top

Exercise A.4 The macro SUBCLASS() is defined as follows (see Exercise A.1):

#define SUBCLASS(class_, superclass_) \ 
   CLASS(class_)                      \ 
      superclass_ super_;

This definition allocates a protected member super_ of type superclass_ as the first attribute in the data structure associated with the class class_.

Back to Top

Exercise A.5 The following two functions define the constructor and the destructor for class Calc derived from class QHsm:

Calc *CalcCtor(Calc *me) {                          /* Constructor */ 
   if (!QHsmCtor_(&me->super_, (QPseudoState)Calc_initial)) {
      return 0; 
   } 
   return me; 
} 
 
void CalcXtor(Calc *me) {                            /* Destructor */
   QHsmXtor_(&me->super_); 
}

Please note the explicit invocation of the superclass' constructor in the subclass constructor, as well as the symmetric invocation of the superclass' destructor in the subclass destructor.

Back to Top

Exercise A.6 The following class diagram shows the classical object-oriented problem used to illustrate inheritance and polymorphism:

An abstract base class Shape defines an abstract method area() for calculating the area of a shape, and a method scale() for scaling a shape. Concrete shapes, like a Circle or a Rect (rectangle) derive from the abstract Shape class and provide concrete implementations for the abstract methods area() and scale(). Additionally, class Shape illustrates aggregation (by composition) of other objects (an object of class String in this case).

The following header file declares class Shape:

SUBCLASS(Shape, Object) 
   String name;               /* public shape's name (aggregation) */
VTABLE(Shape, Object) 
   double (*area)(Shape *me);                     /* pure virtual! */
   void (*scale)(Shape *me, double mag);          /* pure virtual! */
METHODS 
   Shape *ShapeCtor_(Shape *me, char *name);     /* protected Ctor */
   void ShapeXtor_(Shape *me);                   /* protected Xtor */
END_CLASS

And here is the implementation of this class:

BEGIN_VTABLE(Shape, Object) 
   VMETHOD(Object, xtor) = (void (*)(Object *))ShapeXtor_; 
   VMETHOD(Shape, area) = (double (*)(Shape *))ObjectAbstract;
   VMETHOD(Shape, scale) =  
                      (void (*)(Shape *, double))ObjectAbstract;
END_VTABLE 
 
Shape *ShapeCtor_(Shape *me, char *name) { 
   ObjectCtor_(&me->super_);               /* construct superclass */
   VHOOK(Shape);                               /* hook Shape class */ 
   if (!StringCtor1(&me->name, name)) {        /* construct member */
      return NULL;                               /* report failure */ 
   } 
   return me; 
} 
 
void ShapeXtor_(Shape *me) { 
   StringXtor(&me->name);                        /* destroy member */
   ObjectXtor_(&me->super_);                 /* destroy superclass */
}

Please note definition of the Shape's VTABLE and the explicit initialization of the abstract (pure virtual) methods area() and scale().

The following code fragment shows the declaration and definition of Shape's subclass Circle:

SUBCLASS(Circle, Shape)       /* Class Circle extends Shape */
   double r__;                                   /* private radius */
VTABLE(Circle, Shape) 
METHODS 
   Circle *CircleCtor(Circle *me, char *name, double r); 
   double CircleArea(Circle *me); 
   void CircleScale(Circle *me, double mag); 
END_CLASS 
 
BEGIN_VTABLE(Circle, Shape) 
   VMETHOD(Shape, area) = (double (*)(Shape *))CircleArea; 
   VMETHOD(Shape, scale) =  
                        (void (*)(Shape *, double))CircleScale; 
END_VTABLE 
 
Circle *CircleCtor(Circle *me, char *name, double r) { 
   if (!ShapeCtor_(&me->super_, name)) {   /* construct superclass */
      return NULL;                               /* report failure */
   } 
   VHOOK(Circle);                             /* hook Circle class */
   me->r__ = r;                            /* initialise member(s) */
   return me; 
} 
double CircleArea(Circle *me) { 
   return 3.141592535 * me->r__ * me->r__;       /* pi * r-squared */
} 
void CircleScale(Circle *me, double mag) { 
   me->r__ *= mag; 
}

The following two functions test the generic interface of the Shape class:

#include "shape.h" 
 
void testArea(Shape *s) { 
   ASSERT(ObjectIS_KIND_OF(s, Shape)); 
   printf("name=\"%s\", area()=%.2f, ", 
          StringToChar(&s->name),                /* static binding */
          VCALL(Shape, area, s)END_CALL);       /* dynamic binding */
} 
 
void testScale(Shape *s) { 
   double mag = 2.0; 
   ASSERT(ObjectIS_KIND_OF(s, Shape)); 
   printf("scale(%.0f), ", mag); 
   VCALL(Shape, scale, s), mag END_CALL;        /* dynamic binding */
}

Please note that the functions testArea() and testScale() are written entirely in terms of the Shape class interface, and don't need to know anything about concrete subclasses and implementations.

The test harness for the application looks as follows:

#include "circle.h" 
#include "rect.h" 
enum { NRECT = 4 }; 
 
int main() { 
   Circle circle;            /* Circle instance on the stack frame */
   Circle *c; 
   Rect r[NRECT];  
   int i; 
                                           /* construct objects... */
   c = CircleCtor(&circle, "Circle", 1.0); 
   for (i = 0; i < NRECT; i++) { 
      char name[20]; 
      sprintf(name, "Rectangle-%d", i);        /* prepare the name */
      RectCtor(&r[i], name, (double)i, 1.0);     /* construct Rect */
   } 
                                            /* test each object... */
   testArea((Shape *)c); 
   testScale(&c->super_); 
   testArea((Shape *)c); 
   printf("\n"); 
   for (i = 0; i < NRECT; i++) { 
      testArea((Shape *)&r[i]); 
      testScale(&r[i].super_); 
      testArea((Shape *)&r[i]); 
      printf("\n"); 
   } 
                                             /* destroy objects... */
   VCALL(Object, xtor, c)END_CALL; 
   for (i = 0; i < NRECT; i++) { 
      VCALL(Object, xtor, &r[i])END_CALL; 
   } 
   return 0; 
}

You can find the complete implementation of this example in the directory <CD>:\C\CplusTst.

Back to Top