############################################################################## Author: Mark Topic: parallel states Posted: 8/4/03 2:38 PM ------------------------------------------------------------------------------ Im very much impressed by the HSM design pattern that you present. But there is one thing that is not clear to me. That is how it supports parallel states. ------------------------------------------------------------------------------ miro posted 8/4/03 5:43 PM Hi Mark, if by "parallel states" you mean orthogonal regions then the HSM pattern of QF doesn't support it. I discuss the matter in conjunction with the "Orthogonal Component" state design pattern in Chapter 5. The ROOM method (as described by Bran Selic at al.) takes similar tack on this issue (please see the appendix in the ROOM book devoted to comparison between ROOM-charts and Harel statecharts). -- Miro (miro@quantum-leaps.com) ############################################################################## Author: Tero Topic: Representing state topology with/without explicit data structure? Posted: 7/28/03 6:51 AM ------------------------------------------------------------------------------ Hi Miro! In article "State-Oriented Programming" in Embedded Systems Programming magazine (August 2000) [1] you construct the state topology as a tree -like data structure of State objects. In the book the topology is embedded in state handler methods. What are the basic reasons behind this change? What are the pros and cons of these two approaches in your opinion? Best regards, Tero [1] http://www.embedded.com/2000/0008/0008feat1.htm ------------------------------------------------------------------------------ miro posted 8/5/03 0:29 AM Hi Tero, today I consider the implementation published in ESP in August 2000 as one of the "beaten path" approaches (although this implementation is already much simplified compared to the OMG state machine meta-model). You see, such implementation falls out more or less automatically from a standard object-oriented analysis (OOA). OOA prescribes to create a class for every key concept in the problem domain, so you end up with a State class. However, states objects require memory, need to be initialized, don't behave correctly under inheritance of entire state machines, and are otherwise a burden to the client programmer. The state machine implementation published in the book "Practical Statecharts in C/C++" is entirely different. At the time I stumbled at this representation (at first for classical FSMs) I considered it a major breakthrough. Arguably, the most natural (and the fastest!) mapping from state-behavior to code is through an address of the state-related code (pointer-to-function in C). If you think about it, behavior *is* the code (a reactive system "behaves" only by executing code). You don't really need an indirection layer of State objects. Interestingly, such implementation of state machine deeply resembles implementation of polymorphism in C++ (virtual tables stuff). I believe that this is not just a coincidence. Polymorphism really means different *behaviors* at different times, and this is exactly what's happening in a state machine. In short, I think that departure from the standard OOA results in this case in much tighter code with unbeatable performance and minimal memory footprint (a state machine is just a pointer-to-function). Additionally, the signature of a hierarchical state handler (returning the superstate) is really a novelty here. This simple "trick" allows to extend a long-known assembly-language jump-table technique of coding state machines to efficiently implement state hierarchy. The technique is superior, because it so naturally maps to real microprocessors (you need to look at the assembly level output to really appreciate this, I show an example on page 74). -- Miro (miro@quantum-leaps.com) ############################################################################## Author: miro Topic: QF as an RTOS of the future posted: 4/18/03 0:02 AM ------------------------------------------------------------------------------ How can you tightly integrate QF with schedulers to effectively replace a traditional RTOS? What are the advantages/disadvantages. ------------------------------------------------------------------------------ Peter Kraak posted 4/24/03 1:20 AM I once wrote a message based executive that had cooperative multitasking and preemption at the message level, i.e. whenever a task called any o/s call or yield() if there was a higher priority task waiting it ran. the design called for message procssing tasks that ran to completion. the beaut thing was it was all in ansi C and to port it you just needed a c compiler and provide the SysTick() call from a hardware timer. thats it. If QP (c+ version) was melded to this it would provide a simple lean shrinkwrapped solution for new small targets. When real preemption is needed eCos is probably a better host, and is open source so no royalties, but needs a mid to high end platform. ------------------------------------------------------------------------------ Teemu Karevaara posted 6/17/03 9:10 AM "Super Simple Tasker" which Robert Ward introduced in Embedded Systems Conference San Francisco 2002 (http://www.esconline.com/sf/feat_tech_cl.htm#347) seems like a perfect platform for QF. Has someone already made a port? ------------------------------------------------------------------------------ miro posted 6/17/03 5:21 PM Bingo Teemu! Robert Ward's "Super Simple Tasker" (see www.codecraftsman.com) is an ideal fit. I have a first prototype working on ARM processor (exactly EB01 evaluation board for AT91 microcontroller from Atmel). The whole preemptive tasking and scheduling requires only some 40 ARM instruction in assembly (interrupt handler), and some 20 lines of C. The prototype works like magic. SST turns the foreground/background version of QF into a fully deterministic, preemptive RTOS. The limitations of the scheduler are exactly what you want. Active objects cannot block and wait on each other, every event must be processed to completion, only higher-priority active object can preempt current RTC step. This allows to use only *one* execution stack for all active objects. This unorthodox scheduler is exceptionally higher-level language friendly. Because you don't care about the exact layout of the context stack frame (as long as all registers are saved), you can store only the registers that are clobbered by the HLL, and then let the compiler save the rest of the registers in whichever order it likes. This means that the stack consumption is much lower than traditional RTOSs. Also, the SST breaks with the endless-loop structure of tasks. A task in SST is *not* a loop, but rather a one-shot event processing. This alone is remarkable and is a consequence that SST does not need to maintain the context of the endless-loop. In summary, a "native" implementation of QF can be made much *smaller* than a traditional RTOS (both in code space, data space, and CPU usage). Yet, the resulting system works at higher level of abstraction--at the level of active objects and state machines. No direct messing with semaphores, mutexes, monitors, etc--far less possibilities of shooting yourself in the foot. The *native* QF is by far the most exciting project I'm currently involved in. Any comments? --Miro ------------------------------------------------------------------------------ Bernard Mentink posted 7/30/03 10:57 PM Can someone point me to a document that describes how SST works? I can not seem to get hold of the Author .... Many Thanks ------------------------------------------------------------------------------ Henry Choi posted 8/1/03 4:52 AM http://www.codecraftsman.com seems to work just fine for me. Miro, I too think something wonderful might come by making a completely HSM based (and strictly real-time to boot) OS, but have some concerns. Please excuse me if I am missing something obvious. 1. How would the finished product differ from the QNX microkernel approach, which seems to be based on message passing (event publishing in QF lingo)? If QNX couldn't hit the big time marketing robustness, why would QF have a easier go at it? 2. Will HSM paradigm gain wide acceptance among application developers who have been weaned on the poorer solutions? For example, RTC (Run to completion) model flies in the face of all traditional OSes (whether real-time or no) I know of and the applications written on top of them; they block for any number of reasons. Wouldn't you agree that QF forces fundamental change on the applications? Let's take the TCP write() for example, which(may) block up to a time if the TCP send queue fills up. How much change is necessary for the applications that currently block on that write()? And do we have to force the application programmers to deal with the ASSERT() sprinkled throughout QF, because they are (if they didn't know it before) really hitting against the system resource issue? Do the non-UML conversant S/W engineers who glossed over these fundamental issues have to rewrite all their applications to reap the benefits of QF? 3. Performance: As Kahan likes to say, "the fast drives out the slow even if the fast is wrong." In my previous job (Real-Time Innovations), I tried to adopt QF for the middleware product (one of whose strength was the performance) and failed because of the memcpy() hit we would have to take. Our design required overwhelming (at least for me) thought and analysis to achieve zero-copy performance in multi-threaded application. Even though QF would have drastically simplified our middleware, we opted against it because the customers demand the fastest possible performance. At least in my former world of hyperfast network applications, copying data around to publish events would have been a deadly sin. I believe the experts such as Mr. van Jacobson (of TCP congestion avoidance fame) will back me up on this, because they are trying to figure out a way to avoid ANY memcpy(), starting from the H/W! I think QF is still a great option where a few memcpy() is inconsequential. I would even wager that most applications fall in this category. But I have observed that customers choose the fast (and wrong) solution over a robust but inconsequentially slow one. However, despite these concerns, I still would like to see QF based RTOS, and would try to use it in any product I work on! ------------------------------------------------------------------------------ Paul Butler posted 8/6/03 11:22 PM I'm very curious about the SST implementations being discussed here. Is anyone planning to make source available? Or is it already and I just haven't found it? thanks, -paul ------------------------------------------------------------------------------ miro posted 8/8/03 0:17 AM I have added a new page to the QP website intended to cover the developments of the "native" QF (please see www.quantum-leaps.com/qf/native.htm). At this point this page contains just a general introduction, but I plan (time permitting) to add more information. For now, you can find there Robert Ward's ESC paper that explains his SST. The "native" QF won't use Robert's implementation, but rather will directly embed the scheduler. I have a functional version for On-Time's RTTarget-32 (www.on-time.com) that I plan to make available on the QP website. This version grew up from the foreground/background port of QF to RTTarget-32 (please note that RTTarget-32 is just a platform for doing embedded development on PC-like hardware, but it is *not* a kernel). --Miro (miro@quantum-leaps.com) ############################################################################## Author: miro Topic: Hierarchical State Machines in C# posted: 4/18/03 0:03 AM ------------------------------------------------------------------------------ How can you implement Hierarchical State Machines (HSMs) in C#? ------------------------------------------------------------------------------ Louis posted 8/11/03 11:03 PM I thought you already had Rainer Hessmer's C# implementation of QF on this web site. As I recall, he did not implement active objects, but had working code for HSMs. (It's a start :) ############################################################################## Author: Peter Kraak Topic: Python, anyone? posted: 6/4/03 4:30 AM ------------------------------------------------------------------------------ Any python nuts out there who would be interested in collaborating on a python port (straight conversion from C++ maybe)? Or discussing the idea of defining a QP syntax and implementing it in C with python wrappers? ------------------------------------------------------------------------------ Rodney A Ludwig posted 8/18/03 6:46 PM I will be implementing via SWIG a dll that has access to the HSM functions for python. Let me know if you feel this is related to your ideas. ############################################################################## Author: Gavin Haentjens Topic: C+ QF tip: Init your static vars posted: 8/18/03 8:03 PM ------------------------------------------------------------------------------ Just wanted to give a tip to anyone porting the C+ version of the QF to their processor: Make sure your static variables are initialized to 0. This may very well be a standard good programming practice that I didn't know about. If your static variables are not initalized to 0, then you will need to find some way to explicitly initialize all of the transitions in the objects, which as far as I can tell, is nontrivial. For now I should be okay initializing all static vars, but it does create a problem with the part of my code that used to check (and then initialize) a memory location after every reset to determine whether the processor was without power prior to the reset. By the way, in case someone was interested in exchanging ideas, I'm trying to port the QF to an Infineon C167 using the foreground/background scenario (no RTOS). -Gavin ------------------------------------------------------------------------------ miro posted 8/19/03 5:30 PM Hi Gavin, according to the C Standard, all uninitialized static variables are (must be) initialized to zero before calling main(). Typically, all uninitialized static objects are placed in a BSS section, which is zeroed out before calling main(). This is important, because both C+ and the HSM implementations *rely* on this initialization. In C+, implicit zeroing out static variables is important for correct initialization of virtual tables. In the HSM implementation, zeroing out the static Tran objects is important for the "static transition" optimization (see Section 4.4.3 in my book). You bring an important point, though. In embedded systems, zeroing out the BSS section(s) is often in the hands of the programmers, who must often fiddle with the initialization sequence. It is important to perform correct initialization of the BSS each and every time the system goes through reset! This can be sometimes tricky (e.g., when you perform only an incomplete reset, known as "hot start"). Various reset sequences can be quite involved and clearly are beyond the scope of this short reply. However, if your chip/board has a watchdog, it's often the best way to perform a clean hardware reset (including resetting the peripherals and setting the chip selects. (To use the watchdog for reset, simply program it to expire immediately). Thanks for bringing this point up, --Miro (miro@quantum-leaps.com) ------------------------------------------------------------------------------ Henry Choi posted 8/20/03 5:11 PM Dear Gavin, I too ran into the uninitialized variable problem when I ported QF to 8051, which I've given to Miro. I think it makes sense for QF to initialize those variables to 0 no matter what. If you ever get a hold of my 8051 port, you will see many places where BSS initialization caused problems for me. For example, in case you haven't discovered this yet, the static Tran_ t in Q_TRAN macro body must also be initialized to {{0,0,0,0,0,0,0}, 0} to avoid "weird" problems. I am tempted to provide my 8051 port, but as my port contains a few fixes for the as yet unconfirmed bugs, I think it's better if Miro takes a look first. Now, may I ask you why you have decided to use the foreground/background scenario? On 8051, I had no choice but to use that, as the compiler refused to pass more than 1 pointer in a function call through a function pointer, which is the underpinning of state transition in QF. But if you have no such restriction (what compiler are you using?), would you be interested in using the QF native port (which might be called QuantumOS)? It will allow a truly deterministic, preemptive real-time application, and will soon be available under commercial licensing terms. Looking forward to hearing your thoughts, -Henry http://www.quantum-leaps.com/qf/native.htm QuantumOS ############################################################################## Author: Gavin Haentjens Topic: Limiting memory used by transitions posted: 8/22/03 10:13 PM ------------------------------------------------------------------------------ In my application, memory needed for transitions has become an issue. Each transition requires 34 bytes (although it could be less if I decreased the max transition steps down from 8). A possible work around for this is to use Q_TRAN_DYN() for transitions that are simple (transition to self) or ones that occur rarely. Also, if many substates have the same target, they could post reminders to the superstate and let it perform the transition (only one Q_TRAN is required in that case). If anyone has other ideas, I'd be interested in hearing them. -Gavin ------------------------------------------------------------------------------ Henry Choi posted 8/25/03 2:43 AM Gavin, I think you have answered your own question: use Q_TRAN_DYN() instead of Q_TRAN(). I consider Q_TRAN_DYN() a pure optimization, and as such the familiar memory vs. speed rule applies here. Arguments in favor of using Q_TRAN_DYN(): Your QHsm (the children, of course) must be a singleton for you to use Q_TRAN. Maybe it is now, but what about a few months later, or even in the next rev of the product? The guy who takes over the code may be scratching his head when the system exhibits strange behavior just becase he instantiated one more QHsm class. For scalability and maintainability then, Q_TRAN_DYN is the way to go at first. having to keep track of the hard coded limitation on number of transitions is not a good way to prototype the system. You can, for example, crash the QHsmTst example by sending 2 "g" signal in a row, because the number of transitions in that case will blow the hard-coded limit. At least in the current QF implementation, it's not obvious at first that the limit has been breached, so you may spend some time trying to track down the crash. If you can meet all requirements by using Q_TRAN_DYN, you would only be increasing the idle CPU time unused by switching to Q_TRAN. After you meet the correctness requirement with Q_TRAN_DYN, you can then selective optimize the critical path by switching to Q_TRAN. Hope this helps. http://www.quantum-leaps.com/qf/native.htm QF+ ----------------------------------------------------------------------------- Teemu Karevaara posted 8/26/03 2:11 PM How come QHsm needs to be singleton if Q_TRAN macro is used? Q_TRAN is intended for static transitions and the transition chain is the same for every instance of QHsm. So once any of the instances makes the transition (and stores the static Tran-field in the statehandler) other instances can use the same transition chain (since they use the same statehandler) ----------------------------------------------------------------------------- miro posted 8/26/03 6:13 PM The use of macro Q_TRAN() doesn't necessarily mean that a state machine must be a singleton. For example, there are five Philosopher active objects, and they all use Q_TRAN(). The issue is more subtle than this. As one reader pointed out to me, if multiple and concurrent instances of the same state machine class are created, the setup of the static transition (the QHamTranStat_() method) can lead to race conditions among the state machines. I have fixed this problem in the second printing of the book. (So, remedy of the potential race condition was the primary reason I slightly changed the implementation of static transitions between the first and the second printing of the book). In the first printing, I used tran->chain[0] to detect if the static transition has been initialized. This can lead to race conditions if you have multiple instances of a given state machine (active object) executing the same transition simultaneously (like the Dining Philosophers), because tran->chain[0] is set *before* the full transition chain is stored, so if a state machine is preempted after setting tran->chain[0], the transition chain might be inconsistent (incomplete). To remedy this, I decided to use the LS-bit of the tran->actions attribute to indicate if a static transition has been initialized. This attribute is set only *after* the complete transition chain (tran->chain) has been recorded. Setting tran->actions is also *atomic* (at least on 16 and 32-bit machines), which evades the race condition. (On 8-bit machines, setting tran->actions should theoretically be surrounded by a critical section). The second motivation for this modification was for me that in C++ the pointer-to-member function is potentially a complex object (see Chapter 6), so the test of (tran->myChain[0] == 0) is more expensive than the test of (tran->actions & 1). One side-effect of this change is that only 7-step transition chains can be stored in the 16-bit tran->actions (the LSB is already used, remember?) That's why tran->chain[] array has shrunk to 7 entries. However, the QHsmTst state machine (Chapter 4) now asserts for transition g from state s211. As it turns out, this transition has 8 steps and overflows the chain[] array (which is correctly caught by the postcondition in QHsmTran_() method). A simple workaround is not to use static transition in this case, but to use Q_TRAN_DYN() macro for this particular transition. Coming back to the potential hazards of the Q_TRAN() macro, they are mostly related to inheriting entire state machines. I've explained the issues best I could in Section 6.3 in Chapter 6. Having said all this, I would agree with Henry Choi that Q_TRAN() should be viewed as an optimization of Q_TRAN_DYN(). For simpler (most common) state transition Q_TRAN_DYN() doesn't incur much overhead. In fact, the algorithm has been specifically designed to handle the most-common cases first with minimal overhead (see Section 4.4.4 and Figure 4.7). The bonus of using Q_TRAN_DYN() is no memory overhead for storing the transition chain, which might be significant in memory-strapped embedded applications. -- Miro (miro@quantum-leaps.com) ############################################################################## Author: DBercot Topic: QF/ROOM and Scalability Questions posted: 7/28/03 8:54 PM ------------------------------------------------------------------------------ I am back into Architecture work for my company and would appreciate your opinion(s). I believe that the Quantum Framework may be too "small" (for lack of better thought) for our application(s). My greatest concern concerning "small" is the use of a global definition of events known at compile time on which the QF runs. In one of my diversions, I imagined adding "contexts" to the QF, in which the events were constrained, such that the QF could be used recursively from lower to higher levels of abstraction. Then I ran across your references to ROOM and decided to investigate that architecture, which leads to the following questions: 1. Am I wrong in assuming that the QF may not be appropriate for very large systems ? (smallness) 2. IS ROOM a viable candidate architecture, or does it suffer from the ills that the QF addresses ? 3. Have you ever envisioned an extension to the QF such as "QF contexts" ? Thanks in advance ------------------------------------------------------------------------------ miro posted 8/13/03 5:56 PM Hi there, > Am I wrong in assuming that the QF may not be appropriate > for very large systems ? (smallness) it depends, of course, on what you understand as "very large" systems. From my experience, QF can certainly be scaled up to medium-size (say tens KLOC), or even large-scale systems (hundreds of KLOC). Obviously, for larger systems a single enumeration for all signals (that I describe in my book) isn't going to work, because any change in any signal (or event-class declaration, for that matter) requires recompilation of virtually *all* components. The problem of partitioning the signal space and sharing event-class declarations can be approached in several ways. One way is to emulate ROOM protocols, which are the collections of signals and events that are permitted to enter or leave ports of actors. At the highest level, you can partition the signal space into oversized chunks, say like this: enum { COMMON_START = Q_USER_SIG, // common signals shared by all SHUTDOWN_SIG, ERROR_SIG, // ... COMPONENT_A_START = COMMON_START + 20, COMPONENT_B_START = COMPONENT_A_START + 100, COMPONENT_C_START = COMPONENT_B_START + 50, //... MAX_SIG }; All components must include this enumeration. Then, you can declare "protocol" header files (sets of related signals and event-class declarations) that will be included only in specific components that actually use these protocols. > IS ROOM a viable candidate architecture, or does it suffer > from the ills that the QF addresses ? From what I read about the upcoming UML 2.0 standard, many elements of ROOM (as described by Bran Selic at al.) are now incorporated into UML. This actually shouldn't be so surprising, given that Bran Selic is very active in the UML community. In a sense, ROOM has been ahead of its time... However, ROOM (as most of the UML) is designed to be used in conjunction with a specialized design automation tool. If you try to implement "by hand" ROOM (or parts of the UML, say state machines) you'll end up with... QF, or something pretty close. > Have you ever envisioned an extension to the QF > such as "QF contexts"? I don't quite understand what you mean by "contexts". In earlier iterations of the QF, I tried to follow ROOM much closer by implementing ROOM ports and ROOM protocols. In practice, I found that I didn't get much mileage out of these concepts. In the end, I settled for a very minimal, but non-trivial, architecture. In practice, it's much easier to add new features to a minimal foundation than to go the opposite route of limiting features in an overgrown architecture. -- Miro (miro@quantum-leaps.com) ------------------------------------------------------------------------------ Doug Bercot posted 9/9/03 10:39 PM Good answer ! My concept of a QF "context" would correlate to a ROOM Statechart. As I understand it, ROOM provides a mechanism of nesting statecharts (thereby hiding the internal event set) and exporting new events via the ports of the enclosing statechart. If you could have multiple instances of the "QF" object (containing the pools & publish/subscribe mechanism) you could achieve the nesting of statecharts as ROOM does, but you would then have to somehow bind QF objects to a given "context". Anyways, after reading parts of/most of ROOM and evaluating the Rational toolset, I'm guessing that introducing model based computing to my organization would be like introducing Quantum Physics to the Neandrathals (not likely to be fruitful). BTW - I am still using the QF and C+ in my current app and must congratulate you again for your fine work. ############################################################################## Author: fschwiet Topic: Software for drawing Hierchical FSMs/ UML diagrams posted: 9/15/03 4:44 AM ------------------------------------------------------------------------------ I reviewed some UML diagramming software, and couldn't find anything that supports hierchical state machines. I looke at Microsoft's Visio, and Pacestar's UML diagrammer. Does anyone have any software they recommend for drawing hierchical state machines? If your answer is LatEx, please include samples and whatever external libraries you use. I'm hoping for something windows compatible. ------------------------------------------------------------------------------ Gavin Haentjens posted 9/15/03 8:53 PM The CD included with the book (Practical Statechars in C/C++) contains a Visio stencil for drawing hierarchical statecharts (in the "Resources" section of the disc). -Gavin ------------------------------------------------------------------------------ miro posted 9/16/03 5:41 PM Virtually any drawing tool should be capable of creating UML diagrams, including hierarchical state machines. As Gavin points out, I've used Visio to draw all diagrams in my book (the Visio stencil that I used is available from the CD-ROM accompanying my book, and also online from http://www.quantum-leaps.com/resources/goodies.htm.) However, drawing UML state diagrams is very different from being able to analyze the diagrams for correctness and synthesizing code from them. I have enumerated a few leading CASE tools capable of doing that in my article "Quantum Programming for Embedded Systems" available online at http://www.quantum-leaps.com/writings.cuj/Quantum_Programming.pdf. Also, I've received many letters informing me of other tools for state machines. Some examples include: * xjCharts (http://www.xjtek.com/products/) * SmartState (http://www.apesoft.net/ss/) * Liero (http://www.imatix.com/html/libero/) * Trice (http://www.protos.de/Products/products_E.html) to name just a few. I cannot comment on these tools, since I haven't used them. I've used some other such tools, however, and my experience has always been that ultimately you want to have full control over the synthesizing code. (Nowhere is it more true than in deeply embedded applications.) A tool always keeps you a step away from the code, which, by the way, is quite easy to generate manually. The quantum-leaps.com website, my book, conference papers, and my CUJ column describe how to do just that--write clean, efficient, and highly maintainable state machine code. If you are interested in this approach, please refer to the sources I enumerated, most of which are available online from quantum-leaps.com. A good starting point are excerpts from my book available online (http://www.quantum-leaps.com/writings.book/Practical_Statecharts_Excerpts.pdf --Miro (miro@quantum-leaps.com) ############################################################################## Author: Joerg Krein Topic: qf port for vxworks posted: 7/15/03 3:31 PM ------------------------------------------------------------------------------ Hello, I'm looking for a VxWorks port of the QF. Has anyone starting on this? Regards, Joerg ------------------------------------------------------------------------------ Virgil Farnam posted 8/2/03 0:49 AM I will be starting a port of QF to VxWorks in about 2 months, Still working application requirements & design. Application is an implementation of CCSDS. ----------------------------------------------------------------------------- miro posted 9/16/03 7:31 PM Diego Serafin has contributed a QF port to VxWorks (currently only the C version). I've just made this port available from http://www.quantum-leaps.com/qf/code.htm -- Miro (miro@quantum-leaps.com) ############################################################################## Author: Jinsong Topic: QF on Win XP posted 9/12/03 10:44 AM ------------------------------------------------------------------------------ Hi, I would like to know if QF-windows is compatible with windows XP. though, in theory, it can work because QF-windows is based on win32 API. Thanks in advance. ------------------------------------------------------------------------------ Henry Choi posted 9/18/03 4:57 PM Hi Jinsong, I have been developing QF and QF apps on my WinXP laptop since I learned about QF last year. The examples contained in the book CD will run out of the box on your command prompt, for example. Hope this helps. http://www.quantum-leaps.com/qf/native.htm QF+ ############################################################################## Author: wink Topic: Linked lists for messages posted: 9/18/03 6:16 AM ------------------------------------------------------------------------------ Hello all, I'm implementing an embedded system using a significant sub-set of qp features. After reading Miro's book I'm convinced the notion of message passing and active componets would be useful. But there is one thing I didn't like and that is passing messages by copying them into fixed sized queues. So for my project I'm using linked lists. This eliminates any issues of queue sizing and only means I need to worry about having enough messages around, a problem that has been easily managed. It seems to work quite well and I was wondering if others have used this technique or know of reasons it shouldn't be used. Cheers, Wink ------------------------------------------------------------------------------ miro posted 9/23/03 6:06 PM Hi Wink, please note that event passing in the QF does *not* require copying event into the event queues. As I tried to illustrate in Figure 8.6 (Chapter 6 of my book), event queues hold only the *pointers* to the events and not events themselves. The way you use events in the QF is as follows. You first allocate an event (with macro Q_NEW), then you fill the event parameters and finally you publish or post the event. Upon publishing, the event is *not* copied. Rather only the pointer to the event is placed in the event queue. This means that QF implements, in fact, a mechanism of thread-safe sharing of memory that *looks* like event passing. Because event queues store only pointers, they are quite lightweight. However, your idea of incorporating the pointer into events themselves is intriguing. I believe you can get away with singly-linked list, which will cost only one pointer per event. (Please note that this would not be much more memory efficient than the current scheme, because either way you pay the price of one additional pointer per event.) However, what this scheme would buy you is that you don't need to separately size the event queues -- you only need to size the event pools. At this point I don't know quantitatively how the link-list implementation would compare with the current one as far as CPU use is concerned. One disadvantage of the linked-list method that comes to my mind is that you could not insert an event into several event queues *simultaneously*. The current multicasting mechanism of QF does not require this, but I'm contemplating the possibility of changing that. Events should not be modified after publishing (they are passed as const to the state handlers), so you should safely post the *same* event into multiple event queues. This would solve the problem of possible change in event order that can occur with the current multicasting scheme (which I describe in Section 8.5.3). -- Miro (miro@quantum-leaps.com) ------------------------------------------------------------------------------ wink posted 9/24/03 6:09 AM I understand that you only put pointers in the queue, but I wasn't looking at a space problem, but infact trying to solve the "... don't need to separately size the event queues -- you only need to size the event pools.". I viewed this as a significant problem and the linked lists solves it quite nicely. In the environments I'm using memory tends to not be a problem and I just didn't like having to guess in advance the size of a queue, hence link-lists. Also, in the current implementation when an event is removed from the queue the message is "owned" by the SM that removed it. So, if desired the SM can "reuse" the message and would typically use it as the message it might need to generate. This works well but it does mean that messages can easily get lost, so the programmer must be VERY careful:) For that reason I've thought about removing that "feature", but in reality I can only request the programmer not reuse and can't realy enforce it, so I've taken the pragmatic approach and I let the programmer hang themselves if they want. I also, happen to use doubly linked lists since I already had such a library and there was no compelling reason to make another library. (I try to adhere to some XP principles and try to "minimize" extra work, until it's actually a problem). Thanks for the response, Wink ############################################################################## Author: Gavin Jacksons Topic: QF and Delphi posted: 9/30/03 10:29 PM ------------------------------------------------------------------------------ How would one go about implementing a HSM using the QF under Windows using Delphi. Has anyone do it and if so, how did you go about doing it? What would be the best way to use the message handling built into Delphi? ############################################################################## Author: Tad Ashlock Topic: Quantum Lint? posted 10/1/03 4:15 PM ------------------------------------------------------------------------------ On Miro's home page (www.quantum-leaps.com), he invites us to help advance the qp cause by (among other things): Explore the possibilities of implementing a quantum programming language, perhaps by modifying an open-source C or C++ compiler. Although this approach sounds good, I doubt that I'd ever use a quantum programming language. Being an embedded software developer, I have to develop for a number of different processors and platforms. Many times, I don't get much of a choice in compilers or tools. But something that I think would be useful is a "Quantum Lint". This would statically check for common qf and qp mistakes in C/C++ (or even other languages, too). It could be run during the build process just like "lint" and would do things like: Give an error on Q_TRAN being passed an identifier other than a QState. Give a warning on Q_TRAN_DYN being passed the direct name of a QState. (Could be optimized via Q_TRAN.) etc. I'm sure there's other errors and warnings that would be useful to check for. Also, I don't have any experience implementing this sort of tool, so if anybody has advice please speak up. My first inclination is to implement it in lex/yacc (actually, flex/bison) just because these tools were designed for this sort of thing. But before starting, I'd like to hear what others would want from this tool. So what do you think? Tad ------------------------------------------------------------------------------ miro posted 10/3/03 8:52 PM Hi Tad, I believe that a "quantum lint" would be a very good first step towards a "quantum programming language". The main porblem is that such a tool would need to have very detailed "knowledge" of the C/C++ syntax, which will duplicate the functionality of the compiler. Alternatively, one could develop a "q-front compiler", just as first C++ implementations used c-front to compile C++ to C. A "q-front" could be much simpler, because it would rely on the C/C++ compiler for parsing. --Miro ############################################################################## Author: Paul Topic: Events posted: 9/29/03 6:02 PM ------------------------------------------------------------------------------ I am implementing a QF application in Java and I would like some input on event and state transitions. I have a multi-screened Java application that needs to switch from screen to screen based on control events. Each control will be able to fire an event like ON_CLICK which the given state (I'll probably have at least one for each screen) will handle. My question is this: if the state handler fires off a new event (such as GO_TO_SCREEN4 or something), will it get handled immediately, or after this transition is complete? Does this event ever enter the Event Queue or is that only for events coming from outside the Active Object? Perhaps I am modelling the application wrong. Does it make sense to have a GO_TO event or is that more like an action? I wanted the controls to fire generic events and to have the screen loading/unloading in the entry/exit sections of each screen's state. Any ideas for me? ------------------------------------------------------------------------------ Henry Choi posted 9/30/03 3:34 AM Hi Paul, Your idea sounds okay overall, except the GO_TO_SCREEN4 event. Perhaps I am splitting hair, but a button should just be a button, and should not dictate that the subscriber of its event (if you would like, think of it as a signal) should do with the received information. If you have the button tell the screen (or anyone for that matter) you are introducing an artificial coupling that QF tries so hard to prevent. Perhaps you should call the event Q_BUTTON_PRESSED if transient, or Q_BUTTON_ACTIVATED if it's a toggle button. The motivation for this is from QT (from trolltech), which is a GUI framework that has many concepts parallel to QF. In QT, a button "emits" different signals depending on what happens to it. The user pressing it is one of these events, and causes the button to emit "pressed", "activated", "hidden", etc. Another widget then, may have a slot where the emitted signal may be directed to, and that may for example, be the screen widget that hides/shows itself. By looking at the list of signals a QWidget emits (QT documentation is publicly available from www.trolltech.com), you can borrow many use cases. One striking shortcoming of QT compared to QF is that someone must connect these signals and slots explicitly in code, which introduces coupling, albeit in a far weaker form than the commonly seem strong coupling. Hope this helped. Please let me know if your questions were not fully answered. -Henry http://www.quantum-leaps.com/qf/native.htm QF+ ------------------------------------------------------------------------------ Paul posted 10/6/03 11:54 PM Henry Thanks for the reply... I am familiar with the Qt framwork and I really like it as well. I was planning on having the button fire a generic event (the ON_CLICK event). My question is more about how events cause other events. Is it safe for an event to fire another event? The GO_TO event was my example of a second event firing. I guess what I am interested in knowing is wether or not you can process an event in the middle of a state transition without queueing the event and finishing your RTC step. ------------------------------------------------------------------------------ miro posted 10/9/03 5:33 PM Paul, You cannot process another event before you finish processing of the first event (you must complete the RTC step). So, in particular it is not OK to call dispatch() method in the middle of event processing (i.e., call dispatch() on behalf of the same state machine that is just active). Calling dispatch() in the middle of event processing would cause recursion (we are already inside dispatch()) and would confuse the "event processor". The workaround is to use the "Reminder" state pattern (see Chapter 5 in my book), but this requires event queueing. I hope this answers your question. -- Miro (miro@quntum-leaps.com) ############################################################################## Author: Lawrence R. Sweet Topic: QF under QNX Neutrino posted: 10/14/03 6:19 PM ------------------------------------------------------------------------------ Has anyone ported QF to Neutrino yet? ############################################################################## Author: John O. Topic: Problem with QF timers posted: 10/20/03 7:12 PM ------------------------------------------------------------------------------ Hello, I am running into a problem with the timers implemented in the QF. Specifically, it has to do with using the QTimerDisarm() method. This method only sets the number of remaining ticks in the timer to 1, and sets the signal to the "empty" signal. Thus, disarming the timer doesn't really disarm it. It only makes it expire one tick later. This is all fine and well, until a timer is disarmed, and then subsequently restarted before another tick can complete (it asserts under these conditions since the timer is still in use). On my system, my tick rate is one second (reducing it would help reduce the problem but would never eliminate it). Is there a way to truly disarm a timer, so there aren't any requirements about how long you wait before you can actually access the timer again? This seems like a potentially big problem with the timer subsystem. Oh yeah....just so it doesn't seem like I'm only harping on a problem, I have successfully used the QF for the last nine months or so under Linux, and really like it. Thanks for the help, John ------------------------------------------------------------------------------ miro (Moderator) posted 10/29/03 7:09 PM Hi John, I haven't been quite happy with the QTimer class for quite a while now. As you point out, disarming a timer is done by a "trick" to turn it into a one-shot timer that should expire by the next tick. This is to avoid a potentially indeterministic scanning through an (open-ended) list of timers, which must be done in a critical section. Also, the precondition to disarming the timer (i.e., that the timer must be armed) seems to strong. I found it often useful to disarm a timer upon exit from a state, and sometimes the timer was already expired. In short, I've changed and hopefully improved the QTimer class. I've been using this new class for more than half a year now and it works just fine. I've added a new section to the website that describes the new developments of QF(please check http://www.quantum-leaps.com/qf/ code#QFNew). Among others, you'll find there code to download. I hope this helps, --Miro (miro@quantum-leaps.com) ############################################################################## Author: Sam Gu Topic: How is QF related to UML-RT and ROOM? posted: 11/2/03 1:35 AM ------------------------------------------------------------------------------ Seems like the concepts are identical, just QF puts more emphasis on resource efficiency. miro (Moderator) posted 11/3/03 8:25 PM ------------------------------------------------------------------------------ Hi Sam, You are right. QF is based on the *same* fundamental concepts as UML-RT and ROOM. Indeed, as I've been repeating for years (many times in my book, in my articles, and at conferences) the conceptual underpinnings for QF have been known for at least two decades. So in this respect, QF is closely related to UML and the tools you mentioned. However, QF is also very different. What sets QF apart is its minimalist, code-centric, and low-level nature. This characterization is not pejorative; it simply means that QF maps the fundamental concepts directly to the *source code*, without necessarily relying on graphical representations (although you can obviously use diagrams if you like). One of the most important aspects of QF is that hierarchical state machines and active objects (as any other profound concepts in software) are a powerful type of design, not a particular tool. The issue here is not a tool — the issue is understanding. Code-synthesizing tools (such as UML-RT (former ROOM toolset), Rhapsody, BetterState, visualState, and others) can have heft and substance, but they cannot replace a conceptual understanding. The lightweight state machine- based framework like QF shows that (once you know the patterns) it's quite easy to implement the fundamental concepts without sophisticated tools. QF thus dispels many deeply rooted misconceptions and misunderstandings that higher-level UML concepts are not viable without sophisticated tools. I hope you get the point. The Preface and Conclusion of my book available online (http://www.quantum-leaps.com/writings/book.htm) discuss the issues in more detail. Best regards, --Miro (miro@quantum-leaps.com) ############################################################################## Author Topic: QF V3 ? Joerg Krein posted 10/31/03 12:00 AM ------------------------------------------------------------------------------ Hi, in the download section I read something about a new QF version: 'This section describes the latest version of qF (V3.x).' You can download a new version of QTimer there. I bought the book with version 2.2 of QF (ISBN: 1-800-788-3123). Does that mean I have to buy the book again, to get the latest version of the QF? What about the errats? Do you supply patches for the code? Regards, Joerg ------------------------------------------------------------------------------ miro (Moderator) posted 11/5/03 4:15 AM Hi Joerg, As the book publishing cycle goes, it is almost impossible to keep adapting the book to the evolving code. I've tried to do it once (between the first and the second printing of the book) and shot myself in the foot by introducing a bug (which I had to fix in the errata, see http://www.quantum-leaps.com/ writings/book.htm#Errata). Consequently, I have no plans to make any modifications to the published code (not that I really could). Please note, however, that the published code has been thoroughly tested and, in fact, I haven't found or heard of any evident bugs in it yet (except of the one just mentioned). Of course, now that a few thousand copies of the book are in circulation the code is exercised in very diverse environments and some perhaps unexpected behaviors get discovered. In addition to hundreds of e-mails that I received from readers, my own experience with QF has grown considerably since the code was first written (now over two years ago). So, naturally I want to improve and evolve the framework. I don't know yet when the complete QF v3.x will be ready or how I'll make it available to others, but I hope that not only QF V3.x but 4.x and higher will eventually emerge. Depending on the demand, maybe I'll decide to write a second edition of "Practical Statecharts in C/C++". Such next edition would be ideal place for the next generation QF. For now, however, please keep checking quantum-leaps.com from time to time. Best regards, --Miro (miro@quantum-leaps.com) ############################################################################## Author Topic: Port for Ada95 Tad Ashlock posted 9/23/03 10:09 PM ------------------------------------------------------------------------------ Has anybody tried porting the QF to Ada95? It looks like some parts of the QF would be slicker than the C++ implementation, such as: * QSignal could be implemented as a hierarchy of empty tagged records instead of a C++ enumeration. This overcomes the problem of extending the enumeration without having to have all signals being global. * QState could be defined as actually returning a QState, rather than a QPseudoState. * Multi-threading is supported directly in the language -OR- * Use a port of the Single-Stack Tasker with a runtime-less Ada95 (e.g. gnort). ******************** The only problem I currently see is how to port the following construct from QHsm: #define Q_TRAN(target_) if (1) { \ static Tran t_; \ tranStat(&t_, Q_STATIC_CAST(QState, target_));\ } else ((void)0) AFAIK, Ada95 doesn't have anything like this. Anybody have any ideas or other hurdles that I haven't stumbled across yet? Thanks, Tad Jonathan Kaye posted 11/6/03 7:50 AM ------------------------------------------------------------------------------ I don't know Ada95, but as far as your question regarding porting Q_TRAN, I've run into a problem porting QF to ActionScript/Flash (actually, Miro ported it, I just tweaked a bit). ActionScript doesn't have macros, so Q_TRAN's search (or really tran) has to be run each time. To optimize this, I was thinking I would to have to define each transition in a variable before the engine is run. So I'd have to maintain a list of transitions and reference the specific transition in each state method. Not real elegant, but what can one do? -jonathan ############################################################################## Author Topic: QFsm and QHsm port to ActionScript 1 & 2 Jonathan Kaye posted 11/17/03 8:53 PM ------------------------------------------------------------------------------ I wanted to let people know that Miro has ported his QFsm and QHsm to ActionScript 1 & 2 (Macromedia Flash MX and Flash MX 2004). I helped tweak it a bit and make some more examples. The code is available at http://www.FlashSim.com/newsletter/samekengines.zip with info about this at http://www.FlashSim.com/newsletter/v1n6.html you can direct comments to our FlashSim discussion board (http://flashsim.infopop.cc). thanks, Miro! -jonathan http://www.FlashSim.com ############################################################################## Author Topic: States inside States with Visio Brian O'Shea posted 11/6/03 10:40 PM ------------------------------------------------------------------------------ I am using Visio 2002 SR 1, and I have the templates that Miro used to put together the diagrams in the book. I may be having a serious stupid attack, but I can't get the states to layer on top of each other. When I drag one state onto another, it snaps out of the way. It would save me some time if someone who knew Visio could help out a Visio novice... Thanks! miro (Moderator) posted 11/18/03 7:48 PM ------------------------------------------------------------------------------ Hi, just yesterday I installed Microsoft Visio 2003 and had a chance to try out the stencil I used before in my book. I opened the stencil from the menu File/Shapes/Open Stencil. The old stencil opened correctly and I could draw states within states without any problems. I also could save the stencil in the new Visio format (breaking backward compatibility with the older versions of Visio, of course). --Miro (miro@quantum-leaps.com) ############################################################################## Author Topic: Posix Threads JoAnn Peeler posted 11/26/03 4:34 PM ------------------------------------------------------------------------------ I'm a student at Florida State University and I will be taking a class that covers HSM and QF. Looking at the readme for the Linux port of QF, I noticed that there was some problem using gdb with a Posix-threaded app. Has there been a resolution to this problem? I don't know enough about QF at this point to make any salient contributions to this forum, but I'm sure that will change. In the mean time, its nice that this site is here for more information about QF. http://garnet.acns.fsu.edu/~jdp02d/ My Home Page ----------------------------------------------------------------------------- miro (Moderator) posted 12/2/03 6:57 PM Hi JoAnn, POSIX threads, and POSIX APIs in general, have many implementations. In the desktop Linux implementation, I experienced problems when debugging multithreaded applications with gdb (or derivative tools, such as ddd). The problem was that once a breakpoint has been hit in one POSIX thread, the other threads kept going and corrupted the state of the application. The tools significantly improved with newer Linux distributions (I worked with RedHat stuff), but still there were occasional "hiccups". To my knowledge, POSIX threads are still not quite integrated with the gdb debugger (I hope some other readers will correct me here, or provide some tips how to work around the issues I mention.) I don't recall any of such problems in other implementations of POSIX threads, such as VxWorks. VxWorks uses GNU tool chain and, among others, implements POSIX APIs. The gdb worked just fine. --Miro (miro@quantum-leaps.com) ############################################################################## Author Topic: QF lite Bob Lee posted 11/25/03 5:35 AM ------------------------------------------------------------------------------ I've read Practical State Charts in C/C++ and would like to use them on my current project; however, I need to reduce the QF foot print (ROM & RAM) to make it work on the 8-bit micro we are using. Is there a QF lite available? miro (Moderator) posted 11/25/03 7:04 PM ------------------------------------------------------------------------------ I've received quite a few letters from readers who tried QF on small platforms. A few readers reported that they have ported QF to Keil C for 8051 processor family. I guess, Luis Pereira from Network Technologies and Electronics Group (LuisRPereira@Eaton.com) was the most advanced in using QF under these circumstances. Generally, I believe that the basic ideas are scalable down to very small platforms. So in particular, you can fit HSM, events, timers, and so into very resource-constraint environments. From what I see, the most severe limitation is RAM, not so much the CPU cycles. To conserve RAM you should consider using only the dynamic state transitions (see "Practical Statecharts", Section 4.4.3). On very small platforms, I'd probably eliminate the whole publish-subscribe part of the QF and allow only direct messaging among active objects (via QActivePutFIFO(), QActivePutLIFO() methods). On the other hand, I believe that you need to use at least one event queue (at least one active object) and an event pool. Event queue(s) and event pool(s) allow a thread-safe communication between the interrupt-level and the task-level and you don't want to lose this benefit. On small platforms, you can make events smaller. For example, the whole QEvent can be just one byte (if you use only one event pool and one active object you need to store only the signal in QEvent. You should define QSignal to be unsigned char). Recently I've been working on a new version of QF (QF v3.0), which I plan to make freely available to the owners of my book. QF v3.0 is a little more memory-efficient than QF v2.x published in the book. Depending on the demand, I might consider releasing a special stripped-down version of QF v3.x (a "pico-QF") for very small micros. Probably, this version(s) must be platform dependent (e.g., Keil C for 8051). --Miro (miro@quantum-leaps.com) ------------------------------------------------------------------------------ Holt posted 11/26/03 2:27 AM I too just got the book and am thinking about using your methods for a project I am working on. I'm worried about the amount of RAM that is required. Can you give me an idea? I know it's tough without knowing the scope of the problem. To give you an idea I will have only one 2-level HSM with 6 superstates and at most 8 substates. I would estimate about 40 transitions between states (Just counting the number of arrows on the statechart. Maybe this isn't the best way to convey the size of the application). I am considering one of the AVRmega parts from Atmel because the tools are free and plenty of RTOS's available. At most this part has 4K of RAM. Is this going to be enough or should I just not even bother? I'm looking at an RTOS which has been ported to the AVR family. It is called FreeRTOS and can be found at www.freertos.org. It supports preemptive scheduling, message queues, and I'm thinking about trying to port QF to it. None of these decisions are set in stone, so any suggestions you may have that could save me future headaches would be much appreciated. Thanks, Holt ------------------------------------------------------------------------------ miro (Moderator) posted 12/2/03 7:41 PM Hi Holt, To give you a better idea of the RAM requirements for using the HSMs and the rest of the Quantum Framework, here is a little breakdown: -- Each instance of QHsm costs 2-function pointers (4 bytes on 8-bit micro with 64k address space). That's the whole RAM you need, if you don't use static state transitions (only dynamic transitions, see Section 4.4.3 in "Practical Statecharts"). The state handlers are just functions that go into ROM. -- The QHsm class has been specifically designed to use little stack. In particular, no recursion (natural in hierarchical structures like this) has been carefully avoided and replaced with iteration. -- You'd need RAM for event queue(s). Event queues store pointers to events (again, 2-bytes per pointer). If you use a queue 10-events deep, say, you need 20 bytes of RAM for the ring buffer and some 10 bytes for the queue itself. -- You'd need RAM for event pool(s). Event pool stores the events efficiently, without any additional RAM to link the blocks (see Section 9.3.2 in "Practical Statecharts"). The RAM you need here depends entirely on how big your events are and how many of them you need. If you need, say, 10 events of 8-bytes each, you'd need 80 bytes for the event pool buffer and some 8 bytes for the event pool itself. As you can see, I believe that the whopping 4K of RAM is plenty for a minimal QF application. Maybe you could even squeeze in the publish-subscribe feature? Interestingly, state machines often obviate the need for using an RTOS. If you can design your state machine with sufficiently short RTC (run-to-completion) steps then you can achieve the desired responsiveness without a preemptive RTOS. Please refer to the discussion of the "Reminder" state pattern in Chapter 5, and to the foreground-background port of the QF in Chapter 9. The "Reminder" state pattern is particularly useful for chopping any longer processing into shorter RTC steps to achieve better responsiveness. Obviously, eliminating the RTOS frees up significant RAM that you need to pay for the internal RTOS structures and the multiple stacks. Regards, --Miro (miro@quantum-leaps.com) ############################################################################## Author Topic: Generating Code for Embedded Apps ------------------------------------------------------------------------------ Torsten Kuenstler posted 12/9/03 10:40 AM Hello Everybody, I'm studying Computer Science and to become a bachelor in CS I have to do some writings that in Germany we call Diplom. For this, I will invent a Code Generator. Based on QF this will Generate Code from UML to C+ for a MC. This MC will be the C167 from Infinion. So, what I ask for is: Does anybody have experiences or ideas? Regards, Torsten ############################################################################## Author Topic: basic question Mountain Bikin Guy posted 12/11/03 5:05 AM ------------------------------------------------------------------------------ I recently ordered "Practical Statecharts in C/C++" but it has not yet arrived. In the mean time, I have a basic question I hope someone can help me with. I am designing a simple state machine to model a real world situation with 5 possible states. However, instead of the usual clear final state, I have a situation where states 4 and 5 both signify valid end states. I'm not sure how to deal with this. Any advice is appreciated. In both states 4 and 5, control can transition to either state 2 or to another device (another state machine). So there is no difference from this vantage point. However, devices interacting with this device need to make decisions based on whether this state machine is in state 4 or state 5. That information forms the basis for a decision that could influence whether control transitions to this state 2 or to the other device. What is the standard technique for dealing with this? I'm sure this is a common issue that has a well-known solution. I just don't know what it is. Anyone have any advice? Thanks! Mountain (copies to dshiel@yahoo.com appreciated) miro (Moderator) posted 12/15/03 7:13 PM ------------------------------------------------------------------------------ Yeah, I believe that your problem is indeed pretty common. The issue is related to maintaining state consistency across all state machines comprising the system, something I call the "system-wide" state. The "dining philosopher" example from the book illustrate some aspects of this problem. The Philosopher objects and the Table object must coordinate their state. The right way to achieve it is to exchange notification events whenever a state of one object changes and some other state machine object in the system should "know" about it (e.g., a Philosopher is done eating). The wrong way is to check the state of the peer object directly (perhaps by calling isState() method). The most important aspect of QF that facilitates maintaining the consistent "system-wide" state is the guaranteed event delivery (that’s why QF asserts if an event cannot be enqueued). That way, the notification events are never lost. --Miro (miro@quantum-leaps.com) Mountain Bikin Guy posted 12/17/03 3:54 AM ------------------------------------------------------------------------------ Thanks for your reply Miro. Your book just arrived today from Amazon, so I can finally start reading it! I realize the solution to my question is not simple, but instead requires properly designing the statechart. I look forward to more reading in your book! Regards, Mountain ############################################################################## Author Topic: qFJ - Java port of qF Glenn McAllister posted 12/31/03 7:55 AM ------------------------------------------------------------------------------ I've written an open-source Java port of the qF framework, available at http://www.codingknights.com/projects/qFJ/ The current version is 0.9.0. Its fully functional with QFsm, QHsm, and QF implementations. Its the whole shebang, not just QHsm. There are a couple of issues that have to be resolved before a 1.0.0 release: 1. static state transitions in QHsm. 2. efficient event pooling (right now all events have to be created off the heap). I'm working on 2 right now, as its easier. :-) I'd be very happy to recieve feedback on qFJ. Please post replys to this thread; I don't have qmail up and running on codingknights.com yet, and I'm not eager to hand out my home email to a web page; I'm sure to get spammed then. :-) http://www.codingknigths.com/projects/qFJ daniel posted 1/7/04 4:23 AM ------------------------------------------------------------------------------ you mispelt your url, the correct url is: http://codingknights.com/projects/qFJ/ Glenn McAllister posted 1/7/04 5:48 AM ------------------------------------------------------------------------------ I usually catch that. Thanks for pointing out my error. http://www.codingknights.com/projects/qFJ/ Glenn McAllister posted 1/9/04 11:12 PM ------------------------------------------------------------------------------ The 1.0 release of qFJ is available, with reasonably efficient event pooling and a more java IoC style way of hooking the active objects together. http://www.codingknights.com/projects/qFJ/ ############################################################################## Author Topic: Overview of qF 3.0? DeanONH posted 12/28/03 8:50 PM ------------------------------------------------------------------------------ I saw a reference to qF 3.0 on the qF webpage. Can you give us an overview of qF 3.0? TIA, Dean miro (Moderator) posted 12/30/03 7:44 PM ------------------------------------------------------------------------------ The purpose of the recently announced QF v2.5.0 release is to offer the readers of my book "Practical Statecharts in C/C++" a common version of the framework source code with all the bug fixes mentioned in the Errata (http://www.quantum-leaps.com/writings/book.htm#Errata). This version is 100 percent compatible with all the examples scattered throughout the text and all printings of the book (some minor changes were made between the first printing and subsequent ones). Currently, QF v2.5.0 doesn't have any known bugs. However, should new bugs be discovered, I'll update this online distribution. I'll keep numbering these book-compatible versions of QF as major revision 2 (QF v2.x.y). I'll also provide the requested revision history (I'm currently working on it, but my days have only 24 hours). As to the next major revision of QF (QF v3.x), this version will NOT necessarily be fully compatible with the book. Obviously, the main ideas remain the same (HSM, behavioral inheritance, active objects, publish-subscribe event delivery, event queues, event pools, timers, and so on). However, some policies, implementation techniques, and algorithms in QF v3.x will be different from these published in the book. QF 3.x (and subsequent versions) will reflect the experience with QF accumulated over the 2 years since the code for the book was written, as well as countless suggestions from QF users. QF 3.x will come with the updated manual. Just as the book-version of QF (QF v2.x), QF v3.x is intended to be used in conjunction with an RTOS or standalone (in the foreground/background mode). I'll probably offer QF v3.x at a small price (comparable with the price of the book). Finally, in planning is also a fully standalone version of QF (QF+), which would include a tiny, pre-emptive, deterministic kernel and would not require any underlying ROTS. This version would be based on QF v3.x, but will be optimized for concrete microprocessors. It will be offered together with evaluation boards, all development tools (GNU based), startup code, flash-based boot-loader, debugging interface (inexpensive JTAG probes), event-driven device drivers, documentation, support, and so on. I believe that QF+ will address a growing need in the embedded software community for inexpensive, comprehensive event-driven environments for higher-end 8-bit, 16-bit, and lower-end 32-bit platforms. The first planned version of QF+ will be for the ARM7TDMI core, which is rapidly becoming an industry standard. Evaluation versions of QF+ will be available for x86 (real and protected mode). QF+ is planned to be royalty-free and will be available commercially at prices comparable to other royalty-free RTOSes (such as MicroC/OS-II). --Miro (miro@quantum-leaps.com) ############################################################################## Author Topic: 2 Behavioral Inheritance question Mountain Bikin Guy posted 12/30/03 0:02 AM ----------------------------------------------------------------------------- 1. Say a substate overrides (redefines) handling of a certain event. How can it also take advantage of the superstate's generic handling at the same time? In an OO language, the overriding method would perform some actions and call the base class method. How can we (properly) do that with state event handlers? 2. Say we have some deeply nested states. Say we want to have a guaranteed action on exit from one of these deeply nested substate (call it 'dns'). We also want a similar (or identical) exit action from the superstate of all these substates. How can we avoid repeating the exit action twice in the situation where we are in the 'dns' state and exit entirely out of the superstate. ############################################################################## Topic: State Machine Semantics and State Machine Design Author: Miro Samek (Moderator) posted 1/12/04 3:27 AM This discussion thread contains postings related to state machine semantics and using state machines to solving concrete problems. ------------------------------------------------------------------------------ basic question Mountain Bikin Guy posted 12/11/03 5:05 AM I recently ordered "Practical Statecharts in C/C++" but it has not yet arrived. In the mean time, I have a basic question I hope someone can help me with. I am designing a simple state machine to model a real world situation with 5 possible states. However, instead of the usual clear final state, I have a situation where states 4 and 5 both signify valid end states. I'm not sure how to deal with this. Any advice is appreciated. In both states 4 and 5, control can transition to either state 2 or to another device (another state machine). So there is no difference from this vantage point. However, devices interacting with this device need to make decisions based on whether this state machine is in state 4 or state 5. That information forms the basis for a decision that could influence whether control transitions to this state 2 or to the other device. What is the standard technique for dealing with this? I'm sure this is a common issue that has a well-known solution. I just don't know what it is. Anyone have any advice? Thanks! Mountain (copies to dshiel@yahoo.com appreciated) ------------------------------------------------------------------------------ miro (Moderator) posted 12/15/03 7:13 PM Yeah, I believe that your problem is indeed pretty common. The issue is related to maintaining state consistency across all state machines comprising the system, something I call the "system-wide" state. The "dining philosopher" example from the book illustrate some aspects of this problem. The Philosopher objects and the Table object must coordinate their state. The right way to achieve it is to exchange notification events whenever a state of one object changes and some other state machine object in the system should "know" about it (e.g., a Philosopher is done eating). The wrong way is to check the state of the peer object directly (perhaps by calling isState() method). The most important aspect of QF that facilitates maintaining the consistent "system-wide" state is the guaranteed event delivery (that’s why QF asserts if an event cannot be enqueued). That way, the notification events are never lost. --Miro (miro@quantum-leaps.com) ------------------------------------------------------------------------------ Mountain Bikin Guy posted 12/17/03 3:54 AM Thanks for your reply Miro. Your book just arrived today from Amazon, so I can finally start reading it! I realize the solution to my question is not simple, but instead requires properly designing the statechart. I look forward to more reading in your book! Regards, Mountain ------------------------------------------------------------------------------ Behavioral Inheritance question Mountain Bikin Guy posted 12/30/03 0:02 AM 1. Say a substate overrides (redefines) handling of a certain event. How can it also take advantage of the superstate's generic handling at the same time? In an OO language, the overriding method would perform some actions and call the base class method. How can we (properly) do that with state event handlers? 2. Say we have some deeply nested states. Say we want to have a guaranteed action on exit from one of these deeply nested substate (call it 'dns'). We also want a similar (or identical) exit action from the superstate of all these substates. How can we avoid repeating the exit action twice in the situation where we are in the 'dns' state and exit entirely out of the superstate. State Machines from state table edd posted 1/9/04 5:04 PM hello Dr Miro, in the december issue of your column in C++ User journal, you mention that you do not like to derive state machine from state tables, how then do you come up with all the required states needed in a formal method rather based on experience or gut feeling? regards ------------------------------------------------------------------------------ State Machines from state table Tedd posted 1/9/04 5:04 PM hello Dr Miro, in the december issue of your column in C++ User journal, you mention that you do not like to derive state machine from state tables, how then do you come up with all the required states needed in a formal method rather based on experience or gut feeling? regards http://www.quantum-leaps.com ------------------------------------------------------------------------------ Holt posted 4/25/04 11:00 PM Part of the system I am working on requires the use of a small 2 line 8 character per line display. The LCD is a parallel device and to send it a command or write data to it basically requires that you write a value to a register and wait say 10ms. So the action of writing a register and waiting 10ms is a very common action when communicating to the LCD and for the sake of this conversation let's just refer to this action as sending the LCD a command. The intialization of the LCD requires that I send a defined sequence of commands to the LCD. Sometimes the same command may be repeated multiple times. Once the LCD has been initialized it's just a matter of waiting for the application to request that a sequence of commands be sent to the LCD. I started with an approach in which I was basically creating a state machine in which one command corresponded to a state. The state would write the particular command to the register in the entry action then set up a one shot timeout to transition to the next state (10ms) for the next command to send the LCD. This was my approach for the intialization, but I noticed that this was not a very scalable solution. I guess I'm looking for a solution which utilizes a substate which writes a single command to a register and performs the 10ms wait while the rest of the active object feeds the commands to be written to this substate. I'm thinking this is probably a common problem and I'm just looking for any ideas that people may have. Or maybe a different perspective which simplifies the solution. Thanks, Holt ------------------------------------------------------------------------------ Miro Samek posted 4/29/04 0:44 AM Holt, Your situation is indeed quite common, although your LCD access "protocol" is probably too simple to benefit from the generic solution that I use in such cases. In your case each command to the LCD could be modeled simply as a state, which upon entry would write w value to the LCD register and arm a 10ms one-shot timer. The timeout would cause transition to the next state (next command) etc. A more general solution for such communication protocols (perhaps consisting of many steps, timeouts, retransmissions, etc.) is to use the "Orthogonal Component" state pattern (see Chapter 5 in "PSiCC"). The protocol is modeled as a component state machine that encapsulates the details of communication. The container dispatches the communication request event to the component and waits for the notification from the component when the transaction completes. While waiting for the notification, the container dispatches all communication-related events (such as timeouts) to the component, because the component doesn't have its own event queue and relies on the event queue of its container. Upon completion of the whole transaction, the component notifies the container by dispatching a COMPLETE event, at which time the container proceeds to another state. Please note that the container doesn’t need to "know" the details of the protocol, only when the whole transaction completes. Also, the container can easily reuse component's state machine from many different states, so you don't need to repeat the same, possibly complex, sequences of states in the component's state machine. Finally, the container can manage multiple transactions in parallel (each transaction handled by separate component). Typically, the dispatching of events to the protocol components is implemented at the highest level states of the container, so all substates inherit the behavior and don't need to "remember" to dispatch events to various components. Obviously, this pattern is an overkill in your case, because your transaction completes when the 10ms timer expires and there are no other steps to handle by a "LCD" component. Regards, --Miro ------------------------------------------------------------------------------ Brent Arias posted 6/18/04 9:26 PM Dr Samek, Two issues: (1) What is the justification for keeping init() as a seperate function from tran()? (2) Why does QHSM not permit figure 5.4(a)? Your note on page 90 appealed to "simplicity," though I don't see how it is simpler. Somewhere I think I've read a more elaborate defense of your restrictions related to these items, but I can't remember where I read it. Nevertheless, the tran() function waits until the target state is reached, and then begins iteratively sending INIT signals to permit further "initial" transitions. Perfect. This appears to be all the functionality I'd ever need (no need for a seperate init() function). Indeed, for a moment please imagine the following: assume my initial pseudo-state is properly initialized (with my current state set to the top state) and then I initialize the statechart of figure 4.3 by calling tran(s11). This alternate approach I think accomplishes the same intended result (and prevents me from ever needing to use the reminder pattern for certain initial transitions -page 143). Please advise me of the errors in my thinking. Thank you. Brent http://www.ariasamp.net ------------------------------------------------------------------------------ miro (Moderator) posted 6/21/04 4:58 PM Good questions. (1) In principle you're right. The top-most initial transition (section 4.15 in "PSiCC") could be, in principle, implemented with the tran() method. However, the init() method gives the client programmer the opportunity of performing initialization, because it "executes" the initial pseudo-state, which in turn calls Q_INIT(). In Exercise 4.2 I present an alternative design, which relies on a virtual function initial() rather than the concept of an initial pseudostate (the code implementing this design is available from the CD as the answer to Exercise 4.2). Please also refer to pages 127-128 for explanation why two macros Q_INIT() and Q_TRAN() are used. (2) This restriction is really only for ease of implementation. Please note that the natural navigability in this implementation is only from substates to superstates (a substate returns a superstate if it doesn't handle an event). This means that "drilling" down the hierarchy is expensive, because you go "against" the natural direction. By restricting the initial transition to go only one level deep I don't need to test how many nesting levels have been crossed in order to find out which entry actions to execute (see the implementation of the trai() method). Best regards, --Miro ------------------------------------------------------------------------------ Brent Arias posted 6/21/04 10:16 PM Yes, after studying the code more carefully I concluded init() is seperate and distinct in implementation from tran()...so that less computational work is done to achieve the same result. Another benefit of the init() implementation (which is partly re-implemented at the end of tran()), is that it forces "correctness" related to "initial transitions." Put differently, if I used tran() "as is" to perform an "initial transition," I could potentially transition to peers or superstates - which would violate the premise of an "initial transition." As a result of this investigation, it intrigues me that a given leaf state of the QHSM is minimally the "head" of a singly linked list (each state returns its parent), but when you introduce Q_INIT() calls into the "list" of states, then it implicitly becomes a doubly-linked list (which init() exploits). Still, from pages 127-128 which you referred me to, there is something I disagree with. The text says "Using Q_TRAN() in initial transitions would lead to recursive invocation of the underlying QHsm::tranStat() method (the transition chain includes drilling into the state hierarchy with initial transitions)". You see, if I was willing to compromise efficiency for the sake of flexibility (ala. permitting figure 5.4(a) to be legal), then this is what I would do: 1) eliminate the init() function but keep Q_INIT() with a broadened contract (detailed in #2). 2) re-implement the very tail-end of the tran() "inLCA:" code segment of page 114 (which handles initial transitions) so that Q_INIT() can target **grandchildren** in addition to immediate children! Yes, this approach would inefficiently perform twice the computation of the current "inLCA:" code segment, but it also means that there otherwise is no "recursive invocation of the underlying QHsm::tranState() method" since there would no longer be the same **single-step** "drilling" as before. Yes all substate "entry" handlers would still get called properly, and yes an ASSERT could be levied to ensure it is indeed a child or *grandchild* targeted by Q_INIT(). Congruently with this implementation, an "init" signal would *not* be sent to each transitory substate (as it is in the current implementation) because it would no longer be necessary or desireable. Furthermore, the very first transition of a "tran() only" state-machine would still involve the initial pseudo-state, but the initial pseudo-state **would not** make a call to Q_INIT(). Instead the initial pseudo-state handler would be empty (unless extended state initialization was desired). Ergo, this proposed revision to the tran() function would be using its central work-horse mechanism (listing 4:10, lines 1-74) for reaching the initial target state. Perhaps this alternate approach would be "simpler" for those who aren't concerned with loss of performance (e.g. GPP developer's, or non-RT applications). Indeed, loss of performance is the only drawback I can envision (which admittedly would be unacceptable for many developers). I'm curious how much of these thoughts you might agree with or disagree with. Thanks, Brent http://www.ariasamp.net ------------------------------------------------------------------------------ Brent Arias posted 6/21/04 11:37 PM Dr. Samek, A thought occurred to me: consider the notion of a "completion event with priority." It would be implemented like this: case MyEventHandler: tran(MyStatePointer); if (MyCompletionCondition) { dispatch(MyCompletionEvent); } return 0; ... yes I realize this violates the policy that no code should be added to an event handler after a call to tran(), but it seems like this would be a fairly clean way to address a "completion event with priority" scenerio. In other words, this approach assumes you want a given "completion event" to be received by the newly identified state - before other events from the queue are dispatched. Nevertheless, are these particular semantics too barbaric to take seriously? -Brent http://www.ariasamp.net ------------------------------------------------------------------------------ Sreenivas posted 6/24/04 8:06 AM I'm trying to convert a flat state machine that controls an optical line card into an HSM using QF. The current state machine is implemented using tables. When the line card is first created, a CREATE signal transitions the line card from NEE (Non-Existence of Entity) state to one of several possible target states as shown in the table below. Current State (PST+SST), Signal Received, Target State (PST+SST) ----------------------------------------------- NEE+NEE, CREATE, OOS-AU+DGN NEE+NEE, CREATE-N-CARD-MISSING, OOS-AU+UEQ NEE+NEE, CREATE-N-SWVRMM, OOS-AU+MEA NEE+NEE, CREATE-N-BOOT-FAIL, OOS-AU+FLT Before the state table is looked up, the received CREATE signal could further be "enhanced" to one of - 1. CREATE-N-CARD-MISSING, if card is unplugged 2. CREATE-N-SWVRMM, if software version is mismatched 3. CREATE-N-BOOT-FAIL, if card can't boot The enhancement is determined by an ENUM written to the database by another application. 1. The Line Card is an Active Object. NEE and OOS-AU are its peer-level states. DGN, UEQ, MEA & FLT form the sub-states of OOS-AU. Is this a good HSM model? Are there any alternatives? 2. When transitioning from NEE to OOS-AU, should I just replace the enhanced signals with a guard and conditional transitions? Isn't there a more elegant solution? Any suggestions are appreciated. Sreenivas ------------------------------------------------------------------------------ Sreenivas posted 6/25/04 3:59 AM My state machine follows the Telcordia GR-1093 "Generic State Requirements for Network Elements" model. Object State = Primary state + Secondary state Primary State = Primary Service State (IS or OOS) + Primary Service State Qualifier (NR, ANR, AU, MA, AUMA) Secondary State = One or more Secondary Service State Qualifiers (SGEO, MT, FLT, MEA, etc.) Examples of object states are - OOS-AU, SGEO OOS-MA, MT OOS-AUMA, SGEO, MT OOS-AUMA, SGEO, FLT, MT SGEO & FLT can only appear with AU. MA can only appear with MT. Consider the following state hierarchies - Level-1: OOS Level-2: AU Level-3: SGEO, FLT Level-1: OOS Level-2: MA Level-3: MT How do I represent AUMA in this hierarchy? If I make AUMA a separate substate (below OOS), I will have to replicate all substates under AU and MA and their associated transitions in AUMA. AUMA can contain all the secondary service state qualifiers of both AU and MA. I don't want to use multiple inheritance; but even if I did, I can only derive AUMA from AU and MA, which means that I will have to replicate the Level-3 substates in AUMA anyway. AUMA is not orthogonal to AU or MA. Since the Telcordia state model is so common, this problem must have been tackled somewhere. Any suggestions, ideas? Thanks, Sreenivas ------------------------------------------------------------------------------ miro (Moderator) posted 6/25/04 4:27 PM Sreenivas, I don't have expertise in your domain to understand the gazillions of acronyms you're using. It seems to me that you're asking very valid questions, that is, how to best *design* a state machine that would correctly capture the desired behavior of your system. Here I can only point you to the very general guidelines regarding event granularity in Section 4.3.2 of "PSiCC" (you talk about "enhanced" signals). Maybe I sound like a broken record, but choosing the right events is absolutely critical if you want to produce good state machine. I don't get your remarks about inheritance in the second of your postings. Do you mean behavioral inheritance (state nesting), or inheritance entire state machines? --Miro ------------------------------------------------------------------------------ Sreenivas posted 6/25/04 7:14 PM Dr. Samek, Please let me restate my problem in a more generic way. -- Consider the following state hierarchies in my HSM: -- b c, d (c & d are sub-states of b) -- n o, p (o & p are sub-states of n) -- b & n are peers (i.e., one is not a sub-state of the other), but are linked by transitions. -- Now consider this hierarchy. -- bn c, d, o, p -- At any given time the object running this state machine can be in one of the following states: -- 1. b or one of b’s sub-states 2. n or one of n’s sub-states 3. bn or a subset of a combination of b’s and n’s sub-states -- It is this 3rd state (bn) that I’m having trouble representing in the HSM. In theory bn is a peer of b & n. -- If I represent bn as a separate state alongside b & n, I will have to replicate all the sub-states (c, d, o & p) inside bn. -- If I use multiple inheritance (behavioral inheritance as described in Section 6.3.2 of PSiCC) and derive bn from b & n, I still would have to replicate c, d, o & p inside bn. (I didn’t find UML notation for MI in PSiCC). -- bn is not orthogonal to b or n because there are lots of transitions between the three of them. -- Please advise. -- Thanks, Sreenivas ------------------------------------------------------------------------------ miro (Moderator) posted 6/26/04 1:05 AM Sreenivas, As you write "bn or a subset of a combination of b’s *and* n’s sub-states", so it seems to me that b and n are AND-states (see Section 2.2.3 in "PSiCC"). In UML, you model such situation with orthogonal regions. In QF, you need to use the "Orthogonal Component" state pattern (see Section 5.4 in "PSiCC"). Please note that the situations (1: b-active) and (2: n-active) could be modeled easily by putting the inactive orthogonal component in an "inactive" state. --Miro ------------------------------------------------------------------------------ Sreenivas posted 6/27/04 8:45 PM Dr. Samek, Thanks for pointing me in the right direction! Sreenivas Michael ------------------------------------------------------------------------------ Rushton posted 6/29/04 10:35 PM Ooops, sorry posted it as a new topic.. Hi, I have a system consisting of a Container (QActive) which dispatches events to it components (QHsm). The event has an id for the appropriate component in it. The problem is timer events using QTimer, there is no way to specify which component the ttimer event should be dispatched to. I could dispatch it to all components, but that does'nt work with multiple components waiting for a timeout. I need 1. A timer id 2. To be able to specify the event rather than signal ,in QTimer::firein Help! ------------------------------------------------------------------------------ miro (Moderator) posted 6/30/04 4:21 PM Michael, I can relate to your pain. I've run into the same kind of problem a few months ago. I'm addressing this shortcoming of timers more comprehensively in the new version of QF. For now, however, I've prepared a modified QTimer class that you can download from http://www.quantum-leaps.com/qf.code/qf27_cpp_qtimer.ZIP. This version of QTimer *derives* from QEvent instead of just containing a QEvent. This lets you *specialize* QTimers for your needs, say, by adding an ID, like this: struct MyTimer : public QTimer { unsigned char myId; // ...}; So, when you receive a timeout event, you can downcast the event to MyTimer and look into myId. I hope you get a picture.. . Good luck, --Miro P.S. Perhaps a better place for this posting would be the "State Machine and QF Implementation" thread, or the "Help Desk" thread. ------------------------------------------------------------------------------ Michael Rushton posted 6/30/04 7:57 PM Hi, Thanks for that. As I'm running on windows CE i did the following hacks. 1. Replace the queue to use Win32 thread message queues. 2. Replaced QTimer to use Win32 ::SetTimer/::KillTimer 3. Add myTimerId field to QEvent 4. Intercept WM_TIMER messages and place its id in QEvent.myTimerId 5. In my container class I dispatch all events to all components (except Entry, Exit, Empty) I was'nt sure if I'd designed my SM correctly, hence posting it here ------------------------------------------------------------------------------ miro (Moderator) posted 6/30/04 10:10 PM ------------------------------------------------------------------------------ The following thread has been moved here: --Miro Author: John O Topic: Reaction-in-state vs. Self-Transition problem posted 6/30/04 8:40 PM ------------------------------------------------------------------------------ Hello, I recently ran into an odd problem with Statecharts, where I knew EXACTLY how the code should look (if implemented with the HSM engine provided in PSiCC), but I can't figure out how to describe it in a UML statechart properly. Here is the issue: Assume an HSM is currently in state S1. ------- | S1 | ------- Also assume that on reception of event ev1 in S1, I want some code to execute, after which a guard condition is evaluated, and if TRUE takes a transition to S2, and if FALSE, stays in S1. Previously, I would do this with a condition check, like the following: ------------- [else] | | V ev1/ | ------ foo(); --- [flag==1] ------ | S1 |-------->|C|-------------->| S2 | ------ --- ------ On reception of ev1, I'd execute foo(). Then based on the state of flag, I could either go to S2, or back to S1. The problem with this is that the exit/entry conditions for S1 are executed each time through, and this can cause some potential problems. But I can't figure out how to rectify this situation. I came up with another way to do it with guard conditions, which looks like the following: ----------- ev1[flag==1]/ ---------- | S1 | foo(); | S2 | | ev1/ |-------------->| | | foo() | ---------- ----------- ...but this also is questionable, because I don't know what the order of event evaluation will end up being. The C code for this thing is so simple and clean: ... switch(e->sig) { case Q_ENTRY_SIG: entryActions(); return(0); case Q_EXIT_SIG: exitActions(); return(0); case S1: foo(); if (flag==1) Q_TRAN(S2); return(0); } Is there something fundamentally wrong with this? Why can't I figure out a simple way to draw this in UML? Hopeful for an answer... John O. ------------------------------------------------------------------------------ miro (Moderator) posted 6/30/04 10:10 PM John, I know exactly what you're talking about because I run into this problem all the time. Actually, I even wrote about it in my ESP article from August 2000: "In our experience with [GPS] receiver applications we frequently encountered the following situation: in response to a given event, we wished to perform an action (for example, update a digital filter) and then—depending on the state of the filter—potentially take a (conditional) state transition. We did not want to treat the filter update as part of the guard condition because this would add a side effect to the guard (typically a bad idea). The only alternative is to treat the filter update as an action. To this day I'm not absolutely sure how to represent this frequent behavior in a UML-compliant form (and believe me, I've searched all possible resources and asked around). At the risk of going into a "UML jail", here is what I do these days: /----\ | s1 | \----/ | | EVT/foo();... | v O <-- dynamic choice point | | [flag]/... | v /----\ | s2 | \----/ In other words, I use a dynamic choice point (see UML 1.4, page 3-153, Figure 3-81). The action foo() might modify the flag, which is subsequently used as a guard (this part is probably OK). The questionable thing is that the guards on the transition segments leaving the dynamic choice point don't always complement each other. In other words, sometimes the transition doesn't complete, in which case you end up executing only the original action foo(). (So you have only an *internal* transition, without entry and exit actions). Please note, that a complementary to [flag] transition from the dynamic choice point back to "s1" would be a self-transition, which is not what you want to model. As I said, I'm not sure if this notation would be interpreted this way by UML tools, or even if it will not be flagged as a "malformed" state machine. Also, I don't see dynamic choice points in the UML 2.0 Draft, so maybe this notation will not be legitimate in the future... Cheers, --Miro ------------------------------------------------------------------------------ Nick posted 10/6/04 9:27 PM Dr Samek, I am currently trying to port a program I wrote in C for DOS to C++ for WinCE. After reading your book, I thought the QF framework would be perfect. It is a real-time machine control program with a gui interface. Currently, I am thinking I need 4-5 QActive objects. The control logic, display( dialogs, etc), hardware ( custom I/O drivers ), logging ( troubleshooting and diagnostics ), and possibly interrupt handling. Is this how a project of this sort should be divided? In other posts, you state that QActive objects should be used to differentiate between priority levels, which I think fits here. Comments? Also, for my control logic, the machine consists of motors, sensors, and other assemblies ( ie Rotational Axis, Travers Axis ). I intend to make these Component Fsms and Hsms ( modeled after the alarm example). Comments? Lastly, concerning the Component State Pattern, I'm a little confused on how to handle all of my events. Do I need to 'subscribe' to all of my components events in the 'initial' of my control object? Does this then also mean that I need to catch all of the events and dispatch them indiviually there ( in some state of the control object )? void Machine::initial( const QEvent* e ){ QF::subscribe( this, Motor1_sig1 ); QF::subscribe( this, Motor1_sig2 ); QF::subscribe( this, Motor1_sig3 ); QF::subscribe( this, Motor1_sig4 ); QF::subscribe( this, Sensor1_sig1 ); QF::subscribe( this, Sensor1_sig2 ); QF::subscribe( this, Sensor1_sig3 ); QF::subscribe( this, Sensor1_sig4 ); ... Q_INIT( &Machine::Operational );}QSTATE Motor::Operational( const QEvent* e ){ switch( e->sig ) { case Motor1_sig1: case Motor1_sig2: case Motor1_sig3: case Motor1_sig4: Motor1.dispatch( e ); break; case Sensor1_sig1: case Sensor1_sig2: case Sensor1_sig3: case Sensor1_sig4: Sensor1.dispatch( e ); break; ... }} Is that how it's supposed to work? Is there any other way to avoid having the Machine object know about every signal concerning the Component? Any help is greatly appreciated. Thanks, Nick ------------------------------------------------------------------------------ miro (Moderator) posted 10/9/04 0:07 AM Nick, The 4-5 active objects you're contemplating sounds reasonable to me, although "custom I/O drivers" and "interrupt handling" don't sound like good candidates for active objects. It sounds that you intend to further break down the "control logic" into orthogonal components "sensors" and "motors". While this might be OK, the question is if all can be served by a common priority level (one event queue of the container active object). If not, maybe "sensors" need to be separated from "motors". Regarding the signals to components, the direct application of the "Orthogonal Component" pattern from Chapter 5 in "PSiCC" would be indeed as you describe. Other options are to store the component ID in a specialized event (a base for derivation of all component events), and put dispatching events in a highest-level superstate of the container. Here is some pseudocode: struct CompEvt : public QEvent { QSignal mySig; // signal for subcomponent unsigned char myID; // ID of the recipient }; //... QSTATE Motor::Operational( const QEvent* e ) { switch( e->sig ) { // ... case COMP_SIG: { // event for a component QEvent pe; // create an event "on-the-fly" pe.sig = ((CompEvt const *)e)->sig; // container stores pointers to all components // in the myComp[] array... myComp[((CompEvt const *)e)->myId]->dispatch(&pe); return 0; } // ... } return (QSTATE)&QHsm::top; // highest-level state } The other option could be to override the QActive::run() method and dispatch an event to all orthogonal components in turn (this is how tools generate code for orthogonal regions). Here is some pseudocode: void Motor::run() { for (;;) { // get event e from the queue dispatch(e); // dispatch to the container state machine myMotors.dispatch(e); // dispatch to motors component mySensors.dispatch(e); // dispatch to sensors component } } Depending on the complexity of your application, however, I'd recommend to stick to the simplest solution, which is probably the "Orthogonal Component". --Miro ------------------------------------------------------------------------------ Jonathan Kaye posted 10/27/04 3:26 AM This is in response to Nick's issue (post prior to last one), not John's. I would handle this somewhat differently, but it would require extending the basic design of the QHsm (I think along the lines of what Miro suggests in the book, but I don't quite remember now). I would have the foo() method post a new event (for flag being set) if it is determined that a transition should occur. So the transition trigger out of S1 would be the flag-being-set event, whereas the trigger for executing foo() is whatever EV it originally was. -jonathan http://www.FlashSim.com ------------------------------------------------------------------------------ Markus posted 11/16/04 12:46 AM this is in response to John's issue. If you want to get it in a UML statechart I would suggest following change: you have to split s1 in a superstate ss1 with the entry and exit actions and substate sub1 with 2 transitions: if flag is false: an self-transition with action foo() (which is a internal transition for the superstate so no exit and entry actions are done) if flag is true: a transition to s2 and action foo() ------------------------------------------------------------------------------ Markus posted 11/16/04 1:07 PM It sounds like here was already a discussion about so-called completion transitions (or transitions without event-triggering) but I can't find a thread. I'm very interested if someybody knows a good solution to have the feature of transitions in HSM without event-triggering. Thanks --Markus ------------------------------------------------------------------------------ Nils Thorell posted 11/18/04 8:40 AM What about table driven state machines? Each submachine in a separate table. It gives you a better picture of the entire machine at one glance. What are the drawbacks? ############################################################################## Topic: Help Desk Author: Miro Samek (Moderator) posted 1/12/04 4:58 AM This discussion thread is intended for posting requests for immediate help to the Quantum Leaps Community. This first positng is an archived thread moved over from the previous quantum-leaps.com discussion forum. ------------------------------------------------------------------------------ Virgil Farnam posted 2/9/04 2:40 AM I am using the "C+" version of QF. The application runs under VxWorks. I think I need to use QEpool, but I don't understand when and where? Any guideance would be of help. Thanks, vlf ------------------------------------------------------------------------------ miro (Moderator) posted 2/9/04 4:40 PM Hi Virgil, QF uses event pools for dynamically allocating events that are then passed around. Due to the know problems with the traditional heap, QF carefully avoids using malloc() or free() (new or delete) and uses fixed-size heaps instead. These fixed-size heaps specialized to hold events are called in QF event pools. QF provides a thread-safe, quite optimal implementation of event pool encapsulated as the QEPool class. Typically, you will use more than one event pool, because typically you'll have events with different sizes and it would be wasteful to use massively oversized event buffers to pass around tiny events. In the current implementation QF allows to use simultaneously up to three event pools (say, small, medium, and large). To use event pools you need to initialize them upon the startup. You achieve this by calling QFpoolInit() function, to which you must pass memory for the event pool. You must call QFpoolInit() once for every pool you'd like to use (so you can call it up to three times). At a minimum, you must call it once, otherwise QF won't be able to allocate any events. And that's it. QF will handle event allocation automatically (this happens inside the macro Q_NEW()). QF will always try to allocate an event from the smallest event-size pool available. If no events are available in this pool, or the event size is too big to allocate from any pool, QF will assert. --Miro ------------------------------------------------------------------------------ Garth posted 2/13/04 10:51 PM Porting to Unx Has anyone ported the QF software to a Unx machine? I got the software off the CD from the book and am trying to compile it on a Solaris machine, but there seems to be a lot of porting issues. I hope someone has already done the porting work. Thanks, Garth ------------------------------------------------------------------------------ miro (Moderator) posted 2/16/04 5:11 PM Garth, please check the C and C++ ports of QF to Linux available from http://www.quantum-leaps.com/qf/code.htm. Also, I'd recommend you use the updated version of the source code (QF v2.5) as your starting point for the port. This version is available from http://www.quantum-leaps.com/qf/code.htm#QFsource and is much more "Unix friendly", because it uses consistently only lower-case file names and the Unix End-Of-Line convention. --Miro ------------------------------------------------------------------------------ Steve Tether posted 5/14/04 11:20 PM Hi, Miro. There was a slight hitch when I tried to compile the Linux code linux.cpp for QP 2.5 using GCC 3.2.1. The global function run() whose address is passed to pthread_create() needs to be referred to as "::run" because it is hidden by QActive::run(). This hiding is according to the rules but apparently GCC 2 didn't enforce it. ------------------------------------------------------------------------------ Steve Tether posted 5/14/04 11:30 PM Oh, yes, one more thing. qf_linux.a should be named libqf_linux.a in order to conform to the Unix linker convention that "-lfoo" means search libfoo.a (or libfoo.so). ------------------------------------------------------------------------------ John O posted 5/25/04 5:03 PM QF Event Queue problem Hello Dr. Samek/QF fans, I have been using the QF for over a year now in a Linux-based environment with success. However, I have recently stumbled into an odd problem. I have been adding features to my original project (which, as I said, ran on Linux with the foreground/background single-threaded version of the frameworks). I have six active objects in the system. The feature additions to my project recently caused the total number of messages to increase significantly (by a factor of 40 or so). I increased my pools (small event = 16 bytes, medium event = 256 bytes, large event = 4096 bytes) so there is space for 10,000 medium events, which should be plenty. I ran the system for several hours and confirmed (by looking at the low-water marks of the event pools) that I had plenty of headroom left. Then, I began more extended testing over several days. What I noticed was that the QF was asserting after a while, indicating that it tried to create an event and had no pool space left. I've been able to re-create it with some success. It seems as though after some point in time, new events that are created in the system and published, but don't make it to all of their subscribers. Specifically, there is one event (call it eventFoo) that is published once every ten seconds or so, and comes from the medium event pool. Active Object "foo" (call it activeObjectFoo) subscribes to this event, but doesn't ever seem to get the event dispatched to it successfully (again, the glitch only seems to happen after hours and hours of running...it gets the events just fine in the beginning). By examining the high/low water marks, I can see that the medium event pool's low water mark begins creeping lower and lower, towards zero, and the activeObjectFoo's event queue slowly increases in its size (at the same rate that the medium event queue's water mark is decreasing). Eventually, the medium event pool has no events left, and the system asserts. I am trying to figure out what could possibly cause this behavior. The QF still knows about activeObjectFoo, because it is apparently dispatching events to its event queue. However, activeObjectFoo seems to never get the events, and thus can never be annihalated. The odd thing is that other events are going through the system just fine. For example, activeObjectBar gets events dispatched to it without a problem, including medium events (I think...I should double check that med events are going to activeObjectBar). I'm really stumped with this one, and need to figure it out in the near future. Does this ring a bell with anyone? What other explanations could there be as to why an event would get created and allocated from an event pool, then dispatched to a particular active object but NEVER handled and thus never annihalated....all within the same thread of execution where other objects are getting their events just fine.... Awaiting some guidance...thanks in advance! John O. ------------------------------------------------------------------------------ whoie posted 5/25/04 7:42 PM What priority is activeObjectFoo? Is it getting time to run, or are higher priority active objects preventing it from ever running? I know that sounds obvious, and perhaps you have already checked, but that's what springs to mind initially. ------------------------------------------------------------------------------ John O posted 5/25/04 11:10 PM Hello, Yeah, I already looked into this, and the priorities look fine...activeObjectFoo has the second highest priority (well, since I think the QF orders priorities in reverse, the second lowest priority...I can't remember how they order it, but it checks out). Also, I can monitor the number of events coming into the system, and there aren't a flood of events for the highest priority task that would cause the starvation like you mentioned....good thought, though. Any other ideas floating around? The ordering seems as though the events get added to the queue (through QEQueue_putFifo() ), followed by the dispatch process...could the dispatching fail somehow? Still looking for ideas here... John ------------------------------------------------------------------------------ miro (Moderator) posted 5/27/04 9:42 PM John, It seems to me that the variable pkgRdyMask is not handled correctly. (Please refer to Section 9.4.2 in “PSiCC” for the description of the foreground/background processing in QF.) I suspect that the attribute myOsEvent (me->osEvent__ in C) gets corrupted after “hours and hours” of running. (This attribute of your active object “foo” should be a always set to 1 << (p-1), where p is the QF priority of active object “foo”.) To verify this hypothesis,you could set a watchpoint for the myOsEvent attribute which should stop your application when myOsEvent gets changed. --Miro ------------------------------------------------------------------------------ John O posted 6/2/04 7:39 PM Dr. Samek to the rescue... Thanks so much for your insight. I believe I have found the problem. As soon as you mentioned the pkgReadyMask, I recalled a while back that I had modified the basic foreground/background QF. Instead of constantly checking the pkgReadyList, which made the applications use all the resources on the machine (again, I'm running on Linux, with my quanta set to 10 mS), I modified it slightly so that it used a pthread condition variable. Thus, if there are no events in any queues, the application thread goes to sleep through a call to pthread_cond_wait. Upon publication of an event, the QEQueue signal macro was modified so that instead of simply setting a bit in the pkgReadyMask, it also executes a pthread_cond_signal call to wake up the sleeping thread and process the new event. This works great, and requires you to have a mutex to lock and unlock access to the condition variable. Well, I had the mutex properly being used for the condition variable, but I was unlocking the mutex that protects access to pkgReadyMask right BEFORE I was setting the bit in the pkgReadyMask instead of after it. Thus, it was possible for multiple threads to be screwing with the pkgReadyMask and potentially muck things up..... I should also clarify that, though I was running foreground/background, this was only for the main application thread. I did have several other threads that were responsible for watching for asynchronous input from other clients. These other input threads are the ones that I believe were publishing events and stomping on the pkgReadyMask when they shouldn't have been. It all seems to be working now....I'm continuing my longer term testing to be sure, but I wanted to get this info out there in case others were seeing a similar situation. Thanks again for a great framework Dr. Samek. I have wholeheartedly recommended it to many individuals who were looking for a lightweight framework to support their development. Regards, John Orlando ------------------------------------------------------------------------------ miro (Moderator) posted 6/03/04 9:35 AM John, I'm glad to hear that you've come to the bottom of the problem. It seems to methat you're using a significantly modyfied "foreground/background" port of QF to Linux. If you're employing POSIX-threads anyway, you might consider the p-thread QF port. This port doesn't necessary require running under the SCHED_FIFO policy (which in turn requires superuser privileges). You can simply not switch to this scheduling policy (so all your threads will run at the same priority). I believe that the p-thread QF port to Linix handles correctly the condition varialbe and the mutex, as you just learned the hard way. I've moved your original discussion thread to the "Help Desk" thread for reasons described in the "Discussion Board Etiquette". Best regards, --Miro ------------------------------------------------------------------------------ Jouni posted 6/4/04 10:47 AM Hi! I am coding statecharts in win32 application. I am using the same dialog based style as in the PSICC book. But I did get troubles with the edit controls because these controls send WM_COMMAND messages to the main dialog. I quess these WM_COMMAND messages were EN_CHANGE or BN_CLIKED or something like that. In the dialog procedure these WM_COMMAND messages were dispatched to the application and then my program crashed. So I did a filter to the dialog procedure, where I ignore those messages and do not dispatch them to the application. I noticed that there is no such filter in the examples that PSICC book provides. Actually the Orthogonal component state pattern example crashed once when I used it. Maybe this is the reason or am I chasing chosts? Regards Jouni ------------------------------------------------------------------------------ miro (Moderator) posted 6/7/04 4:28 PM Hi Jouni, You don't mention how exactly your application crashes, but I suppose that the reason is that some of the signals dispatched to the state machine overlap numerically the values of the reserved signals (0 through 3). Obviously, when this happens, the state machine attempts to execute entry, exit, or initial transition completely out of context and crashes. As to handling of the WM_COMMAND, I'd always recommend remapping it to finer granularity signals that actually mean something. As I describe in Section 4.3.2 of "PSiCC", WM_COMMAND is a typical example of a "kitchen sink" message with too coarse granularity. For compactness, I haven't provided a nice and explicit filter of the Windows messages in my Windows examples (which all handle just a handful of events). However, for any more serious GUI application, I'd highly recommend providing such a filter--exactly as you do. Such a filter (or pre-processor) should very clearly avoid overlapping the reserved signals, as I mentioned above. Best regards, --Miro ------------------------------------------------------------------------------ miro (Moderator) posted 9/21/04 4:42 PM Topic: ho to use the framework in building MFC apps ? posted: 9/18/04 1:18 AM ------------------------------------------------------------------------------ Hello. I enjoyed reading your book : Practical Statecharts in C++. We develop pc based test systems for manufacturing industry. I am interested in utilizing your QHSM framework for my future applications. I have downloaded the updated source code from your website. I am eager to get started with the framework by building a "bare bones" MFC "dialog based" application with VC++ 6.0. However, I get the errors similar to this one: Qf_win32D.lib(Qequeue.obj) : error LNK2001: unresolved external symbol _onAssert__ Where, Qf_win32D.lib is the "debug" version of your framework. I had compiled the lib files prior to using in this project. I notice that this error goes away when I copy and paste from one of your examples : extern "C" void onAssert__(char const *file, unsigned line) { fprintf(stderr, "Assertion failed in %s, line %d", file, line); exit(-1);} So, the bottom line is, what is the "recommended" way that I can use this QF framework in a MFC application? For example my QHsm derived class looks like : class CMicrowaveOven : public QHsm { public: CMicrowaveOven() : QHsm((QPseudoState)&CMicrowaveOven::initial) {} protected: void initial(QEvent const *e); // initial pseudostate QSTATE s0(QEvent const *e); // state-handler QSTATE s1(QEvent const *e); // state-handler QSTATE s11(QEvent const *e); // state-handler QSTATE s2(QEvent const *e); // state-handler QSTATE s21(QEvent const *e); // state-handler QSTATE s211(QEvent const *e); // state-handler private: // extended state variables... int m_iSomeVariable; }; Thanks. Madhav Shidhaye ------------------------------------------------------------------------------ miro (Moderator) posted 9/21/04 4:43 PM Madhav, I've moved your posting here to reduce the number of threads in this discussion forum. Using the framework with MFC is no much different from using it directly with low-level Win32 API, as demonstrated in the book (see the Calculator example). Actually, you use only the hierarchical state machine engine (the QHsm class), because MFC already is an event-driven framework. I have supplied only the raw Win32 example in the book, because MFC (as virtually all GUI programming environments today) is based on the event-action paradigm, which is not quite compatible with state machines. (My CUJ article "Who Moved My State?" describes perils of the event-action paradigm. The article is available online from http://www.quantum-leaps.com/writings.cuj/samek0304.pdf.) In case of MFC, the mapping from events to code occurs through "message maps". With state machines, you need to defeat the whole idea of "message map", because you end up mapping all events to QHsm::dispatch() (possibly you could massage the Windows events a little before dispatching, just as it is done in the Calculator example). As to the onAssert__() function, again the Calculator example provides an implementation which pops up a dialog box. This function is invoked in case of assertion failure, which indicates a serious error in the application (please check Section 8.2.1 in "PSiCC"). --Miro ------------------------------------------------------------------------------ P Montgomery posted 9/22/04 7:20 PM QF 2.5 distribution uses Unix EOL convention. Unfortunately, making modifications to the distributed code in VC++ v6.0 causes an inconsistent set of EOL conventions to be used. I have tried to find the setting in VC++ to make it adopt the Unix EOL convention or to keep the existing EOL convention in use (as emacs does). Are you aware of how to set VC++ environment to handle this annoying cross platform sharing issue? I have drawn a blank so far. Thanks, PYM ------------------------------------------------------------------------------ miro (Moderator) posted 10/9/04 1:26 AM Paul, I don't know how to enforce Unix-EOL in the Visual Studio :-( However, http://www.quantum-leaps.com/resources/goodies.htm contains a "CleanCode" utility that I use to clean up the code before a build. Among others, CleanCode enforces Unix-EOL, replaces tabs with spaces, and removes trailing blanks. CleanCode scans directories recursively. It is free for download and is available in source code for customizations. --Miro ############################################################################## Author: miro Topic: Hierarchical State Machines in C# posted: 4/18/03 0:03 AM ------------------------------------------------------------------------------ How can you implement Hierarchical State Machines (HSMs) in C#? ------------------------------------------------------------------------------ Louis posted 8/11/03 11:03 PM I thought you already had Rainer Hessmer's C# implementation of QF on this web site. As I recall, he did not implement active objects, but had working code for HSMs. (It's a start :) ############################################################################## Author: Peter Kraak Topic: Python, anyone? posted: 6/4/03 4:30 AM ------------------------------------------------------------------------------ Any python nuts out there who would be interested in collaborating on a python port (straight conversion from C++ maybe)? Or discussing the idea of defining a QP syntax and implementing it in C with python wrappers? ------------------------------------------------------------------------------ Rodney A Ludwig posted 8/18/03 6:46 PM I will be implementing via SWIG a dll that has access to the HSM functions for python. Let me know if you feel this is related to your ideas. ############################################################################## Author: fschwiet Topic: Software for drawing Hierchical FSMs/ UML diagrams posted: 9/15/03 4:44 AM ------------------------------------------------------------------------------ I reviewed some UML diagramming software, and couldn't find anything that supports hierchical state machines. I looke at Microsoft's Visio, and Pacestar's UML diagrammer. Does anyone have any software they recommend for drawing hierchical state machines? If your answer is LatEx, please include samples and whatever external libraries you use. I'm hoping for something windows compatible. ------------------------------------------------------------------------------ Gavin Haentjens posted 9/15/03 8:53 PM The CD included with the book (Practical Statechars in C/C++) contains a Visio stencil for drawing hierarchical statecharts (in the "Resources" section of the disc). -Gavin ------------------------------------------------------------------------------ miro posted 9/16/03 5:41 PM Virtually any drawing tool should be capable of creating UML diagrams, including hierarchical state machines. As Gavin points out, I've used Visio to draw all diagrams in my book (the Visio stencil that I used is available from the CD-ROM accompanying my book, and also online from http://www.quantum-leaps.com/resources/goodies.htm.) However, drawing UML state diagrams is very different from being able to analyze the diagrams for correctness and synthesizing code from them. I have enumerated a few leading CASE tools capable of doing that in my article "Quantum Programming for Embedded Systems" available online at http://www.quantum-leaps.com/writings.cuj/Quantum_Programming.pdf. Also, I've received many letters informing me of other tools for state machines. Some examples include: * xjCharts (http://www.xjtek.com/products/) * SmartState (http://www.apesoft.net/ss/) * Liero (http://www.imatix.com/html/libero/) * Trice (http://www.protos.de/Products/products_E.html) to name just a few. I cannot comment on these tools, since I haven't used them. I've used some other such tools, however, and my experience has always been that ultimately you want to have full control over the synthesizing code. (Nowhere is it more true than in deeply embedded applications.) A tool always keeps you a step away from the code, which, by the way, is quite easy to generate manually. The quantum-leaps.com website, my book, conference papers, and my CUJ column describe how to do just that--write clean, efficient, and highly maintainable state machine code. If you are interested in this approach, please refer to the sources I enumerated, most of which are available online from quantum-leaps.com. A good starting point are excerpts from my book available online (http://www.quantum-leaps.com/writings.book/Practical_Statecharts_Excerpts.pdf --Miro (miro@quantum-leaps.com) ############################################################################## Author: Jinsong Topic: QF on Win XP posted 9/12/03 10:44 AM ------------------------------------------------------------------------------ Hi, I would like to know if QF-windows is compatible with windows XP. though, in theory, it can work because QF-windows is based on win32 API. Thanks in advance. ------------------------------------------------------------------------------ Henry Choi posted 9/18/03 4:57 PM Hi Jinsong, I have been developing QF and QF apps on my WinXP laptop since I learned about QF last year. The examples contained in the book CD will run out of the box on your command prompt, for example. Hope this helps. http://www.quantum-leaps.com/qf/native.htm QF+ ############################################################################## Author: Gavin Jacksons Topic: QF and Delphi posted: 9/30/03 10:29 PM ------------------------------------------------------------------------------ How would one go about implementing a HSM using the QF under Windows using Delphi. Has anyone do it and if so, how did you go about doing it? What would be the best way to use the message handling built into Delphi? ############################################################################## Author: Tad Ashlock Topic: Quantum Lint? posted 10/1/03 4:15 PM ------------------------------------------------------------------------------ On Miro's home page (www.quantum-leaps.com), he invites us to help advance the qp cause by (among other things): Explore the possibilities of implementing a quantum programming language, perhaps by modifying an open-source C or C++ compiler. Although this approach sounds good, I doubt that I'd ever use a quantum programming language. Being an embedded software developer, I have to develop for a number of different processors and platforms. Many times, I don't get much of a choice in compilers or tools. But something that I think would be useful is a "Quantum Lint". This would statically check for common qf and qp mistakes in C/C++ (or even other languages, too). It could be run during the build process just like "lint" and would do things like: Give an error on Q_TRAN being passed an identifier other than a QState. Give a warning on Q_TRAN_DYN being passed the direct name of a QState. (Could be optimized via Q_TRAN.) etc. I'm sure there's other errors and warnings that would be useful to check for. Also, I don't have any experience implementing this sort of tool, so if anybody has advice please speak up. My first inclination is to implement it in lex/yacc (actually, flex/bison) just because these tools were designed for this sort of thing. But before starting, I'd like to hear what others would want from this tool. So what do you think? Tad ------------------------------------------------------------------------------ miro posted 10/3/03 8:52 PM Hi Tad, I believe that a "quantum lint" would be a very good first step towards a "quantum programming language". The main porblem is that such a tool would need to have very detailed "knowledge" of the C/C++ syntax, which will duplicate the functionality of the compiler. Alternatively, one could develop a "q-front compiler", just as first C++ implementations used c-front to compile C++ to C. A "q-front" could be much simpler, because it would rely on the C/C++ compiler for parsing. --Miro ############################################################################## Author: Lawrence R. Sweet Topic: QF under QNX Neutrino posted: 10/14/03 6:19 PM ------------------------------------------------------------------------------ Has anyone ported QF to Neutrino yet? ############################################################################## Author Topic: QF V3 ? Joerg Krein posted 10/31/03 12:00 AM ------------------------------------------------------------------------------ Hi, in the download section I read something about a new QF version: 'This section describes the latest version of qF (V3.x).' You can download a new version of QTimer there. I bought the book with version 2.2 of QF (ISBN: 1-800-788-3123). Does that mean I have to buy the book again, to get the latest version of the QF? What about the errats? Do you supply patches for the code? Regards, Joerg ------------------------------------------------------------------------------ miro (Moderator) posted 11/5/03 4:15 AM Hi Joerg, As the book publishing cycle goes, it is almost impossible to keep adapting the book to the evolving code. I've tried to do it once (between the first and the second printing of the book) and shot myself in the foot by introducing a bug (which I had to fix in the errata, see http://www.quantum-leaps.com/ writings/book.htm#Errata). Consequently, I have no plans to make any modifications to the published code (not that I really could). Please note, however, that the published code has been thoroughly tested and, in fact, I haven't found or heard of any evident bugs in it yet (except of the one just mentioned). Of course, now that a few thousand copies of the book are in circulation the code is exercised in very diverse environments and some perhaps unexpected behaviors get discovered. In addition to hundreds of e-mails that I received from readers, my own experience with QF has grown considerably since the code was first written (now over two years ago). So, naturally I want to improve and evolve the framework. I don't know yet when the complete QF v3.x will be ready or how I'll make it available to others, but I hope that not only QF V3.x but 4.x and higher will eventually emerge. Depending on the demand, maybe I'll decide to write a second edition of "Practical Statecharts in C/C++". Such next edition would be ideal place for the next generation QF. For now, however, please keep checking quantum-leaps.com from time to time. Best regards, --Miro (miro@quantum-leaps.com) ############################################################################## Author Topic: QFsm and QHsm port to ActionScript 1 & 2 Jonathan Kaye posted 11/17/03 8:53 PM ------------------------------------------------------------------------------ I wanted to let people know that Miro has ported his QFsm and QHsm to ActionScript 1 & 2 (Macromedia Flash MX and Flash MX 2004). I helped tweak it a bit and make some more examples. The code is available at http://www.FlashSim.com/newsletter/samekengines.zip with info about this at http://www.FlashSim.com/newsletter/v1n6.html you can direct comments to our FlashSim discussion board (http://flashsim.infopop.cc). thanks, Miro! -jonathan http://www.FlashSim.com ############################################################################## Author Topic: States inside States with Visio Brian O'Shea posted 11/6/03 10:40 PM ------------------------------------------------------------------------------ I am using Visio 2002 SR 1, and I have the templates that Miro used to put together the diagrams in the book. I may be having a serious stupid attack, but I can't get the states to layer on top of each other. When I drag one state onto another, it snaps out of the way. It would save me some time if someone who knew Visio could help out a Visio novice... Thanks! miro (Moderator) posted 11/18/03 7:48 PM ------------------------------------------------------------------------------ Hi, just yesterday I installed Microsoft Visio 2003 and had a chance to try out the stencil I used before in my book. I opened the stencil from the menu File/Shapes/Open Stencil. The old stencil opened correctly and I could draw states within states without any problems. I also could save the stencil in the new Visio format (breaking backward compatibility with the older versions of Visio, of course). --Miro (miro@quantum-leaps.com) ############################################################################## Author Topic: Overview of qF 3.0? DeanONH posted 12/28/03 8:50 PM ------------------------------------------------------------------------------ I saw a reference to qF 3.0 on the qF webpage. Can you give us an overview of qF 3.0? TIA, Dean miro (Moderator) posted 12/30/03 7:44 PM ------------------------------------------------------------------------------ The purpose of the recently announced QF v2.5.0 release is to offer the readers of my book "Practical Statecharts in C/C++" a common version of the framework source code with all the bug fixes mentioned in the Errata (http://www.quantum-leaps.com/writings/book.htm#Errata). This version is 100 percent compatible with all the examples scattered throughout the text and all printings of the book (some minor changes were made between the first printing and subsequent ones). Currently, QF v2.5.0 doesn't have any known bugs. However, should new bugs be discovered, I'll update this online distribution. I'll keep numbering these book-compatible versions of QF as major revision 2 (QF v2.x.y). I'll also provide the requested revision history (I'm currently working on it, but my days have only 24 hours). As to the next major revision of QF (QF v3.x), this version will NOT necessarily be fully compatible with the book. Obviously, the main ideas remain the same (HSM, behavioral inheritance, active objects, publish-subscribe event delivery, event queues, event pools, timers, and so on). However, some policies, implementation techniques, and algorithms in QF v3.x will be different from these published in the book. QF 3.x (and subsequent versions) will reflect the experience with QF accumulated over the 2 years since the code for the book was written, as well as countless suggestions from QF users. QF 3.x will come with the updated manual. Just as the book-version of QF (QF v2.x), QF v3.x is intended to be used in conjunction with an RTOS or standalone (in the foreground/background mode). I'll probably offer QF v3.x at a small price (comparable with the price of the book). Finally, in planning is also a fully standalone version of QF (QF+), which would include a tiny, pre-emptive, deterministic kernel and would not require any underlying ROTS. This version would be based on QF v3.x, but will be optimized for concrete microprocessors. It will be offered together with evaluation boards, all development tools (GNU based), startup code, flash-based boot-loader, debugging interface (inexpensive JTAG probes), event-driven device drivers, documentation, support, and so on. I believe that QF+ will address a growing need in the embedded software community for inexpensive, comprehensive event-driven environments for higher-end 8-bit, 16-bit, and lower-end 32-bit platforms. The first planned version of QF+ will be for the ARM7TDMI core, which is rapidly becoming an industry standard. Evaluation versions of QF+ will be available for x86 (real and protected mode). QF+ is planned to be royalty-free and will be available commercially at prices comparable to other royalty-free RTOSes (such as MicroC/OS-II). --Miro (miro@quantum-leaps.com) ############################################################################## Author Topic: Generating Code for Embedded Apps Torsten Kuenstler posted 12/9/03 10:40 AM ------------------------------------------------------------------------------ Hello Everybody, I'm studying Computer Science and to become a bachelor in CS I have to do some writings that in Germany we call Diplom. For this, I will invent a Code Generator. Based on QF this will Generate Code from UML to C+ for a MC. This MC will be the C167 from Infinion. So, what I ask for is: Does anybody have experiences or ideas? Regards, Torsten miro (Moderator) posted 12/11/03 6:59 PM ------------------------------------------------------------------------------ Hi Torsten, Many commercial software products capable of code synthesis from state diagrams already exist on the market. The "bigger" ones are: Rhapsody (I-Logix), Rational Real-Time (former ObjecTime toolset), BetterState (now marketed by WindRiver), visualState (IAR). Other, more lightweight tools are, for example xjCharts (www.xjtek.com/products/), Trice (www.protos.de/Spheres/Trice_E.html), and many others. You might first take a look at these tools to get an idea what's currently available. More specifically to QF version of state machines, Jonathan Kaye has a Macromedia Flash-based tool to generate ActionScript code (see his latest newsletter at www.flashsim.com/newsletter/v1n6ns1103.html). I also heard from Louis Pereira [LuisRPereira@eaton.com] that he wanted to tweak Rhapsody to generate QF code rather than the "native" I-Logix code. I guess you can contact these people directly. Good luck with your Diplomarbeit! Miro ############################################################################## Topic: QP and C# Author: Brent Arias posted 12/18/03 5:09 AM This first positng is an archived thread moved over from the previous quantum-leaps.com discussion forum. I've just learned of QP tonight, and I'm wanting to use it in C#. What am I up against? http://www.ariasamp.net ------------------------------------------------------------------------------ Mountain Bikin Guy posted 12/18/03 4:54 PM It's very easy. See http://www.hessmer.org/dev/qhsm/. I implemented the calculator example in C# and Dr. Hessmer will be making that example available thru his site in a few days. But Qhsm in C# is available now (and it is very easy to use in C#). ------------------------------------------------------------------------------ DeanONH posted 12/24/03 11:25 PM I too have just learned of qF and am impressed as to what it may offer. I ordered the Statecharts book today. I have just started working with C# & the .NET Framework. I have seen the qHSM C# port and was wondering, is there a plan to port the qF platform to C#? Now with the new hard real time version of Win CE & the .NET Framework for embedded applications, a C# port would be appropriate. I am experimenting with the C++ version and trying to make it into a .NET class assembly, but was wondering about the delegate / event handler paradigm. Thanks for such great work! ------------------------------------------------------------------------------ Mountain Bikin Guy posted 12/27/03 2:10 AM Dr. Rainer Hessmer has QF for C# well under way. He has just implemented the first example with it. See the link I posted above ------------------------------------------------------------------------------ R.Schnitz posted 2/22/04 9:42 PM When I first ran across QF in an article by Dr. Samek, I knew it was exactly the kind of solution I've needed for the last 5 years. However, before I adopt the QF into my projects, I am still trying to answer some questions. We build embedded imagery processing products on an 1GHz PIII with 512MB, C++/C#, etc. However, it seems like some of the focus and/or design constraint of QF is efficiency. What (if any) specific limitations do I suffer, e.g in terms of configurability, programmability, etc., as opposed to using a framework designed without this efficiency constraint? Any advice is greatly appreciated. ------------------------------------------------------------------------------ miro (Moderator) posted 2/24/04 6:13 PM I guess that along with quite powerful hardware you're going to use a desktop operating system, such as Microsoft Windows. While in "PSiCC" I give an example of QF port to the Win32 API, I also note that you cannot expect truly real-time performance. Perhaps more importantly, the design philosophy behind QF reflects an "embedded mindset", which is quite different from programming general-purpose computers (I write about it in my first installment of "The Embedded Angle" column, available online from http://www.quantum-leaps.com/writings.cuj/samek0302.pdf). For example, QF avoids using the heap (but doesn't limit the clients to static memory only). You might find it a little inflexible. Also, desktop environments universally offer the "event-action" paradigm to handle GUI events (I write about it in "Who Moved my State", http://www.quantum-leaps.com/writings.cuj/samek0304.pdf). In contrast QF offers state machine approach, which requires quite a different way of thinking about the problem. I also guess that you're concerned about scalability of QF. Here I would recommend treating the HSM implementation separately from the rest of the framework. I believe that the QHsm base class is very scalable. I have constructed state machines with over 130 nested states, and didn't see any signs of stressing the structure. The publish-subscribe architecture of the framework, on the other hand, puts a rather low limit on the number of active objects, for example. When you familiarize yourself with the implementation, you'll be able to easily increase this limit at some memory and performance cost. However, before you start inventing hundreds of active objects, I'd recommend you look at the "Orthogonal Component" state pattern. In fact, beyond some 200 threads all desktop systems show lousy performance. Orthogonal Component allows you to use even thousands of HSMs that all share just a few threads of execution. Another issue is sharing the resources. In the desktop system you typically don't pay much attention to sharing the heap, files, sockets, and so on. Yeah, the QF application will work (when you compile a "Multithreaded" version, which uses mutexes), but you'll have excessive blocking of active objects (see Section 8.4 in "PSiCC"). Unfortunately, I cannot comment on integration QF with the .NET framework, because I don't know .NET. Your question is a bit vague and I'm not sure that I answered it to your satisfaction. Please ask more specifically if you need more details. --Miro ############################################################################## Hierarchical State Machines and QF in ActionScript This discussion thread contains postings related to the ActionScript implementations of the Quantum Framework, which includes the implementation of Hierarchical State Machines in ActionScript. ------------------------------------------------------------------------------ Here is the archive of related postings. QFsm and QHsm port to ActionScript 1 & 2 Jonathan Kaye posted 11/17/03 8:53 PM I wanted to let people know that Miro has ported his QFsm and QHsm to ActionScript 1 & 2 (Macromedia Flash MX and Flash MX 2004). I helped tweak it a bit and make some more examples. The code is available at http://www.FlashSim.com/newsletter/samekengines.zip with info about this at http://www.FlashSim.com/newsletter/v1n6.html you can direct comments to our FlashSim discussion board (http://flashsim.infopop.cc). thanks, Miro! -jonathan ------------------------------------------------------------------------------ ActionScript and C++ code generator available Jonathan Kaye posted 1/5/04 11:36 PM Dear All, I've found when I'm teaching people how to code statecharts that people can get bogged down in detail by setting up the basic skeleton code (states, switch statements, hierarchies, etc.). Therefore, I put together a quick-and-dirty program to generate skeleton code from my own XML description. It is pretty fragile, but perhaps others will find it useful and can suggest extensions. Here is the URL: http://www.amethyst-research.com/sc2xml.html On the page I have a couple of text file examples you can use to paste into the program, then generate example code. I also have a Word file that details the elements and attributes that the program recognizes. The C++ code requires Miro Samek's engine (this is not provided). The ActionScript engines are available on my web site (see the URL for information). I'm eager to hear how people find this! -jonathan P.S. If there's any interest, I can add other target languages. Let me know what you think. http://www.FlashSim.com ############################################################################## QF and Embedded Systems This discussion thread contains postings related to Quantum Framework and embedded systems, including severly resource-constraint environments. ------------------------------------------------------------------------------ Here is the archive of related postings. ------------------------------------------------------------------------------ QF as an RTOS of the future miro posted: 4/18/03 0:02 AM How can you tightly integrate QF with schedulers to effectively replace a traditional RTOS? What are the advantages/disadvantages? ------------------------------------------------------------------------------ Peter Kraak posted 4/24/03 1:20 AM I once wrote a message based executive that had cooperative multitasking and preemption at the message level, i.e. whenever a task called any o/s call or yield() if there was a higher priority task waiting it ran. the design called for message procssing tasks that ran to completion. the beaut thing was it was all in ansi C and to port it you just needed a c compiler and provide the SysTick() call from a hardware timer. thats it. If QP (c+ version) was melded to this it would provide a simple lean shrinkwrapped solution for new small targets. When real preemption is needed eCos is probably a better host, and is open source so no royalties, but needs a mid to high end platform. ------------------------------------------------------------------------------ Teemu Karevaara posted 6/17/03 9:10 AM "Super Simple Tasker" which Robert Ward introduced in Embedded Systems Conference San Francisco 2002 (http://www.esconline.com/sf/feat_tech_cl.htm#347) seems like a perfect platform for QF. Has someone already made a port? ------------------------------------------------------------------------------ miro posted 6/17/03 5:21 PM Bingo Teemu! Robert Ward's "Super Simple Tasker" (see www.codecraftsman.com) is an ideal fit. I have a first prototype working on ARM processor (exactly EB01 evaluation board for AT91 microcontroller from Atmel). The whole preemptive tasking and scheduling requires only some 40 ARM instruction in assembly (interrupt handler), and some 20 lines of C. The prototype works like magic. SST turns the foreground/background version of QF into a fully deterministic, preemptive RTOS. The limitations of the scheduler are exactly what you want. Active objects cannot block and wait on each other, every event must be processed to completion, only higher-priority active object can preempt current RTC step. This allows to use only *one* execution stack for all active objects. This unorthodox scheduler is exceptionally higher-level language friendly. Because you don't care about the exact layout of the context stack frame (as long as all registers are saved), you can store only the registers that are clobbered by the HLL, and then let the compiler save the rest of the registers in whichever order it likes. This means that the stack consumption is much lower than traditional RTOSs. Also, the SST breaks with the endless-loop structure of tasks. A task in SST is *not* a loop, but rather a one-shot event processing. This alone is remarkable and is a consequence that SST does not need to maintain the context of the endless-loop. In summary, a "native" implementation of QF can be made much *smaller* than a traditional RTOS (both in code space, data space, and CPU usage). Yet, the resulting system works at higher level of abstraction--at the level of active objects and state machines. No direct messing with semaphores, mutexes, monitors, etc--far less possibilities of shooting yourself in the foot. The *native* QF is by far the most exciting project I'm currently involved in. Any comments? --Miro ------------------------------------------------------------------------------ Bernard Mentink posted 7/30/03 10:57 PM Can someone point me to a document that describes how SST works? I can not seem to get hold of the Author .... Many Thanks ------------------------------------------------------------------------------ Henry Choi posted 8/1/03 4:52 AM http://www.codecraftsman.com seems to work just fine for me. Miro, I too think something wonderful might come by making a completely HSM based (and strictly real-time to boot) OS, but have some concerns. Please excuse me if I am missing something obvious. 1. How would the finished product differ from the QNX microkernel approach, which seems to be based on message passing (event publishing in QF lingo)? If QNX couldn't hit the big time marketing robustness, why would QF have a easier go at it? 2. Will HSM paradigm gain wide acceptance among application developers who have been weaned on the poorer solutions? For example, RTC (Run to completion) model flies in the face of all traditional OSes (whether real-time or no) I know of and the applications written on top of them; they block for any number of reasons. Wouldn't you agree that QF forces fundamental change on the applications? Let's take the TCP write() for example, which(may) block up to a time if the TCP send queue fills up. How much change is necessary for the applications that currently block on that write()? And do we have to force the application programmers to deal with the ASSERT() sprinkled throughout QF, because they are (if they didn't know it before) really hitting against the system resource issue? Do the non-UML conversant S/W engineers who glossed over these fundamental issues have to rewrite all their applications to reap the benefits of QF? 3. Performance: As Kahan likes to say, "the fast drives out the slow even if the fast is wrong." In my previous job (Real-Time Innovations), I tried to adopt QF for the middleware product (one of whose strength was the performance) and failed because of the memcpy() hit we would have to take. Our design required overwhelming (at least for me) thought and analysis to achieve zero-copy performance in multi-threaded application. Even though QF would have drastically simplified our middleware, we opted against it because the customers demand the fastest possible performance. At least in my former world of hyperfast network applications, copying data around to publish events would have been a deadly sin. I believe the experts such as Mr. van Jacobson (of TCP congestion avoidance fame) will back me up on this, because they are trying to figure out a way to avoid ANY memcpy(), starting from the H/W! I think QF is still a great option where a few memcpy() is inconsequential. I would even wager that most applications fall in this category. But I have observed that customers choose the fast (and wrong) solution over a robust but inconsequentially slow one. However, despite these concerns, I still would like to see QF based RTOS, and would try to use it in any product I work on! ------------------------------------------------------------------------------ Paul Butler posted 8/6/03 11:22 PM I'm very curious about the SST implementations being discussed here. Is anyone planning to make source available? Or is it already and I just haven't found it? thanks, -paul ------------------------------------------------------------------------------ miro posted 8/8/03 0:17 AM I have added a new page to the QP website intended to cover the developments of the "native" QF (please see www.quantum-leaps.com/qf/native.htm). At this point this page contains just a general introduction, but I plan (time permitting) to add more information. For now, you can find there Robert Ward's ESC paper that explains his SST. The "native" QF won't use Robert's implementation, but rather will directly embed the scheduler. I have a functional version for On-Time's RTTarget-32 (www.on-time.com) that I plan to make available on the QP website. This version grew up from the foreground/background port of QF to RTTarget-32 (please note that RTTarget-32 is just a platform for doing embedded development on PC-like hardware, but it is *not* a kernel). --Miro (miro@quantum-leaps.com) ------------------------------------------------------------------------------ QF lite Bob Lee posted 11/25/03 5:35 AM I've read Practical State Charts in C/C++ and would like to use them on my current project; however, I need to reduce the QF foot print (ROM & RAM) to make it work on the 8-bit micro we are using. Is there a QF lite available? ------------------------------------------------------------------------------ miro (Moderator) posted 11/25/03 7:04 PM I've received quite a few letters from readers who tried QF on small platforms. A few readers reported that they have ported QF to Keil C for 8051 processor family. I guess, Luis Pereira from Network Technologies and Electronics Group (LuisRPereira@Eaton.com) was the most advanced in using QF under these circumstances. Generally, I believe that the basic ideas are scalable down to very small platforms. So in particular, you can fit HSM, events, timers, and so into very resource-constraint environments. From what I see, the most severe limitation is RAM, not so much the CPU cycles. To conserve RAM you should consider using only the dynamic state transitions (see "Practical Statecharts", Section 4.4.3). On very small platforms, I'd probably eliminate the whole publish-subscribe part of the QF and allow only direct messaging among active objects (via QActivePutFIFO(), QActivePutLIFO() methods). On the other hand, I believe that you need to use at least one event queue (at least one active object) and an event pool. Event queue(s) and event pool(s) allow a thread-safe communication between the interrupt-level and the task-level and you don't want to lose this benefit. On small platforms, you can make events smaller. For example, the whole QEvent can be just one byte (if you use only one event pool and one active object you need to store only the signal in QEvent. You should define QSignal to be unsigned char). Recently I've been working on a new version of QF (QF v3.0), which I plan to make freely available to the owners of my book. QF v3.0 is a little more memory-efficient than QF v2.x published in the book. Depending on the demand, I might consider releasing a special stripped-down version of QF v3.x (a "pico-QF") for very small micros. Probably, this version(s) must be platform dependent (e.g., Keil C for 8051). --Miro (miro@quantum-leaps.com) ------------------------------------------------------------------------------ Holt posted 11/26/03 2:27 AM I too just got the book and am thinking about using your methods for a project I am working on. I'm worried about the amount of RAM that is required. Can you give me an idea? I know it's tough without knowing the scope of the problem. To give you an idea I will have only one 2-level HSM with 6 superstates and at most 8 substates. I would estimate about 40 transitions between states (Just counting the number of arrows on the statechart. Maybe this isn't the best way to convey the size of the application). I am considering one of the AVRmega parts from Atmel because the tools are free and plenty of RTOS's available. At most this part has 4K of RAM. Is this going to be enough or should I just not even bother? I'm looking at an RTOS which has been ported to the AVR family. It is called FreeRTOS and can be found at www.freertos.org. It supports preemptive scheduling, message queues, and I'm thinking about trying to port QF to it. None of these decisions are set in stone, so any suggestions you may have that could save me future headaches would be much appreciated. Thanks, Holt ------------------------------------------------------------------------------ miro (Moderator) posted 12/2/03 7:41 PM Hi Holt, To give you a better idea of the RAM requirements for using the HSMs and the rest of the Quantum Framework, here is a little breakdown: -- Each instance of QHsm costs 2-function pointers (4 bytes on 8-bit micro with 64k address space). That's the whole RAM you need, if you don't use static state transitions (only dynamic transitions, see Section 4.4.3 in "Practical Statecharts"). The state handlers are just functions that go into ROM. -- The QHsm class has been specifically designed to use little stack. In particular, no recursion (natural in hierarchical structures like this) has been carefully avoided and replaced with iteration. -- You'd need RAM for event queue(s). Event queues store pointers to events (again, 2-bytes per pointer). If you use a queue 10-events deep, say, you need 20 bytes of RAM for the ring buffer and some 10 bytes for the queue itself. -- You'd need RAM for event pool(s). Event pool stores the events efficiently, without any additional RAM to link the blocks (see Section 9.3.2 in "Practical Statecharts"). The RAM you need here depends entirely on how big your events are and how many of them you need. If you need, say, 10 events of 8-bytes each, you'd need 80 bytes for the event pool buffer and some 8 bytes for the event pool itself. As you can see, I believe that the whopping 4K of RAM is plenty for a minimal QF application. Maybe you could even squeeze in the publish-subscribe feature? Interestingly, state machines often obviate the need for using an RTOS. If you can design your state machine with sufficiently short RTC (run-to-completion) steps then you can achieve the desired responsiveness without a preemptive RTOS. Please refer to the discussion of the "Reminder" state pattern in Chapter 5, and to the foreground-background port of the QF in Chapter 9. The "Reminder" state pattern is particularly useful for chopping any longer processing into shorter RTC steps to achieve better responsiveness. Obviously, eliminating the RTOS frees up significant RAM that you need to pay for the internal RTOS structures and the multiple stacks. Regards, --Miro (miro@quantum-leaps.com) ------------------------------------------------------------------------------ QF/ROOM and Scalability Questions DBercot posted 7/28/03 8:54 PM I am back into Architecture work for my company and would appreciate your opinion(s). I believe that the Quantum Framework may be too "small" (for lack of better thought) for our application(s). My greatest concern concerning "small" is the use of a global definition of events known at compile time on which the QF runs. In one of my diversions, I imagined adding "contexts" to the QF, in which the events were constrained, such that the QF could be used recursively from lower to higher levels of abstraction. Then I ran across your references to ROOM and decided to investigate that architecture, which leads to the following questions: 1. Am I wrong in assuming that the QF may not be appropriate for very large systems ? (smallness) 2. IS ROOM a viable candidate architecture, or does it suffer from the ills that the QF addresses ? 3. Have you ever envisioned an extension to the QF such as "QF contexts" ? Thanks in advance ------------------------------------------------------------------------------ miro posted 8/13/03 5:56 PM Hi there, > Am I wrong in assuming that the QF may not be appropriate > for very large systems ? (smallness) it depends, of course, on what you understand as "very large" systems. From my experience, QF can certainly be scaled up to medium-size (say tens KLOC), or even large-scale systems (hundreds of KLOC). Obviously, for larger systems a single enumeration for all signals (that I describe in my book) isn't going to work, because any change in any signal (or event-class declaration, for that matter) requires recompilation of virtually *all* components. The problem of partitioning the signal space and sharing event-class declarations can be approached in several ways. One way is to emulate ROOM protocols, which are the collections of signals and events that are permitted to enter or leave ports of actors. At the highest level, you can partition the signal space into oversized chunks, say like this: enum { COMMON_START = Q_USER_SIG, // common signals shared by all SHUTDOWN_SIG, ERROR_SIG, // ... COMPONENT_A_START = COMMON_START + 20, COMPONENT_B_START = COMPONENT_A_START + 100, COMPONENT_C_START = COMPONENT_B_START + 50, //... MAX_SIG }; All components must include this enumeration. Then, you can declare "protocol" header files (sets of related signals and event-class declarations) that will be included only in specific components that actually use these protocols. > IS ROOM a viable candidate architecture, or does it suffer > from the ills that the QF addresses ? From what I read about the upcoming UML 2.0 standard, many elements of ROOM (as described by Bran Selic at al.) are now incorporated into UML. This actually shouldn't be so surprising, given that Bran Selic is very active in the UML community. In a sense, ROOM has been ahead of its time... However, ROOM (as most of the UML) is designed to be used in conjunction with a specialized design automation tool. If you try to implement "by hand" ROOM (or parts of the UML, say state machines) you'll end up with... QF, or something pretty close. > Have you ever envisioned an extension to the QF such as "QF contexts"? I don't quite understand what you mean by "contexts". In earlier iterations of the QF, I tried to follow ROOM much closer by implementing ROOM ports and ROOM protocols. In practice, I found that I didn't get much mileage out of these concepts. In the end, I settled for a very minimal, but non-trivial, architecture. In practice, it's much easier to add new features to a minimal foundation than to go the opposite route of limiting features in an overgrown architecture. -- Miro (miro@quantum-leaps.com) ------------------------------------------------------------------------------ Doug Bercot posted 9/9/03 10:39 PM Good answer ! My concept of a QF "context" would correlate to a ROOM Statechart. As I understand it, ROOM provides a mechanism of nesting statecharts (thereby hiding the internal event set) and exporting new events via the ports of the enclosing statechart. If you could have multiple instances of the "QF" object (containing the pools & publish/subscribe mechanism) you could achieve the nesting of statecharts as ROOM does, but you would then have to somehow bind QF objects to a given "context". Anyways, after reading parts of/most of ROOM and evaluating the Rational toolset, I'm guessing that introducing model based computing to my organization would be like introducing Quantum Physics to the Neandrathals (not likely to be fruitful). BTW - I am still using the QF and C+ in my current app and must congratulate you again for your fine work. ------------------------------------------------------------------------------ Port for Ada95 Tad Ashlock posted 9/23/03 10:09 PM Has anybody tried porting the QF to Ada95? It looks like some parts of the QF would be slicker than the C++ implementation, such as: * QSignal could be implemented as a hierarchy of empty tagged records instead of a C++ enumeration. This overcomes the problem of extending the enumeration without having to have all signals being global. * QState could be defined as actually returning a QState, rather than a QPseudoState. * Multi-threading is supported directly in the language -OR- * Use a port of the Single-Stack Tasker with a runtime-less Ada95 (e.g. gnort). ******************** The only problem I currently see is how to port the following construct from QHsm: #define Q_TRAN(target_) if (1) { \ static Tran t_; \ tranStat(&t_, Q_STATIC_CAST(QState, target_));\ } else ((void)0) AFAIK, Ada95 doesn't have anything like this. Anybody have any ideas or other hurdles that I haven't stumbled across yet? Thanks, Tad ------------------------------------------------------------------------------ Jonathan Kaye posted 11/6/03 7:50 AM I don't know Ada95, but as far as your question regarding porting Q_TRAN, I've run into a problem porting QF to ActionScript/Flash (actually, Miro ported it, I just tweaked a bit). ActionScript doesn't have macros, so Q_TRAN's search (or really tran) has to be run each time. To optimize this, I was thinking I would to have to define each transition in a variable before the engine is run. So I'd have to maintain a list of transitions and reference the specific transition in each state method. Not real elegant, but what can one do? -jonathan ------------------------------------------------------------------------------ qf port for vxworks Joerg Krein posted: 7/15/03 3:31 PM Hello, I'm looking for a VxWorks port of the QF. Has anyone starting on this? Regards, Joerg ------------------------------------------------------------------------------ Virgil Farnam posted 8/2/03 0:49 AM I will be starting a port of QF to VxWorks in about 2 months, Still working application requirements & design. Application is an implementation of CCSDS. ----------------------------------------------------------------------------- miro posted 9/16/03 7:31 PM Diego Serafin has contributed a QF port to VxWorks (currently only the C version). I've just made this port available from http://www.quantum-leaps.com/qf/code.htm -- Miro (miro@quantum-leaps.com) ------------------------------------------------------------------------------ How is QF related to UML-RT and ROOM? Sam Gu posted 11/2/03 1:35 AM Seems like the concepts are identical, just QF puts more emphasis on resource efficiency. ------------------------------------------------------------------------------ miro (Moderator) posted 11/3/03 8:25 PM Hi Sam, You are right. QF is based on the *same* fundamental concepts as UML-RT and ROOM. Indeed, as I've been repeating for years (many times in my book, in my articles, and at conferences) the conceptual underpinnings for QF have been known for at least two decades. So in this respect, QF is closely related to UML and the tools you mentioned. However, QF is also very different. What sets QF apart is its minimalist, code-centric, and low-level nature. This characterization is not pejorative; it simply means that QF maps the fundamental concepts directly to the *source code*, without necessarily relying on graphical representations (although you can obviously use diagrams if you like). One of the most important aspects of QF is that hierarchical state machines and active objects (as any other profound concepts in software) are a powerful type of design, not a particular tool. The issue here is not a tool — the issue is understanding. Code-synthesizing tools (such as UML-RT (former ROOM toolset), Rhapsody, BetterState, visualState, and others) can have heft and substance, but they cannot replace a conceptual understanding. The lightweight state machine- based framework like QF shows that (once you know the patterns) it's quite easy to implement the fundamental concepts without sophisticated tools. QF thus dispels many deeply rooted misconceptions and misunderstandings that higher-level UML concepts are not viable without sophisticated tools. I hope you get the point. The Preface and Conclusion of my book available online (http://www.quantum-leaps.com/writings/book.htm) discuss the issues in more detail. Best regards, --Miro (miro@quantum-leaps.com) ------------------------------------------------------------------------------ Posix Threads JoAnn Peeler posted 11/26/03 4:34 PM I'm a student at Florida State University and I will be taking a class that covers HSM and QF. Looking at the readme for the Linux port of QF, I noticed that there was some problem using gdb with a Posix-threaded app. Has there been a resolution to this problem? I don't know enough about QF at this point to make any salient contributions to this forum, but I'm sure that will change. In the mean time, its nice that this site is here for more information about QF. http://garnet.acns.fsu.edu/~jdp02d/ My Home Page ------------------------------------------------------------------------------ miro (Moderator) posted 12/2/03 6:57 PM Hi JoAnn, POSIX threads, and POSIX APIs in general, have many implementations. In the desktop Linux implementation, I experienced problems when debugging multithreaded applications with gdb (or derivative tools, such as ddd). The problem was that once a breakpoint has been hit in one POSIX thread, the other threads kept going and corrupted the state of the application. The tools significantly improved with newer Linux distributions (I worked with RedHat stuff), but still there were occasional "hiccups". To my knowledge, POSIX threads are still not quite integrated with the gdb debugger (I hope some other readers will correct me here, or provide some tips how to work around the issues I mention.) I don't recall any of such problems in other implementations of POSIX threads, such as VxWorks. VxWorks uses GNU tool chain and, among others, implements POSIX APIs. The gdb worked just fine. --Miro (miro@quantum-leaps.com) ------------------------------------------------------------------------------ Generating Code for Embedded Apps Torsten Kuenstler posted 12/9/03 10:40 AM Hello Everybody, I'm studying Computer Science and to become a bachelor in CS I have to do some writings that in Germany we call Diplom. For this, I will invent a Code Generator. Based on QF this will Generate Code from UML to C+ for a MC. This MC will be the C167 from Infinion. So, what I ask for is: Does anybody have experiences or ideas? Regards, Torsten ############################################################################## Hierarchical State Machines and QF in Java This discussion thread contains postings related to the Java implementations of the Quantum Framework, which includes the implementation of Hierarchical State Machines in Java. ------------------------------------------------------------------------------ Here is the archive of related postings. Author: Paul Topic: Events posted: 9/29/03 6:02 PM ------------------------------------------------------------------------------ I am implementing a QF application in Java and I would like some input on event and state transitions. I have a multi-screened Java application that needs to switch from screen to screen based on control events. Each control will be able to fire an event like ON_CLICK which the given state (I'll probably have at least one for each screen) will handle. My question is this: if the state handler fires off a new event (such as GO_TO_SCREEN4 or something), will it get handled immediately, or after this transition is complete? Does this event ever enter the Event Queue or is that only for events coming from outside the Active Object? Perhaps I am modelling the application wrong. Does it make sense to have a GO_TO event or is that more like an action? I wanted the controls to fire generic events and to have the screen loading/unloading in the entry/exit sections of each screen's state. Any ideas for me? ------------------------------------------------------------------------------ Henry Choi posted 9/30/03 3:34 AM Hi Paul, Your idea sounds okay overall, except the GO_TO_SCREEN4 event. Perhaps I am splitting hair, but a button should just be a button, and should not dictate that the subscriber of its event (if you would like, think of it as a signal) should do with the received information. If you have the button tell the screen (or anyone for that matter) you are introducing an artificial coupling that QF tries so hard to prevent. Perhaps you should call the event Q_BUTTON_PRESSED if transient, or Q_BUTTON_ACTIVATED if it's a toggle button. The motivation for this is from QT (from trolltech), which is a GUI framework that has many concepts parallel to QF. In QT, a button "emits" different signals depending on what happens to it. The user pressing it is one of these events, and causes the button to emit "pressed", "activated", "hidden", etc. Another widget then, may have a slot where the emitted signal may be directed to, and that may for example, be the screen widget that hides/shows itself. By looking at the list of signals a QWidget emits (QT documentation is publicly available from www.trolltech.com), you can borrow many use cases. One striking shortcoming of QT compared to QF is that someone must connect these signals and slots explicitly in code, which introduces coupling, albeit in a far weaker form than the commonly seem strong coupling. Hope this helped. Please let me know if your questions were not fully answered. -Henry http://www.quantum-leaps.com/qf/native.htm QF+ ------------------------------------------------------------------------------ Paul posted 10/6/03 11:54 PM Henry Thanks for the reply... I am familiar with the Qt framwork and I really like it as well. I was planning on having the button fire a generic event (the ON_CLICK event). My question is more about how events cause other events. Is it safe for an event to fire another event? The GO_TO event was my example of a second event firing. I guess what I am interested in knowing is wether or not you can process an event in the middle of a state transition without queueing the event and finishing your RTC step. ------------------------------------------------------------------------------ miro posted 10/9/03 5:33 PM Paul, You cannot process another event before you finish processing of the first event (you must complete the RTC step). So, in particular it is not OK to call dispatch() method in the middle of event processing (i.e., call dispatch() on behalf of the same state machine that is just active). Calling dispatch() in the middle of event processing would cause recursion (we are already inside dispatch()) and would confuse the "event processor". The workaround is to use the "Reminder" state pattern (see Chapter 5 in my book), but this requires event queueing. I hope this answers your question. -- Miro (miro@quntum-leaps.com) ------------------------------------------------------------------------------ qFJ - Java port of qF Glenn McAllister posted 12/31/03 7:55 AM I've written an open-source Java port of the qF framework, available at http://www.codingknights.com/projects/qFJ/ The current version is 0.9.0. Its fully functional with QFsm, QHsm, and QF implementations. Its the whole shebang, not just QHsm. There are a couple of issues that have to be resolved before a 1.0.0 release: 1. static state transitions in QHsm. 2. efficient event pooling (right now all events have to be created off the heap). I'm working on 2 right now, as its easier. :-) I'd be very happy to recieve feedback on qFJ. Please post replys to this thread; I don't have qmail up and running on codingknights.com yet, and I'm not eager to hand out my home email to a web page; I'm sure to get spammed then. :-) http://www.codingknigths.com/projects/qFJ ------------------------------------------------------------------------------ daniel posted 1/7/04 4:23 AM you mispelt your url, the correct url is: http://codingknights.com/projects/qFJ/ ------------------------------------------------------------------------------ Glenn McAllister posted 1/7/04 5:48 AM I usually catch that. Thanks for pointing out my error. http://www.codingknights.com/projects/qFJ/ ------------------------------------------------------------------------------ Glenn McAllister posted 1/9/04 11:12 PM The 1.0 release of qFJ is available, with reasonably efficient event pooling and a more java IoC style way of hooking the active objects together. http://www.codingknights.com/projects/qFJ/ ############################################################################## Topic: QP and Embedded Systems Author: Miro Samek (Moderator) posted 1/12/04 4:30 AM ------------------------------------------------------------------------------ This discussion thread contains postings related to Quantum Framework and embedded systems, including severly resource-constraint environments. This first positng is an archived thread moved over from the previous quantum-leaps.com discussion forum. http://www.quantum-leaps.com ------------------------------------------------------------------------------ Peter Kraak posted 4/24/03 1:20 AM I once wrote a message based executive that had cooperative multitasking and preemption at the message level, i.e. whenever a task called any o/s call or yield() if there was a higher priority task waiting it ran. the design called for message procssing tasks that ran to completion. the beaut thing was it was all in ansi C and to port it you just needed a c compiler and provide the SysTick() call from a hardware timer. thats it. If QP (c+ version) was melded to this it would provide a simple lean shrinkwrapped solution for new small targets. When real preemption is needed eCos is probably a better host, and is open source so no royalties, but needs a mid to high end platform. ------------------------------------------------------------------------------ Teemu Karevaara posted 6/17/03 9:10 AM "Super Simple Tasker" which Robert Ward introduced in Embedded Systems Conference San Francisco 2002 (http://www.esconline.com/sf/feat_tech_cl.htm#347) seems like a perfect platform for QF. Has someone already made a port? ------------------------------------------------------------------------------ miro posted 6/17/03 5:21 PM Bingo Teemu! Robert Ward's "Super Simple Tasker" (see www.codecraftsman.com) is an ideal fit. I have a first prototype working on ARM processor (exactly EB01 evaluation board for AT91 microcontroller from Atmel). The whole preemptive tasking and scheduling requires only some 40 ARM instruction in assembly (interrupt handler), and some 20 lines of C. The prototype works like magic. SST turns the foreground/background version of QF into a fully deterministic, preemptive RTOS. The limitations of the scheduler are exactly what you want. Active objects cannot block and wait on each other, every event must be processed to completion, only higher-priority active object can preempt current RTC step. This allows to use only *one* execution stack for all active objects. This unorthodox scheduler is exceptionally higher-level language friendly. Because you don't care about the exact layout of the context stack frame (as long as all registers are saved), you can store only the registers that are clobbered by the HLL, and then let the compiler save the rest of the registers in whichever order it likes. This means that the stack consumption is much lower than traditional RTOSs. Also, the SST breaks with the endless-loop structure of tasks. A task in SST is *not* a loop, but rather a one-shot event processing. This alone is remarkable and is a consequence that SST does not need to maintain the context of the endless-loop. In summary, a "native" implementation of QF can be made much *smaller* than a traditional RTOS (both in code space, data space, and CPU usage). Yet, the resulting system works at higher level of abstraction--at the level of active objects and state machines. No direct messing with semaphores, mutexes, monitors, etc--far less possibilities of shooting yourself in the foot. The *native* QF is by far the most exciting project I'm currently involved in. Any comments? --Miro ------------------------------------------------------------------------------ Bernard Mentink posted 7/30/03 10:57 PM Can someone point me to a document that describes how SST works? I can not seem to get hold of the Author .... Many Thanks ------------------------------------------------------------------------------ Henry Choi posted 8/1/03 4:52 AM http://www.codecraftsman.com seems to work just fine for me. Miro, I too think something wonderful might come by making a completely HSM based (and strictly real-time to boot) OS, but have some concerns. Please excuse me if I am missing something obvious. 1. How would the finished product differ from the QNX microkernel approach, which seems to be based on message passing (event publishing in QF lingo)? If QNX couldn't hit the big time marketing robustness, why would QF have a easier go at it? 2. Will HSM paradigm gain wide acceptance among application developers who have been weaned on the poorer solutions? For example, RTC (Run to completion) model flies in the face of all traditional OSes (whether real-time or no) I know of and the applications written on top of them; they block for any number of reasons. Wouldn't you agree that QF forces fundamental change on the applications? Let's take the TCP write() for example, which(may) block up to a time if the TCP send queue fills up. How much change is necessary for the applications that currently block on that write()? And do we have to force the application programmers to deal with the ASSERT() sprinkled throughout QF, because they are (if they didn't know it before) really hitting against the system resource issue? Do the non-UML conversant S/W engineers who glossed over these fundamental issues have to rewrite all their applications to reap the benefits of QF? 3. Performance: As Kahan likes to say, "the fast drives out the slow even if the fast is wrong." In my previous job (Real-Time Innovations), I tried to adopt QF for the middleware product (one of whose strength was the performance) and failed because of the memcpy() hit we would have to take. Our design required overwhelming (at least for me) thought and analysis to achieve zero-copy performance in multi-threaded application. Even though QF would have drastically simplified our middleware, we opted against it because the customers demand the fastest possible performance. At least in my former world of hyperfast network applications, copying data around to publish events would have been a deadly sin. I believe the experts such as Mr. van Jacobson (of TCP congestion avoidance fame) will back me up on this, because they are trying to figure out a way to avoid ANY memcpy(), starting from the H/W! I think QF is still a great option where a few memcpy() is inconsequential. I would even wager that most applications fall in this category. But I have observed that customers choose the fast (and wrong) solution over a robust but inconsequentially slow one. However, despite these concerns, I still would like to see QF based RTOS, and would try to use it in any product I work on! ------------------------------------------------------------------------------ Paul Butler posted 8/6/03 11:22 PM I'm very curious about the SST implementations being discussed here. Is anyone planning to make source available? Or is it already and I just haven't found it? thanks, -paul ------------------------------------------------------------------------------ miro posted 8/8/03 0:17 AM I have added a new page to the QP website intended to cover the developments of the "native" QF (please see www.quantum-leaps.com/qf/native.htm). At this point this page contains just a general introduction, but I plan (time permitting) to add more information. For now, you can find there Robert Ward's ESC paper that explains his SST. The "native" QF won't use Robert's implementation, but rather will directly embed the scheduler. I have a functional version for On-Time's RTTarget-32 (www.on-time.com) that I plan to make available on the QP website. This version grew up from the foreground/background port of QF to RTTarget-32 (please note that RTTarget-32 is just a platform for doing embedded development on PC-like hardware, but it is *not* a kernel). --Miro (miro@quantum-leaps.com) ------------------------------------------------------------------------------ QF lite Bob Lee posted 11/25/03 5:35 AM I've read Practical State Charts in C/C++ and would like to use them on my current project; however, I need to reduce the QF foot print (ROM & RAM) to make it work on the 8-bit micro we are using. Is there a QF lite available? ------------------------------------------------------------------------------ miro (Moderator) posted 11/25/03 7:04 PM I've received quite a few letters from readers who tried QF on small platforms. A few readers reported that they have ported QF to Keil C for 8051 processor family. I guess, Luis Pereira from Network Technologies and Electronics Group (LuisRPereira@Eaton.com) was the most advanced in using QF under these circumstances. Generally, I believe that the basic ideas are scalable down to very small platforms. So in particular, you can fit HSM, events, timers, and so into very resource-constraint environments. From what I see, the most severe limitation is RAM, not so much the CPU cycles. To conserve RAM you should consider using only the dynamic state transitions (see "Practical Statecharts", Section 4.4.3). On very small platforms, I'd probably eliminate the whole publish-subscribe part of the QF and allow only direct messaging among active objects (via QActivePutFIFO(), QActivePutLIFO() methods). On the other hand, I believe that you need to use at least one event queue (at least one active object) and an event pool. Event queue(s) and event pool(s) allow a thread-safe communication between the interrupt-level and the task-level and you don't want to lose this benefit. On small platforms, you can make events smaller. For example, the whole QEvent can be just one byte (if you use only one event pool and one active object you need to store only the signal in QEvent. You should define QSignal to be unsigned char). Recently I've been working on a new version of QF (QF v3.0), which I plan to make freely available to the owners of my book. QF v3.0 is a little more memory-efficient than QF v2.x published in the book. Depending on the demand, I might consider releasing a special stripped-down version of QF v3.x (a "pico-QF") for very small micros. Probably, this version(s) must be platform dependent (e.g., Keil C for 8051). --Miro (miro@quantum-leaps.com) ------------------------------------------------------------------------------ Holt posted 11/26/03 2:27 AM I too just got the book and am thinking about using your methods for a project I am working on. I'm worried about the amount of RAM that is required. Can you give me an idea? I know it's tough without knowing the scope of the problem. To give you an idea I will have only one 2-level HSM with 6 superstates and at most 8 substates. I would estimate about 40 transitions between states (Just counting the number of arrows on the statechart. Maybe this isn't the best way to convey the size of the application). I am considering one of the AVRmega parts from Atmel because the tools are free and plenty of RTOS's available. At most this part has 4K of RAM. Is this going to be enough or should I just not even bother? I'm looking at an RTOS which has been ported to the AVR family. It is called FreeRTOS and can be found at www.freertos.org. It supports preemptive scheduling, message queues, and I'm thinking about trying to port QF to it. None of these decisions are set in stone, so any suggestions you may have that could save me future headaches would be much appreciated. Thanks, Holt ------------------------------------------------------------------------------ miro (Moderator) posted 12/2/03 7:41 PM Hi Holt, To give you a better idea of the RAM requirements for using the HSMs and the rest of the Quantum Framework, here is a little breakdown: -- Each instance of QHsm costs 2-function pointers (4 bytes on 8-bit micro with 64k address space). That's the whole RAM you need, if you don't use static state transitions (only dynamic transitions, see Section 4.4.3 in "Practical Statecharts"). The state handlers are just functions that go into ROM. -- The QHsm class has been specifically designed to use little stack. In particular, no recursion (natural in hierarchical structures like this) has been carefully avoided and replaced with iteration. -- You'd need RAM for event queue(s). Event queues store pointers to events (again, 2-bytes per pointer). If you use a queue 10-events deep, say, you need 20 bytes of RAM for the ring buffer and some 10 bytes for the queue itself. -- You'd need RAM for event pool(s). Event pool stores the events efficiently, without any additional RAM to link the blocks (see Section 9.3.2 in "Practical Statecharts"). The RAM you need here depends entirely on how big your events are and how many of them you need. If you need, say, 10 events of 8-bytes each, you'd need 80 bytes for the event pool buffer and some 8 bytes for the event pool itself. As you can see, I believe that the whopping 4K of RAM is plenty for a minimal QF application. Maybe you could even squeeze in the publish-subscribe feature? Interestingly, state machines often obviate the need for using an RTOS. If you can design your state machine with sufficiently short RTC (run-to-completion) steps then you can achieve the desired responsiveness without a preemptive RTOS. Please refer to the discussion of the "Reminder" state pattern in Chapter 5, and to the foreground-background port of the QF in Chapter 9. The "Reminder" state pattern is particularly useful for chopping any longer processing into shorter RTC steps to achieve better responsiveness. Obviously, eliminating the RTOS frees up significant RAM that you need to pay for the internal RTOS structures and the multiple stacks. Regards, --Miro (miro@quantum-leaps.com) ------------------------------------------------------------------------------ QF/ROOM and Scalability Questions DBercot posted 7/28/03 8:54 PM I am back into Architecture work for my company and would appreciate your opinion(s). I believe that the Quantum Framework may be too "small" (for lack of better thought) for our application(s). My greatest concern concerning "small" is the use of a global definition of events known at compile time on which the QF runs. In one of my diversions, I imagined adding "contexts" to the QF, in which the events were constrained, such that the QF could be used recursively from lower to higher levels of abstraction. Then I ran across your references to ROOM and decided to investigate that architecture, which leads to the following questions: 1. Am I wrong in assuming that the QF may not be appropriate for very large systems ? (smallness) 2. IS ROOM a viable candidate architecture, or does it suffer from the ills that the QF addresses ? 3. Have you ever envisioned an extension to the QF such as "QF contexts" ? Thanks in advance ------------------------------------------------------------------------------ miro posted 8/13/03 5:56 PM Hi there, > Am I wrong in assuming that the QF may not be appropriate > for very large systems ? (smallness) it depends, of course, on what you understand as "very large" systems. From my experience, QF can certainly be scaled up to medium-size (say tens KLOC), or even large-scale systems (hundreds of KLOC). Obviously, for larger systems a single enumeration for all signals (that I describe in my book) isn't going to work, because any change in any signal (or event-class declaration, for that matter) requires recompilation of virtually *all* components. The problem of partitioning the signal space and sharing event-class declarations can be approached in several ways. One way is to emulate ROOM protocols, which are the collections of signals and events that are permitted to enter or leave ports of actors. At the highest level, you can partition the signal space into oversized chunks, say like this: enum { COMMON_START = Q_USER_SIG, // common signals shared by all SHUTDOWN_SIG, ERROR_SIG, // ... COMPONENT_A_START = COMMON_START + 20, COMPONENT_B_START = COMPONENT_A_START + 100, COMPONENT_C_START = COMPONENT_B_START + 50, //... MAX_SIG }; All components must include this enumeration. Then, you can declare "protocol" header files (sets of related signals and event-class declarations) that will be included only in specific components that actually use these protocols. > IS ROOM a viable candidate architecture, or does it suffer > from the ills that the QF addresses ? From what I read about the upcoming UML 2.0 standard, many elements of ROOM (as described by Bran Selic at al.) are now incorporated into UML. This actually shouldn't be so surprising, given that Bran Selic is very active in the UML community. In a sense, ROOM has been ahead of its time... However, ROOM (as most of the UML) is designed to be used in conjunction with a specialized design automation tool. If you try to implement "by hand" ROOM (or parts of the UML, say state machines) you'll end up with... QF, or something pretty close. > Have you ever envisioned an extension to the QF such as "QF contexts"? I don't quite understand what you mean by "contexts". In earlier iterations of the QF, I tried to follow ROOM much closer by implementing ROOM ports and ROOM protocols. In practice, I found that I didn't get much mileage out of these concepts. In the end, I settled for a very minimal, but non-trivial, architecture. In practice, it's much easier to add new features to a minimal foundation than to go the opposite route of limiting features in an overgrown architecture. -- Miro (miro@quantum-leaps.com) ------------------------------------------------------------------------------ Doug Bercot posted 9/9/03 10:39 PM Good answer ! My concept of a QF "context" would correlate to a ROOM Statechart. As I understand it, ROOM provides a mechanism of nesting statecharts (thereby hiding the internal event set) and exporting new events via the ports of the enclosing statechart. If you could have multiple instances of the "QF" object (containing the pools & publish/subscribe mechanism) you could achieve the nesting of statecharts as ROOM does, but you would then have to somehow bind QF objects to a given "context". Anyways, after reading parts of/most of ROOM and evaluating the Rational toolset, I'm guessing that introducing model based computing to my organization would be like introducing Quantum Physics to the Neandrathals (not likely to be fruitful). BTW - I am still using the QF and C+ in my current app and must congratulate you again for your fine work. ------------------------------------------------------------------------------ ------------------------------------------------------------------------------ Port for Ada95 Tad Ashlock posted 9/23/03 10:09 PM Has anybody tried porting the QF to Ada95? It looks like some parts of the QF would be slicker than the C++ implementation, such as: * QSignal could be implemented as a hierarchy of empty tagged records instead of a C++ enumeration. This overcomes the problem of extending the enumeration without having to have all signals being global. * QState could be defined as actually returning a QState, rather than a QPseudoState. * Multi-threading is supported directly in the language -OR- * Use a port of the Single-Stack Tasker with a runtime-less Ada95 (e.g. gnort). ******************** The only problem I currently see is how to port the following construct from QHsm: #define Q_TRAN(target_) if (1) { \ static Tran t_; \ tranStat(&t_, Q_STATIC_CAST(QState, target_));\ } else ((void)0) AFAIK, Ada95 doesn't have anything like this. Anybody have any ideas or other hurdles that I haven't stumbled across yet? Thanks, Tad ------------------------------------------------------------------------------ Jonathan Kaye posted 11/6/03 7:50 AM I don't know Ada95, but as far as your question regarding porting Q_TRAN, I've run into a problem porting QF to ActionScript/Flash (actually, Miro ported it, I just tweaked a bit). ActionScript doesn't have macros, so Q_TRAN's search (or really tran) has to be run each time. To optimize this, I was thinking I would to have to define each transition in a variable before the engine is run. So I'd have to maintain a list of transitions and reference the specific transition in each state method. Not real elegant, but what can one do? -jonathan ------------------------------------------------------------------------------ qf port for vxworks Joerg Krein posted: 7/15/03 3:31 PM Hello, I'm looking for a VxWorks port of the QF. Has anyone starting on this? Regards, Joerg ------------------------------------------------------------------------------ Virgil Farnam posted 8/2/03 0:49 AM I will be starting a port of QF to VxWorks in about 2 months, Still working application requirements & design. Application is an implementation of CCSDS. ----------------------------------------------------------------------------- miro posted 9/16/03 7:31 PM Diego Serafin has contributed a QF port to VxWorks (currently only the C version). I've just made this port available from http://www.quantum-leaps.com/qf/code.htm -- Miro (miro@quantum-leaps.com) ------------------------------------------------------------------------------ How is QF related to UML-RT and ROOM? Sam Gu posted 11/2/03 1:35 AM Seems like the concepts are identical, just QF puts more emphasis on resource efficiency. ------------------------------------------------------------------------------ miro (Moderator) posted 11/3/03 8:25 PM Hi Sam, You are right. QF is based on the *same* fundamental concepts as UML-RT and ROOM. Indeed, as I've been repeating for years (many times in my book, in my articles, and at conferences) the conceptual underpinnings for QF have been known for at least two decades. So in this respect, QF is closely related to UML and the tools you mentioned. However, QF is also very different. What sets QF apart is its minimalist, code-centric, and low-level nature. This characterization is not pejorative; it simply means that QF maps the fundamental concepts directly to the *source code*, without necessarily relying on graphical representations (although you can obviously use diagrams if you like). One of the most important aspects of QF is that hierarchical state machines and active objects (as any other profound concepts in software) are a powerful type of design, not a particular tool. The issue here is not a tool — the issue is understanding. Code-synthesizing tools (such as UML-RT (former ROOM toolset), Rhapsody, BetterState, visualState, and others) can have heft and substance, but they cannot replace a conceptual understanding. The lightweight state machine- based framework like QF shows that (once you know the patterns) it's quite easy to implement the fundamental concepts without sophisticated tools. QF thus dispels many deeply rooted misconceptions and misunderstandings that higher-level UML concepts are not viable without sophisticated tools. I hope you get the point. The Preface and Conclusion of my book available online (http://www.quantum-leaps.com/writings/book.htm) discuss the issues in more detail. Best regards, --Miro (miro@quantum-leaps.com) ------------------------------------------------------------------------------ Posix Threads JoAnn Peeler posted 11/26/03 4:34 PM I'm a student at Florida State University and I will be taking a class that covers HSM and QF. Looking at the readme for the Linux port of QF, I noticed that there was some problem using gdb with a Posix-threaded app. Has there been a resolution to this problem? I don't know enough about QF at this point to make any salient contributions to this forum, but I'm sure that will change. In the mean time, its nice that this site is here for more information about QF. http://garnet.acns.fsu.edu/~jdp02d/ My Home Page ------------------------------------------------------------------------------ miro (Moderator) posted 12/2/03 6:57 PM Hi JoAnn, POSIX threads, and POSIX APIs in general, have many implementations. In the desktop Linux implementation, I experienced problems when debugging multithreaded applications with gdb (or derivative tools, such as ddd). The problem was that once a breakpoint has been hit in one POSIX thread, the other threads kept going and corrupted the state of the application. The tools significantly improved with newer Linux distributions (I worked with RedHat stuff), but still there were occasional "hiccups". To my knowledge, POSIX threads are still not quite integrated with the gdb debugger (I hope some other readers will correct me here, or provide some tips how to work around the issues I mention.) I don't recall any of such problems in other implementations of POSIX threads, such as VxWorks. VxWorks uses GNU tool chain and, among others, implements POSIX APIs. The gdb worked just fine. --Miro (miro@quantum-leaps.com) ------------------------------------------------------------------------------ Generating Code for Embedded Apps Torsten Kuenstler posted 12/9/03 10:40 AM Hello Everybody, I'm studying Computer Science and to become a bachelor in CS I have to do some writings that in Germany we call Diplom. For this, I will invent a Code Generator. Based on QF this will Generate Code from UML to C+ for a MC. This MC will be the C167 from Infinion. So, what I ask for is: Does anybody have experiences or ideas? Regards, Torsten http://www.quantum-leaps.com Matt Wheeler posted 1/17/04 7:07 AM ------------------------------------------------------------------------------ I'm thinking of porting QF to run on a TI C6x DSP. I'm thinking about using DSPBios as the base RTOS. Has anyone tried this? ############################################################################## Author Topic: State Machine and QF Implementation Miro Samek (Moderator) posted 1/12/04 4:01 AM ------------------------------------------------------------------------------ This discussion thread contains postings related to various implementation aspects of state machines and the Quantum Framework (QF). http://www.quantum-leaps.com Miro Samek (Moderator) posted 1/12/04 4:02 AM ------------------------------------------------------------------------------ [This message has been edited on 01/12/2004] Miro Samek (Moderator) posted 1/12/04 4:09 AM ------------------------------------------------------------------------------ Here is the archive of related postings. ------------------------------------------------------------------------------ ------------------------------------------------------------------------------ Representing state topology with/without explicit data structure? Tero posted 7/28/03 6:51 AM ------------------------------------------------------------------------------ Hi Miro! In article "State-Oriented Programming" in Embedded Systems Programming magazine (August 2000) [1] you construct the state topology as a tree -like data structure of State objects. In the book the topology is embedded in state handler methods. What are the basic reasons behind this change? What are the pros and cons of these two approaches in your opinion? Best regards, Tero [1] http://www.embedded.com/2000/0008/0008feat1.htm ------------------------------------------------------------------------------ miro posted 8/5/03 0:29 AM Hi Tero, today I consider the implementation published in ESP in August 2000 as one of the "beaten path" approaches (although this implementation is already much simplified compared to the OMG state machine meta-model). You see, such implementation falls out more or less automatically from a standard object-oriented analysis (OOA). OOA prescribes to create a class for every key concept in the problem domain, so you end up with a State class. However, states objects require memory, need to be initialized, don't behave correctly under inheritance of entire state machines, and are otherwise a burden to the client programmer. The state machine implementation published in the book "Practical Statecharts in C/C++" is entirely different. At the time I stumbled at this representation (at first for classical FSMs) I considered it a major breakthrough. Arguably, the most natural (and the fastest!) mapping from state-behavior to code is through an address of the state-related code (pointer-to-function in C). If you think about it, behavior *is* the code (a reactive system "behaves" only by executing code). You don't really need an indirection layer of State objects. Interestingly, such implementation of state machine deeply resembles implementation of polymorphism in C++ (virtual tables stuff). I believe that this is not just a coincidence. Polymorphism really means different *behaviors* at different times, and this is exactly what's happening in a state machine. In short, I think that departure from the standard OOA results in this case in much tighter code with unbeatable performance and minimal memory footprint (a state machine is just a pointer-to-function). Additionally, the signature of a hierarchical state handler (returning the superstate) is really a novelty here. This simple "trick" allows to extend a long-known assembly-language jump-table technique of coding state machines to efficiently implement state hierarchy. The technique is superior, because it so naturally maps to real microprocessors (you need to look at the assembly level output to really appreciate this, I show an example on page 74). -- Miro (miro@quantum-leaps.com) ------------------------------------------------------------------------------ ------------------------------------------------------------------------------ C+ QF tip: Init your static vars Gavin Haentjens posted 8/18/03 8:03 PM Just wanted to give a tip to anyone porting the C+ version of the QF to their processor: Make sure your static variables are initialized to 0. This may very well be a standard good programming practice that I didn't know about. If your static variables are not initalized to 0, then you will need to find some way to explicitly initialize all of the transitions in the objects, which as far as I can tell, is nontrivial. For now I should be okay initializing all static vars, but it does create a problem with the part of my code that used to check (and then initialize) a memory location after every reset to determine whether the processor was without power prior to the reset. By the way, in case someone was interested in exchanging ideas, I'm trying to port the QF to an Infineon C167 using the foreground/background scenario (no RTOS). -Gavin ------------------------------------------------------------------------------ miro posted 8/19/03 5:30 PM Hi Gavin, according to the C Standard, all uninitialized static variables are (must be) initialized to zero before calling main(). Typically, all uninitialized static objects are placed in a BSS section, which is zeroed out before calling main(). This is important, because both C+ and the HSM implementations *rely* on this initialization. In C+, implicit zeroing out static variables is important for correct initialization of virtual tables. In the HSM implementation, zeroing out the static Tran objects is important for the "static transition" optimization (see Section 4.4.3 in my book). You bring an important point, though. In embedded systems, zeroing out the BSS section(s) is often in the hands of the programmers, who must often fiddle with the initialization sequence. It is important to perform correct initialization of the BSS each and every time the system goes through reset! This can be sometimes tricky (e.g., when you perform only an incomplete reset, known as "hot start"). Various reset sequences can be quite involved and clearly are beyond the scope of this short reply. However, if your chip/board has a watchdog, it's often the best way to perform a clean hardware reset (including resetting the peripherals and setting the chip selects. (To use the watchdog for reset, simply program it to expire immediately). Thanks for bringing this point up, --Miro (miro@quantum-leaps.com) ------------------------------------------------------------------------------ Henry Choi posted 8/20/03 5:11 PM Dear Gavin, I too ran into the uninitialized variable problem when I ported QF to 8051, which I've given to Miro. I think it makes sense for QF to initialize those variables to 0 no matter what. If you ever get a hold of my 8051 port, you will see many places where BSS initialization caused problems for me. For example, in case you haven't discovered this yet, the static Tran_ t in Q_TRAN macro body must also be initialized to {{0,0,0,0,0,0,0}, 0} to avoid "weird" problems. I am tempted to provide my 8051 port, but as my port contains a few fixes for the as yet unconfirmed bugs, I think it's better if Miro takes a look first. Now, may I ask you why you have decided to use the foreground/background scenario? On 8051, I had no choice but to use that, as the compiler refused to pass more than 1 pointer in a function call through a function pointer, which is the underpinning of state transition in QF. But if you have no such restriction (what compiler are you using?), would you be interested in using the QF native port (which might be called QuantumOS)? It will allow a truly deterministic, preemptive real-time application, and will soon be available under commercial licensing terms. Looking forward to hearing your thoughts, -Henry http://www.quantum-leaps.com/qf/native.htm QuantumOS ------------------------------------------------------------------------------ ------------------------------------------------------------------------------ Limiting memory used by transitions Gavin Haentjens posted 8/22/03 10:13 PM In my application, memory needed for transitions has become an issue. Each transition requires 34 bytes (although it could be less if I decreased the max transition steps down from 8). A possible work around for this is to use Q_TRAN_DYN() for transitions that are simple (transition to self) or ones that occur rarely. Also, if many substates have the same target, they could post reminders to the superstate and let it perform the transition (only one Q_TRAN is required in that case). If anyone has other ideas, I'd be interested in hearing them. -Gavin ------------------------------------------------------------------------------ Henry Choi posted 8/25/03 2:43 AM Gavin, I think you have answered your own question: use Q_TRAN_DYN() instead of Q_TRAN(). I consider Q_TRAN_DYN() a pure optimization, and as such the familiar memory vs. speed rule applies here. Arguments in favor of using Q_TRAN_DYN(): Your QHsm (the children, of course) must be a singleton for you to use Q_TRAN. Maybe it is now, but what about a few months later, or even in the next rev of the product? The guy who takes over the code may be scratching his head when the system exhibits strange behavior just becase he instantiated one more QHsm class. For scalability and maintainability then, Q_TRAN_DYN is the way to go at first. having to keep track of the hard coded limitation on number of transitions is not a good way to prototype the system. You can, for example, crash the QHsmTst example by sending 2 "g" signal in a row, because the number of transitions in that case will blow the hard-coded limit. At least in the current QF implementation, it's not obvious at first that the limit has been breached, so you may spend some time trying to track down the crash. If you can meet all requirements by using Q_TRAN_DYN, you would only be increasing the idle CPU time unused by switching to Q_TRAN. After you meet the correctness requirement with Q_TRAN_DYN, you can then selective optimize the critical path by switching to Q_TRAN. Hope this helps. http://www.quantum-leaps.com/qf/native.htm QF+ ----------------------------------------------------------------------------- Teemu Karevaara posted 8/26/03 2:11 PM How come QHsm needs to be singleton if Q_TRAN macro is used? Q_TRAN is intended for static transitions and the transition chain is the same for every instance of QHsm. So once any of the instances makes the transition (and stores the static Tran-field in the statehandler) other instances can use the same transition chain (since they use the same statehandler) ----------------------------------------------------------------------------- miro posted 8/26/03 6:13 PM The use of macro Q_TRAN() doesn't necessarily mean that a state machine must be a singleton. For example, there are five Philosopher active objects, and they all use Q_TRAN(). The issue is more subtle than this. As one reader pointed out to me, if multiple and concurrent instances of the same state machine class are created, the setup of the static transition (the QHamTranStat_() method) can lead to race conditions among the state machines. I have fixed this problem in the second printing of the book. (So, remedy of the potential race condition was the primary reason I slightly changed the implementation of static transitions between the first and the second printing of the book). In the first printing, I used tran->chain[0] to detect if the static transition has been initialized. This can lead to race conditions if you have multiple instances of a given state machine (active object) executing the same transition simultaneously (like the Dining Philosophers), because tran->chain[0] is set *before* the full transition chain is stored, so if a state machine is preempted after setting tran->chain[0], the transition chain might be inconsistent (incomplete). To remedy this, I decided to use the LS-bit of the tran->actions attribute to indicate if a static transition has been initialized. This attribute is set only *after* the complete transition chain (tran->chain) has been recorded. Setting tran->actions is also *atomic* (at least on 16 and 32-bit machines), which evades the race condition. (On 8-bit machines, setting tran->actions should theoretically be surrounded by a critical section). The second motivation for this modification was for me that in C++ the pointer-to-member function is potentially a complex object (see Chapter 6), so the test of (tran->myChain[0] == 0) is more expensive than the test of (tran->actions & 1). One side-effect of this change is that only 7-step transition chains can be stored in the 16-bit tran->actions (the LSB is already used, remember?) That's why tran->chain[] array has shrunk to 7 entries. However, the QHsmTst state machine (Chapter 4) now asserts for transition g from state s211. As it turns out, this transition has 8 steps and overflows the chain[] array (which is correctly caught by the postcondition in QHsmTran_() method). A simple workaround is not to use static transition in this case, but to use Q_TRAN_DYN() macro for this particular transition. Coming back to the potential hazards of the Q_TRAN() macro, they are mostly related to inheriting entire state machines. I've explained the issues best I could in Section 6.3 in Chapter 6. Having said all this, I would agree with Henry Choi that Q_TRAN() should be viewed as an optimization of Q_TRAN_DYN(). For simpler (most common) state transition Q_TRAN_DYN() doesn't incur much overhead. In fact, the algorithm has been specifically designed to handle the most-common cases first with minimal overhead (see Section 4.4.4 and Figure 4.7). The bonus of using Q_TRAN_DYN() is no memory overhead for storing the transition chain, which might be significant in memory-strapped embedded applications. -- Miro (miro@quantum-leaps.com) ------------------------------------------------------------------------------ ------------------------------------------------------------------------------ Linked lists for messages wink posted 9/18/03 6:16 AM Hello all, I'm implementing an embedded system using a significant sub-set of qp features. After reading Miro's book I'm convinced the notion of message passing and active componets would be useful. But there is one thing I didn't like and that is passing messages by copying them into fixed sized queues. So for my project I'm using linked lists. This eliminates any issues of queue sizing and only means I need to worry about having enough messages around, a problem that has been easily managed. It seems to work quite well and I was wondering if others have used this technique or know of reasons it shouldn't be used. Cheers, Wink ------------------------------------------------------------------------------ miro posted 9/23/03 6:06 PM Hi Wink, please note that event passing in the QF does *not* require copying event into the event queues. As I tried to illustrate in Figure 8.6 (Chapter 6 of my book), event queues hold only the *pointers* to the events and not events themselves. The way you use events in the QF is as follows. You first allocate an event (with macro Q_NEW), then you fill the event parameters and finally you publish or post the event. Upon publishing, the event is *not* copied. Rather only the pointer to the event is placed in the event queue. This means that QF implements, in fact, a mechanism of thread-safe sharing of memory that *looks* like event passing. Because event queues store only pointers, they are quite lightweight. However, your idea of incorporating the pointer into events themselves is intriguing. I believe you can get away with singly-linked list, which will cost only one pointer per event. (Please note that this would not be much more memory efficient than the current scheme, because either way you pay the price of one additional pointer per event.) However, what this scheme would buy you is that you don't need to separately size the event queues -- you only need to size the event pools. At this point I don't know quantitatively how the link-list implementation would compare with the current one as far as CPU use is concerned. One disadvantage of the linked-list method that comes to my mind is that you could not insert an event into several event queues *simultaneously*. The current multicasting mechanism of QF does not require this, but I'm contemplating the possibility of changing that. Events should not be modified after publishing (they are passed as const to the state handlers), so you should safely post the *same* event into multiple event queues. This would solve the problem of possible change in event order that can occur with the current multicasting scheme (which I describe in Section 8.5.3). -- Miro (miro@quantum-leaps.com) ------------------------------------------------------------------------------ wink posted 9/24/03 6:09 AM I understand that you only put pointers in the queue, but I wasn't looking at a space problem, but infact trying to solve the "... don't need to separately size the event queues -- you only need to size the event pools.". I viewed this as a significant problem and the linked lists solves it quite nicely. In the environments I'm using memory tends to not be a problem and I just didn't like having to guess in advance the size of a queue, hence link-lists. Also, in the current implementation when an event is removed from the queue the message is "owned" by the SM that removed it. So, if desired the SM can "reuse" the message and would typically use it as the message it might need to generate. This works well but it does mean that messages can easily get lost, so the programmer must be VERY careful:) For that reason I've thought about removing that "feature", but in reality I can only request the programmer not reuse and can't realy enforce it, so I've taken the pragmatic approach and I let the programmer hang themselves if they want. I also, happen to use doubly linked lists since I already had such a library and there was no compelling reason to make another library. (I try to adhere to some XP principles and try to "minimize" extra work, until it's actually a problem). Thanks for the response, Wink ------------------------------------------------------------------------------ ------------------------------------------------------------------------------ Problem with QF timers John O. posted 10/20/03 7:12 PM Hello, I am running into a problem with the timers implemented in the QF. Specifically, it has to do with using the QTimerDisarm() method. This method only sets the number of remaining ticks in the timer to 1, and sets the signal to the "empty" signal. Thus, disarming the timer doesn't really disarm it. It only makes it expire one tick later. This is all fine and well, until a timer is disarmed, and then subsequently restarted before another tick can complete (it asserts under these conditions since the timer is still in use). On my system, my tick rate is one second (reducing it would help reduce the problem but would never eliminate it). Is there a way to truly disarm a timer, so there aren't any requirements about how long you wait before you can actually access the timer again? This seems like a potentially big problem with the timer subsystem. Oh yeah....just so it doesn't seem like I'm only harping on a problem, I have successfully used the QF for the last nine months or so under Linux, and really like it. Thanks for the help, John ------------------------------------------------------------------------------ miro (Moderator) posted 10/29/03 7:09 PM Hi John, I haven't been quite happy with the QTimer class for quite a while now. As you point out, disarming a timer is done by a "trick" to turn it into a one-shot timer that should expire by the next tick. This is to avoid a potentially indeterministic scanning through an (open-ended) list of timers, which must be done in a critical section. Also, the precondition to disarming the timer (i.e., that the timer must be armed) seems to strong. I found it often useful to disarm a timer upon exit from a state, and sometimes the timer was already expired. In short, I've changed and hopefully improved the QTimer class. I've been using this new class for more than half a year now and it works just fine. I've added a new section to the website that describes the new developments of QF(please check http://www.quantum-leaps.com/qf/ code#QFNew). Among others, you'll find there code to download. I hope this helps, --Miro (miro@quantum-leaps.com) ------------------------------------------------------------------------------ ------------------------------------------------------------------------------ Transistion algorithm and debug of HSM's Christopher Meisner posted 12/11/03 11:18 AM Hi All First of all "Practical Statecharts ...." is a realy great book. Two topics i would like to discuss are the algorithm for state transistions and debug of HSM's. I personnaly found the algorithm for state transistions complex. It started to bug me that there was not one but several different cases that had to be considered. I the came up with the following: 1) Find level of nesting for src and dst state (simply count) 2) Back up state with deepest nesting recording entry or exit path respectively until src and dst are at same level. 3) Find LCA (now simple iteration) 4) Do transistion. I will provide some source code if anybody is interested. Second topic. Only having a function pointer as a state variable clealy is optimal but.. When developing realtime embedded software for Telecom appliactions one of the essentiel tools is a real time trace tool. Our tool logs all message between tasks. Off cause when implementing a FSM/HSM framework you also want to be able to log state transistions. I have not found any really good solution of implementing this in the framework with having to add code to the actual HSM implementation because there is no state Id. or other value that is easy for humans to decode (function pointers are not :-) ) Any ideas? Thanks for Input Christop Meisner Senior Coordinator, Software RTX Telecom A/S http://www.rtx.dk ------------------------------------------------------------------------------ Iain McInnes posted 12/15/03 12:29 AM Hi, Christopher. I have come to exactly the same conclusion as you. Yes, in my next app, I will almost certainly add sufficient instrumentation so that I can log the events and transitions. Allowing the state information to grow beyond a simple pointer, we can add: - State name for trace purposes. - The hierarchical level of the state. As you said, knowing the levels of source and destination makes the transition algorithm much simpler. - The identity of the enclosing state. While sending an null event is elegant, directly storing the enclosing state makes the transition algorithm more efficient. One issue, of course, is that this information is known to the client (subclass) of the HSM. The implementation that I am thinking of requires the client to provide an array of struct with the above information. The state variable then becomes an index into that array. Iain. Christopher Meisner posted 12/15/03 5:20 PM ------------------------------------------------------------------------------ Hi Iain, Miro's orginally idea of making the HSM implementation code-centric is a great idea. HSM's implemented by lookup tables are a pain to code and maintain. They do however offer some advantages. The "optimum" solution has many facets :-). The best i have come up with for debugging QF HSM is for the Clint HSM to provide a lookup table providing a MAP between state handler and State Id. (as enum or string or both depending on what you like and how much space you can use for debug code. I think a compromise is to add a state object containg name for debug/trace and a link to parent state. Christopher http://www.rtx.dk ------------------------------------------------------------------------------ miro (Moderator) posted 12/15/03 6:55 PM The algorithm for taking a state transition (i.e., executing the right sequence of exit and entry actions as well as initial transitions) can obviously be made much smaller. For example, I published such an implementation in ESC ("State Oriented Programming", August 2000). The main point of the implementation published in "Practical Statecharts in C/C++" is that it is more optimal. This implementation handles the most common transition topologies (such as peer-to-peer) explicitly in the most optimal way. (All these lowest-order transition topologies are enlisted in Figure 4.7 on page 112.) In practice, the lowest-order topologies account for 90+ percent of all transitions. I believe that a slight complication of the QHsm::tran() method is worth speeding up these 90% of cases. As to representing states as objects, I already described my position in the book. The issue is RAM. Please remember that my goal here is a truly practical solution for *embedded* systems. From the other discussion thread (QF "lite") it should be clear how precious RAM is in smaller embedded projects. State objects would use up this precious RAM in no time. In contract, state handlers use only ROM. Regarding instrumentation, you are all right. Instrumentation of a state machine is often invaluable. In fact, a hierarchical state machine is ideal for adding such instrumentation. Here innovativeness has no limits. You can use entry/exit actions to print execution logs, you can easily build real-time sequence diagrams, you can drive external pins and "see" the state changes on the oscilloscope at real time, and so much more. (Actually, that's exactly what CASE tools do...) The problem is that instrumentation always adds overhead. In a generic implementation I could not add such overhead, because it will be not acceptable for all systems. You guys use the code now in particular situations, so you can judge for yourself what kind of overhead is acceptable in your case. Then you can then go ahead and add instrumentation, perhaps directly to QHsm::tran() and QHsm::dispatch(). If anybody finds out particularly "cool" instrumentation, please let me know or publish it in this forum. Maybe others will benefit from it too. Cheers, --Miro (miro@quantum-leaps.com) ------------------------------------------------------------------------------ Iain McInnes posted 12/16/03 10:59 AM Thanks, Miro. I completely agree with your comments about instrumentation - including the fact that there is no "one size fits all". Two things that always seem to be true about embedded systems - there is never enough memory to store log and trace information; and there is never enough bandwidth in the instrumentation port to get the events off the device fast enough. One solution that I like is to combine both of these: Capture events in a log, and have a dedicated process (could be an active object !) who'se job is to empty the buffer through the diagnostic port. My current platform is Linux, and so I am positively spoiled with the syslog facilities that are available. One thing that I routinely do is to add profiling to the event dispatch. Its easy to create some timer macros which read a timer register, and compute elapsed time. Then, I allocate a budget for each active object, which can be stored as a property of the QActive class. Lastly, REQUIRE() that the measured dispatch time never exceeds the budget. I believe that continuously measuring execution times is the only way to be confident that the requirements are always met. I normally write the timing macros like assert, in such a way that they can be turned off before final testing and shipping - it would be nice to leave them in, but it can be hard to justify the extra overhead in the delivered code. I have some reasonably portable code that does the timing - I'll forward it if anybody is interested. ------------------------------------------------------------------------------ Christopher Meisner posted 12/16/03 11:00 AM Hi Miro Adding a state object / (or struct in a non OO implementation) does not necessarily have to be instansiated in RAM. This off cause requires that the topology of the HSM is static. In fact we might be able to save RAM because we could reduce the state variable to an id. Which could be 8 bits for small and reasonable sized HSM's. The penalty is const code space. Currently I am investigating both table based implementation and QF like HSM's. From my initial conclusion it seems that table based HSM's can be implemented with less code but are a pain / almost mpossible to code manually with out a tool and are even worse maintaining. HSM's are perfectly code centric which is what we want and the code penalty is acceptable. Just need to find a way to add the trace functionality in the framework which i what we require as we do not want to have to add debug code manually to each HSM. Christopher http://www.rtx.dk http://www.quantum-leaps.com Matt Wheeler posted 1/17/04 7:04 AM ------------------------------------------------------------------------------ What's the limit on levels of hierarchy in a QF Statechart? I have 5 levels now. Is there any penalty for having deep hierarchies? miro (Moderator) posted 1/19/04 7:33 PM ------------------------------------------------------------------------------ The latest implementation of QF (QF 2.5.0, see http://www.quantum-leaps.com/qf.code/qf25_notes.txt) limits the maximum state nesting to eight levels. You can easily change this limit to whatever you like by changing the dimension of the automatic array entry[]in the QHsm::tran()/QHsm::tranStat() methods (QHsmTran()/QHsmTranStat() in C). Additionally, for static state transitions (see "PSiCC" Section 4.4.3) the latest version of QF limits the maximum transition complexity to eight steps. Again, this limit can be easily changed by modifying the dimension of the myChain[] array in the Tran structure. Transition complexity is different from nesting level, because a transition can have few exit/entry actions or initial transitions, even though the state nesting might be deep. In HSMs, there typically is some cost associated with deep state hierarchies. You can immediately understand why by looking at the implementation of the QHsm::dispatch() method (Listing 4.9 in "PSiCC"). The semantics of state nesting requires dispatching the same event to higher and higher hierarchy levels until it is handled, or the highest level (the top state) is reached. Obviously, the cost is lower for events handled at lower levels of nesting. In particular, the QF implementation of HSM does not impose any additional cost (compared to non-hierarchical FSM) for events that are handled at the lowest levels of nesting. (This provides a hint for optimal structuring your state machines--handle the most frequent events directly at the lowest levels of nesting and use higher-level states for relatively infrequent events, such as exceptions). --Miro Brent Arias posted 1/27/04 8:11 AM ------------------------------------------------------------------------------ I'm curious about the distinction you make in your book about "suspended interrupts" versus "suspended multi-tasking." Why is it sufficient for the QF to perform only "suspended interrupts" to protect its critical section? Assuming that "suspended interrupts" is not sufficient to block an actor from gaining CPU time - then what happens if an actor's thread is activated and attempts QF reentrancy during the critical steps of the QF publish/subscribe? Furthermore, does the "suspended interrupts" interval last for the entire publish/subscribe procedure or does it occur only during allocation from the memory pool? http://www.ariasamp.net professional/ technical playground Brent Arias posted 1/27/04 8:47 AM ------------------------------------------------------------------------------ As the book stated, a significant concept in the QF is the combination of the mediator and observer patterns. It was exciting for me to see this idea presented, since I eventually recognized I had implemented the same combination a couple years ago - in a single threaded GPP environment using C++ and the STL. At that time I made *awkward* attempts to relate this mechanism to MVC or Bushman's PAC pattern. Clearly it is much better, as Miro has done, simply to say it is a combination of mediator and observer. Still, in the single-threaded version I permitted a particular event to be published repeatedly/recursively. QF does not allow that. Perhaps my implementation was therefore highly susceptible to bugs in ways I did not fathom. However, I'm not certain why the QF itself permits only one event publication at a time. The "Statecharts" book did not elaborate on **precisely** what error could happen without the restriction. I would love to hear an example of a bug that may manifest itself if a particular event could be published twice during a QF multi-cast. And on another note, I'm curious to hear about: 1) Has anyone seen a published class/object level implementation of a HSM? Samek's book covers the "State" pattern from Gamma which operates at the "class" abstraction, but it is not a HSM. Does there exist a popular/published class level HSM pattern? It would be helpful to compare it with the quantum HSM. 2) How might the QF be adapted to serve a pipeline architecture? Currently it seems like a pipeline parallel processing problem is not the place to apply the QF. But perhaps someone has contrived an intuitive QF adaptation for that kind of problem? 3) How did the old "Object Time" product from Rational implement its HSM? I've heard of this product, but I have no idea how it functioned "under the hood." http://www.ariasamp.net professional/ technical playground miro (Moderator) posted 1/27/04 7:16 PM ------------------------------------------------------------------------------ Brent, Let me address a few of your questions. As I discuss in Section 8.4.1 of "PSiCC", briefly disabling interrupts is the simplest and bullet-proof way of preventing preemption on a single-CPU system. Virtually all RTOSes internally use this technique to guarantee that certain sections of code (aka critical sections) are atomic (indivisible). QF uses carefully designed, short critical sections to protect sensitive sections of code. A good discussion of this subject can be found in the book "MicroC/OS-II" by Jean Labrosse. Amazingly little published implementations of HSMs exist to my knowledge.In contrast, quite a few non-hierarchical FSMs implementations have been published. In Chapter 3 of "PSiCC" I give a few references to prior art in this area. I'd recommend going, for example to the ESP archive (www.embedded.com), or simply "googling" around a little. In Section 4.1.2 of "PSiCC", I also refer to my earlier ESP article ("State-Oriented Programming", ESP, August 2000) that was exactly based on states-as-objects (as opposed to states-as-functions). (This article is available online from ESP archive and from http://www.quantum-leaps.com/writings.esp/samek00.pdf). The code generated by ObjecTime toolset resembled the "Nested switch-statement" technique (see Section 3.2 in "PSiCC"). The state machine was hierarchical, though, so the tool generated passing control to the superstate in case an event was not processed in the substate. Clearly, code like this is not intended for manual maintenance. If you are interested in the quality of automatically generated code, you could download an evaluation version of Rhapsody from www.i-logix.com and play a little with it. --Miro Viacheslav posted 1/29/04 7:37 AM ------------------------------------------------------------------------------ Brent, For pipeline architecture it is possible to show application of FSM (or HSM) by the example of having dinner philosophers. For this purpose they need to be put in one line and on the one hand to give it of a fork, and on the other hand they will fold them. Thus philosophers does not eat, but simply transfer fofks. Holt posted 2/4/04 9:36 PM ------------------------------------------------------------------------------ I have the same problem as John O. described in his 10/20/03 posting to this topic. I have a state which has an entry action which arms a one shot timer. The exit action for the same state disarms the timer. It is possible for an event to occur (handled by a super state) which returns the HSM to the same state descibed above. So upon the occurence of this event, the state is exited (timer disarmed) and entered (timer armed) very quickly. When this happens my application hangs. Before I started investing the problem I checked this discussion board. I found the John O. was having a simular problem. If a timer is disarmed and rearmed before the next tick it looks like it creates a problem. I checked out the link you refereced in the John O. reply and found the QF2.5 site which I already have. Does your new QTimer implementation fix the problem described above? Does QF2.5 have the new QTimer implementation (the release notes don't mention QTimer, so I assume no)? If no, how do I remedy the situation so it can handle the scenario described above. I just want to say that I am very pleased with your framework. It has saved me a lot of time. Thanks, Holt miro (Moderator) posted 2/5/04 6:59 PM ------------------------------------------------------------------------------ Hi Holt, From all the QF features, I've got the most complaints about the QTimer implementation. Unfortunately, in the book-compatible release QF v2.5, I could not fix the class completely, because this would be inconsistent with the book's text. In particular, QF v2.5 still has the problem you're describing (i.e., disarming and arming a timer within one clock tick). I've, however, prepared an improved QTimer implementation, based on bidirectional link list (as opposed to unidirectional link list in QF v2.5 or earlier). This QTimer class is available online from: http://www.quantum-leaps.com/qf.code/qf26_cpp_qtimer.ZIP. This is only the C++ version, but the C version is analogous. Please note that the QF::tick() method (file qftick.cpp) should replace the previous implementation of QF::tick() in qf.cpp. The new QTimer is also less restrictive. For example, it is OK to disarm an already disarmed timer, which exactly happens when you put the disarm() method in an exit action and the timer happens to expire before you exit a state. I hope this will solve your immediate problem. In the meantime I'm finishing the next major version of QF (QF v3.0), which will include the improved timers among other features. --Miro JoAnn Peeler posted 2/9/04 11:45 AM ------------------------------------------------------------------------------ I hope this is the appropriate place for this post. If not, I'm sure Dr. Samek will either move it (or deleted it!) I'm digging into the QF for the first time in a class at Florida State. I hope this is not too tangential; however, I have a question I would like to pose -- would this problem domain warrant its own language? While OOP can be implemented in a non-OOP language (see the C+ macros), implementing the OOP patterns directly in the language results in code that is easier to understand and read. To me there seems to be some advantage of having a language that sematically maps one-to-one to UML statecharts and that clearly exposes behavioral inheritance. The output of the language could target QF/C+, QF/C++, QF/Java, QF/C#, etc. The language implementation might be able to produce various optimizations. One optmization that comes to mind is during semantic analysis, the transitions for static statecharts could be optimized resulting in transition tables being large enough (but no larger!) I'd love to hear anyone else's thoughts about this including, "what a loon -- QF doesn't need no stinking language!" :) -- JoAnn Peeler http://garnet.acns.fsu.edu/~jdp02d/ My Home Page Rob Bultman posted 2/21/04 12:57 AM ------------------------------------------------------------------------------ I just wanted to weigh in on the Q_TRAN/Q_TRAN_DYN discussion... I ran into RAM problems too on a microcontroller with 2K RAM when using Q_TRAN. I switched to Q_TRAN_DYN and did some very simple, non-statistically significant timing measurements. In my micro (Renesas 3687 with 4.9152mhz clock), Q_TRAN executed a chain in 16us on the second pass of a sibling-to-sibling transition. Q_TRAN_DYN required 150us. Although 150us is still probably acceptable, I didn't like the "performance hit". I then looked at my active objects and realized that they almost always have an HSM with a single state at the top level followed by a classical flat FSM below. (Do I smell a state pattern here?) I looked at the Orthogonal Component section and implemented the lower-level SM as an FSM. Because I only had one state in the HSM, the dispatch mechanism was extremely simple. I just dispatch the event to the FSM before I do anything else in the HSM handler. This makes the dispatch model identical to the HSM where the substates receive the events before the superstate. The superstate handler only gets called if the substate does not handle the event. More below. I changed the implementation of the QFsmState functions to return a QFSMSTATE type instead of void so that I could mimic the return Top/return 0 model of the HSM. To do this, I changed the typedefs in qfsm.h to match qhsm.h so there are now QFsmState and QFSMSTATE types. This made changing the substates trivial. I had to change the function prototypes to return QFSMSTATE instead of QSTATE. I also moved all of the member variables from the HSM to the FSM. This meant fewer changes to the substate code since all of the my->var lines largely remained unchanged. I added a parent__ member variable so that the substates could easily call QActivePostFIFO to inject an event if needed or do things like QTimerRearm. Changing the QFhsm to return QFHSMSTATE also helped with the dispatch mechanism at the superstate. Here is my dispatch code. (This is from memory so it may not be correct. Notably all type casts are missing. The var names have been changed to protect the innocent. Hopefully you will get the idea.) QSTATE MyHSMHandler(me, e) { QFSMSTATE LastState; QEvent EntryEvent = {MY_ENTRY_SIG, 0, 0}; // save current state LastState = QFsmGetState(&me->MyFSM); // dispatch event to FSM QFsmDispatch(&me->MyFSM, e); // check for a change of state from the FSM if (LastState != QFsmGetState(&me->MyFSM)) { // make sure the new state receives an ENTRY event QActivePostFIFO(me, &EntryEvent); } // continue with normal HSM code switch (e->sig) ... As you can see, I detect a change of state and "issue" an entry event to the new state. I could have called the new state directly, but posting the entry event breaks up the execution of the state machine and allows other code to execute. In others words, it plays nice. MY_ENTRY_SIG is placed above MAX_SIG in the enum of signals. Note that you could add an exit signal in the same manner. My substates don't happen to used exit conditions. One big benefit of using FSMs in this manner is that you can make transitions in the entry event. You can't do this with HSMs. This is possible since QFSM_TRAN only changes the state__ pointer to point to the new state and does not call any routines. The top-level HSM then detects the change and posts the entry event for the new state. There are two benefits here. One is that this is one fewer event occurs in the system. With an HSM, the event trail would look like this: entry event -> post to self -> entry event for new state. With the FSM, the event trail would look like this: entry event -> entry event for the new state. It removes the "dummy" post-to-self required by the HSM implementation. The second benefit is a reduction in code size. Although you take the hit for the additional dispatch code, all post-to-selfs required to implement transitions in the entry events are gone. One down-side here is that you have to explicitly post an additional event to implement a Q_TRAN(self) if you are subscribing to an entry event. This does not cause additional events in the system but does take an additional line of code for the QActivePostFIFO. All this being said, I like this implementation. It uses no more RAM that Q_TRAN_DYN and is as fast or faster than Q_TRAN. It is conceptually simple and consistent with the rest of the QF. Take care, Rob Rob Bultman posted 2/21/04 1:01 PM ------------------------------------------------------------------------------ Is it possible to repost my last reply? The formatting got messed up when I cut and pasted. Sorry and thanks, Rob Rob Bultman posted 2/27/04 10:27 AM ------------------------------------------------------------------------------ I just wanted to weigh in on the Q_TRAN/Q_TRAN_DYN discussion... I ran into RAM problems too on a microcontroller with 2K RAM when using Q_TRAN. I switched to Q_TRAN_DYN and did some very simple, non-statistically significant timing measurements. In my micro (Renesas 3687 with 4.9152mhz clock), Q_TRAN executed a chain in 16us on the second pass of a sibling-to-sibling transition. Q_TRAN_DYN required 150us. Although 150us is still probably acceptable, I didn't like the "performance hit". I then looked at my active objects and realized that they almost always have an HSM with a single state at the top level followed by a classical flat FSM below. (Do I smell a state pattern here?) I looked at the Orthogonal Component section and implemented the lower-level SM as an FSM. Because I only had one state in the HSM, the dispatch mechanism was extremely simple. I just dispatch the event to the FSM before I do anything else in the HSM handler. This makes the dispatch model identical to the HSM where the substates receive the events before the superstate. The superstate handler only gets called if the substate does not handle the event. More below. I changed the implementation of the QFsmState functions to return a QFSMSTATE type instead of void so that I could mimic the return Top/return 0 model of the HSM. To do this, I changed the typedefs in qfsm.h to match qhsm.h so there are now QFsmState and QFSMSTATE types. This made changing the substates trivial. I had to change the function prototypes to return QFSMSTATE instead of QSTATE. I also moved all of the member variables from the HSM to the FSM. This meant fewer changes to the substate code since all of the my->var lines largely remained unchanged. I added a parent__ member variable so that the substates could easily call QActivePostFIFO to inject an event if needed or do things like QTimerRearm. Changing the QFhsm to return QFHSMSTATE also helped with the dispatch mechanism at the superstate. Here is my dispatch code. (This is from memory so it may not be correct. Notably all type casts are missing. The var names have been changed to protect the innocent. Hopefully you will get the idea.) QSTATE MyHSMHandler(me, e) { QFSMSTATE LastState; QEvent EntryEvent = {MY_ENTRY_SIG, 0, 0}; // save current state LastState = QFsmGetState(&me->MyFSM); // dispatch event to FSM QFsmDispatch(&me->MyFSM, e); // check for a change of state from the FSM if (LastState != QFsmGetState(&me->MyFSM)) { // make sure the new state receives an ENTRY event QActivePostFIFO(me, &EntryEvent); } // continue with normal HSM code switch (e->sig) ... As you can see, I detect a change of state and "issue" an entry event to the new state. I could have called the new state directly, but posting the entry event breaks up the execution of the state machine and allows other code to execute. In others words, it plays nice. MY_ENTRY_SIG is placed above MAX_SIG in the enum of signals. Note that you could add an exit signal in the same manner. My substates don't happen to used exit conditions. One big benefit of using FSMs in this manner is that you can make transitions in the entry event. You can't do this with HSMs. This is possible since QFSM_TRAN only changes the state__ pointer to point to the new state and does not call any routines. The top-level HSM then detects the change and posts the entry event for the new state. There are two benefits here. One is that one fewer events occur in the system. With an HSM, the event trail would look like this: entry event -> post to self -> entry event for new state. With the FSM, the event trail would look like this: entry event -> entry event for the new state. It removes the "dummy" post-to-self required by the HSM implementation. The second benefit is a reduction in code size. Although you take the hit for the additional dispatch code, all post-to-selfs required to implement transitions in the entry events are gone. One down-side here is that you have to explicitly post an additional event to implement a Q_TRAN(self) if you are subscribing to an entry event. This does not cause additional events in the system but does take an additional line of code for the QActivePostFIFO. All this being said, I like this implementation. It uses no more RAM that Q_TRAN_DYN and is as fast or faster than Q_TRAN. It is conceptually simple and consistent with the rest of the QF. Take care, Rob miro (Moderator) posted 3/3/04 10:47 PM ------------------------------------------------------------------------------ Hi Rob, Thanks for an interesting data point regarding the performance difference between static and dynamic state transitions. As to your modifications to the state machine, I am not sure that I like them. For example, adding entry/exit actions (or just entry actions, if you will) to the QFsm class can be done more easily. As I described in the C/C++ Users Journal article ("Déjà Vu" June, 2003, available online from http://www.quantum-leaps.com/writings/cuj.htm), you just dispatch the exit event to the source and entry event to the target, like this: static Event const entryEvt = { Q_ENTRY_SIG };static Event const exitEvt = { Q_EXIT_SIG }; void QFsmTran_(QFsm *me, State target){ QFsmDispatch(me, &exitEvt); /* exit the source */ me->state__ = target; /* change current state */ QFsmDispatch(me, &entryEvt); /* enter the target */} I don't feel good about your posting entry/exit events to event queues. This is not only expensive, but potentially dangerous, because the state machine really doesn’t complete its RTC step and is left in the inconsistent state. Should some other event "sneak into" the queue before the entry/exit event, the state machine would have to process that other event in an unknown state. This is bad. I recall a discussion in this forum about transitions from entry actions. (I believe this topic has been pushed "over the edge" by other discussion threads.) This subject is related to so-called completion transitions in the UML. Admittedly, sometimes you run into situations that you want to bail out of a state just after entering it. From my experience, however, such designs are indicative of confusing a state with a stage of processing in a flowchart (I write about it in Section 2.2.10 of "PSiCC"). Almost always in such situations a better truly state-oriented design is possible. --Miro miro (Moderator) posted 3/23/04 5:05 PM ------------------------------------------------------------------------------ Stefan posted 3/22/04 11:39 AM ------------------------------------------------------------------------------ First of all, I would like to express my highest appreciation for sharing the outstanding information coming along with "Practical Statecharts in C/C++". I think that is the most valuable book, I've read so far in my embedded Systems Developer Carrer which is 5 years so far. The explanation around the HSM and QF design is really exceptional great. I'm continously discover about the greatness of this design-approach, and also try to convince some collegues of this better-approach. I've read your book cover-to-cover and think to understand most of it. Nonetheless, I am also wondering at some points. One of them is the QTimer implementation. I'm working with the QF 2.5.0 version using the provided Win32 port in C++. One issue in my current design is, that in a certain State (which transit to after a RESET_SIG), I would like to be able to clear/disarm all available timer in my system, independent on wether a timer is active at this certain time or not. Unfortunatly, the QTimer.disarm() function does only work when the timer is armed. "Disarming an unarmed timer causes a contract violation (Precondition failure)" page 263. Is there a possibility to disarm all available timer (even non-armed ones)? If not, I would fancy if the QF could be consider this feature in future versions. Another issue, I am interested in is: How would the C Code look like for an active object to empty its own EventQueue? Best Regards, Stefan miro (Moderator) posted 3/23/04 5:07 PM ------------------------------------------------------------------------------ Hi Stefan, Thank you for your good words about my book. As I already posted to this forum, the new QTimer implementation is available for download from: http://www.quantum-leaps.com/qf.code/qf26_cpp_qtimer.ZIP. Among other things, this version allows to disarm an already disarmed timer. As to the issue of an active object emptying its own event queue, I have intentionally not provided the standard flush() operation (although adding it is not at all complicated). One of the main challenges of active object computing is synchronizing the system-wide state. To this end, one of the most simplifying assumptions is that an enqueued event is GUARANTEED to be processed. (Imagine, for example, that in the DPP problem the Table object ignores the HUNGRY event from a Philosopher--the poor Philosopher will surely starve!) Now, if you allow flushing event queues, some important events will be surely lost. A better alternative is to put an active object in a state, in which it ignores events, but is not indiscriminate (as a flush() operation would be). --Miro miro (Moderator) posted 3/24/04 6:08 PM ------------------------------------------------------------------------------ Sam posted 3/22/04 2:39 AM How to map design model into multi-threaded runtime model? ------------------------------------------------------------------------------ each active object has its own thread of execution, at least conceptually. But when there are thousands of active objects in the system, it may carry too much overhead to actually assign an OS thread to each active object. Rather, it makes sense to group one or more active objects into the same OS thread to reduce context switching overhead. Is this sth. that has been considered? miro (Moderator) posted 3/24/04 6:09 PM ------------------------------------------------------------------------------ Hi Sam, Thanks for bringing up this problem. I've already received several letters that asked these kinds of questions, so obviously the issue requires explanation. First, let me clarify that an application comprised of hundreds or thousands of active objects is probably wrong. As you correctly observe, an active object requires a separate thread of execution and an event queue. Not every state machine in the system needs these facilities. In fact, I believe that an application with more than a few active objects is unmanageable, and that's why I don't plan to add more priority levels into QF (current limit is around 15, which I probably will reduce to 8). Partitioning a piece of functionality into an active object is a strategic decision, not a tactical one. You need a separate active object only when you need a separate priority level. For example, you need to handle some events very timely, possibly preempting other lower-priority events.But then what if you need to manage hundreds or thousands of conceptually independent and concurrent "things"? Well, I propose to use the "Orthogonal Component" state pattern (that's why I devoted almost 11 pages to this pattern in Section 5.4 of "PSiCC"). Orthogonal Components are state machines (HSMs) that all *share* one thread of execution and one event queue of their container. The overhead of an Orthogonal Component is minimal and there is no limit on how many of such components you can have. In fact, I plan to post soon a version of Dining Philosophers that would handle a few thousand of Philosophers, implemented as Orthogonal Components of the Table. My motivation for such an example comes from an e-mail I received concerning a Java implementation of HSM. A reader writes me: "I agree that the greatest value lies in the HSM concepts. However, I do see a lot of value in creating both embedded and server side applications that are based on active objects, rather than simply threads and services. I've done the latter to death, and there are lots of issues with that approach. The biggest problem is that most server implementations still use the one-connection/one-thread approach to servicing requests, which doesn't scale well beyond a certain point. Usually when Java apps get to around 250 concurrent threads, the JVM spends an inordinate amount of time context switching and your application suffers dramatically..." I believe that the "Orthogonal Component" state pattern is an ideal fit for server applications. A state machine is the most efficient way of storing a minimal context so that you can process an event and immediately *return*. The "sate" and extended state variables store the relevant context, so that you can always pick up where you left off. That's a very different philosophy than using a "heavyweight" context of an execution thread to "remember" where you left off when you block (to wait for an event). I describe this more in Section 10.1.5 of "PSiCC" as well as in my article "Quantum Programming for Embedded Systems", CUJ, March 2003, available online from http://www.quantum-leaps.com/writings.cuj/samek0303.pdf). --Miro JoAnn Peeler posted 3/26/04 5:08 PM ------------------------------------------------------------------------------ I'm working on a class project that involves using QF in a Windows application. The application is currently design with several active objects where one of the active objects is responsible for managing the user interface (a GUI.) Correct me if I am wrong (I am often), but don't I need to perform some minor surgery to QF so that I can pump the Windows message loop inside the thread of the QActive derived object? My bright idea for this project is to rebuild QF after making QActive::run() virtual. In this manner I can override the run() method in the GUI QActive object and add in Windows message queue functionality. You might ask why we are trying to manage a UI in a QActive thread rather than in the main application thread. I'm afraid its probably due to not knowing how to subscribe to or publish events/signals from a simple QHsm derived object. (The framework expects a QActive object.) Does it sound like I'm on the right track with my proposed surgery to QF? Or is the a better way to accomplish my goals? http://garnet.acns.fsu.edu/~jdp02d/ My Home Page miro (Moderator) posted 3/29/04 6:14 PM ------------------------------------------------------------------------------ JoAnn, As I indicate several times in "PSiCC", Windows GUI already is an event-driven framework, with its own "message pump", timers, GUI-specific messages (events), and so on. The problem is that QF provides also all these facilities, so you have a conflict of two different frameworks trying to control one application. I believe that the safest way would be to let Windows control the GUI, and from the GUI thread start all other QF active objects. Then you need an adaptation layer around the Windows GUI thread, so that it appears as a QF active object to the rest of the application. To that end, you probably need to override ("virtualize") not so much the QActive::run(), but perhaps the QActive::enqueue(). The QActive::enqueue() for the GUI thread could convert a QEvent into a Windows message, either packaging the QEvent parameters directly into wParam/lParam, or by passing a pointer to QEvent as lParam. In the latter case, you must not forget to recycle the QEvent in the GUI thread *after* you're done with it. Please note that in this scenario you don't need to explicitly start the GUI thread (active object), because it will be started automatically the moment you launch your application. --Miro Holt posted 4/20/04 11:31 PM ------------------------------------------------------------------------------ I just used the quantum framework in a system which we are having problems such as the system hanging in various states (some states more than others). We are investigating both hardware and software to try and combat these errors. Since I am in charge of the software, I am trying to investigate things I may have messed up when porting the QF to our processor. Also, I have some general questions and maybe people can give me some ideas. First off, I am using QF 2.5 in the foreground/backgroud mode (Without multitasking kernel p.283). The only exception is that I grabbed Miro's latest version of the Qtimer module and rewrote it in C to use with the rest of my software (this may be the problem, but I tried to be very cautious and I followed Miro's methods for converting to C). Also I am using an atmel AVR ATmega 64 processor with gcc compiler. The system may fail once per hour while running. The nature of the problem is intermittent and occurs in different states (but one particular state 35 percent of the time). The nature of the errors makes me think that I am missing an interrupt suppression somewhere, but I tried to make sure that all of my interrupt routines have interrupts suppressed during isr execution then enabled upon exiting the isr. This brings up my first question. I have a somewhat bouncy input connected to one of my external interrupts. This interrupt fires off a signal which is handled by one of my active objects. This signal causes a transition to another state which ignores this particular signal. So, I'm thinking that the first bounce is handled causing the state machine to transition then the remaining bounces (signals) are ignored as expected thus debouncing the external interrupt. Do several quick signals (or events, I can't remember the correct terminology) cause the event queues to overflow, thus causing intermittent problems. I'm assuming this doesn't cause any problems. Next I have some questions about the new timer module that I mentioned. I think Miro referred me to this module on his website. I rewrote the module in C as I mentioned. I currently have two active objects and I use one timer per active object because my timers are usually used only in one state at a time. For instance, I enter a state and set up a timer. Then the timer expiring event usually causes me to transition to another state or some other event causes a transition prior to the timer event and I disarm the timer in the exit case for that state. All I want to do is use the same timer over and over for each active object. I use a one shot timer and arm it by calling "fireIn()". If I want to reuse this timer should I just call "rearm()", or should I just call "fireIn()" again. I'm confused by what p. 256 says because it appears that I can only rearm a timer if it is currently armed. Yet a one shot timer becomes disarmed automatically when it expires. This implies that I can only use "rearm()" if the timer has not expired yet, which is not always the case so I have been calling "fireIn()" each time I want to use a timer which is quite often. I noticed that the "fireIn()" routine calls "AddTimer()". Does this mean I am allocating memory each time I call "fireIn()"? I'm wondering if I might be causing a memory leak. Either way, what is the proper way to accomplish my timer goal? I'm cofident that it is something I've done wrong and I would appreciate any suggestions that anyone may have. Thanks, Holt Holt posted 4/21/04 0:33 AM ------------------------------------------------------------------------------ BTW, I forgot to mention that I am failing the "REQUIRE(me->active__ == 0)" check on all invocations of "FireIn()" routine but the first one. This makes sense I guess since this routine invokes the "QTimerAdd()" routine, but I'm not sure what the ramifications might be to doing this. Thanks, Todd Miro Samek posted 4/21/04 5:09 PM ------------------------------------------------------------------------------ Holt, It's hard to diagnose your problem precisely, since you don't even describe HOW your system fails (assertion? Which one?). All I can do at this point is to clarify some confusion. First, regarding the interrupts disabling and enabling you should note that publishing an event (via QFpublish()) disables and then ENABLES interrupts internally. This enabling interrupts inside QFpublish() shouldn't be a problem for the internal consistency of the QF, but might be a problem in your particular case inside the ISR context. You should NOT assume that no other ISRs are enabled wile you're already processing an interrupt (especially when you have a "bouncy" interrupt). Second, overflowing an event queue is always a crime in QF and an assertion will fire. You need to prevent queue overflows BY DESIGN. Finally, your biggest confusion seems to be with QTimers. You shouldn't worry about memory leaks (in the traditional sense) because QF never allocates dynamic memory. Also, QF has built-in assertions to prevent double-allocation of objects, such as arming an already armed timer. If you're not sure if the timer is armed, please disarm it first and then arm it again. (NOTE: in the new QTimer implementation disarming an already disarmed timer is not a crime.) The precondition (assertion) failure you mention in your second posting checks exactly this case (arming an already armed timer). BTW, arming a timer inserts it into the linked-lists of active timers (AddTimer), which are checked inside QFtick(). AddTimer() doesn't allocate memory! --Miro Holt posted 4/25/04 10:22 PM ------------------------------------------------------------------------------ Thanks Miro. It appears that I was overflowing the event queues with the bouncing interrupt. I added the logic to prevent this and it appears to have cured the problem. Unfortunately I do not have a tool which will allow me to see the code execute with the actual hardware (limited budget). I do have a free simulator that I can use on my PC, but this does not help me when it comes to diagnosing the actual hardware. I can try to simulate hardware events, but it can be tedious at times. Thanks for your help, Holt Nick posted 9/3/04 2:21 PM ------------------------------------------------------------------------------ Dr. Samek, I am using your qf for my current project running on windows ce. The port to CE was very painless and so far things are working well. This project is for some manufacturing machinery and I am relying heavily on the "Orthogonal Component Pattern". My machine active object contains mostly motor and sensor QHSm derived objects. Now, the problem is when I try to use the "isIn" function call, and my problem may only be due to my misuse of the call. In the handling of a message to my machine object I want to take action based on the state of a component so I call is in. QSTATE Machine::Fault( const QEvent* e ) { ... case some_event: if( motor.isIn( static_cast( &Motor::Running ) ) { //Do Something } First, is this how it was intended to be used? Second, when I make this call, the function fails on the second iteration through the for loop in isIn because mySource is 0 in the TRIGGER call. If I change it to int QHsm::isIn(QState state) { register QState s; for (s = myState; s != 0; s = TRIGGER(s, Q_EMPTY_SIG)) { if (s == state) { // do the states match? return !0; // match found, return true } } return 0; // no match found, return false } everything seems to work on the surface, but I don't know the inner workings enough to know if this idea is completely flawed. Any help or insight is greatly appreciated. Thanks, Nick Nick posted 9/3/04 2:25 PM ------------------------------------------------------------------------------ I'm terribly sorry, but in my flurry of thought on my problem, I was completely thoughtless and posted some of you qf source code. Please remove your qf source from my above post. I would do it myself, but I can't seem to find a way to do it. Thanks, and sorry, Nick miro (Moderator) posted 9/3/04 4:19 PM ------------------------------------------------------------------------------ Nick, Your use of the QHsm::isIn() method seems correct, although I'd argue that this operation should be used very sparingly. If you think about it, the isIn() query defeats the purpose of a state machine, because you end up with explicit ifs and elses that you wanted to avoid in the first place. If handling of an event depends on the state of a component, then probably you should dispatch this event to the component and let it handle this event depending on its state. The implementation of QHsm::isIn() method in your posting is correct (it seems to come from QF v2.5). At the same time, the symptoms you describe would be consistent with the incorrect implementation published on the CD-ROM. Please check which version you actually use. I've posted the correct version of QHsm::isIn() in the errata to the book (http://www.quantum-leaps.com/writings/book.htm#Errata) and also in QF v2.5 (http://www.quantum-leaps.com/qf/code.htm#QFsource). I apologize for this mistake in the published materials. Best regards, --Miro miro (Moderator) posted 9/4/04 1:15 AM ------------------------------------------------------------------------------ Author bob Topic: Reusing parent state handler posted: 9/3/04 11:17 PM ------------------------------------------------------------------------------ Is reusing a parent state handler for an event by using a break instead of a return incorrect or considered bad form? I wanted to avoid duplicating the parent state handler code inside the sub-state handlers by reusing the parent state handler. For example, I have a battery charger state machine and one of the states is "ErrorCharging", which is a sub-state of "Charging". When I get a poll event in the ErrorCharging state, I do a little work, but instead of returning 0, I break from the switch statement and return ::Charging, which causes the parent Charging state to also do some work in response to the poll event. Related to the first question is whether it is ok if Q_TRAN_DYN is invoked multiple times while handling an event. If you consider my example case above, if the :ErrorCharging state did a Q_TRAN_DYN to ::NormalCharging then when the parent ::Charging state handler was invoked (as a result of the break instead of returning 0 by ::ErrorCharging for that event) it did another Q_TRAN_DYN to ::WaitingToCharge, would this be bad? Here's a simplified version of the code to illustrate: QSTATE BatteryHSM::Charging( QEvent const *inEvent ){ switch( inEvent->sig ) { case SIG_POLL: if( TooHot() ) Q_TRAN_DYN( &BatteryHSM::WaitingToCharge ); return( 0 ); } return( (QSTATE) &BatteryHSM::Inserted );}QSTATE BatteryHSM::ErrorCharging( QEvent const *inEvent ){ switch( inEvent->sig ) { case SIG_POLL: if( CanCommunicate() ) Q_TRAN_DYN( &BatteryHSM::NormalCharging ); break; // Note: this breaks to return the parent state. } return( (QSTATE) &BatteryHSM::Charging );} If CanCommunicate() returned true, this would transition to the NormalChargingstate, but if TooHot() returned true, it would then immediately transition to WaitingToCharge. Is there a better way to do this? miro (Moderator) posted 9/4/04 1:38 AM ------------------------------------------------------------------------------ Bob, First, I've moved your posting to this thread to limit the number of differentthreads (this forum can hold up to 25). I don't believe that reusing state hierarchy as you propose is safe. Yes, this particular implementation allows such tricks, but I wouldn't recommend them. The reuse of internal state transitions (actions that are invoked at several hierarchy levels in one RTC step) is questionable. Taking more than one state transition in one RTC is for sure a very *bad* idea. I've been tempted many times to reuse internal transitions the way you describe (and it even works!), but this approach brings several problems. The lesser one is that it's not UML-compliant and you cannot draw this behavior in a state diagram. The more important one is that you create a new kind of coupling between substates and superstates. The simplifying idea of hierarchical state machines is that an event is handled entirely in one state only. In your approach you allow an event to be partially handled in the substate and partially in the superstate. The handling of such an event is no longer centralized, but rather becomes a mixture of behaviors (partially substate and partially superstate). --Miro Bob posted 9/8/04 9:58 AM ------------------------------------------------------------------------------ Miro, thanks for the reply. I had a feeling what I was thinking of doing would be problematic. I've changed it to move the code from the super-state handler into each sub-state handler (it was only one function so it didn't add much extra code). Now each state handler is complete and the issue of multiple potential transitions per RTC is avoided. Jonathan Kaye posted 10/27/04 3:45 AM ------------------------------------------------------------------------------ I was talking with a fellow quantum-leaps.com groupee who was surprised when I told him what I had been doing but it seemed to have gotten pushed to the bottom of the forums. I have thrown together an XML description of statecharts to use as input to a code generator that produces C++ code consistent with the book's QHsm. I find that the code generator is good to rapidly produce skeleton code so I don't make mistakes with signatures or hierarchies. The code generator is on the web and free: http://www.eqsim.com/SCXML2Code.html I'd love to get comments or suggestions! You'll see that it not only generates C++, but also different variants of ActionScript (Macromedia Flash). Several posts ago, people on this forum were talking about "instrumentation" and debugging. In the statechart code I wrote (for Flash), what I call FStEng v 1.5, I also built a debugging tool that allows you to see the current state(s) while the system is running. This is made in Flash, and has to run in Flash, but one possibility to help debug statecharts is to generate the code in Flash based on an XML description (and the schema I made), and debug it in Flash, then take the same description and crank out a C++ implementation with the code generator. This obviously requires some comfort in Flash, and there might be one or two holes I haven't anticipated, but it seems to me that it would work. For people interested in checking this out more, please visit http://www.flashsim.com/newsletter/v2n2.html#xml -jonathan http://www.FlashSim.com gavin haentjens posted 10/28/04 11:40 AM ------------------------------------------------------------------------------ It seems to me that Jonathan's XML description of statecharts is a very important and useful development. I would love to see it standardized, and what I would really love to see is a program that could take an XML file in his format and convert it to, say a .gif file. That way, I could tag the XML file with the corresponding source code in a version control program. (I assume that proprietary CASE tools already do this, but I have never used one.) I have tried UMLgraph and Graphviz for creating statecharts from text files, but neither does statecharts (although Graphviz seems to do finite state machines very nicely). If anyone out there has suggestions for creating statecharts from text files, I would love to hear them. -Gavin chackochan posted 11/23/04 5:00 PM ------------------------------------------------------------------------------ Looking for Holt!!! Looking for Holt!!! Thanks Dr. Miro for writing this gem of book. I am trying to port QF on freeRTOS a pre-emptble multitasking kernel and I found that Holt has attempted the same before. I would really appreciate if you can provide me your feedback on the port attempt and the performance. Regards Chackochan ############################################################################## State Machine and QF Implementation This discussion thread contains postings related to various implementation aspects of state machines and the Quantum Framework (QF). ------------------------------------------------------------------------------ ------------------------------------------------------------------------------ Here is the archive of related postings. ------------------------------------------------------------------------------ ------------------------------------------------------------------------------ Representing state topology with/without explicit data structure? Tero posted 7/28/03 6:51 AM ------------------------------------------------------------------------------ Hi Miro! In article "State-Oriented Programming" in Embedded Systems Programming magazine (August 2000) [1] you construct the state topology as a tree -like data structure of State objects. In the book the topology is embedded in state handler methods. What are the basic reasons behind this change? What are the pros and cons of these two approaches in your opinion? Best regards, Tero [1] http://www.embedded.com/2000/0008/0008feat1.htm ------------------------------------------------------------------------------ miro posted 8/5/03 0:29 AM Hi Tero, today I consider the implementation published in ESP in August 2000 as one of the "beaten path" approaches (although this implementation is already much simplified compared to the OMG state machine meta-model). You see, such implementation falls out more or less automatically from a standard object-oriented analysis (OOA). OOA prescribes to create a class for every key concept in the problem domain, so you end up with a State class. However, states objects require memory, need to be initialized, don't behave correctly under inheritance of entire state machines, and are otherwise a burden to the client programmer. The state machine implementation published in the book "Practical Statecharts in C/C++" is entirely different. At the time I stumbled at this representation (at first for classical FSMs) I considered it a major breakthrough. Arguably, the most natural (and the fastest!) mapping from state-behavior to code is through an address of the state-related code (pointer-to-function in C). If you think about it, behavior *is* the code (a reactive system "behaves" only by executing code). You don't really need an indirection layer of State objects. Interestingly, such implementation of state machine deeply resembles implementation of polymorphism in C++ (virtual tables stuff). I believe that this is not just a coincidence. Polymorphism really means different *behaviors* at different times, and this is exactly what's happening in a state machine. In short, I think that departure from the standard OOA results in this case in much tighter code with unbeatable performance and minimal memory footprint (a state machine is just a pointer-to-function). Additionally, the signature of a hierarchical state handler (returning the superstate) is really a novelty here. This simple "trick" allows to extend a long-known assembly-language jump-table technique of coding state machines to efficiently implement state hierarchy. The technique is superior, because it so naturally maps to real microprocessors (you need to look at the assembly level output to really appreciate this, I show an example on page 74). -- Miro (miro@quantum-leaps.com) ------------------------------------------------------------------------------ ------------------------------------------------------------------------------ C+ QF tip: Init your static vars Gavin Haentjens posted 8/18/03 8:03 PM Just wanted to give a tip to anyone porting the C+ version of the QF to their processor: Make sure your static variables are initialized to 0. This may very well be a standard good programming practice that I didn't know about. If your static variables are not initalized to 0, then you will need to find some way to explicitly initialize all of the transitions in the objects, which as far as I can tell, is nontrivial. For now I should be okay initializing all static vars, but it does create a problem with the part of my code that used to check (and then initialize) a memory location after every reset to determine whether the processor was without power prior to the reset. By the way, in case someone was interested in exchanging ideas, I'm trying to port the QF to an Infineon C167 using the foreground/background scenario (no RTOS). -Gavin ------------------------------------------------------------------------------ miro posted 8/19/03 5:30 PM Hi Gavin, according to the C Standard, all uninitialized static variables are (must be) initialized to zero before calling main(). Typically, all uninitialized static objects are placed in a BSS section, which is zeroed out before calling main(). This is important, because both C+ and the HSM implementations *rely* on this initialization. In C+, implicit zeroing out static variables is important for correct initialization of virtual tables. In the HSM implementation, zeroing out the static Tran objects is important for the "static transition" optimization (see Section 4.4.3 in my book). You bring an important point, though. In embedded systems, zeroing out the BSS section(s) is often in the hands of the programmers, who must often fiddle with the initialization sequence. It is important to perform correct initialization of the BSS each and every time the system goes through reset! This can be sometimes tricky (e.g., when you perform only an incomplete reset, known as "hot start"). Various reset sequences can be quite involved and clearly are beyond the scope of this short reply. However, if your chip/board has a watchdog, it's often the best way to perform a clean hardware reset (including resetting the peripherals and setting the chip selects. (To use the watchdog for reset, simply program it to expire immediately). Thanks for bringing this point up, --Miro (miro@quantum-leaps.com) ------------------------------------------------------------------------------ Henry Choi posted 8/20/03 5:11 PM Dear Gavin, I too ran into the uninitialized variable problem when I ported QF to 8051, which I've given to Miro. I think it makes sense for QF to initialize those variables to 0 no matter what. If you ever get a hold of my 8051 port, you will see many places where BSS initialization caused problems for me. For example, in case you haven't discovered this yet, the static Tran_ t in Q_TRAN macro body must also be initialized to {{0,0,0,0,0,0,0}, 0} to avoid "weird" problems. I am tempted to provide my 8051 port, but as my port contains a few fixes for the as yet unconfirmed bugs, I think it's better if Miro takes a look first. Now, may I ask you why you have decided to use the foreground/background scenario? On 8051, I had no choice but to use that, as the compiler refused to pass more than 1 pointer in a function call through a function pointer, which is the underpinning of state transition in QF. But if you have no such restriction (what compiler are you using?), would you be interested in using the QF native port (which might be called QuantumOS)? It will allow a truly deterministic, preemptive real-time application, and will soon be available under commercial licensing terms. Looking forward to hearing your thoughts, -Henry http://www.quantum-leaps.com/qf/native.htm QuantumOS ------------------------------------------------------------------------------ ------------------------------------------------------------------------------ Limiting memory used by transitions Gavin Haentjens posted 8/22/03 10:13 PM In my application, memory needed for transitions has become an issue. Each transition requires 34 bytes (although it could be less if I decreased the max transition steps down from 8). A possible work around for this is to use Q_TRAN_DYN() for transitions that are simple (transition to self) or ones that occur rarely. Also, if many substates have the same target, they could post reminders to the superstate and let it perform the transition (only one Q_TRAN is required in that case). If anyone has other ideas, I'd be interested in hearing them. -Gavin ------------------------------------------------------------------------------ Henry Choi posted 8/25/03 2:43 AM Gavin, I think you have answered your own question: use Q_TRAN_DYN() instead of Q_TRAN(). I consider Q_TRAN_DYN() a pure optimization, and as such the familiar memory vs. speed rule applies here. Arguments in favor of using Q_TRAN_DYN(): Your QHsm (the children, of course) must be a singleton for you to use Q_TRAN. Maybe it is now, but what about a few months later, or even in the next rev of the product? The guy who takes over the code may be scratching his head when the system exhibits strange behavior just becase he instantiated one more QHsm class. For scalability and maintainability then, Q_TRAN_DYN is the way to go at first. having to keep track of the hard coded limitation on number of transitions is not a good way to prototype the system. You can, for example, crash the QHsmTst example by sending 2 "g" signal in a row, because the number of transitions in that case will blow the hard-coded limit. At least in the current QF implementation, it's not obvious at first that the limit has been breached, so you may spend some time trying to track down the crash. If you can meet all requirements by using Q_TRAN_DYN, you would only be increasing the idle CPU time unused by switching to Q_TRAN. After you meet the correctness requirement with Q_TRAN_DYN, you can then selective optimize the critical path by switching to Q_TRAN. Hope this helps. http://www.quantum-leaps.com/qf/native.htm QF+ ----------------------------------------------------------------------------- Teemu Karevaara posted 8/26/03 2:11 PM How come QHsm needs to be singleton if Q_TRAN macro is used? Q_TRAN is intended for static transitions and the transition chain is the same for every instance of QHsm. So once any of the instances makes the transition (and stores the static Tran-field in the statehandler) other instances can use the same transition chain (since they use the same statehandler) ----------------------------------------------------------------------------- miro posted 8/26/03 6:13 PM The use of macro Q_TRAN() doesn't necessarily mean that a state machine must be a singleton. For example, there are five Philosopher active objects, and they all use Q_TRAN(). The issue is more subtle than this. As one reader pointed out to me, if multiple and concurrent instances of the same state machine class are created, the setup of the static transition (the QHamTranStat_() method) can lead to race conditions among the state machines. I have fixed this problem in the second printing of the book. (So, remedy of the potential race condition was the primary reason I slightly changed the implementation of static transitions between the first and the second printing of the book). In the first printing, I used tran->chain[0] to detect if the static transition has been initialized. This can lead to race conditions if you have multiple instances of a given state machine (active object) executing the same transition simultaneously (like the Dining Philosophers), because tran->chain[0] is set *before* the full transition chain is stored, so if a state machine is preempted after setting tran->chain[0], the transition chain might be inconsistent (incomplete). To remedy this, I decided to use the LS-bit of the tran->actions attribute to indicate if a static transition has been initialized. This attribute is set only *after* the complete transition chain (tran->chain) has been recorded. Setting tran->actions is also *atomic* (at least on 16 and 32-bit machines), which evades the race condition. (On 8-bit machines, setting tran->actions should theoretically be surrounded by a critical section). The second motivation for this modification was for me that in C++ the pointer-to-member function is potentially a complex object (see Chapter 6), so the test of (tran->myChain[0] == 0) is more expensive than the test of (tran->actions & 1). One side-effect of this change is that only 7-step transition chains can be stored in the 16-bit tran->actions (the LSB is already used, remember?) That's why tran->chain[] array has shrunk to 7 entries. However, the QHsmTst state machine (Chapter 4) now asserts for transition g from state s211. As it turns out, this transition has 8 steps and overflows the chain[] array (which is correctly caught by the postcondition in QHsmTran_() method). A simple workaround is not to use static transition in this case, but to use Q_TRAN_DYN() macro for this particular transition. Coming back to the potential hazards of the Q_TRAN() macro, they are mostly related to inheriting entire state machines. I've explained the issues best I could in Section 6.3 in Chapter 6. Having said all this, I would agree with Henry Choi that Q_TRAN() should be viewed as an optimization of Q_TRAN_DYN(). For simpler (most common) state transition Q_TRAN_DYN() doesn't incur much overhead. In fact, the algorithm has been specifically designed to handle the most-common cases first with minimal overhead (see Section 4.4.4 and Figure 4.7). The bonus of using Q_TRAN_DYN() is no memory overhead for storing the transition chain, which might be significant in memory-strapped embedded applications. -- Miro (miro@quantum-leaps.com) ------------------------------------------------------------------------------ ------------------------------------------------------------------------------ Linked lists for messages wink posted 9/18/03 6:16 AM Hello all, I'm implementing an embedded system using a significant sub-set of qp features. After reading Miro's book I'm convinced the notion of message passing and active componets would be useful. But there is one thing I didn't like and that is passing messages by copying them into fixed sized queues. So for my project I'm using linked lists. This eliminates any issues of queue sizing and only means I need to worry about having enough messages around, a problem that has been easily managed. It seems to work quite well and I was wondering if others have used this technique or know of reasons it shouldn't be used. Cheers, Wink ------------------------------------------------------------------------------ miro posted 9/23/03 6:06 PM Hi Wink, please note that event passing in the QF does *not* require copying event into the event queues. As I tried to illustrate in Figure 8.6 (Chapter 6 of my book), event queues hold only the *pointers* to the events and not events themselves. The way you use events in the QF is as follows. You first allocate an event (with macro Q_NEW), then you fill the event parameters and finally you publish or post the event. Upon publishing, the event is *not* copied. Rather only the pointer to the event is placed in the event queue. This means that QF implements, in fact, a mechanism of thread-safe sharing of memory that *looks* like event passing. Because event queues store only pointers, they are quite lightweight. However, your idea of incorporating the pointer into events themselves is intriguing. I believe you can get away with singly-linked list, which will cost only one pointer per event. (Please note that this would not be much more memory efficient than the current scheme, because either way you pay the price of one additional pointer per event.) However, what this scheme would buy you is that you don't need to separately size the event queues -- you only need to size the event pools. At this point I don't know quantitatively how the link-list implementation would compare with the current one as far as CPU use is concerned. One disadvantage of the linked-list method that comes to my mind is that you could not insert an event into several event queues *simultaneously*. The current multicasting mechanism of QF does not require this, but I'm contemplating the possibility of changing that. Events should not be modified after publishing (they are passed as const to the state handlers), so you should safely post the *same* event into multiple event queues. This would solve the problem of possible change in event order that can occur with the current multicasting scheme (which I describe in Section 8.5.3). -- Miro (miro@quantum-leaps.com) ------------------------------------------------------------------------------ wink posted 9/24/03 6:09 AM I understand that you only put pointers in the queue, but I wasn't looking at a space problem, but infact trying to solve the "... don't need to separately size the event queues -- you only need to size the event pools.". I viewed this as a significant problem and the linked lists solves it quite nicely. In the environments I'm using memory tends to not be a problem and I just didn't like having to guess in advance the size of a queue, hence link-lists. Also, in the current implementation when an event is removed from the queue the message is "owned" by the SM that removed it. So, if desired the SM can "reuse" the message and would typically use it as the message it might need to generate. This works well but it does mean that messages can easily get lost, so the programmer must be VERY careful:) For that reason I've thought about removing that "feature", but in reality I can only request the programmer not reuse and can't realy enforce it, so I've taken the pragmatic approach and I let the programmer hang themselves if they want. I also, happen to use doubly linked lists since I already had such a library and there was no compelling reason to make another library. (I try to adhere to some XP principles and try to "minimize" extra work, until it's actually a problem). Thanks for the response, Wink ------------------------------------------------------------------------------ ------------------------------------------------------------------------------ Problem with QF timers John O. posted 10/20/03 7:12 PM Hello, I am running into a problem with the timers implemented in the QF. Specifically, it has to do with using the QTimerDisarm() method. This method only sets the number of remaining ticks in the timer to 1, and sets the signal to the "empty" signal. Thus, disarming the timer doesn't really disarm it. It only makes it expire one tick later. This is all fine and well, until a timer is disarmed, and then subsequently restarted before another tick can complete (it asserts under these conditions since the timer is still in use). On my system, my tick rate is one second (reducing it would help reduce the problem but would never eliminate it). Is there a way to truly disarm a timer, so there aren't any requirements about how long you wait before you can actually access the timer again? This seems like a potentially big problem with the timer subsystem. Oh yeah....just so it doesn't seem like I'm only harping on a problem, I have successfully used the QF for the last nine months or so under Linux, and really like it. Thanks for the help, John ------------------------------------------------------------------------------ miro (Moderator) posted 10/29/03 7:09 PM Hi John, I haven't been quite happy with the QTimer class for quite a while now. As you point out, disarming a timer is done by a "trick" to turn it into a one-shot timer that should expire by the next tick. This is to avoid a potentially indeterministic scanning through an (open-ended) list of timers, which must be done in a critical section. Also, the precondition to disarming the timer (i.e., that the timer must be armed) seems to strong. I found it often useful to disarm a timer upon exit from a state, and sometimes the timer was already expired. In short, I've changed and hopefully improved the QTimer class. I've been using this new class for more than half a year now and it works just fine. I've added a new section to the website that describes the new developments of QF(please check http://www.quantum-leaps.com/qf/ code#QFNew). Among others, you'll find there code to download. I hope this helps, --Miro (miro@quantum-leaps.com) ------------------------------------------------------------------------------ ------------------------------------------------------------------------------ Transistion algorithm and debug of HSM's Christopher Meisner posted 12/11/03 11:18 AM Hi All First of all "Practical Statecharts ...." is a realy great book. Two topics i would like to discuss are the algorithm for state transistions and debug of HSM's. I personnaly found the algorithm for state transistions complex. It started to bug me that there was not one but several different cases that had to be considered. I the came up with the following: 1) Find level of nesting for src and dst state (simply count) 2) Back up state with deepest nesting recording entry or exit path respectively until src and dst are at same level. 3) Find LCA (now simple iteration) 4) Do transistion. I will provide some source code if anybody is interested. Second topic. Only having a function pointer as a state variable clealy is optimal but.. When developing realtime embedded software for Telecom appliactions one of the essentiel tools is a real time trace tool. Our tool logs all message between tasks. Off cause when implementing a FSM/HSM framework you also want to be able to log state transistions. I have not found any really good solution of implementing this in the framework with having to add code to the actual HSM implementation because there is no state Id. or other value that is easy for humans to decode (function pointers are not :-) ) Any ideas? Thanks for Input Christop Meisner Senior Coordinator, Software RTX Telecom A/S http://www.rtx.dk ------------------------------------------------------------------------------ Iain McInnes posted 12/15/03 12:29 AM Hi, Christopher. I have come to exactly the same conclusion as you. Yes, in my next app, I will almost certainly add sufficient instrumentation so that I can log the events and transitions. Allowing the state information to grow beyond a simple pointer, we can add: - State name for trace purposes. - The hierarchical level of the state. As you said, knowing the levels of source and destination makes the transition algorithm much simpler. - The identity of the enclosing state. While sending an null event is elegant, directly storing the enclosing state makes the transition algorithm more efficient. One issue, of course, is that this information is known to the client (subclass) of the HSM. The implementation that I am thinking of requires the client to provide an array of struct with the above information. The state variable then becomes an index into that array. Iain. Christopher Meisner posted 12/15/03 5:20 PM -------------------------------------------------------------------------------- Hi Iain, Miro's orginally idea of making the HSM implementation code-centric is a great idea. HSM's implemented by lookup tables are a pain to code and maintain. They do however offer some advantages. The "optimum" solution has many facets :-). The best i have come up with for debugging QF HSM is for the Clint HSM to provide a lookup table providing a MAP between state handler and State Id. (as enum or string or both depending on what you like and how much space you can use for debug code. I think a compromise is to add a state object containg name for debug/trace and a link to parent state. Christopher http://www.rtx.dk ------------------------------------------------------------------------------ miro (Moderator) posted 12/15/03 6:55 PM The algorithm for taking a state transition (i.e., executing the right sequence of exit and entry actions as well as initial transitions) can obviously be made much smaller. For example, I published such an implementation in ESC ("State Oriented Programming", August 2000). The main point of the implementation published in "Practical Statecharts in C/C++" is that it is more optimal. This implementation handles the most common transition topologies (such as peer-to-peer) explicitly in the most optimal way. (All these lowest-order transition topologies are enlisted in Figure 4.7 on page 112.) In practice, the lowest-order topologies account for 90+ percent of all transitions. I believe that a slight complication of the QHsm::tran() method is worth speeding up these 90% of cases. As to representing states as objects, I already described my position in the book. The issue is RAM. Please remember that my goal here is a truly practical solution for *embedded* systems. From the other discussion thread (QF "lite") it should be clear how precious RAM is in smaller embedded projects. State objects would use up this precious RAM in no time. In contract, state handlers use only ROM. Regarding instrumentation, you are all right. Instrumentation of a state machine is often invaluable. In fact, a hierarchical state machine is ideal for adding such instrumentation. Here innovativeness has no limits. You can use entry/exit actions to print execution logs, you can easily build real-time sequence diagrams, you can drive external pins and "see" the state changes on the oscilloscope at real time, and so much more. (Actually, that's exactly what CASE tools do...) The problem is that instrumentation always adds overhead. In a generic implementation I could not add such overhead, because it will be not acceptable for all systems. You guys use the code now in particular situations, so you can judge for yourself what kind of overhead is acceptable in your case. Then you can then go ahead and add instrumentation, perhaps directly to QHsm::tran() and QHsm::dispatch(). If anybody finds out particularly "cool" instrumentation, please let me know or publish it in this forum. Maybe others will benefit from it too. Cheers, --Miro (miro@quantum-leaps.com) ------------------------------------------------------------------------------ Iain McInnes posted 12/16/03 10:59 AM Thanks, Miro. I completely agree with your comments about instrumentation - including the fact that there is no "one size fits all". Two things that always seem to be true about embedded systems - there is never enough memory to store log and trace information; and there is never enough bandwidth in the instrumentation port to get the events off the device fast enough. One solution that I like is to combine both of these: Capture events in a log, and have a dedicated process (could be an active object !) who'se job is to empty the buffer through the diagnostic port. My current platform is Linux, and so I am positively spoiled with the syslog facilities that are available. One thing that I routinely do is to add profiling to the event dispatch. Its easy to create some timer macros which read a timer register, and compute elapsed time. Then, I allocate a budget for each active object, which can be stored as a property of the QActive class. Lastly, REQUIRE() that the measured dispatch time never exceeds the budget. I believe that continuously measuring execution times is the only way to be confident that the requirements are always met. I normally write the timing macros like assert, in such a way that they can be turned off before final testing and shipping - it would be nice to leave them in, but it can be hard to justify the extra overhead in the delivered code. I have some reasonably portable code that does the timing - I'll forward it if anybody is interested. ------------------------------------------------------------------------------ Christopher Meisner posted 12/16/03 11:00 AM Hi Miro Adding a state object / (or struct in a non OO implementation) does not necessarily have to be instansiated in RAM. This off cause requires that the topology of the HSM is static. In fact we might be able to save RAM because we could reduce the state variable to an id. Which could be 8 bits for small and reasonable sized HSM's. The penalty is const code space. Currently I am investigating both table based implementation and QF like HSM's. From my initial conclusion it seems that table based HSM's can be implemented with less code but are a pain / almost mpossible to code manually with out a tool and are even worse maintaining. HSM's are perfectly code centric which is what we want and the code penalty is acceptable. Just need to find a way to add the trace functionality in the framework which i what we require as we do not want to have to add debug code manually to each HSM. Christopher http://www.rtx.dk ############################################################################## Topic: State Machine Semantics and State Machine Design Author: Miro Samek (Moderator) posted 1/12/04 3:27 AM This discussion thread contains postings related to state machine semantics and using state machines to solving concrete problems. ------------------------------------------------------------------------------ parallel states Mark posted 8/4/03 2:38 PM Im very much impressed by the HSM design pattern that you present. But there is one thing that is not clear to me. That is how it supports parallel states. ------------------------------------------------------------------------------ miro posted 8/4/03 5:43 PM Hi Mark, if by "parallel states" you mean orthogonal regions then the HSM pattern of QF doesn't support it. I discuss the matter in conjunction with the "Orthogonal Component" state design pattern in Chapter 5 of "PSiCC". The ROOM method (as described by Bran Selic at al.) takes similar tack on this issue (please see the appendix in the ROOM book devoted to comparison between ROOM-charts and Harel statecharts). -- Miro (miro@quantum-leaps.com) ------------------------------------------------------------------------------ basic question Mountain Bikin Guy posted 12/11/03 5:05 AM I recently ordered "Practical Statecharts in C/C++" but it has not yet arrived. In the mean time, I have a basic question I hope someone can help me with. I am designing a simple state machine to model a real world situation with 5 possible states. However, instead of the usual clear final state, I have a situation where states 4 and 5 both signify valid end states. I'm not sure how to deal with this. Any advice is appreciated. In both states 4 and 5, control can transition to either state 2 or to another device (another state machine). So there is no difference from this vantage point. However, devices interacting with this device need to make decisions based on whether this state machine is in state 4 or state 5. That information forms the basis for a decision that could influence whether control transitions to this state 2 or to the other device. What is the standard technique for dealing with this? I'm sure this is a common issue that has a well-known solution. I just don't know what it is. Anyone have any advice? Thanks! Mountain (copies to dshiel@yahoo.com appreciated) ------------------------------------------------------------------------------ miro (Moderator) posted 12/15/03 7:13 PM Yeah, I believe that your problem is indeed pretty common. The issue is related to maintaining state consistency across all state machines comprising the system, something I call the "system-wide" state. The "dining philosopher" example from the book illustrate some aspects of this problem. The Philosopher objects and the Table object must coordinate their state. The right way to achieve it is to exchange notification events whenever a state of one object changes and some other state machine object in the system should "know" about it (e.g., a Philosopher is done eating). The wrong way is to check the state of the peer object directly (perhaps by calling isState() method). The most important aspect of QF that facilitates maintaining the consistent "system-wide" state is the guaranteed event delivery (that’s why QF asserts if an event cannot be enqueued). That way, the notification events are never lost. --Miro (miro@quantum-leaps.com) ------------------------------------------------------------------------------ Mountain Bikin Guy posted 12/17/03 3:54 AM Thanks for your reply Miro. Your book just arrived today from Amazon, so I can finally start reading it! I realize the solution to my question is not simple, but instead requires properly designing the statechart. I look forward to more reading in your book! Regards, Mountain ------------------------------------------------------------------------------ Behavioral Inheritance question Mountain Bikin Guy posted 12/30/03 0:02 AM 1. Say a substate overrides (redefines) handling of a certain event. How can it also take advantage of the superstate's generic handling at the same time? In an OO language, the overriding method would perform some actions and call the base class method. How can we (properly) do that with state event handlers? 2. Say we have some deeply nested states. Say we want to have a guaranteed action on exit from one of these deeply nested substate (call it 'dns'). We also want a similar (or identical) exit action from the superstate of all these substates. How can we avoid repeating the exit action twice in the situation where we are in the 'dns' state and exit entirely out of the superstate. State Machines from state table edd posted 1/9/04 5:04 PM hello Dr Miro, in the december issue of your column in C++ User journal, you mention that you do not like to derive state machine from state tables, how then do you come up with all the required states needed in a formal method rather based on experience or gut feeling? regards ------------------------------------------------------------------------------ State Machines from state table Tedd posted 1/9/04 5:04 PM hello Dr Miro, in the december issue of your column in C++ User journal, you mention that you do not like to derive state machine from state tables, how then do you come up with all the required states needed in a formal method rather based on experience or gut feeling? regards http://www.quantum-leaps.com ------------------------------------------------------------------------------ Holt posted 4/25/04 11:00 PM Part of the system I am working on requires the use of a small 2 line 8 character per line display. The LCD is a parallel device and to send it a command or write data to it basically requires that you write a value to a register and wait say 10ms. So the action of writing a register and waiting 10ms is a very common action when communicating to the LCD and for the sake of this conversation let's just refer to this action as sending the LCD a command. The intialization of the LCD requires that I send a defined sequence of commands to the LCD. Sometimes the same command may be repeated multiple times. Once the LCD has been initialized it's just a matter of waiting for the application to request that a sequence of commands be sent to the LCD. I started with an approach in which I was basically creating a state machine in which one command corresponded to a state. The state would write the particular command to the register in the entry action then set up a one shot timeout to transition to the next state (10ms) for the next command to send the LCD. This was my approach for the intialization, but I noticed that this was not a very scalable solution. I guess I'm looking for a solution which utilizes a substate which writes a single command to a register and performs the 10ms wait while the rest of the active object feeds the commands to be written to this substate. I'm thinking this is probably a common problem and I'm just looking for any ideas that people may have. Or maybe a different perspective which simplifies the solution. Thanks, Holt ------------------------------------------------------------------------------ Miro Samek posted 4/29/04 0:44 AM Holt, Your situation is indeed quite common, although your LCD access "protocol" is probably too simple to benefit from the generic solution that I use in such cases. In your case each command to the LCD could be modeled simply as a state, which upon entry would write w value to the LCD register and arm a 10ms one-shot timer. The timeout would cause transition to the next state (next command) etc. A more general solution for such communication protocols (perhaps consisting of many steps, timeouts, retransmissions, etc.) is to use the "Orthogonal Component" state pattern (see Chapter 5 in "PSiCC"). The protocol is modeled as a component state machine that encapsulates the details of communication. The container dispatches the communication request event to the component and waits for the notification from the component when the transaction completes. While waiting for the notification, the container dispatches all communication-related events (such as timeouts) to the component, because the component doesn't have its own event queue and relies on the event queue of its container. Upon completion of the whole transaction, the component notifies the container by dispatching a COMPLETE event, at which time the container proceeds to another state. Please note that the container doesn’t need to "know" the details of the protocol, only when the whole transaction completes. Also, the container can easily reuse component's state machine from many different states, so you don't need to repeat the same, possibly complex, sequences of states in the component's state machine. Finally, the container can manage multiple transactions in parallel (each transaction handled by separate component). Typically, the dispatching of events to the protocol components is implemented at the highest level states of the container, so all substates inherit the behavior and don't need to "remember" to dispatch events to various components. Obviously, this pattern is an overkill in your case, because your transaction completes when the 10ms timer expires and there are no other steps to handle by a "LCD" component. Regards, --Miro ------------------------------------------------------------------------------ Brent Arias posted 6/18/04 9:26 PM Dr Samek, Two issues: (1) What is the justification for keeping init() as a seperate function from tran()? (2) Why does QHSM not permit figure 5.4(a)? Your note on page 90 appealed to "simplicity," though I don't see how it is simpler. Somewhere I think I've read a more elaborate defense of your restrictions related to these items, but I can't remember where I read it. Nevertheless, the tran() function waits until the target state is reached, and then begins iteratively sending INIT signals to permit further "initial" transitions. Perfect. This appears to be all the functionality I'd ever need (no need for a seperate init() function). Indeed, for a moment please imagine the following: assume my initial pseudo-state is properly initialized (with my current state set to the top state) and then I initialize the statechart of figure 4.3 by calling tran(s11). This alternate approach I think accomplishes the same intended result (and prevents me from ever needing to use the reminder pattern for certain initial transitions -page 143). Please advise me of the errors in my thinking. Thank you. Brent http://www.ariasamp.net ------------------------------------------------------------------------------ miro (Moderator) posted 6/21/04 4:58 PM Good questions. (1) In principle you're right. The top-most initial transition (section 4.15 in "PSiCC") could be, in principle, implemented with the tran() method. However, the init() method gives the client programmer the opportunity of performing initialization, because it "executes" the initial pseudo-state, which in turn calls Q_INIT(). In Exercise 4.2 I present an alternative design, which relies on a virtual function initial() rather than the concept of an initial pseudostate (the code implementing this design is available from the CD as the answer to Exercise 4.2). Please also refer to pages 127-128 for explanation why two macros Q_INIT() and Q_TRAN() are used. (2) This restriction is really only for ease of implementation. Please note that the natural navigability in this implementation is only from substates to superstates (a substate returns a superstate if it doesn't handle an event). This means that "drilling" down the hierarchy is expensive, because you go "against" the natural direction. By restricting the initial transition to go only one level deep I don't need to test how many nesting levels have been crossed in order to find out which entry actions to execute (see the implementation of the trai() method). Best regards, --Miro ------------------------------------------------------------------------------ Brent Arias posted 6/21/04 10:16 PM Yes, after studying the code more carefully I concluded init() is seperate and distinct in implementation from tran()...so that less computational work is done to achieve the same result. Another benefit of the init() implementation (which is partly re-implemented at the end of tran()), is that it forces "correctness" related to "initial transitions." Put differently, if I used tran() "as is" to perform an "initial transition," I could potentially transition to peers or superstates - which would violate the premise of an "initial transition." As a result of this investigation, it intrigues me that a given leaf state of the QHSM is minimally the "head" of a singly linked list (each state returns its parent), but when you introduce Q_INIT() calls into the "list" of states, then it implicitly becomes a doubly-linked list (which init() exploits). Still, from pages 127-128 which you referred me to, there is something I disagree with. The text says "Using Q_TRAN() in initial transitions would lead to recursive invocation of the underlying QHsm::tranStat() method (the transition chain includes drilling into the state hierarchy with initial transitions)". You see, if I was willing to compromise efficiency for the sake of flexibility (ala. permitting figure 5.4(a) to be legal), then this is what I would do: 1) eliminate the init() function but keep Q_INIT() with a broadened contract (detailed in #2). 2) re-implement the very tail-end of the tran() "inLCA:" code segment of page 114 (which handles initial transitions) so that Q_INIT() can target **grandchildren** in addition to immediate children! Yes, this approach would inefficiently perform twice the computation of the current "inLCA:" code segment, but it also means that there otherwise is no "recursive invocation of the underlying QHsm::tranState() method" since there would no longer be the same **single-step** "drilling" as before. Yes all substate "entry" handlers would still get called properly, and yes an ASSERT could be levied to ensure it is indeed a child or *grandchild* targeted by Q_INIT(). Congruently with this implementation, an "init" signal would *not* be sent to each transitory substate (as it is in the current implementation) because it would no longer be necessary or desireable. Furthermore, the very first transition of a "tran() only" state-machine would still involve the initial pseudo-state, but the initial pseudo-state **would not** make a call to Q_INIT(). Instead the initial pseudo-state handler would be empty (unless extended state initialization was desired). Ergo, this proposed revision to the tran() function would be using its central work-horse mechanism (listing 4:10, lines 1-74) for reaching the initial target state. Perhaps this alternate approach would be "simpler" for those who aren't concerned with loss of performance (e.g. GPP developer's, or non-RT applications). Indeed, loss of performance is the only drawback I can envision (which admittedly would be unacceptable for many developers). I'm curious how much of these thoughts you might agree with or disagree with. Thanks, Brent http://www.ariasamp.net ------------------------------------------------------------------------------ Brent Arias posted 6/21/04 11:37 PM Dr. Samek, A thought occurred to me: consider the notion of a "completion event with priority." It would be implemented like this: case MyEventHandler: tran(MyStatePointer); if (MyCompletionCondition) { dispatch(MyCompletionEvent); } return 0; ... yes I realize this violates the policy that no code should be added to an event handler after a call to tran(), but it seems like this would be a fairly clean way to address a "completion event with priority" scenerio. In other words, this approach assumes you want a given "completion event" to be received by the newly identified state - before other events from the queue are dispatched. Nevertheless, are these particular semantics too barbaric to take seriously? -Brent http://www.ariasamp.net ------------------------------------------------------------------------------ Sreenivas posted 6/24/04 8:06 AM I'm trying to convert a flat state machine that controls an optical line card into an HSM using QF. The current state machine is implemented using tables. When the line card is first created, a CREATE signal transitions the line card from NEE (Non-Existence of Entity) state to one of several possible target states as shown in the table below. Current State (PST+SST), Signal Received, Target State (PST+SST) ----------------------------------------------- NEE+NEE, CREATE, OOS-AU+DGN NEE+NEE, CREATE-N-CARD-MISSING, OOS-AU+UEQ NEE+NEE, CREATE-N-SWVRMM, OOS-AU+MEA NEE+NEE, CREATE-N-BOOT-FAIL, OOS-AU+FLT Before the state table is looked up, the received CREATE signal could further be "enhanced" to one of - 1. CREATE-N-CARD-MISSING, if card is unplugged 2. CREATE-N-SWVRMM, if software version is mismatched 3. CREATE-N-BOOT-FAIL, if card can't boot The enhancement is determined by an ENUM written to the database by another application. 1. The Line Card is an Active Object. NEE and OOS-AU are its peer-level states. DGN, UEQ, MEA & FLT form the sub-states of OOS-AU. Is this a good HSM model? Are there any alternatives? 2. When transitioning from NEE to OOS-AU, should I just replace the enhanced signals with a guard and conditional transitions? Isn't there a more elegant solution? Any suggestions are appreciated. Sreenivas ------------------------------------------------------------------------------ Sreenivas posted 6/25/04 3:59 AM My state machine follows the Telcordia GR-1093 "Generic State Requirements for Network Elements" model. Object State = Primary state + Secondary state Primary State = Primary Service State (IS or OOS) + Primary Service State Qualifier (NR, ANR, AU, MA, AUMA) Secondary State = One or more Secondary Service State Qualifiers (SGEO, MT, FLT, MEA, etc.) Examples of object states are - OOS-AU, SGEO OOS-MA, MT OOS-AUMA, SGEO, MT OOS-AUMA, SGEO, FLT, MT SGEO & FLT can only appear with AU. MA can only appear with MT. Consider the following state hierarchies - Level-1: OOS Level-2: AU Level-3: SGEO, FLT Level-1: OOS Level-2: MA Level-3: MT How do I represent AUMA in this hierarchy? If I make AUMA a separate substate (below OOS), I will have to replicate all substates under AU and MA and their associated transitions in AUMA. AUMA can contain all the secondary service state qualifiers of both AU and MA. I don't want to use multiple inheritance; but even if I did, I can only derive AUMA from AU and MA, which means that I will have to replicate the Level-3 substates in AUMA anyway. AUMA is not orthogonal to AU or MA. Since the Telcordia state model is so common, this problem must have been tackled somewhere. Any suggestions, ideas? Thanks, Sreenivas ------------------------------------------------------------------------------ miro (Moderator) posted 6/25/04 4:27 PM Sreenivas, I don't have expertise in your domain to understand the gazillions of acronyms you're using. It seems to me that you're asking very valid questions, that is, how to best *design* a state machine that would correctly capture the desired behavior of your system. Here I can only point you to the very general guidelines regarding event granularity in Section 4.3.2 of "PSiCC" (you talk about "enhanced" signals). Maybe I sound like a broken record, but choosing the right events is absolutely critical if you want to produce good state machine. I don't get your remarks about inheritance in the second of your postings. Do you mean behavioral inheritance (state nesting), or inheritance entire state machines? --Miro ------------------------------------------------------------------------------ Sreenivas posted 6/25/04 7:14 PM Dr. Samek, Please let me restate my problem in a more generic way. -- Consider the following state hierarchies in my HSM: -- b c, d (c & d are sub-states of b) -- n o, p (o & p are sub-states of n) -- b & n are peers (i.e., one is not a sub-state of the other), but are linked by transitions. -- Now consider this hierarchy. -- bn c, d, o, p -- At any given time the object running this state machine can be in one of the following states: -- 1. b or one of b’s sub-states 2. n or one of n’s sub-states 3. bn or a subset of a combination of b’s and n’s sub-states -- It is this 3rd state (bn) that I’m having trouble representing in the HSM. In theory bn is a peer of b & n. -- If I represent bn as a separate state alongside b & n, I will have to replicate all the sub-states (c, d, o & p) inside bn. -- If I use multiple inheritance (behavioral inheritance as described in Section 6.3.2 of PSiCC) and derive bn from b & n, I still would have to replicate c, d, o & p inside bn. (I didn’t find UML notation for MI in PSiCC). -- bn is not orthogonal to b or n because there are lots of transitions between the three of them. -- Please advise. -- Thanks, Sreenivas ------------------------------------------------------------------------------ miro (Moderator) posted 6/26/04 1:05 AM Sreenivas, As you write "bn or a subset of a combination of b’s *and* n’s sub-states", so it seems to me that b and n are AND-states (see Section 2.2.3 in "PSiCC"). In UML, you model such situation with orthogonal regions. In QF, you need to use the "Orthogonal Component" state pattern (see Section 5.4 in "PSiCC"). Please note that the situations (1: b-active) and (2: n-active) could be modeled easily by putting the inactive orthogonal component in an "inactive" state. --Miro ------------------------------------------------------------------------------ Sreenivas posted 6/27/04 8:45 PM Dr. Samek, Thanks for pointing me in the right direction! Sreenivas Michael ------------------------------------------------------------------------------ Rushton posted 6/29/04 10:35 PM Ooops, sorry posted it as a new topic.. Hi, I have a system consisting of a Container (QActive) which dispatches events to it components (QHsm). The event has an id for the appropriate component in it. The problem is timer events using QTimer, there is no way to specify which component the ttimer event should be dispatched to. I could dispatch it to all components, but that does'nt work with multiple components waiting for a timeout. I need 1. A timer id 2. To be able to specify the event rather than signal ,in QTimer::firein Help! ------------------------------------------------------------------------------ miro (Moderator) posted 6/30/04 4:21 PM Michael, I can relate to your pain. I've run into the same kind of problem a few months ago. I'm addressing this shortcoming of timers more comprehensively in the new version of QF. For now, however, I've prepared a modified QTimer class that you can download from http://www.quantum-leaps.com/qf.code/qf27_cpp_qtimer.ZIP. This version of QTimer *derives* from QEvent instead of just containing a QEvent. This lets you *specialize* QTimers for your needs, say, by adding an ID, like this: struct MyTimer : public QTimer { unsigned char myId; // ...}; So, when you receive a timeout event, you can downcast the event to MyTimer and look into myId. I hope you get a picture.. . Good luck, --Miro P.S. Perhaps a better place for this posting would be the "State Machine and QF Implementation" thread, or the "Help Desk" thread. ------------------------------------------------------------------------------ Michael Rushton posted 6/30/04 7:57 PM Hi, Thanks for that. As I'm running on windows CE i did the following hacks. 1. Replace the queue to use Win32 thread message queues. 2. Replaced QTimer to use Win32 ::SetTimer/::KillTimer 3. Add myTimerId field to QEvent 4. Intercept WM_TIMER messages and place its id in QEvent.myTimerId 5. In my container class I dispatch all events to all components (except Entry, Exit, Empty) I was'nt sure if I'd designed my SM correctly, hence posting it here ------------------------------------------------------------------------------ miro (Moderator) posted 6/30/04 10:10 PM ------------------------------------------------------------------------------ The following thread has been moved here: --Miro Author: John O Topic: Reaction-in-state vs. Self-Transition problem posted 6/30/04 8:40 PM ------------------------------------------------------------------------------ Hello, I recently ran into an odd problem with Statecharts, where I knew EXACTLY how the code should look (if implemented with the HSM engine provided in PSiCC), but I can't figure out how to describe it in a UML statechart properly. Here is the issue: Assume an HSM is currently in state S1. ------- | S1 | ------- Also assume that on reception of event ev1 in S1, I want some code to execute, after which a guard condition is evaluated, and if TRUE takes a transition to S2, and if FALSE, stays in S1. Previously, I would do this with a condition check, like the following: ------------- [else] | | V ev1/ | ------ foo(); --- [flag==1] ------ | S1 |-------->|C|-------------->| S2 | ------ --- ------ On reception of ev1, I'd execute foo(). Then based on the state of flag, I could either go to S2, or back to S1. The problem with this is that the exit/entry conditions for S1 are executed each time through, and this can cause some potential problems. But I can't figure out how to rectify this situation. I came up with another way to do it with guard conditions, which looks like the following: ----------- ev1[flag==1]/ ---------- | S1 | foo(); | S2 | | ev1/ |-------------->| | | foo() | ---------- ----------- ...but this also is questionable, because I don't know what the order of event evaluation will end up being. The C code for this thing is so simple and clean: ... switch(e->sig) { case Q_ENTRY_SIG: entryActions(); return(0); case Q_EXIT_SIG: exitActions(); return(0); case S1: foo(); if (flag==1) Q_TRAN(S2); return(0); } Is there something fundamentally wrong with this? Why can't I figure out a simple way to draw this in UML? Hopeful for an answer... John O. ------------------------------------------------------------------------------ miro (Moderator) posted 6/30/04 10:10 PM John, I know exactly what you're talking about because I run into this problem all the time. Actually, I even wrote about it in my ESP article from August 2000: "In our experience with [GPS] receiver applications we frequently encountered the following situation: in response to a given event, we wished to perform an action (for example, update a digital filter) and then—depending on the state of the filter—potentially take a (conditional) state transition. We did not want to treat the filter update as part of the guard condition because this would add a side effect to the guard (typically a bad idea). The only alternative is to treat the filter update as an action. To this day I'm not absolutely sure how to represent this frequent behavior in a UML-compliant form (and believe me, I've searched all possible resources and asked around). At the risk of going into a "UML jail", here is what I do these days: /----\ | s1 | \----/ | | EVT/foo();... | v O <-- dynamic choice point | | [flag]/... | v /----\ | s2 | \----/ In other words, I use a dynamic choice point (see UML 1.4, page 3-153, Figure 3-81). The action foo() might modify the flag, which is subsequently used as a guard (this part is probably OK). The questionable thing is that the guards on the transition segments leaving the dynamic choice point don't always complement each other. In other words, sometimes the transition doesn't complete, in which case you end up executing only the original action foo(). (So you have only an *internal* transition, without entry and exit actions). Please note, that a complementary to [flag] transition from the dynamic choice point back to "s1" would be a self-transition, which is not what you want to model. As I said, I'm not sure if this notation would be interpreted this way by UML tools, or even if it will not be flagged as a "malformed" state machine. Also, I don't see dynamic choice points in the UML 2.0 Draft, so maybe this notation will not be legitimate in the future... Cheers, --Miro ------------------------------------------------------------------------------ Nick posted 10/6/04 9:27 PM Dr Samek, I am currently trying to port a program I wrote in C for DOS to C++ for WinCE. After reading your book, I thought the QF framework would be perfect. It is a real-time machine control program with a gui interface. Currently, I am thinking I need 4-5 QActive objects. The control logic, display( dialogs, etc), hardware ( custom I/O drivers ), logging ( troubleshooting and diagnostics ), and possibly interrupt handling. Is this how a project of this sort should be divided? In other posts, you state that QActive objects should be used to differentiate between priority levels, which I think fits here. Comments? Also, for my control logic, the machine consists of motors, sensors, and other assemblies ( ie Rotational Axis, Travers Axis ). I intend to make these Component Fsms and Hsms ( modeled after the alarm example). Comments? Lastly, concerning the Component State Pattern, I'm a little confused on how to handle all of my events. Do I need to 'subscribe' to all of my components events in the 'initial' of my control object? Does this then also mean that I need to catch all of the events and dispatch them indiviually there ( in some state of the control object )? void Machine::initial( const QEvent* e ){ QF::subscribe( this, Motor1_sig1 ); QF::subscribe( this, Motor1_sig2 ); QF::subscribe( this, Motor1_sig3 ); QF::subscribe( this, Motor1_sig4 ); QF::subscribe( this, Sensor1_sig1 ); QF::subscribe( this, Sensor1_sig2 ); QF::subscribe( this, Sensor1_sig3 ); QF::subscribe( this, Sensor1_sig4 ); ... Q_INIT( &Machine::Operational );}QSTATE Motor::Operational( const QEvent* e ){ switch( e->sig ) { case Motor1_sig1: case Motor1_sig2: case Motor1_sig3: case Motor1_sig4: Motor1.dispatch( e ); break; case Sensor1_sig1: case Sensor1_sig2: case Sensor1_sig3: case Sensor1_sig4: Sensor1.dispatch( e ); break; ... }} Is that how it's supposed to work? Is there any other way to avoid having the Machine object know about every signal concerning the Component? Any help is greatly appreciated. Thanks, Nick ------------------------------------------------------------------------------ miro (Moderator) posted 10/9/04 0:07 AM Nick, The 4-5 active objects you're contemplating sounds reasonable to me, although "custom I/O drivers" and "interrupt handling" don't sound like good candidates for active objects. It sounds that you intend to further break down the "control logic" into orthogonal components "sensors" and "motors". While this might be OK, the question is if all can be served by a common priority level (one event queue of the container active object). If not, maybe "sensors" need to be separated from "motors". Regarding the signals to components, the direct application of the "Orthogonal Component" pattern from Chapter 5 in "PSiCC" would be indeed as you describe. Other options are to store the component ID in a specialized event (a base for derivation of all component events), and put dispatching events in a highest-level superstate of the container. Here is some pseudocode: struct CompEvt : public QEvent { QSignal mySig; // signal for subcomponent unsigned char myID; // ID of the recipient }; //... QSTATE Motor::Operational( const QEvent* e ) { switch( e->sig ) { // ... case COMP_SIG: { // event for a component QEvent pe; // create an event "on-the-fly" pe.sig = ((CompEvt const *)e)->sig; // container stores pointers to all components // in the myComp[] array... myComp[((CompEvt const *)e)->myId]->dispatch(&pe); return 0; } // ... } return (QSTATE)&QHsm::top; // highest-level state } The other option could be to override the QActive::run() method and dispatch an event to all orthogonal components in turn (this is how tools generate code for orthogonal regions). Here is some pseudocode: void Motor::run() { for (;;) { // get event e from the queue dispatch(e); // dispatch to the container state machine myMotors.dispatch(e); // dispatch to motors component mySensors.dispatch(e); // dispatch to sensors component } } Depending on the complexity of your application, however, I'd recommend to stick to the simplest solution, which is probably the "Orthogonal Component". --Miro ------------------------------------------------------------------------------ Jonathan Kaye posted 10/27/04 3:26 AM This is in response to Nick's issue (post prior to last one), not John's. I would handle this somewhat differently, but it would require extending the basic design of the QHsm (I think along the lines of what Miro suggests in the book, but I don't quite remember now). I would have the foo() method post a new event (for flag being set) if it is determined that a transition should occur. So the transition trigger out of S1 would be the flag-being-set event, whereas the trigger for executing foo() is whatever EV it originally was. -jonathan http://www.FlashSim.com ------------------------------------------------------------------------------ Markus posted 11/16/04 12:46 AM this is in response to John's issue. If you want to get it in a UML statechart I would suggest following change: you have to split s1 in a superstate ss1 with the entry and exit actions and substate sub1 with 2 transitions: if flag is false: an self-transition with action foo() (which is a internal transition for the superstate so no exit and entry actions are done) if flag is true: a transition to s2 and action foo() ------------------------------------------------------------------------------ Markus posted 11/16/04 1:07 PM It sounds like here was already a discussion about so-called completion transitions (or transitions without event-triggering) but I can't find a thread. I'm very interested if someybody knows a good solution to have the feature of transitions in HSM without event-triggering. Thanks --Markus ------------------------------------------------------------------------------ Nils Thorell posted 11/18/04 8:40 AM What about table driven state machines? Each submachine in a separate table. It gives you a better picture of the entire machine at one glance. What are the drawbacks?