(Still OT) Hierarchical State Machines
Helmut Giese
since there seems to be some interest on state machines let me
elaborate a bit.
I am a big fan of state machines since they are a very effective means
to reduce complexity: Instead of having one large block of nested 'if'
or 'switch' statements, the code falls apart in (usually very small
and simple) pieces, where each piece is associated with exactly one
state.
The beauty of this design principle is: If you identified your states
correctly, your machine doesn't have to handle ANY special conditions
- it just jumps from state to state, because everything special is
captured by the proper definition / separation of states.
So far so good.
However, if you have a situation where states share functionality,
simple state machines are not efficient because of combinatorial
explosion and / or duplication of code -> enter Hierarchical State
Machines (HSM). And here begins my problem: I do not grok the concept
sufficiently well to adapt it to my current problem.
The only "real world problem" I found is that of a microwave oven
where the 2 states 'baking' and 'heating' share the common behaviour
for the event 'door open' (where they would probably shut down
everything). Sorry, the URL is on a different machine and momentarily
not available.
Looks convincing, but I cannot adapt it to my current problem. Here is
the setup:
I am writing a little "menu system" for an embedded device with a 2
line LCD. This system has 4 levels, which are sufficiently different
to merit their own states. Ok, I have a state machine which handles
those 4 states.
Now we have an additional requirement: a system message (some sort of
error condition). This kind of message is only to be displayed while
in level 1, thereby replacing whatever was currently shown. If this
event occurs while in level 2 thru 4, it is to be marked as 'pending',
and has to be displayed as soon as the user returns to level 1.
So what do I do? Have states Level2, Level2WithSysMsgPending, Level3,
Level3With..., etc.? Never! What I did instead was to introduce a
boolean 'SysMsgPending' which I now have to test for (a bit) all over
the place. Nothing really bad, but the clean design of the original
machine is gone.
This irks me, because I have the gut feeling that it should be
possible to capture these requirements with a HSM - after all, it's
nothing really spectacular - but I don't grok it.
Any ideas welcome.
Best regards
Helmut Giese
Gerald W. Lester
Does Level2 and Level2WithSysMsgPending have different behavior?
If not then you really need to just introduce one new state
Level1WithSysMsgPending, depending on how retentive you want to be you can
transition to this state just from Level1 or transition to it instead of
Level1 everywhere you transition to Level1. So you now only have a test at
the top of Level1 for SysMsgPending that sets the state to
Level1SysMsgPending and returns. Level1SysMsgPending displays the error
message, gets the user's ack then sets the state to Level1 and returns.
Am I making any sense?
--
+--------------------------------+---------------------------------------+
| Gerald W. Lester |
|"The man who fights for his ideals is the man who is alive." - Cervantes|
+------------------------------------------------------------------------+
Jonathan Bromley
(Helmut Giese) wrote:
>However, if you have a situation where states share functionality,
>simple state machines are not efficient because of combinatorial
>explosion and / or duplication of code -> enter Hierarchical State
>Machines (HSM). And here begins my problem: I do not grok the concept
>sufficiently well to adapt it to my current problem.
Hardware designers of necessity use state machine descriptions
all the time. We have exactly the same problems of
combinational explosion of states.
Hierarchical state machines can cut it, but the hardware
experience is that it's usually easier to decompose the
problem into a flat structure of interacting state machines.
In a sense, software does a lot of this. Think of a device
driver as a state machine whose job is to manage
the low-level operations of a device. Your program is
a higher-level state machine (in which the program
counter does duty as the state variable!!) that interacts
with the device driver FSM in a well-defined way.
Event-driven programs in the Tk style are state
machines of a sort.
--
Jonathan Bromley, Consultant
DOULOS - Developing Design Know-how
VHDL * Verilog * SystemC * e * Perl * Tcl/Tk * Project Services
Doulos Ltd., 22 Market Place, Ringwood, BH24 1AW, UK
jonathan...@MYCOMPANY.com
http://www.MYCOMPANY.com
The contents of this message may contain personal views which
are not the views of Doulos Ltd., unless specifically stated.
Arjen Markus
why not use a second state machine that records the state
of the system message?
- If the main machine is in state 1, the message machine is
in a state "display whatever message there is immediately".
- If the main machine is in any other state, the message
machine is in state "pending".
Jonathan already hinted at using several machines that
interact, I think the above is a simple enough implementation
of these ideas.
Regards,
Arjen
Uwe Klein
Introduce a message/event queue for your State2
( for other states to measure )
work through the queue for the level you are in.
pop one level up if queue is empty.
uwe