The Design of Software (CLOSED)

A public forum for discussing the design of software, from the user interface to the code architecture. Now closed.

The "Design of Software" discussion group has been merged with the main Joel on Software discussion group.

The archives will remain online indefinitely.

Interruptable state machine

I'm working on (what I call) an interruptable state machine. It is basically a very simple FSM that you give a kick when it's in the idle state, after which it automatically progresses through a series of states until it reaches one of two possible end-states:

    +---------+-------> G
    |        |
A -> B -> C -> D -> E -> F

The kicker here is that at any time during this process, there can be an external call that, depending on the details, either has no impact on the above flow OR immediately forces the flow to end up in terminal state G.

I implemented the basic state machine using the State design pattern, and it works nicely, but I haven't worked out a "proper" way to shoehorn the last bit (interruption that forces FSM to end-state G) into this pattern.

Anyone have an idea how to approach this?

Thanks in advance.
Jeroen
Wednesday, June 04, 2008
 
 
How is this different from a normal finite state machine?

A normal finite state machine has:

- States
- Events
- Event handlers, in each state, which can cause state transitions
- (Also, optionally, processing in each event handler, entry and exit conditions and/or processing in each state, default event handlers, context data with each event, context data with each state, and substates)

For example, you have:

- A kickoff event
- A kickoff event handler in state A which causes transitions from state A to B
- Presumably, other events which cause transitions from states B through F

What you need is one more 'interrupt' event, and corresponding event handler[s] in each state which may cause a transition to state G.
Christopher Wells Send private email
Wednesday, June 04, 2008
 
 
I don't see what the problem is. What a state machine does, in general is to traverse a state graph based on some state transition which generally are either the occurrence of external event or an internal condition.

So, what you describe is a state machine that at each state Sn (n=a, b, ..) has two possible transition: "continue" or "interruption".  Each state has its own "continue" transition to a next state, but all states have the same interruption transition to the state g.

Therefore, I would create an abstract class InterruptableState which transitions to the G state and make all other state classes to inherit this behavior.

My 2 cents.
Pablo Send private email
Wednesday, June 04, 2008
 
 
> I would create an abstract class InterruptableState

The implementation of a FSM depends on the programming language. For example in C++ you might have multiple inheritance to "mixin" behaviour (i.e event handler implementations). Untested pseudo-code ahead:

//pure abstract interface, defines events to be handled by any/every state
class IState
{
  virtual void kickoff() = 0;
  virtual void interrupt() = 0;
};

class InterruptableState : virtual IState
{
  virtual void interrupt();
};

class InitialState : virtual IState
{
  virtual void kickoff();
};

class NonInitialState : virtual IState
{
  virtual void kickoff();
};

class StateA: InterruptableState, InitialState
{
};

class StateB: InterruptableState, NonInitialState
{
};
Christopher Wells Send private email
Wednesday, June 04, 2008
 
 
What I was struggling with is that the transitions are all automatic. For example, the code would perform the actions necessary to transition from B to C, then change the state of the Context object to C, and immediately start executing the transition to D.

However, while the transitions take place, the "interrupting" event could occur, which should somehow lead to the state transitioning not from B to C, but to G. It felt clumsy to, for example, maintain a flag that indicates the interrupt took place, and check for that at the end of the B->C transition.

What I ended up doing is actually pretty much what you suggest: Instead of setting the Context state to C immediately when the B->C transition is complete, I enqueue the state change. If the "interrupt" event occurs while this transition takes place, the change to state G will end up in front of the change to state C.

The only implementation detail left was to clear the state change queue when a terminal state was reached.

Thanks for the input. Talking about a problem always helps!
Jeroen
Wednesday, June 04, 2008
 
 
> The only implementation detail left was to clear the state change queue when a terminal state was reached.

An alternative might be:

* Leave the event in the queue
* Let the event be dequeued as usual by the event dispatcher
* The event is dispatched into the current state, which is the terminal state
* The event handler in the terminal state handles/consumes the event, by ignoring it

This might be better than adding new (state- and/or event-specific) functionality to the queue+dispatcher.
Christopher Wells Send private email
Wednesday, June 04, 2008
 
 
"However, while the transitions take place, the "interrupting" event could occur, which should somehow lead to the state transitioning not from B to C, but to G. It felt clumsy to, for example, maintain a flag that indicates the interrupt took place, and check for that at the end of the B->C transition"

I think you a deeper problem here. The interruption is nothing special, is yet another transition. Maybe because you have a quite linear sequence, it seams to you that there are some special cases ("normal" and "interruption"), but soppose that you have a more complex state machine like this one

  |---------->G
  |
A->B->C->D->E->F
  |        ^
  |->H-----|

Now state B has three possible transitions (C, H and G) depending on what happens while in state B. Therefore your states should implement a run() method where they evaluates its current state and decide where to move next.

Pablo
Pablo Send private email
Wednesday, June 04, 2008
 
 
Perhaps it isn't entirely clear from what I wrote that the "interrupt" event comes from another thread altogether. This means it can also happen while transitioning from one state to another, or literally at ANY other moment. That's why the event is "special", and what prompted me to introduce the state change queue.
Jeroen
Wednesday, June 04, 2008
 
 
@christopher:

>* The event is dispatched into the current state, which is
>the terminal state

I am not enqueueing the events, but that actual state changes. At some point, there has to be a line like:

Context->State = newState

which gets executed after the actions are performed to achieve a specific state. It's this line that was causing me problems.

In any case, thanks everybody for your input. Discussing issues like these through a forum is always tricky business, as the're so much room for (mis)interpretation. The solution I have now (asynchronous state changes) works for my purpose, so I'll leave it at that for now.
Jeroen
Wednesday, June 04, 2008
 
 
Jeroen

Sorry if this sound too obvious, but, haven't you google for  "FSM framework". I did and found tens of frameworks you could just reuse.

for example, this one (in C++) even mention the asynchronous events:
http://www.boost.org/doc/libs/1_34_0/libs/statechart/doc/rationale.html


Pablo
Pablo Send private email
Wednesday, June 04, 2008
 
 
@pablo:

Yes, I knew Boost has an FSM framework. It's a little overkill for my 8-state FSM though :).

Jeroen
Jeroen
Thursday, June 05, 2008
 
 

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
 
Powered by FogBugz