Introduction
Harel StateCharts are gaining widespread usage since a variant has become part of the Unified Modeling Language. The diagram type allows the modeling of superstates, concurrent states, and activities as part of a state. Problems with Conventional FSMClassic Mealy-Moore state machine modeling techniques require the creation of distinct nodes for every valid combination of parameters that define the state. This can lead to a very large number of nodes and transitions between nodes for all but the simplest of systems. This complexity reduces the readability of the state diagram. Another of the limitations of modeling a computer system as a conventional state machine is the lack of support for concurrent constructs. Traditional state machine modeling is based on sequential transitions from one state to the next. Concurrent systems cannot be modeled in this manner as various aspects of the system may be in different states. It is seen that the limitations inherent in state machine models include the inherent complexity which occurs as the number of states increases, and also the modeling of concurrent systems. This article presents a commercial-grade cross-platform Harel UML StateChart Open-Source application framework named StateWizard for concurrent, distributed, and real-time reactive system development with simplicity, efficiency, and scalability. The following sections describe the ways to solve complex, reactive system problems with the following Harel StateChart features:
How to Reduce the Size of the Representation?The solution is hierarchical state machines. 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 a similar fashion and differ only in the handling of a 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 the hierarchy perform the common message handling, while the lower level states inherit the commonality from the higher level ones and perform the state specific functions. The state machine state hierarchy is based on a parent-child
relationship, which is depicted by the arrangement of the tree branches.
For example, in the following figure: State Hierarchy in Tree Form, the
node Player in the state tree is a root state which has two children: This hierarchical organization means that when a transition from state Player
Figure: State Hierarchy in Tree Form
The same hierarchy may be represented in a nested chart form. In this format, the hierarchy among states are shown by nesting child states within their parent state. Figure: State Hierarchy in Chart Form
Using the StateWizard application framework API set, the Collapse
/* The definition of the Player composite root state. */
#define SME_CURR_DEFAULT_PARENT Player
SME_BEGIN_ROOT_COMP_STATE_DEF(Player, PlayerEntry, PlayerExit)
SME_ON_INIT_STATE(SME_NULL_ACTION, PowerDown)
SME_END_STATE_DEF
SME_BEGIN_LEAF_STATE_DEF_P(PowerDown, PowerDownEntry, PowerDownExit)
SME_ON_EVENT(EXT_EVENT_ID_POWER, OnPowerDownEXT_EVENT_ID_POWER, PowerUp)
SME_END_STATE_DEF
SME_BEGIN_SUB_STATE_DEF_P(PowerUp)
SME_ON_EVENT(EXT_EVENT_ID_POWER,OnPowerUpEXT_EVENT_ID_POWER,PowerDown)
SME_END_STATE_DEF
SME_END_COMP_STATE_DEF(Player)
Collapse
#define SME_CURR_DEFAULT_PARENT PowerUp
SME_BEGIN_COMP_STATE_DEF(PowerUp, Player, PowerUpEntry, PowerUpExit)
SME_ON_INIT_STATE(OnPowerUpInitChild, Playing)
SME_END_STATE_DEF
SME_BEGIN_LEAF_STATE_DEF_P(Playing, PlayingEntry, PlayingExit)
SME_ON_EVENT(EXT_EVENT_ID_PAUSE_RESUME,OnPlayingEXT_EVENT_ID_PAUSE_RESUME,Pause)
SME_END_STATE_DEF
SME_BEGIN_LEAF_STATE_DEF_P(Pause, PauseEntry, PauseExit)
SME_ON_EVENT(EXT_EVENT_ID_START_RECORD,OnPauseEXT_EVENT_ID_START_RECORD,Record)
SME_END_STATE_DEF
SME_BEGIN_LEAF_STATE_DEF_P(Record,RecordEntry,RecordExit)
SME_ON_EVENT(EXT_EVENT_ID_STOP_RECORD,OnRecordEXT_EVENT_ID_STOP_RECORD,Pause)
SME_END_STATE_DEF
SME_END_COMP_STATE_DEF(PowerUp)
Root State is the uppermost state, bearing the application name. As you add states, the state tree grows downwards from the root state. For example, the Collapse
SME_BEGIN_ROOT_COMP_STATE_DEF(Player, PlayerEntry, PlayerExit)
Parent State is a state that branches into one or more child states. A parent can have several children, but a child has only one parent. For example, the Collapse
SME_BEGIN_COMP_STATE_DEF(PowerUp, Player, PowerUpEntry, PowerUpExit)
Initial Child State identifies the initial state for state machines that have substates. This child must occur if and only if the machine has one or more states or parallel children. For example, an initial child state, Collapse
SME_BEGIN_COMP_STATE_DEF(PowerUp, Player, PowerUpEntry, PowerUpExit)
SME_ON_INIT_STATE(OnPowerUpInitChild, Playing)
SME_END_STATE_DEF
Sibling States are the child states with a common parent. How to Scale State Machines?In complex large-scale reactive systems, a state machine object could be composed of more than 100 states, it is not a good way to place all state definitions in a source file. The definitions of different composite states could be spread in source files. For example, the Collapse
// File: Player.c
#define SME_CURR_DEFAULT_PARENT Player
SME_BEGIN_ROOT_COMP_STATE_DEF(Player, PlayerEntry, PlayerExit)
SME_ON_INIT_STATE(SME_NULL_ACTION, PowerDown)
SME_END_STATE_DEF
SME_BEGIN_LEAF_STATE_DEF_P(PowerDown, PowerDownEntry, PowerDownExit)
SME_ON_EVENT_WITH_GUARD(EXT_EVENT_ID_POWER, Guard1_func,
OnPowerDownEXT_EVENT_ID_POWER, Join1)
SME_END_STATE_DEF
SME_BEGIN_SUB_STATE_DEF_P(PowerUp)
SME_ON_EVENT(EXT_EVENT_ID_POWER,OnPowerUpEXT_EVENT_ID_POWER,PowerDown)
SME_END_STATE_DEF
SME_END_COMP_STATE_DEF(Player)
And, the detail Collapse
// File: Player2.c
#define SME_CURR_DEFAULT_PARENT PowerUp
SME_BEGIN_COMP_STATE_DEF(PowerUp, Player, PowerUpEntry, PowerUpExit)
SME_ON_INIT_STATE(OnPowerUpInitChild, Playing)
SME_ON_STATE_TIMEOUT_INTERNAL_TRAN(3000, PowerUpTimeOut)
SME_END_STATE_DEF
SME_BEGIN_LEAF_STATE_DEF_P(Playing, PlayingEntry, PlayingExit)
SME_ON_EVENT(EXT_EVENT_ID_PAUSE_RESUME,OnPlayingEXT_EVENT_ID_PAUSE_RESUME,Pause)
SME_END_STATE_DEF
SME_BEGIN_LEAF_STATE_DEF_P(Pause, PauseEntry, PauseExit)
SME_ON_EVENT(EXT_EVENT_ID_PAUSE_RESUME,OnPauseEXT_EVENT_ID_PAUSE_RESUME,Playing)
SME_END_STATE_DEF
SME_END_COMP_STATE_DEF(PowerUp)
How to Activate a State Machine Instance?A state machine application is an instance of a state machine, or an instance of a region which is an orthogonal part of either a composite state or a state machine. Applications can have one of two modes: active or inactive. Active applications are the ones running on the state machine at a given time, whereas inactive applications are not. In other words, only active applications can handle events. A state machine engine is responsible for managing these applications and dispatching events to specific applications. The following macro defines an application instance, Collapse
SME_OBJ_DEF(Player1, Player)
SmeActivateObj(&Player1,NULL);
How to Conveniently Describe State Concurrency?The solution is to allow Orthogonal states to operate concurrently. Composite states have one or more regions for substates. A region is simply a container for substates. A composite state is a state that consists of sub-states. A composite state can be decomposed using AND-relationships into two or more concurrent regions which are containers for sub-states, or using OR-relationships into mutually exclusive disjoint sub-states. Orthogonal state: If a composite state can be decomposed using AND-relationships into two or more concurrent regions, it is called Orthogonal State. The following macros defines an Orthogonal state named
Collapse
SME_BEGIN_ROOT_COMP_STATE_DEF(Player, PlayerEntry, PlayerExit)
SME_ON_INIT_STATE(SME_NULL_ACTION, PowerDown)
SME_END_STATE_DEF
SME_BEGIN_ORTHO_SUB_STATE_DEF_P(OrthoState)
SME_ON_EVENT(EXT_EVENT_ID_POWER, OnPowerDownEXT_EVENT_ID_POWER, Join1)
SME_END_STATE_DEF
SME_BEGIN_ORTHO_COMP_STATE_DEF(OrthoState, Player, OrthoStateEntry, OrthoStateExit)
SME_REGION_DEF(PlayerReg1,Player,SME_RUN_MODE_PARENT_THREAD,0)
SME_REGION_DEF(PlayerReg2,Player,SME_RUN_MODE_SEPARATE_THREAD,0)
SME_REGION_DEF(PlayerReg3,Player,SME_RUN_MODE_SEPARATE_THREAD,0)
SME_END_ORTHO_STATE_DEF
With the StateWizard, you may define a transition from/to an Orthogonal state, using How to Model State Built-in Timer for a Real-time System?Timers need to be modeled in real-time systems. The engine supports two kinds of timers, state-built-in timers and regular timers. State-built-in timers work tightly with the state machine. They are
managed by the engine. On a state entry, automatically start the
built-in timer, if it is available. On a state exit, stop it. On
timeout, they trigger Regular timers are explicit timers. Developers have to start or stop them using API calls. On timeout, they trigger Collapse
enum {SME_TIMER_TYPE_CALLBACK, SME_TIMER_TYPE_EVENT};
An explicit callback function should be defined for a callback
function mode timer. This mode is independent from state machine
definitions. For a timer event mode, The following sample defines a 3000-ms timer in the Player state and a 9000-ms timer in the Playing state. On timeout, a Collapse
#define SME_CURR_DEFAULT_PARENT PowerUp
SME_BEGIN_COMP_STATE_DEF(PowerUp, Player, PowerUpEntry, PowerUpExit)
SME_ON_INIT_STATE(OnPowerUpInitChild, Playing)
SME_ON_STATE_TIMEOUT_INTERNAL_TRAN(3000, PowerUpTimeOut)
SME_END_STATE_DEF
SME_BEGIN_LEAF_STATE_DEF_P(Playing, PlayingEntry, PlayingExit)
SME_ON_EVENT(EXT_EVENT_ID_PAUSE_RESUME,
OnPlayingEXT_EVENT_ID_PAUSE_RESUME,Pause)
SME_ON_INTERNAL_TRAN_WITH_GUARD(SME_EVENT_TIMER,
GuardTimer2_func,OnTimer2Proc) /* Regular timer event */
SME_ON_STATE_TIMEOUT(9000, PlayingTimeOut, Pause)
/* Go to Pause state if 9 sec is timeout. */
SME_END_STATE_DEF
SME_BEGIN_LEAF_STATE_DEF_P(Pause, PauseEntry, PauseExit)
SME_ON_EVENT(EXT_EVENT_ID_PAUSE_RESUME,
OnPauseEXT_EVENT_ID_PAUSE_RESUME,Playing)
SME_END_STATE_DEF
SME_END_COMP_STATE_DEF(PowerUp)
How to Model Pseudo States?A PseudoState is an abstraction of different types of nodes in the state machine graph which represent transient points in transition paths from one state to another (e.g., branch and fork points). Pseudo states are used to construct complex transitions from simple transitions. For example, by combining a transition entering a fork pseudo state with a set of transitions exiting the fork pseudo state, we get a complex transition that leads to a set of target states. Conditional (Fork) PseudoStates are a notational shorthand for multiple exiting transitions all triggered by the same event but each having different guards. Join PseudoState is a state with several incoming transitions and a single outgoing one. Using the StateWizard application framework API set, a Conditional PseudoState Collapse
#define SME_CURR_DEFAULT_PARENT Player
SME_BEGIN_ROOT_COMP_STATE_DEF(Player, PlayerEntry, PlayerExit)
SME_ON_INIT_STATE(SME_NULL_ACTION, PowerDown)
SME_END_STATE_DEF
....
SME_BEGIN_COND_STATE_DEF_P(Cond1, Cond1_func)
SME_ON_EVENT(COND_EV_COND1, CondAct1, Playing)
SME_ON_EVENT(COND_EV_COND2, CondAct2, Pause)
SME_ON_EVENT(SME_EVENT_COND_ELSE, CondActElse, PowerUp)
SME_END_STATE_DEF
SME_BEGIN_JOIN_STATE_DEF_P(Join1)
SME_ON_JOIN_TRAN(JoinAct, Cond1)
SME_END_STATE_DEF
...
StateWizard Event Handling WorkflowEvent Handling LoopThe If an external event is triggered, it will be transformed to an internal event via an external event waiting function which is an OS virtual layer function. If an external event destroy function is hooked, Collapse
void SmeRun(void)
{
SME_EVENT_T ExtEvent;
SME_EVENT_T *pEvent=NULL;
SME_OBJ_T *pObj;
SME_THREAD_CONTEXT_PT pThreadContext=NULL;
if (g_pfnGetThreadContext)
pThreadContext = (*g_pfnGetThreadContext)();
if (!pThreadContext) return;
if (!g_pfnGetExtEvent) return;
pObj = pThreadContext->pActObjHdr;
while (TRUE)
{
/* Check the internal event pool firstly. */
pEvent = GetEventFromQueue();
if (pEvent == NULL)
{
/* Wait for an external event. */
if (FALSE == (*g_pfnGetExtEvent)(&ExtEvent))
return; // Exit the thread.
pEvent = &ExtEvent;
pEvent->nOrigin = SME_EVENT_ORIGIN_EXTERNAL;
/* Call hook function on an external event coming. */
if (pThreadContext->fnOnEventComeHook)
(*pThreadContext->fnOnEventComeHook)
(SME_EVENT_ORIGIN_EXTERNAL, pEvent);
}else
{
/* Call hook function on an internal event coming. */
if (pThreadContext->fnOnEventComeHook)
(*pThreadContext->fnOnEventComeHook)
(SME_EVENT_ORIGIN_INTERNAL, pEvent);
}
do {
DispatchEventToApps(pThreadContext, pEvent);
/* Free internal event. Free external event later. */
if (pEvent != &ExtEvent)
SmeDeleteEvent(pEvent);
/* Get an event from event queue if available. */
pEvent = GetEventFromQueue();
if (pEvent != NULL)
{
/* Call hook function on an
internal event coming. */
if (pThreadContext->fnOnEventComeHook)
(*pThreadContext->fnOnEventComeHook)
(SME_EVENT_ORIGIN_INTERNAL, pEvent);
}
else
{
/* The internal event queue is empty. */
break;
}
} while (TRUE); /* Get all events from the internal event pool. */
/* Free external event if necessary. */
if (g_pfnDelExtEvent)
{
(*g_pfnDelExtEvent)(&ExtEvent);
// Engine should delete this event,
// because translation of external event
// will create an internal event.
SmeDeleteEvent(&ExtEvent);
}
} /* Wait for an external event. */
}
The Collapse
void SmeSetExtEventOprProc(SME_GET_EXT_EVENT_PROC_T fnGetExtEvent,
SME_DEL_EXT_EVENT_PROC_T fnDelExtEvent,
SME_POST_THREAD_EXT_INT_EVENT_PROC_T fnPostThreadExtIntEvent,
SME_POST_THREAD_EXT_PTR_EVENT_PROC_T fnPostThreadExtPtrEvent,
SME_INIT_THREAD_EXT_MSG_BUF_PROC_T fnInitThreadExtMsgBuf,
SME_INIT_THREAD_EXT_MSG_BUF_PROC_T fnFreeThreadExtMsgBuf)
{
g_pfnGetExtEvent = fnGetExtEvent;
g_pfnDelExtEvent = fnDelExtEvent;
g_pfnPostThreadExtIntEvent = fnPostThreadExtIntEvent;
g_pfnPostThreadExtPtrEvent = fnPostThreadExtPtrEvent;
g_pfnInitThreadExtMsgBuf = fnInitThreadExtMsgBuf;
g_pfnFreeThreadExtMsgBuf = fnFreeThreadExtMsgBuf;
}
External Event Management as OS Virtual LayerThe Collapse
BOOL XGetExtEvent(SME_EVENT_T* pEvent)
{
X_EXT_MSG_T NativeMsg;
int ret=0;
SME_THREAD_CONTEXT_T* p = XGetThreadContext();
X_EXT_MSG_POOL_T *pMsgPool;
if (NULL==pEvent || NULL==p || NULL==p->pExtEventPool)
return FALSE;
pMsgPool = (X_EXT_MSG_POOL_T*)(p->pExtEventPool);
memset(&NativeMsg,0,sizeof(NativeMsg));
while (TRUE)
{
ret = XWaitForEvent(&(pMsgPool->EventToThread),
&(pMsgPool->MutexForPool),
(XIS_CODITION_OK_T)XIsMsgAvailable, NULL,
(XTHREAD_SAFE_ACTION_T)XGetMsgFromBuf,&NativeMsg);
if (NativeMsg.nMsgID == SME_EVENT_EXIT_LOOP)
{
return FALSE; //Request Exit
}
#ifdef SME_WIN32
#else
// Built-in call back timer on Linux
else if (SME_EVENT_TIMER == NativeMsg.nMsgID
&& SME_TIMER_TYPE_CALLBACK == NativeMsg.Data.Int.nParam1)
{
// Invoke the call back function.
SME_TIMER_PROC_T pfnCallback =
(SME_TIMER_PROC_T)(NativeMsg.Data.Int.nParam2);
(*pfnCallback)(NativeMsg.pDestObj, NativeMsg.nSequenceNum);
}
#endif
else {
// Translate the native message to SME event.
memset(pEvent,0,sizeof(SME_EVENT_T));
pEvent->nEventID = NativeMsg.nMsgID;
pEvent->pDestObj = NativeMsg.pDestObj;
pEvent->nSequenceNum = NativeMsg.nSequenceNum;
pEvent->nDataFormat = NativeMsg.nDataFormat;
pEvent->nCategory = NativeMsg.nCategory;
pEvent->bIsConsumed = FALSE;
memcpy(&(pEvent->Data),&(NativeMsg.Data),
sizeof(union SME_EVENT_DATA_T));
}
//printf("External message received. \n");
return TRUE;
}; // while (TRUE)
}
BOOL XDelExtEvent(SME_EVENT_T *pEvent)
{
if (0==pEvent)
return FALSE;
if (pEvent->nDataFormat == SME_EVENT_DATA_FORMAT_PTR)
{
if (pEvent->Data.Ptr.pData)
{
#if SME_CPP
delete pEvent->Data.Ptr.pData;
#else
free(pEvent->Data.Ptr.pData);
#endif
pEvent->Data.Ptr.pData=NULL;
}
}
return TRUE;
}
Application and SampleAssume there are two state machine instances Collapse
CPlayer Player1;
CPlayer Player2;
SME_THREAD_CONTEXT_T g_AppThreadContext1;
SME_THREAD_CONTEXT_T g_AppThreadContext2;
There is a control panel which allows the user to post events to these two state machine instances. Collapse
int main(int argc, char* argv[])
{
XTHREADHANDLE ThreadHandle = 0;
int ret;
printf("Cross-Platform State Timer Sample: \n");
// Install thread local storage data functions.
XTlsAlloc();
SmeSetTlsProc(XSetThreadContext, XGetThreadContext);
////////////////////////////////////////////////////////////////
// Engine initialization.
SmeInitEngine(&g_AppThreadContext1); // Initialize at the thread-1
XInitMsgBuf();
// Install event handler functions.
SmeSetExtEventOprProc(XGetExtEvent, XDelExtEvent,
XPostThreadExtIntEvent, XPostThreadExtPtrEvent, XInitMsgBuf, XFreeMsgBuf);
// Create a thread to trigger external events.
ret = XCreateThread(ConsoleProc, NULL, &ThreadHandle);
// Create the Player2 application thread
ret = XCreateThread(AppThread2Proc, NULL, &ThreadHandle);
SmeActivateObj(&Player1,NULL);
SmeRun();
printf("Exit from SmeRun() at thread-1 \n");
XFreeMsgBuf();
XFreeThreadContext(&g_AppThreadContext1); /* At last, free thread local
storage resource. */
}
The second application thread function. The Collapse
#ifdef WIN32
unsigned __stdcall AppThread2Proc(void *Param)
#else
void* AppThread2Proc(void *Param)
#endif
{
SmeInitEngine(&g_AppThreadContext2); // Initialize at the thread-2
// Save the thread context pointer to the TLS.
// XSetThreadContext(&g_AppThreadContext2);
XInitMsgBuf();
// Install event handler functions.
SmeSetExtEventOprProc(XGetExtEvent, XDelExtEvent,
XPostThreadExtIntEvent, XPostThreadExtPtrEvent, XInitMsgBuf, XFreeMsgBuf);
SmeActivateObj(&Player2,NULL);
SmeRun();
printf("Exit from SmeRun() at thread-2 \n");
XFreeMsgBuf();
XFreeThreadContext(&g_AppThreadContext2); /* At last, free thread local
storage resource. */
return 0;
}
A control panel to trigger external events. Collapse
#ifdef WIN32
unsigned __stdcall ConsoleProc(void *Param)
#else
void* ConsoleProc(void *Param)
#endif
{
// On Linux platform, call the XInitTimer function at the
// time-out event trigger thread.
// On time-out, the external event trigger thread posts
// SME_EVENT_TIMER to the state machine application thread,
// and then invokes the callback function
// installed by the XSetTimer function.
XInitTimer();
printf("Enter the console procedure thread.\n");
ConsoleProcUsage();
while(TRUE)
{
int nParam1 =0;
if(g_bQuit) break;
//OSRelated::Sleep(ISVW_LOOP_INTERVAL);
nParam1 = fgetc(stdin);
switch(nParam1)
{
case EOF: return 0;//Cancel ConsoleProc in Daemon
case 'x':
case 'X'://Quit
XPostThreadExtIntEvent(&g_AppThreadContext1,
SME_EVENT_EXIT_LOOP, 0, 0, NULL,0,
SME_EVENT_CAT_OTHER);
printf("Exiting thread-1 ... Please wait. \n");
XPostThreadExtIntEvent(&g_AppThreadContext2,
SME_EVENT_EXIT_LOOP, 0, 0, NULL,0,
SME_EVENT_CAT_OTHER);
printf("Exiting thread-2 ... Please wait. \n");
return 0;
break;
. . .
default:
break;
}
}
return 0;
}
Further InformationYou may get further information and download the UML StateChart Open Source framework and IDE tool here. History
LicenseThis article, along with any associated source code and files, is licensed under The GNU Lesser General Public License (LGPLv3) |
|