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.
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.
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.
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.
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.
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.
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.
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;
}
. . .
}
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.
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.
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;
}
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) },
. . .
};
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;
}
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.
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' */
}
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.
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.
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).
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.
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.
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.
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".
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.
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).
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.
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).
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() .
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.
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.
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.
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.
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.
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.
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".
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.
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.
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.
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).
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.
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.
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.
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.
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).
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).
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
}
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).
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);
}
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() .
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\.
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".
You can find the source code corresponding to this example in
the directory <CD>:\C\dpp\.
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.
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.
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();
. . .
}
. . .
}
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.
Exercise 9.4 The following steps describe how to
prepare the host and target for cross-platform development with
On Time RTOS-32:
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.
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.
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;
}
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.
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.
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.
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.
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.
Exercise 10.8 The following screen shot demonstrates
the empirical method of determining event queue size for an
active object.
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.
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.
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).
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
|
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 */
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 */
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_.
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.
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.
|