5
$\begingroup$

I have a number of interrupt service routines on an AVR. These include interrupts for USART serial communication, timers, and SPI communication.

For all of these, I use circular queues (using a start and end pointer, without boundary checking).

Some problems start to occur if the AVR starts to get overloaded. The circular queues will lose chunks of data. To solve this, I can reduce the load on the AVR (for example, by skipping some cycles in the timer). However, this is a manual process, where it is reduced if the AVR appears to have problems. This is partly because I do want relatively consistent timer periods.

However, even at 70% average processor load, the queues can fill up randomly by chance.

In case of spurious overloading at times, how can I make this more adaptive to avoid queue overflows?

$\endgroup$
  • 1
    $\begingroup$ I wonder whether this question isn't more suited to the StackOverflow site, than Robotics? $\endgroup$ – Anindo Ghosh Oct 24 '12 at 15:44
  • $\begingroup$ Defiantly a StackOverflow question with the embedded tag. $\endgroup$ – embedded.kyle Oct 24 '12 at 16:34
  • 1
    $\begingroup$ If we are going to try to shunt this off to another site then it would be more appropriate to Programmers Stack Exchange than Stack Overflow as it is a concepts question. As it is, since answers to this with relation to robotics would be different to this question on a non robotic context, I think it's fine here. $\endgroup$ – Mark Booth Oct 24 '12 at 23:56
  • 1
    $\begingroup$ What model AVR? Have you considered running FreeRTOS? It provides built in queue management, and the ability to dynamically prioritize tasks in response to load. $\endgroup$ – Crake Oct 25 '12 at 18:28
  • 4
    $\begingroup$ Guys please stop saying that robot programming questions do not relate to this. cause they do. Believe it or not if you ask this on stackoverflow, you won't get any answer. cause programmers over there hardly know anything about interrupts or avr programming.. Please if you don't know the answer, just go to another question instead of down-voting or voting to close. Thank You. Lets keep the community living.! $\endgroup$ – Miro Markaravanes Oct 25 '12 at 19:30
8
$\begingroup$

It sounds like you're observing the symptom of "lost bytes". There are several different things that can cause an AVR to lose bytes.

It sounds like you are guessing that it's losing bytes when new bytes are coming in while the buffer is full. While there are several remedies to fix or at least ameliorate that particular problem, those approaches are useless and counter-productive if the real cause of the "lost bytes" is something else.

The first thing I would do in your shoes is to set up some sort of "status debug" port that gives me a clue of why exactly bytes have been lost -- at least a status LED. Once you know why bytes are being lost, you can apply the appropriate remedy.

Most modern protocols have some sort of check value at the end of each packet. It's nice if your status debug system can report on the packet goodput rate and the packet error rate -- at least blink a green LED for each validated packet and a red LED for each failed packet check.

Since (especially with radio connections) the occasional corrupted byte is pretty much inevitable, most modern protocols are carefully designed such that if any byte is corrupted or lost, the system will eventually discard that packet, and eventually re-sync and correctly handle future packets.

Bytes lost because the interrupt handler somehow never put them into the buffer

Often bytes are lost because the interrupt handler somehow never put them into the buffer. There are several causes, each with a different remedy: external problems, and internal interrupts turned off too long.

External problems:

  • Line noise causing errors
  • Physical wired connections accidentally getting temporarily unplugged
  • Loss of signal on radio connections

Typically we clip an oscilloscope to the input pin and -- if we're lucky -- we can see the problem and try various techniques to see if that cleans up the signal.

Even when the signal at the input pin looks perfect, we can still have data loss issues.

Immediately after the last bit of a byte comes in a USART or SPI port, normally the interrupt handler for that port is triggered, and that interrupt handler pulls that byte and sticks it into a circular buffer. However, if the interrupts are turned off too long, the next byte to come in that port will inevitably overwriting and losing the first byte -- the interrupt handler for that port never sees that first byte. The four "ways an interrupt handler can be turned off too long" are listed at "What can be the cause of an exceptionally large latency for the UART receive interrupt?".

To fix this problem, you need to get the longest time an interrupt handler is ever turned off to be less than the time to transfer one character. So you must either

  • Reduce the amount of time interrupts are turned off; or
  • Slow down the communication bit rate to increase the time to transfer one character;
  • Or both.

It's very tempting to write the interrupt routine such that, immediately after it puts a byte into the circular buffer, the same interrupt routine then checks to see if it's a complete packet and, if so, completely parse and handle it. Alas, parsing usually takes so long that any further bytes coming in the same or any other port are lost.

We typically fix this by reducing each interrupt handler (and therefore the time interrupts are disabled while processing this handler) to the minimum possible to grab a byte and stick it in the circular buffer and return from interrupt. All the packet-parsing and packet-handling stuff executes with interrupts enabled.

The simplest way is for the main loop (AKA the "background task") to periodically call a function that checks if there is a complete packet in the circular buffer, and if so parse and handle it. Other more complex approaches involve second-level interrupt handlers, nested interrupts, etc.

However, even when the interrupt handler perfectly receives every byte and correctly puts it into the buffer, sometimes a system can still lose bytes from buffer overflow:

Bytes lost from buffer overflow

Many people write packet handlers that don't do anything until the handler sees a complete packet in the buffer -- then the handler processes the entire packet as a whole. That approach overflows the buffer and data is lost if any incoming packet is larger than you are expecting, too big to fit in the buffer -- single-packet overflow.

Even if your buffer is plenty big enough to hold the largest possible packet, sometimes during the time you're processing that packet, the next packet is so large that it overflows the circular queue before your packet-handler gets around to removing the first packet from the queue to make room for future packets -- two-packet overflow.

Is there some way your status debug system could detect and signal if a byte comes in and it has to be thrown away because there's no more room in the queue? The simple solution to both these problems is to increase the size of the buffer to hold at least two maximum-size packets, or somehow change the thing that's sending the packets to send smaller packets -- so two packets will fit in the space you have now.

Sometimes incoming data fills the buffers faster than the packet handler can pull data out of the buffer. Increasing the size of the buffer only briefly delays the problem, and sending smaller packets (but more of them) will probably only make things worse. A real-time system must process incoming data at least as fast as that data can come in; otherwise the processor overload will only make the processor get further and further behind. Is there some way your status debug system could detect and signal this sort of overflow?

If this overflow only happens rarely, perhaps the simplest "solution" (arguably merely a hack) is to handle it in more-or-less the same way you would handle a (hopefully rare) power glitch or loss-of-signal on a radio connection: when an overflow is detected, have the AVR erase the entire buffer and pretend it never received those bytes. Most modern protocols are carefully designed such that, if any packet is lost, the system will eventually re-sync and correctly handle future packets.

To really fix this problem requires somehow making the "time to process a packet" less than "time from the end of one packet to the end of the next packet". so you must either

  • Reduce the bit rate.
  • Modify the sender to give the AVR more time to process a packet -- perhaps unconditionally send 50 additional "dummy bytes" in the packet preamble -- or however many is needed to give the AVR more than enough time to completely process the last packet and get ready for the next packet.
  • Decrease the time to process a packet
  • Or some combination.

The wall-clock time to process a packet involves both the time the AVR spends in actually processing the packet, and also the time the AVR spends doing "other stuff" such as dealing with all the other I/O ports and interrupt handlers.

Some methods of decreasing the time to actually process a packet are:

  • Sometimes it's faster to copy the packet out of the queue into some other buffer for further processing, removing it from the circular queue. It makes the packet-handler simpler if the packet starts at the beginning of that other buffer, so key parts of the packet are a fixed constant offset from the beginning of that buffer. (This has the advantage of making it impossible for the serial interrupt handler, which only writes into the circular queue, to accidentally corrupt that packet after it's been copied to that other buffer.) (This approach lets you use tested and "optimized" and known-good functions that handle numbers represented as ASCII strings of hex digits or decimal digits in consecutive order, which may run faster operating on that linear buffer than "equivalent" functions that also have to deal with the wrap-around split of a circular buffer). This requires both the queue and the other buffer to each be at least the size of the maximum possible packet.
  • Sometimes it's faster to leave the packet in the queue while parsing it and remove it from the queue only after the packet handler is completely done with it.
  • Sometimes a pair of "ping-pong" buffers is faster than a circular queue.
  • Many systems use only a single buffer large enough for the largest possible valid packet, and completely disable interrupts from that port until the interrupt handler has finished with the last packet and is ready for the next packet.
  • Somehow actually do less work per packet.

More general approaches to dealing with situations where "other stuff" is eating so much time that there's not enough time to deal with the packet in the buffer (and may also help reduce the time to actually process the packet):

  • If you're lucky, you can find some algorithmic tweaks to effectively do the same work in fewer cycles.
  • Load-shedding: do less important stuff less often; or perhaps don't do them at all in times of heavy load. (As implemented in the Apollo 11 AGC).
  • yield() more often: if your main loop does fair round-robin cycling between "if we have a complete packet from port 1, handle it" and "if we have a complete packet from port 2, handle it", and the packet parser for either one takes so long that the buffer for the other port overflows, it may help to break the packet parser up into shorter pieces and do only a little processing each time through the main loop, giving the other packet parser a chance to deal with packets before its buffer overflows. Perhaps even consider switching to a pre-emptive task scheduler or a full-up RTOS.
  • yield() less often: sometimes a processor spends more time in "task switching" or "multitasking overhead" than actually doing anything productive.
  • Reduce the time spent processing interrupt handlers. (Preventing Interrupt Overload ). High-frequency pulses on one interrupt line can pause main loop tasks indefinitely. It may be necessary to program each low-priority interrupt handler to recognize high-load situations and completely disable its own particular interrupt before re-enabling global interrupts at its return-from-interrupt instruction, and have the main loop recognize low-load situations and re-enable those interrupts.
  • Increase the clock rate of the processor.
  • Switch to a more powerful processor. A "more powerful" processor is not the same as "a processor with a faster clock rate". You might be able to find a processor that does the same work in fewer cycles than your particular 8-bit AVR -- perhaps some other AVR with specialized peripherals that do work in hardware that you're currently doing in software, freeing up software cycles for other things; or perhaps a 32-bit processor that can do certain tasks in software in fewer cycles than any 8-bit processor.
  • Occasionally in robotics "one big fast processor" is better than lots of little processors: the amount of code and the communication latency to copy a message from one task to another task on the same processor is always much less than to copy that same message from one task to another task on some other processor.
  • Often in robotics it makes things simpler and more "provably correct" to add more processors, perhaps one processor per leg or even one processor per servo. If you have one task per processor, then many of the above potential problems can't ever happen.
$\endgroup$
  • $\begingroup$ Excellent answer David, puts my more general answer to shame. *8') I especially like the gem of advice in the middle which recommends not trying to parse a packet in your interrupt service routine, a mistake that it's easy to make when starting out. $\endgroup$ – Mark Booth Nov 6 '12 at 20:50
3
$\begingroup$

I can't answer specifically for the AVR, but I can offer some more general advice.

Low level

I think you are going to have to prioritise. Look at what you can afford to throw away and what you can afford to process when your system starts to get overloaded. Also, profile your usage to see what data you have coming in when.

For instance, if you have a higher level retry protocol on your serial comms, then when you are overloaded perhaps you could drop incoming serial bytes, leaving it to the retry mechanism to catch up when the CPU has the time.

If you can do this then you are going to want to fail early. When your serial buffer is full, there is no point reading the data from the uart, writing it into your buffer, overwriting existing data - that's just wasting cycles which could be used elsewhere (you are going to have to throw away the partial serial stream anyway). When you experience a serial buffer overrun, just clear the uart without reading it, leave the buffer in it's old state and return, letting the CPU get on with things it can complete successfully.

Alternatively, you could disable interrupts entirely for low priority events.

Profiling your usage can also be very valuable. Lets say you have four 16 byte buffers where one is constantly going into an overrun condition because you are sending 36 byte packets to it, but where the other 3 never have more than 5 or 6 bytes in them at once. In this case it is worth rewriting your buffer code to allow different sized buffers. That way you could allocate 8 bytes each to three streams and 40 bytes for the final stream.

High level

You need to analyse why your buffers randomly fill up by chance. Are you trying to do too much with the data in one go? Could you split that processing up and do several shorter processes rather than one long process.

For instance, if your interrupts normally take up 70% of your CPU and another routine takes up 20% on average, but only needs 10% some of the time and runs out of CPU at others, then breaking up that processing into more predictable, repeatable blocks could be worthwhile, even if it takes more processing power power overall.

Also, if you don't have a higher level retry mechanism, consider implementing one, this would enable low level prioritisation which might otherwise not be possible.

Finally, learn how to optimise for your hardware. Again, profiling can help here. If your ISRs are taking up a significant proportion of your CPU time, every cycle you save is a cycle you can use elsewhere. Don't blindly 'optimise' everywhere, chose your battles.

Profiling will tell you where in your code is most critical so you can put your efforts where it will count (See Is micro-optimisation important when coding?).

$\endgroup$
2
$\begingroup$

First, all processors have limited performance. So the effect could be that the performance is just not good enough for the amount of work you have to do.

The average load is pretty uninteresting for diagnosing lost interrupts. The interesting thing is how many interrupts and therefore how much load on the interrupt service routines are there in peak situations. If the interrupts cause too much calculation that is needed to be done in a fixed amount of time then you need a faster CPU.

With little computing in the ISR and a big buffer, these peaks can be flattened out, but this introduces a delay. If you can decrease the amount of data written into the buffer then a bit more processing in the ISR could pay off.

If your solution is to skip the unimportant(?) processing in the main routine, then you should put more processing into the ISRs. This way the CPU load will go to the ISRs and the main routine will get less. The problem here is that if the processing of one interrupt is ongoing, the next interrupt will be delayed, as its ISR can only run after finishing the other ISR. If this delay is too long then the interrupt will get lost.

So choose the way that is best fitted for your solution. But be aware that: "The only replacement for CPU power is CPU power."

$\endgroup$
  • $\begingroup$ I once worked on a robot with a forth microcontroller, swapping it for another wasn't economically viable, we had squeezed every last ounce of performance out of it and it still wasn't fast enough for some new features we needed. We discovered though that 80% of the chips would run 20% overclocked and this gave us the performance we needed, so we bought twice as many as we needed and screened out the failures. We never had a single warranty return due to CPU failure and it saved us a whole bunch or redevelopment. *8') $\endgroup$ – Mark Booth Nov 9 '12 at 11:30
  • $\begingroup$ Thank you for your answer. My current solution is just to limit the rate at which data is gathered (it is doing analog DAQ, but doing trigonometry, implementing a smoothing filter at the same time, and differentiating - a Savitzky-Golay filter). There may come a time when I won't need to do it anymore - we are planning on getting encoders which won't have the kind of noise which made smoothing necessary. $\endgroup$ – ronalchn Nov 12 '12 at 3:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.