Chinaunix首页 | 论坛 | 博客
  • 博客访问: 2097471
  • 博文数量: 414
  • 博客积分: 10312
  • 博客等级: 上将
  • 技术积分: 4921
  • 用 户 组: 普通用户
  • 注册时间: 2007-10-31 01:49
文章分类

全部博文(414)

文章存档

2011年(1)

2010年(29)

2009年(82)

2008年(301)

2007年(1)

分类: Java

2008-07-19 16:47:30

Hierarchical State Machine

Click here to open Hierarchical State Machine Documentation in a new window Hierarchical State Machine Documentation
Click here to download Hierarchical State Machine Source Code

In this article, we will be highlighting the advantages of hierarchical state machine design over conventional state machine design.

In conventional state machine design, all states are considered at the same level. The design does not capture the commonality that exists among states. In real life, many states handle most  messages in similar fashion and differ only in handling of few key messages. Even when the actual handling differs, there is still some commonality. Hierarchical state machine design captures the commonality by organizing the states as a hierarchy. The states at the higher level in hierarchy perform the common message handling, while the lower level states inherit the commonality from higher level ones and perform the state specific functions. The table given below shows the mapping between conventional states and their hierarchical counterparts for a typical call state machine.

Conventional States Hierarchical States
Awaiting First Digit Setup.CollectingDigits.AwaitingFirstDigit
Collecting Digits Setup.CollectingDigits.AwaitingSubsequent Digits
Routing Call Setup.RoutingCall
Switching Path Setup.SwitchingPath
Conversation Conversation
Awaiting Onhook Releasing.AwaitingOnhook
Releasing Path Releasing.ReleasingPath

 A conventional state machine is designed as a two dimensional array with one dimension as the state and the other dimension specifying the message to be handled. The state machine determines the message handler to be called by indexing with the current state and the received message. In real life scenario, a task usually has a number of states along with many different types of input messages. This leads to a message handler code explosion. Also, a huge two dimensional array needs to be maintained. Hierarchical state machine design avoids this problem by recognizing that most states differ in the handling of only a few messages. When a new hierarchical state is defined, only the state specific handlers need to be specified.

Conventional State Machine Example

The figure below describes the state transition diagram for an active standby pair. The design here assumes that the active and standby are being managed by an external entity.

Conventional state transition diagram

The different states for the state machine are Active, Standby, Suspect and Failed. The input messages to be handled are Switchover, Fault Trigger, Diagnostics Passed, Diagnostics Failed and Operator Inservice. Thus the handler two dimensional array is 4 x 5 i.e. 20 handlers need to be managed. 

The code below shows the handlers that need to be defined. A dummy "do nothing" handler should be specified for all other entries of the two dimensional state table. This simple example clearly illustrates the problem with conventional state design. There is a lot of code repetition between handlers. This creates a maintenance headache for state machine designers. We will see in the following section that hierarchical state machine design exploits these very similarities to implement a more elegant state structure. 


/* == Active State Handlers == */
void ActiveStateFaultTriggerHandler(Msg *pMsg)
{
PerformSwitchover(); // Perform Switchover, as active failed
NextState = SUSPECT; // Run diagnostics to confirm fault
SendDiagnosticsRequest();
RaiseAlarm(LOSS_OF_REDUNDANCY); // Report loss of redundancy to operator
}

void ActiveStateSwitchoverHandler(Msg *pMsg)
{
PerformSwitchover(); // Perform Switchover on operator command
CheckMateStatus(); // Check if switchover completed
SendSwitchoverResponse(); // Inform operator about switchover
NextState = STANDBY; // Transition to standby
}

/* == Standby State Handlers == */
void StandbyStateFaultTriggerHandler(Msg *pMsg)
{
NextState = SUSPECT; // Run diagnostics to confirm fault
SendDiagnosticsRequest();
RaiseAlarm(LOSS_OF_REDUNDANCY); // Report loss of redundancy to operator
}

void StandbyStateSwitchoverHandler(Msg *pMsg)
{
PerformSwitchover(); // Perform switchover on operator command
CheckMateStatus(); // Check if switchover completed
SendSwitchoverResponse(); // Inform operator about switchover
NextState = ACTIVE; // Transition to active
}

/* == Suspect State Handlers == */
void SuspectStateDiagnosticsFailedHandler(Msg *pMsg)
{
SendDiagnosticsFailureReport(); // Inform operator about diagnostics
NextState = FAILED; // Move to the failed state
}

void SuspectStateDiagnosticsPassedHandler(Msg *pMsg)
{
SendDiagnosticsPassReport(); // Inform operator about diagnostics
ClearAlarm(LOSS_OF_REDUNDANCY); // Clear loss of redundancy alarm
NextState = STANDBY; // Move to standby state
}

void SuspectStateOperatorInservice(Msg *pMsg)
{
// Operator has replaced the card, so abort the current diagnostics
// and restart new diagnostics on the replaced card.
AbortDiagostics();
SendDiagnosticsRequest(); // Run diagnostics on replaced card
SendOperatorInserviceResponse(); // Inform operator about diagnostics start
}
/* == Failed State Handlers == */
void FailedStateOperatorInservice(Msg *pMsg)
{
SendDiagnosticsRequest(); // Run diagnostics on replaced card
SendOperatorInserviceResponse(); // Inform operator about diagnostics start
NextState = SUSPECT; // Move to suspect state for diagnostics
}

Hierarchical State Machine Example

The following state transition diagram recasts the state machine by introducing two levels in the hierarchy. Inservice and Out_Of_Service are the high level states that capture the common message handling. Active and Standby states are low level states inheriting from Inservice state. Suspect and Failed are low level states inheriting from Out_Of_Service state.

Hierarchical state transition diagram

The following diagram clearly illustrates the state hierarchy. Even the Inservice and Out_Of_Service, high level states inherit from the Unit_State that is at the highest level.

State hierarchy for Unit

Hierarchical State Machine Source Code

The C++ implementation details of the hierarchical state machine are given below. It is apparent that all the commonality has moved to the high level states viz. Inservice and Out_Of_Service. Also, contrast this with the .

The code below contains hyperlinks to more detailed information about the classes, methods and variables in this information.

Header File

The header file below declares the Unit state machine using the   class. Important points to note are:

  • The state classes are nested private classes within the state machine class. Thus they are not visible to other classes.
  • The state machine declares all states to be friend classes. This does not break the encapsulation as only a private class is being declared as a friend.
  • The base class () provides a "do nothing" implementation for all handlers. Thus an inheriting state has to provide an implementation only for that methods it supports.
  • State objects are declared static. Thus multiple instances of the state machine will share the same state objects. Due to this, the   class has a small memory footprint.
  • Only the main message handler, ,  is declared public. All helper functions are private.
  • A pointer to the current state is maintained in p_Current_State variable. This variable gets initialized using the method.

 

Hierarchical_State_Machine.h
00001 
00002 class Message;
00009
00010
00011
00031
class
00033 {
00037
class
00039 {
00040 public:
00041
virtual void ( &u,
const
Message *p_Message) {}
00044
virtual void ( &u,
const
Message *p_Message) {}
00047
virtual void ( &u,
const
Message *p_Message) {}
00050
virtual void ( &u,
const
Message *p_Message) {}
00053
virtual void ( &u,
const
Message *p_Message) {}
00056 };
00057 friend Unit_State;
00058
00059
00062
class : public
00064 {
00065 public:
00066 void ( &u,
const
Message *p_Message);
00067 void ( &u,
const
Message *p_Message);
00068 };
00069 friend ;
00070
00075
class : public
00077 {
00078 public:
00079 void ( &u,
const
Message *p_Message);
00080 void ( &u,
const
Message *p_Message);
00081 };
00082 friend ;
00083
00088
class : public
00090 {
00091 public:
00092 void ( &u,
const
Message *p_Message);
00093 };
00094 friend ;
00095
00098
class : public
00100 {
00101 public:
00102 void ( &u,
const
Message *p_Message);
00103 };
00104 friend ;
00105
class : public
00110 {
00111 public:
00112 void ( &u,
const
Message *p_Message);
00113 void ( &u,
const
Message *p_Message);
00114 void ( &u,
const
Message *p_Message);
00115 };
00116 friend ;
00117
class : public
00122 {
00123 public:
00124 // No Need to Override any other method
00125 };
00126 friend ;
00127
00128 private:
static ;
static ;
static ;
static ;
00133
00134 void ( &r_State);
00135
00136
00137 // Common Methods invoked from several states
00138 // (See article on FSM Inheritance for details)
00139 virtual void Send_Diagnostics_Request();
00140 virtual void Raise_Alarm(int reason);
00141 virtual void Clear_Alarm(int reason);
00142 virtual void Perform_Switchover();
00143 // . . .
00144 virtual void Send_Switchover_Response();
00145 virtual void Send_Operator_Inservice_Response();
00146 virtual void Send_Diagnostics_Failure_Report();
00147 virtual void Send_Diagnostics_Pass_Report();
00148 virtual void Abort_Diagnostics();
00149 virtual void Check_Mate_Status();
00150 *p_Current_State;
00151
00152 public:
00153 void (const Message *p_Message);
00154 };
00155
00159
void ( &r_State)
00161 {
00162 p_Current_State = &r_State;
00163 }
00164
00165

Source File

Important things to note about the source file:

  • , the main message handler invokes the appropriate handler based on the type of the message. The message is passed to the current state object.
  • The and base states handle most of the message processing. In some cases, the inheriting states perform some additonal action and call the handler for the base state for the common part of the handling.

 

Hierarchical_State_Machine.cpp
00007 
00008 #include ""
00009 #include "Unit_Messages.h"
00010 #include "assert.h"
00011
00016
void (const Message *p_Message)
00018 {
00019 switch (p_Message->GetType())
00020 {
00021 case Message::FAULT_TRIGGER:
00022 p_Current_State->(*this, p_Message);
00023 break;
00024
00025 case Message::SWITCHOVER:
00026 p_Current_State->(*this, p_Message);
00027 break;
00028
00029 case Message::DIAGNOSTICS_PASSED:
00030 p_Current_State->(*this, p_Message);
00031 break;
00032
00033 case Message::DIAGNOSTICS_FAILED:
00034 p_Current_State->(*this, p_Message);
00035 break;
00036
00037 case Message::OPERATOR_INSERVICE:
00038 p_Current_State->(*this, p_Message);
00039 break;
00040
00041 default:
00042 assert(false);
00043 break;
00044 }
00045 }
00046
00055
void (
&u,
const
Message *p_Message)
00057 {
00058 u.(u.);
00059 u.();
00060 u.(LOSS_OF_REDUNDANCY);
00061 }
00062
00070
void (
&u,
const
Message *p_Message)
00072 {
00073 u.();
00074 u.();
00075 u.();
00076 }
00077
00088
void (
&u,
const
Message *p_Message)
00090 {
00091 u.();
00092 Inservice::On_Fault_Trigger(u, p_Message);
00093 }
00094
00100
void (
&u,
const
Message *p_Message)
00102 {
00103 Inservice::On_Switchover(u, p_Message);
00104 u.(u.);
00105 }
00106
00112
void (
&u,
const
Message *p_Message)
00114 {
00115 Inservice::On_Switchover(u, p_Message);
00116 u.(u.);
00117 }
00118
00127
void (
&u,
const
Message *p_Message)
00129 {
00130 // Operator has replaced the card, so abort the current diagnostics
00131 // and restart new diagnostics on the replaced card.
00132 u.();
00133 u.();
00134 u.(u.);
00135 }
00136
00142
void (
&u,
const
Message *p_Message)
00144 {
00145 u.();
00146 u.(u.);
00147 }
00148
00155
void (
&u,
const
Message *p_Message)
00157 {
00158 u.();
00159 u.(LOSS_OF_REDUNDANCY);
00160 u.(u.);
00161 }
00162
00167
void (
&u,
const
Message *p_Message)
00169 {
00170 u.();
00171 Out_Of_Service::On_Operator_Inservice(u, p_Message);
00172 }

 

Explore More ...
Click here to open Hierarchical State Machine Documentation in a new window Hierarchical State Machine Documentation
Click here to download Hierarchical State Machine Source Code
阅读(1886) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~