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.
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.
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.
Conventional State Machine Implementation |
|
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.
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.
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 conventional state machine implementation.
The code below contains hyperlinks to more detailed information about the classes, methods and variables in this information.
The header file below declares the Unit state machine using the Hierarchical_State_Machine class. Important points to note are:
Hierarchical_State_Machine.h |
00001 00002 class Message; 00009 00010 00011 00031 00032 class Hierarchical_State_Machine 00033 { 00037 00038 class Unit_State 00039 { 00040 public: 00041 00043 virtual void On_Switchover(Hierarchical_State_Machine &u, const Message *p_Message) {} 00044 00046 virtual void On_Fault_Trigger(Hierarchical_State_Machine &u, const Message *p_Message) {} 00047 00049 virtual void On_Diagnostics_Failed(Hierarchical_State_Machine &u, const Message *p_Message) {} 00050 00052 virtual void On_Diagnostics_Passed(Hierarchical_State_Machine &u, const Message *p_Message) {} 00053 00055 virtual void On_Operator_Inservice(Hierarchical_State_Machine &u, const Message *p_Message) {} 00056 }; 00057 friend Unit_State; 00058 00059 00062 00063 class Inservice : public Unit_State 00064 { 00065 public: 00066 void On_Switchover(Hierarchical_State_Machine &u, const Message *p_Message); 00067 void On_Fault_Trigger(Hierarchical_State_Machine &u, const Message *p_Message); 00068 }; 00069 friend Inservice; 00070 00075 00076 class Active : public Inservice 00077 { 00078 public: 00079 void On_Switchover(Hierarchical_State_Machine &u, const Message *p_Message); 00080 void On_Fault_Trigger(Hierarchical_State_Machine &u, const Message *p_Message); 00081 }; 00082 friend Active; 00083 00088 00089 class Standby : public Inservice 00090 { 00091 public: 00092 void On_Switchover(Hierarchical_State_Machine &u, const Message *p_Message); 00093 }; 00094 friend Standby; 00095 00098 00099 class Out_Of_Service : public Unit_State 00100 { 00101 public: 00102 void On_Operator_Inservice(Hierarchical_State_Machine &u, const Message *p_Message); 00103 }; 00104 friend Out_Of_Service; 00105 00109 class Suspect : public Out_Of_Service 00110 { 00111 public: 00112 void On_Diagnostics_Failed(Hierarchical_State_Machine &u, const Message *p_Message); 00113 void On_Diagnostics_Passed(Hierarchical_State_Machine &u, const Message *p_Message); 00114 void On_Operator_Inservice(Hierarchical_State_Machine &u, const Message *p_Message); 00115 }; 00116 friend Suspect; 00117 00121 class Failed : public Out_Of_Service 00122 { 00123 public: 00124 // No Need to Override any other method 00125 }; 00126 friend Failed; 00127 00128 private: 00129 static Active Active_State; 00130 static Standby Standby_State; 00131 static Suspect Suspect_State; 00132 static Failed Failed_State; 00133 00134 void Next_State(Unit_State &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 Unit_State *p_Current_State; 00151 00152 public: 00153 void On_Message(const Message *p_Message); 00154 }; 00155 00159 00160 void Hierarchical_State_Machine::Next_State(Unit_State &r_State) 00161 { 00162 p_Current_State = &r_State; 00163 } 00164 00165 |
Important things to note about the source file:
Hierarchical_State_Machine.cpp |
00007 00008 #include "Hierarchical_State_Machine.h" 00009 #include "Unit_Messages.h" 00010 #include "assert.h" 00011 00016 00017 void Hierarchical_State_Machine::On_Message(const Message *p_Message) 00018 { 00019 switch (p_Message->GetType()) 00020 { 00021 case Message::FAULT_TRIGGER: 00022 p_Current_State->On_Fault_Trigger(*this, p_Message); 00023 break; 00024 00025 case Message::SWITCHOVER: 00026 p_Current_State->On_Switchover(*this, p_Message); 00027 break; 00028 00029 case Message::DIAGNOSTICS_PASSED: 00030 p_Current_State->On_Diagnostics_Passed(*this, p_Message); 00031 break; 00032 00033 case Message::DIAGNOSTICS_FAILED: 00034 p_Current_State->On_Diagnostics_Failed(*this, p_Message); 00035 break; 00036 00037 case Message::OPERATOR_INSERVICE: 00038 p_Current_State->On_Operator_Inservice(*this, p_Message); 00039 break; 00040 00041 default: 00042 assert(false); 00043 break; 00044 } 00045 } 00046 00055 00056 void Hierarchical_State_Machine::Inservice::On_Fault_Trigger( Hierarchical_State_Machine &u, const Message *p_Message) 00057 { 00058 u.Next_State(u.Suspect_State); 00059 u.Send_Diagnostics_Request(); 00060 u.Raise_Alarm(LOSS_OF_REDUNDANCY); 00061 } 00062 00070 00071 void Hierarchical_State_Machine::Inservice::On_Switchover( Hierarchical_State_Machine &u, const Message *p_Message) 00072 { 00073 u.Perform_Switchover(); 00074 u.Check_Mate_Status(); 00075 u.Send_Switchover_Response(); 00076 } 00077 00088 00089 void Hierarchical_State_Machine::Active::On_Fault_Trigger( Hierarchical_State_Machine &u, const Message *p_Message) 00090 { 00091 u.Perform_Switchover(); 00092 Inservice::On_Fault_Trigger(u, p_Message); 00093 } 00094 00100 00101 void Hierarchical_State_Machine::Active::On_Switchover( Hierarchical_State_Machine &u, const Message *p_Message) 00102 { 00103 Inservice::On_Switchover(u, p_Message); 00104 u.Next_State(u.Standby_State); 00105 } 00106 00112 00113 void Hierarchical_State_Machine::Standby::On_Switchover( Hierarchical_State_Machine &u, const Message *p_Message) 00114 { 00115 Inservice::On_Switchover(u, p_Message); 00116 u.Next_State(u.Active_State); 00117 } 00118 00127 00128 void Hierarchical_State_Machine::Out_Of_Service::On_Operator_Inservice( Hierarchical_State_Machine &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.Send_Diagnostics_Request(); 00133 u.Send_Operator_Inservice_Response(); 00134 u.Next_State(u.Suspect_State); 00135 } 00136 00142 00143 void Hierarchical_State_Machine::Suspect::On_Diagnostics_Failed( Hierarchical_State_Machine &u, const Message *p_Message) 00144 { 00145 u.Send_Diagnostics_Failure_Report(); 00146 u.Next_State(u.Failed_State); 00147 } 00148 00155 00156 void Hierarchical_State_Machine::Suspect::On_Diagnostics_Passed( Hierarchical_State_Machine &u, const Message *p_Message) 00157 { 00158 u.Send_Diagnostics_Pass_Report(); 00159 u.Clear_Alarm(LOSS_OF_REDUNDANCY); 00160 u.Next_State(u.Standby_State); 00161 } 00162 00167 00168 void Hierarchical_State_Machine::Suspect::On_Operator_Inservice( Hierarchical_State_Machine &u, const Message *p_Message) 00169 { 00170 u.Abort_Diagnostics(); 00171 Out_Of_Service::On_Operator_Inservice(u, p_Message); 00172 } |
Explore More ... |
Hierarchical State Machine
Documentation Hierarchical State Machine Source Code |