Alternatives to explicit stacks in RTOS-removal excercise?

Question

In an embedded application programmed on C on ARM7 (with portability requirements), currently using a commercial priority-based preemptive RTOS, we need to remove that RTOS and any RTOS dependency per customer mandate. We have 8 tasks using many HW interfaces, sleep statements, I2C communications. As it is, the SW makes good use of RTOS features for simplification of the code, though timing requirements would be manageable without an RTOS.

Several functions, including routines called in many places currently implement sequences of blocking (for that thread) calls to I2c driver functions, sleep statements, etc. Based on the premise that polling on I2C calls / sleep is not acceptable for customers, such calls must then be non-blocking and return. The issue of course is to "come back" to the "statement", possibly 4 calls down from top-level task entry, when I2C completes or sleep time has elapsed.

I'm converging towards a hierarchical state machine design for each task, with a simple scheduler on top. But handling several routines, which used to make sequences of then-blocking calls and now become each a state machine, which can get called in several places and at different function call depths, seems to necessitate an explicit stack feature for each task, so that each time I start a sub-state-machine, I can allocate the states for that process and push them on the "state-stack" of that task, so that the next scheduler call to that task will be able to go down all the hierarchical states to continue processing where it "left off".

Can you see other design architectures applicable to the issue, considerations for fast porting of the code to a non-preemptive paradigm, or point to thought-enriching resources and discussions about "RTOS-removal" techniques and designs?

---

The three answers all together paint a good picture of state machine-based development relevancy and the associated tools to avoid re-inventing the wheel. Our customers won't take any kind of license, including GPL. From the answers it seems that there is no way around caching states if one wants to use hierarchical state machines without RTOS and with polling calls prohibited. As hierarchical SM help a lot porting the existing code by conserving its structure (function calls to routines become invocation of sub-state machines), I will go that way, using the provided tools as good examples. - Thanks.

Answer 1

Using a tool, such as IAR visualState, you can generate code for hierarchical state machines without separate stacks. There is a freebie SMC that is a bit less efficient, with fewer features, and that doesn't support the pretty UML StateChart pictures.

You can also hand code state machines as functions with switch statements and static variables to hold the state.

There are lightweight state machine based pseudo-threading libraries that do this using C macros. Check out protothreads

Answer 2

I would highly recommend looking at Miro Samek's Quantum programming framework. He has one of the most efficient HSM's out there that runs on a lot of platforms such as the ARM7. He also has various levels of complexity of the framework to suit your needs. I would recommend grabbing his book called Practical StateCharts in C/C++ as well. He has a hierarchical state machine in both C and C++. The beauty of this framework is that it's not to hard to go from UML or state diagrams to actual code with some degree of efficiency. This framework can be run as it's own scheduler or used along side an RTOS.

I have actually implemented my own HSM in C++ for one of my company's home grown RTOS with some success. I used a lot of Samek's design principles, but not his code due to GPL (free version) and pricing for commercial license (non-GPL).

Answer 3

Have you checked out Adam Dunkels' Protothreads? He calls them "Lightweight, Stackless Threads in C"

Rather than re-invent the wheel, I'll quote a tad from the protothreads site directly in-line here:

Protothreads are extremely lightweight stackless threads designed for severely memory constrained systems, such as small embedded systems or wireless sensor network nodes. Protothreads provide linear code execution for event-driven systems implemented in C. Protothreads can be used with or without an underlying operating system to provide blocking event-handlers. Protothreads provide sequential flow of control without complex state machines or full multi-threading.

I've used Protothreads & Samek's QP HSMs -- they're both good solutions for problems in overlapping domains. For this I'd probably lean towards protothreads.

You mentioned eliminating the commercial RTOS. Wondering if that's because of code space, cost, engineer learning curves, performance... could you just replace the RTOS with one of the (many) free ones? I guess not but it doesn't hurt to ask.

P.S. Dunkels also has a great website with a lot of useful resources & software for embedded developers - check it out (Contiki, protocol stacks, etc..)

Answer 4

I would as well go for the Quantum Programming Framework!