Design Article
Tracing of the event flow in state-based designs
Peter Mueller
11/9/2010 9:17 AM EST
Tracing is useful both during development and after the software is released. Here is an explanation of the different parts required for realizing a tracing function and how to implement tracing of state-based designs with minimal effort.
Finite state machines (FSMs) are a well-established tool for the design of embedded systems. Using state machines offers many benefits throughout the whole development process.1 In an FSM-based software architecture the application is designed as individual state machines. Such a system design can be realized with or without an operating system.
In systems with real-time operating systems (RTOSes), the individual state machines typically run in its own task. Tasks are generally constructed as while () loops, and the task body realizes the state machine. After an event is received, the task becomes ready and reads the event, for example, from a message queue. The event is then processed from the state machine and eventually a state change happens. The task then waits for the next event. The code in Listing 1 shows this principle.
Click on image to enlarge.
In a non-RTOS design (foreground/background system design), the difference is that in the background a main loop executes the different state machines one after the other. The state machines return immediately if an eventually available event was processed. One of the advantages of this design is that the issues of task switching and resource-sharing between RTOS tasks is not relevant, as Listing 2 demonstrates.
Click on image to enlarge.
In both designs, the individual state machine can be coded by hand, such as in C. But this is an error-prone task especially for hierarchical designs. In practice, a code generator can fully transform UML state diagrams into source code. This saves a lot of time especially if the model is not complete from the beginning and transitions or entry/do/exit code are to be added later. Additionally, a code generator can perform design checks on the model level before generating the source code.
Testing state-based designs
After the design and coding phase, the behavior of a state machine must be tested. It's recommended that you go through every state transition at least once. Based on the state diagram, a tool can suggest test routes through the state chart ensuring 100% transition coverage.
Debugging an application that is based on generated code from a state diagram is a bit different from debugging handwritten state-machine code. Why? Because you can assume that the generated code is correct. You don't have to worry about all the nitty gritty details of the realization of a state machine, such as handling history, handling hierarchical designs, placement of entry/exit. If the machine does not do what it should do, then most probably the model is not correct. To track down the problem—especially in deeply embedded real-time systems—typically means to add a tracing mechanism that allows you to see which events do fire. Here a code generator can support you again by automatically generate trace code that provides you with information useful for debugging or testing.
Next: Page 2
Finite state machines (FSMs) are a well-established tool for the design of embedded systems. Using state machines offers many benefits throughout the whole development process.1 In an FSM-based software architecture the application is designed as individual state machines. Such a system design can be realized with or without an operating system.
In systems with real-time operating systems (RTOSes), the individual state machines typically run in its own task. Tasks are generally constructed as while () loops, and the task body realizes the state machine. After an event is received, the task becomes ready and reads the event, for example, from a message queue. The event is then processed from the state machine and eventually a state change happens. The task then waits for the next event. The code in Listing 1 shows this principle.
Click on image to enlarge.
In a non-RTOS design (foreground/background system design), the difference is that in the background a main loop executes the different state machines one after the other. The state machines return immediately if an eventually available event was processed. One of the advantages of this design is that the issues of task switching and resource-sharing between RTOS tasks is not relevant, as Listing 2 demonstrates.
Click on image to enlarge.
In both designs, the individual state machine can be coded by hand, such as in C. But this is an error-prone task especially for hierarchical designs. In practice, a code generator can fully transform UML state diagrams into source code. This saves a lot of time especially if the model is not complete from the beginning and transitions or entry/do/exit code are to be added later. Additionally, a code generator can perform design checks on the model level before generating the source code.
Testing state-based designs
After the design and coding phase, the behavior of a state machine must be tested. It's recommended that you go through every state transition at least once. Based on the state diagram, a tool can suggest test routes through the state chart ensuring 100% transition coverage.
Debugging an application that is based on generated code from a state diagram is a bit different from debugging handwritten state-machine code. Why? Because you can assume that the generated code is correct. You don't have to worry about all the nitty gritty details of the realization of a state machine, such as handling history, handling hierarchical designs, placement of entry/exit. If the machine does not do what it should do, then most probably the model is not correct. To track down the problem—especially in deeply embedded real-time systems—typically means to add a tracing mechanism that allows you to see which events do fire. Here a code generator can support you again by automatically generate trace code that provides you with information useful for debugging or testing.
Next: Page 2
|
|
|
|
|
Navigate to related information
Miro Samek
11/12/2010 4:39 PM EST
The article focuses on automatic generation of software tracing instrumentation in-line with the generated state machine code. An alternative implementation strategy for state machines is to use a generic event processor, which executes the user-defined actions and transitions generically. The benefit for software tracing is that the tracing instrumentation can be placed inside the event processor instead of being repeated in every entry action, exit action, initial transition, regular transition, etc. This avoidance of repetitions can save a lot of code.
Another aspect not fully exploited in the article is that the execution environment for state machines can also be used for software tracing. For example, the article shows how to execute state machines with an RTOS (Listing 1) and in a "superloop" (Listing 2). The presented designs are reusable, but in any real-life project you need additionally event queues, timeout events, etc.. Instead of re-inventing all this for every project at hand, you can combine them into a generic, reusable state machine *framework*.
A framework like this allows you to take software tracing to the entirely new level, because a framework funnels all important interactions within the system. So, even without instrumenting the application, an instrumented framework can output tracing information about every event posted, every timeout, every queue in the system, etc. This comes on top of the information about every state machine action and transition, all tied to the common timeline.
This sort of software tracing is not just a theoretical possibility. For example, the open source QP state machine frameworks that I've described in my book "Practical UML Statecharts in C/C++, 2nd Ed" contain software tracing instrumentation called Q-SPY. For anybody interested in automatic code generation, the QP frameworks gained recently support from a free graphical tool called QM (QP Modeler).
Miro Samek
state-machine.com
Sign in to Reply
Peter Mueller
11/25/2010 5:04 PM EST
If the state code is fully generated there is no need for a framework. Sending events back and forth between tasks of an RTOS is no problem at all.
Frameworks also often have the problem that only specialists can adjust the framework to a used RTOS, compiler or CPU. Unfortunately this is too often the reason why users have to buy consultancy services.
Peter Mueller
Sign in to Reply
pteryx
11/15/2010 2:40 AM EST
Tracing book is not "on Wikipedia"! LTTng and Wikipedia are different projects, the fact that this part of LTTng runs on a wiki-engine does not mean that it is "wikipedia".
Sign in to Reply
Eric Kamps
11/19/2010 8:28 AM EST
The article focuses on the generation of traces from UML charts and the use of traces for
debugging purposes. It is generally known that debugging state machine oriented applications
is notoriously hard. This is mainly because a range of hard-to-debug defects are associated with these applications.
First of all, the number of all possible sequences of events grows exponentially
with the number of states and the number of events. Therefore, fully testing all possible sequences quickly becomes a daunting task.
Another issue is the type of defects associated with state machines. Typical defects are
livelocks, deadlocks and race conditions. Deadlocks and race conditions can occur
unexpectedly because the arrival of events is often non-deterministic and faulty situations
are therefore hard to catch.
The cause of these problems is in the state model itself and the article mentions the possibility to perform design checks on the model level before generating the source code. This is actually the only approach to effectively avoid defects. A tool that exactly addresses the problem in this way is ASD:Suite. It is a software development environment where state machines are modelled in sequence based specifications.
The ASD:Suite environment incorporates a formal model verification tool that performs various design checks on a model. It can check for a whole range of possible defects like livelocks, deadlocks and conformance to the interface. Furthermore, a user can specify illegal sequences. These are sequences of events that should not or can not occur. The model verification will detect the presence of these illegal sequences in the model.
Of course testing is still needed. But the testing is no longer focused on finding defects
in the state model. Testing and using the traces is more about the verification of the
integration of the state machine in the overall system. And this is what integration testing
is actually all about.
Eric Kamps
www.verum.com
Sign in to Reply