finite state machine : transitions in absence of external events

S

srp113

Hello,
I am desigining a FSM (plan to use C++ to implement it). One of the
issues I am encountering is dealing with transient states ex:
A----B--------C-----------D-------E
| |
| |
| |
|
The transition from A-B happens because of some external event (like
timer expiration).
The transition from B-C is always immediate, basically state B exists
to perform some actions before entering state C. Its also possible
that FSM starts off with initial state as B instead of A which is
why
state B is needed. The transition from C-D is again immediate, C
executes some actions before entering state D. The reason we have
state C is because we need to reexecute these actions when we
transition from E to C(loopback)
Transition from D to E and from E to C are based on external events
(timer events).
(Transition from C to E not possible)

So in above FSM A,D,E are states that transition to next state only
on receipt of some external event while states B,C are transient/
temporary states that exist only to execute some actions before
transitioning to next state. One way I could think of achieving this
is to provide entry/exit routines for each of the state. Essentially
B::eek:nEntry() {
do B's actions
moveToState(C)


}


B::eek:nExit() {
//Do nothing or if there are any exit actions for B


}


C::eek:nEntry() {
do C's actions
moveToState(D)


}


C::eek:nExit() {
//Do nothing or if there are any exit actions for C


}


..............
//Some class that has pointer to currentState
moveToState(newState) {
currentState->exit();
currentState = newState;
newState->entry();


}


This was only solution I could think of. What I dont like about what
happens when we move from say A-B, we finally end in D (A-B,B-C,C-D)
and then at runtime call graph looks like: procesTimeoutInA()-
()->B's actions->B()::exit()- (B'S::exit called from with B::s entry
()!!)->C::entry()->C's actions->C's::exit() (again C's exit is called
from C's entry)->D's::entry() and unwind in the opposite order. Is
there any better way to handle this?
Thanks Much,
Sunil
 
P

Pascal J. Bourguignon

srp113 said:
This was only solution I could think of. What I dont like about what
happens when we move from say A-B, we finally end in D (A-B,B-C,C-D)
and then at runtime call graph looks like: procesTimeoutInA()->B::entry
()->B's actions->B()::exit()- (B'S::exit called from with B::s entry
()!!)->C::entry()->C's actions->C's::exit() (again C's exit is called
from C's entry)->D's::entry() and unwind in the opposite order. Is
there any better way to handle this?

The call graph shouldn't matter. This was a perfectly good option.

An alternative would be to reify the events, which would allow you to
enqueue epsilon events.

class Event{ ... };
class Timeout:public Event{ ... };
class Epsilon:public Event{ ... };

class EventQueue {
protected: std::queue<Event*> queue;
Epsilon* epsilon;
static template<T> T pop(std::queue<T>& q){ T result=q.front(); q.pop(); return(result); }
public:
void enqueue(Epsilon* e){ epsilon=e; }
void enqueue(Event* e){ queue.push(e); }
Event* dequeue(){ Event* result=((epsilon!=0)
? epsilon
: (queue.empty()
? 0
: pop(queue)));
epsilon=0;
return(result); }
...
};



So now your state machine would have a queue of event to process, and
you could enqueue epsilon events:


class FSM {
proctected:
EventQueue* events;
State* currentState;
public:

void postEvent(Event* e){
events->enqueue(e);
}

void processEvents(){
Event* e=events.dequeue();
while(e){
currentState->processEvent(this,e);
e=events.dequeue();
}
}

void doTransition(State* oldState,Event* event,State* newState){
log("transition %1% ---(%2%)---> %3%",oldState->name(),event->name(),newState->name());
currentState->onExit(this);
currentState=newState;
currentState->onEntry(this);
}
};

class StateC:public State{
void onEntry(FSM* m){
m->postEvent(new Epsilon());
}
void processEvent(FSM* m,Event* e){
// ignore other events
}
void processEvent(FSM* m,Epsilon* e){
m->doTransition(this,e,new StateD);
}
};


This way, in the processEvent loop, the calls to the old state return
before processing the next event, including epsilon events.
 
S

srp113

Hey Pascal,
Thanks for your quick response. I dont think I need an event queue as
FSM is running in a thread that has its own queue and so all events
are serialized there. I can use the concept of epsilon though to get
around call graph problem... thats good idea.
Thanks,
Sunil
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top