techniques for writing non blocking code

[tggzzz]

One way of achieving a deterministic and a robust system is to use time-triggered software architecture:

https://www.safetty.net/products/publications/pttes

In a time-triggered system there are no interrupts which would interrupt the program execution. There may be a timer-based, deterministic interrupt which will run the actual program. The main program loop will consist only of while (1) loop with the sleep() function which will keep the system in a low-power mode when it is not executing the code. The system is built using state machines and the program will be run to completion within each timer tick.

I've worked with systems written using techniques like those described in that book and found the pervasive use of state machines makes the code tedious to write and maintain.

Writing the code is usually a trivial part of the implementation. Deciding what needs to be done, how to do it, and then ensuring that it does it takes far more time and brain power. Validation and verification is usually much more awkward than writing code.

FSMs come with important side benefits

• they force you to think about corner cases before running the code
• if the specification is in the form of an FSM, seeing a correspondence between the spec and code is very helpful initially, during commissioning and during maintenance/enhancement
• they provide easy hooks for figuring out what the system is doing and why: just record the sequence of states and events plus when they've occurred. And with care that can be left in the production system too.
• if the implementation technique is remotely sensible, once a fault is identified it is easy to see where the change needs to be made (not always the case!)

I've used that in anger; in one production system I was able to rapidly demonstrate that another company's code wasn't doing what it needed to do. That avoided recrimination and lawsuits.

Since everything is run from a timer interrupt, you have to maintain state yourself between each task invocation and you have to make sure that each task (and each group that runs from the same timer interrupt) doesn't take longer to execute than the timer period. Except for the very first task run when the timer tick interrupt is entered, all other tasks will experience scheduling jitter because the time they start running depends on how long all of the tasks ahead of them in the queue run, and this can vary from one tick to the next.

That's rather in the nature of code that shares a single resource, in this case a processor.

All-in-all, I prefer to design embedded systems (except for extremely simple ones) using an RTOS with good task synchronization facilities.

That's valid. Of course - whether or not you realise it - you are creating an FSM implemented using the RTOS facilities. Personally I prefer to go the whole hog and code FSMs explicitly.

And whenever possible I like RTOS features to be implemented in hardware, e.g. http://www.xmos.com/download/private/xCORE-Architecture-Flyer(1.1).pdf

[tggzzz]

yup, with interrupts and tasks competing on shared resources we need mutex (special semaphores) reflecting the relative urgency of these tasks to access the shared resource.

This makes things more complex and more difficult to be analyzed.

Most of the time the combination works fine, and you can believe your system works.  However, very infrequently, it is also possible for an interrupt to occur in the way that it can introduce the perfect scenario of priority inversion and ...

... ops, Shit Happens ... if you aren't aware of consequences, and able to sort it out.

~ ~ ~ ~ ~ ~ ~ ~

interrupts + shared resourced(on mutex) = more cares 

Precisely. Too many embedded developers have never even heard of priority inversion!

Debugging the Mars Pathfinder on the surface of Mars? Wozzat?

[Mechatrommer]

You capture the time-of-arrival of an event in a hardware counter, and read that time when you get around to processing the event.
Modern embedded processors have such facilities built-in and easy-to-use,

what about mcu that doesnt have the feature?

Here's an infamous classic that all embedded software engineers need to understand: https://catless.ncl.ac.uk/Risks/19.49.html#subj1

irrelevant. interrupt routine is not to be blamed. a simple switch to priority inversion parameter value fix everything, interrupt still runs. i would say it has something to do with the complexity of the program and as they put it "HUMAN NATURE, DEADLINE PRESSURE" the real lesson is, dont push your employee too hard. people nowadays have put DEADLINE ahead of HUMAN NATURE, thats the root of all problems. anyway, its irrelevant to this topic, the problem does not apply to simpler project.

interrupts + shared resourced(on mutex) = more cares

true but... DEADLINE = less care..

Debugging the Mars Pathfinder on the surface of Mars? Wozzat?

no, debugging was conducted in simulation on earth from received data. the fix is sending single line interpreted C command to the mars. the lesson, leave your debugging feature intact, how luxurious, it was a beta version.

[legacy]

In micro-robotics (I sometimes help a friend) we use MPUs with built in features like quadrature encoders and dedicated hardware (MPU built-in or inside an external fpga) which helps at motor controlling. These features do their job very well and can reduce the interrupt requests.

Of course you have to go to specialized pieces of hardware, but it's greatly better by several orders of magnitude. At least from my point of view 

[Sal Ammoniac]

Writing the code is usually a trivial part of the implementation. Deciding what needs to be done, how to do it, and then ensuring that it does it takes far more time and brain power. Validation and verification is usually much more awkward than writing code.

By "writing code" I also meant its design, plus I did use the word "maintain" in there too.

FSMs come with important side benefits

Sure, FSMs have benefits, but writing an entire complex application as a series of interacting state machines can quickly get out of hand, especially if more than one person is involved with the development work.

That's rather in the nature of code that shares a single resource, in this case a processor.

True, but I'd rather use facilities provided by the OS than have to worry about such things myself. For instance, every time you add code to one or more tasks running from a timer tick interrupt, you have to ensure that the total execution time is less than the tick period. It's a pain to have to do this manually. Ditto for task latency. Every time tasks in the queue ahead of the one you're working on changes, it changes the relative timing of that task. If timing is critical, this can lead to subtle bugs that are hard to find. With a pre-emptive RTOS, you can arrange the task priorities such that a task that needs to meet a certain timing requirement is only subject to the (usually fixed) context switch time of the OS itself.

All-in-all, I prefer to design embedded systems (except for extremely simple ones) using an RTOS with good task synchronization facilities.

That's valid. Of course - whether or not you realise it - you are creating an FSM implemented using the RTOS facilities. Personally I prefer to go the whole hog and code FSMs explicitly.

Sometimes FSMs are necessary, and in that case a hybrid OS (one that implements regular tasking plus timer queue execution of a list of C functions) can come in handy. You can have the best of both worlds.

And whenever possible I like RTOS features to be implemented in hardware, e.g. http://www.xmos.com/download/private/xCORE-Architecture-Flyer(1.1).pdf

XMOS is an interesting architecture, but rather niche, with only one vendor and one tool set (which sucks if you hate Eclipse like a lot of people do).

[tggzzz]

That xCORE devices are single vendor is a valid concern. however, the xC code can also be run on ARMs, and one of their devices even has one out of eight cores being an ARM.

The architecture is unique, but I don't think it is niche. I think it confronts head-on the problems that are arising with modern semiconductor technology, and deals with them very effectively. Most architecture and tools skirt around the modern problems, wishing they weren't there, and blaming the developer for not understanding all the arcane caveats in the specification and implementation. (Yes C/C++, I'm pointing a finger at you!)

As for not liking Eclipse, I don't think that should be a valid criticsm - just us whatever tool is necessary to get the job done. Even Visual Studio is OK,if unremarkable

[Sal Ammoniac]

The architecture is unique, but I don't think it is niche. I think it confronts head-on the problems that are arising with modern semiconductor technology, and deals with them very effectively. Most architecture and tools skirt around the modern problems, wishing they weren't there, and blaming the developer for not understanding all the arcane caveats in the specification and implementation.

Yet millions of embedded applications are successfully developed every year with traditional architectures. XMOS seems to have only made inroads in the voice and audio arenas. Perhaps I'll consider them if they start to become more mainstream.

[legacy]

Yet millions of embedded applications are successfully developed every year with traditional architectures.

so, this theory smells interesting and millions of flies are right because they fly on a common poop on the grass 

[NorthGuy]

Concerning Interrupts vs FSM vs RTOS.

If you want the lower possible latency, you have to use interrupts.

If you don't need urgency them either FSM or cooperative scheduler or RTOS will work. They all will produce jitter and won't have perfect timing. It is impossible to have perfect timing on a single CPU for several tasks. Nor do you need it.

FSM will be more work, but if you have lots of tasks which you have already written for FSM, you can often mix them freely, so it might be actually the easiest way.

RTOS consumes lots of resources and forces you to do lots of manual synchronization between tasks. It cannnot run on smaller MCUs at all.

Cooperative scheduler is much more lightweight and at the same time more efficient. Would be my best choice most of the time.

Of course you can combine these 3 with interrupts - the highest priority task is driven by interrupts, but everything else forms the mix where the timing is less important.

In case of the button, there's no need for urgency and the timing is very relaxed. Therefore there are lots of different way to handle it, and it really doesn't matter what you choose. The most important thing is to make sure it doesn't interfere with more urgent tasks (if any).

[Mechatrommer]

Yet millions of embedded applications are successfully developed every year with traditional architectures.

so, this theory smells interesting and millions of flies are right because they fly on a common poop on the grass 

what he's saying is... we dont need xmos to make things work. you can keep how holy the xmos to yourself. "poop" is a bad analogy, "cake" should be the good one. btw, we can always outsource tasks to another mcu doing particular/specialized task like many i2c chips do. so the main process only need to ask and the external mcu may provide the data in silver plater through i2c/spi (controlled event), no problem, this stuff has many solutions to it, rather than limiting oneself to one particular architecture or school of thought.

[tggzzz]

Concerning Interrupts vs FSM vs RTOS.

If you want the lower possible latency, you have to use interrupts.

What is the guaranteed latency using interrupts? Make sure you include the effects of any caches and already being inside an ISR.

I'll bet it is orders of magnitude worse than with the xCORE processors. The £12 board I am using will respond to 8 different inputs simultaneously within <100ns. Guaranteed.

If you don't need urgency them either FSM or cooperative scheduler or RTOS will work. They all will produce jitter and won't have perfect timing. It is impossible to have perfect timing on a single CPU for several tasks. Nor do you need it.

I am getting guaranteed perfect timing for two hard real time inputs (capturing and counting the transitions in two 62.5Mb/s data streams) plus front panel buttons and LCD, plus USB comms with a PC.

That application requires zero jitter, and is achieving it; naturally other applications don't require that and zero jitter can't be achieved on most architectures.

RTOS consumes lots of resources and forces you to do lots of manual synchronization between tasks. It cannnot run on smaller MCUs at all.

The xCORE "RTOS" is effectively in hardware; zero resources.

Cooperative scheduler is much more lightweight and at the same time more efficient. Would be my best choice most of the time.

Agreed, within your constraints.

[tggzzz]

The architecture is unique, but I don't think it is niche. I think it confronts head-on the problems that are arising with modern semiconductor technology, and deals with them very effectively. Most architecture and tools skirt around the modern problems, wishing they weren't there, and blaming the developer for not understanding all the arcane caveats in the specification and implementation.

Yet millions of embedded applications are successfully developed every year with traditional architectures. XMOS seems to have only made inroads in the voice and audio arenas. Perhaps I'll consider them if they start to become more mainstream.

Nobody would claim that XMOS is the only game in town. But it is the only one I have seen directly addressing using multiple independent cores. There aren't millions of such applications, partly there are many infrequent latent bugs when using C/C++ and shared memory.

As for mainstream, that's difficult to quantify. Certainly XMOS has big powerful backers and lots of investment, and they have been developing and shipping this architecture for a decade (based on fundamental concepts from 30/40 years ago).

[Sal Ammoniac]

Nobody would claim that XMOS is the only game in town. But it is the only one I have seen directly addressing using multiple independent cores. There aren't millions of such applications, partly there are many infrequent latent bugs when using C/C++ and shared memory.

Some applications do need the timing guarantees that XMOS supports, but those are probably in the minority. For such applications I've usually resorted to pairing a microcontroller with an FPGA where the FPGA does the heavy lifting and provides more flexibility than XMOS can. XMOS, as an integrated solution, is probably more cost effective for high-volume products.

As for mainstream, that's difficult to quantify. Certainly XMOS has big powerful backers and lots of investment, and they have been developing and shipping this architecture for a decade (based on fundamental concepts from 30/40 years ago).

Perhaps. I think you're probably referring to the Transputer from the 1980s here. I think David May had something to do with that and the XMOS architecture. The transputer was certainly hyped in its day, but it kind of ran out of steam in the early 1990s and fell off the map. I hope XMOS doesn't suffer that fate.

[Kalvin]

If you don't need urgency them either FSM or cooperative scheduler or RTOS will work. They all will produce jitter and won't have perfect timing. It is impossible to have perfect timing on a single CPU for several tasks. Nor do you need it.

There are some techniques which can be used to reduce or eliminate the task jitter:

"Employing Two “Sandwich Delay” Mechanisms to Enhance Predictability of Embedded Systems Which Use Time-Triggered Co-operative Architectures"
http://file.scirp.org/pdf/JSEA20110700008_45225471.pdf

[Wilksey]

I use a software debounce routine inside a timer, and I have a state machine, several in fact, and the main loop goes through each machine in turn, the timers are interrupt driven and just set flags, if I have multiple buttons / LEDs I will use an array to keep track.

Perhaps a better way is mentioned elsewhere, but that's how I do it and it works for me.

[tggzzz]

Nobody would claim that XMOS is the only game in town. But it is the only one I have seen directly addressing using multiple independent cores. There aren't millions of such applications, partly there are many infrequent latent bugs when using C/C++ and shared memory.

Some applications do need the timing guarantees that XMOS supports, but those are probably in the minority. For such applications I've usually resorted to pairing a microcontroller with an FPGA where the FPGA does the heavy lifting and provides more flexibility than XMOS can. XMOS, as an integrated solution, is probably more cost effective for high-volume products.

I wouldn't disagree with any of that. My attitude is that xCORE is encroaching into FPGA territory, no more.

xCORE/xC is based on CSP, which is a sound tested paradigm for parallel programming: you can even see CSP's influence in Go and Rust.

But my jibe at C/C++ wasn't to do with speed, it was to do with the behaviour that is deliberately left unspecified in those languages, plus their complexity. They were designed for single processors with uniform memory and no caches, and have struggled to produce clean simple behaviour with modern SMP machines. A simple example of that is that the committees have only just got around to creating a memory model specification, and I don't know how well or poorly that is implemented in various compilers (for that minority that can use the latest compilers).

As for mainstream, that's difficult to quantify. Certainly XMOS has big powerful backers and lots of investment, and they have been developing and shipping this architecture for a decade (based on fundamental concepts from 30/40 years ago).

Perhaps. I think you're probably referring to the Transputer from the 1980s here. I think David May had something to do with that and the XMOS architecture. The transputer was certainly hyped in its day, but it kind of ran out of steam in the early 1990s and fell off the map. I hope XMOS doesn't suffer that fate.

Basically yes. XMOS xC and xCORE has been around for a decade, and is continuing to gatheher investment. The Transputer and Occam are from the 80s, and CSP is from the 70s. Not a bad track record!

[NorthGuy]

There are some techniques which can be used to reduce or eliminate the task jitter:

Yes, for example you can run only one task per interrupt. One timer interrupt - you run task one. Second time interrupt - you run task two. And so on. And you repeat this loop over and over again. The jitter will be minimal.

But what is the reason to have less jitter?

The tasks don't need to be called at the exact interval. All they need to do is to meet their timing requirements. For example, if you debounce a button, you want to check the button state every 20 ms, but really anything from 10 to 50 ms will do. Jitter is clearly not a problem here. And if you look at your tasks, many of them can leave with quite significant jitter, and if not then you can use FIFOs, DMA or other methods to relax time requirements.

If you make good use of your chip's peripheral, you don't really need to get to the processing immediately - periphery has buffers, may be able to tolerate significant delays, so jitter will not pose much problems.

Of course, you may have something time critical which cannot tolerate any delays, but you cannot have very many of these, otherwise they will interfere with each other. Such time critical tasks cannot be treated just as others. You have to process them in high priority interrupts, possible write the interrupts in assembler to avoid C prologue/epilogue. There's no techniques which will help you with this - nothing you can do can give your interrupts better latency than your hardware can provide.

[NorthGuy]

I'll bet it is orders of magnitude worse than with the xCORE processors. The £12 board I am using will respond to 8 different inputs simultaneously within <100ns. Guaranteed.

I am getting guaranteed perfect timing for two hard real time inputs (capturing and counting the transitions in two 62.5Mb/s data streams) plus front panel buttons and LCD, plus USB comms with a PC.

Of course, if you have multiple cores they won't interfere with each other. The same way as if I had multiple MCUs on a board where each of them works on its own time-critical task without any interference.

However, the techniques for achieving multitasking in such a system would be completely different than with a single MCU. You don't need to lift a finger to ensure simultaneous action - each CPU does its own job.

Implementing multitasking on a single CPU is a little bit more complicated. You can use several different techniques. These techniques help you avoid adding extra CPUs to your system. IMHO, this thread is about such techniques.

[tggzzz]

There are some techniques which can be used to reduce or eliminate the task jitter:

...
If you make good use of your chip's peripheral, you don't really need to get to the processing immediately - periphery has buffers, may be able to tolerate significant delays, so jitter will not pose much problems.

The extent to which that can be achieved depends on the application, the inputs, and a computer's peripherals.

For the specific case of debouncing a switch, there ought to be peripheral support in an MCU.

Of course, you may have something time critical which cannot tolerate any delays, but you cannot have very many of these, otherwise they will interfere with each other. Such time critical tasks cannot be treated just as others. You have to process them in high priority interrupts, possible write the interrupts in assembler to avoid C prologue/epilogue. There's no techniques which will help you with this - nothing you can do can give your interrupts better latency than your hardware can provide.

You are confusing "time critical" with "fast". The two concepts are orthogonal, and completely different design techniques and implementation techniques are required to address each of them.

[tggzzz]

I'll bet it is orders of magnitude worse than with the xCORE processors. The £12 board I am using will respond to 8 different inputs simultaneously within <100ns. Guaranteed.

I am getting guaranteed perfect timing for two hard real time inputs (capturing and counting the transitions in two 62.5Mb/s data streams) plus front panel buttons and LCD, plus USB comms with a PC.

Of course, if you have multiple cores they won't interfere with each other. The same way as if I had multiple MCUs on a board where each of them works on its own time-critical task without any interference.

However, the techniques for achieving multitasking in such a system would be completely different than with a single MCU. You don't need to lift a finger to ensure simultaneous action - each CPU does its own job.

Implementing multitasking on a single CPU is a little bit more complicated. You can use several different techniques. These techniques help you avoid adding extra CPUs to your system. IMHO, this thread is about such techniques.

I did note write that. I will answer on the basis that you simply messed up the quote delimiters.

You appear not to understand the relevance of the classic "dining philosophers" problem to your position.

Your statements are only true in a limited and uninteresting way. (Plus if you use common implementation techniques they are frequently inapplicable; and people often do just that )

Fundamentally your statement is only true so long as the threads/cores/tasks are independent and to not have to communicate with each other.  When, as happens in all non-trivial systems, one task/thread/core's progress depends on another, then you have time dependency. That leads to jitter and or deadlock/livelock.

And that is why CSP (Communicating Sequential Processes) is so valuable in such systems, whether on single processor or multiprocessor systems, whether in languages that directly support CSP concepts (e.g.xC, Go) or as an architectural design pattern realised in a common language.

[legacy]

as an architectural design pattern realised in a common language.

Exactly the point.
Perhaps those who like the C language will have a shock reading a paper like this 

[Kalvin]

There are some techniques which can be used to reduce or eliminate the task jitter:

Yes, for example you can run only one task per interrupt. One timer interrupt - you run task one. Second time interrupt - you run task two. And so on. And you repeat this loop over and over again. The jitter will be minimal.

But what is the reason to have less jitter?
<snip>

Yes, there are many different techniques one can use to reduce task jitter. I just wanted to post the paper as there were some discussion about task timing jitter. In most application the jitter is not a problem as long as the tasks meet the timing requirements. Obviously there are some applications that require more strict, hard realtime timing and and tolerate only very little jitter, and the techniques presented in the paper address those systems.

Of course, in order to achieve the best performance the on-chip hardware peripherals, dedicated hardware (ie. FPGA etc.) and/or using processor architectures designed for accurate timing purposes (ie. DSP and XMOS) is used when possible.

In some high reliability systems one just cannot use the state of the art compilers, embedded devices, peripheral components and FPGA etc. as they are not certified to be used in high reliability systems. In these systems one has to use the devices that are certified, but these devices may not contain necessary optimized hardware resources and the designers need to use other techniques in order to meet the requirements.

In some systems the cost is the driving force to use the cheapest device possible and use software techniques to meet the requirements. If the manufacturer can reduce device cost $1 for each device manufactured and they manufacture those device in millions, then the financial gains are quite high even if the actual development costs will be somewhat higher.

[tggzzz]

as an architectural design pattern realised in a common language.

Exactly the point.
Perhaps those who like the C language will have a shock reading a paper like this 

C/C++ zealots are often willfully blind, preferring to blame all the developers rather than admit the tool is causing the problems. The C++ FQA is entertaining.

Thanks for the decent reference. Boehm is not a fool, even if he did chase after an "often works but you can't rely on it" GC for C.

I knew the PThreads/C problem existed, based the summation of the statements about what is explictly not defined in C. However, it is useful to have a pointer to a high quality paper bringing the arguments together.

I note the paper referred to a Java-like memory model. I believe a dozen(!) or so years later one has been produced. If so, it will be interesting to see how well it is implemented and how well it works. Based on the C/C++ 99 experience, I'm not going to hold my breath!

[JPortici]

as an architectural design pattern realised in a common language.

Exactly the point.
Perhaps those who like the C language will have a shock reading a paper like this 

not shocking by any means I already pondered on many of the problems described in the paper, and i have never ever used an RTOS or used anything else than C/basic for microcontrollers.
Just state machines and interrupt-enabled code.
one just have to spend a single minute to think and wonder at what would happen if the variable he's using -not in accumulators or onto the stack- changes its value during a functions, because DMA or a piece of code during interrupts altered the memory content... i think it was even mentioned by my high-school (!) teachers once or twice

[tggzzz]

as an architectural design pattern realised in a common language.

Exactly the point.
Perhaps those who like the C language will have a shock reading a paper like this 

not shocking by any means I already pondered on many of the problems described in the paper, and i have never ever used an RTOS or used anything else than C/basic for microcontrollers.
Just state machines and interrupt-enabled code.
one just have to spend a single minute to think and wonder at what would happen if the variable he's using -not in accumulators or onto the stack- changes its value during a functions, because DMA or a piece of code during interrupts altered the memory content... i think it was even mentioned by my high-school (!) teachers once or twice

Good for you It is pleasing always to come across people that think, and to have switched-on high school teachers

Unfortunately it is normal for such considerations to not be understood. All too often people haven't considered it, and/or think "you declare function as an ISR", and/or "the library takes care of that", and/or "that's why you use volatile". As for considering the interactions between L1/L2/L3 caches, main memory and the cores - dream on!

I've heard all of those - more than once