In testing Real-time systems, we typically must answer the question “Will all my tasks complete their work on time … in the worst case?”. In other words, we must assure that all the hard timing deadlines are met. Utilization is the first test. It simply determines what percent of the processor’s capability is used to get all the work done. If Utilization is >100%, you’re in real trouble. Either use a faster, more capable processor, redesign your tasking, or live with the reality that some work will never be done.

To demonstrate the concept, we’ll consider a simple multi-tasking system which runs on a Cyclic Executive.

• Code loops forever at a base periodic rate – the Minor Loop – 10 ms for this example
• Other “tasks” called at integral multiples of the Minor Loop
  • Keypad debouncing task runs every 40ms
  • LCD Update task runs every 100ms

Furthermore, lets say we have painstakingly determined that all the work performed in the Minor Loop requires 5.0 ms in the worst case. Similarly, we have determined that the Keypad task requires 2.0 ms and that the LCD Update requires 1.0 ms. The work is scheduled as indicated in the following diagram.

Every Minor Loop, the processor uses 5ms of it’s available 10ms to execute the Minor Loop tasks. Then, once every 40ms, it takes an additional 2.0ms to process the Keypad task. Lastly, once every 100ms, it needs an additional 1.0ms, on top of whatever else was required, to process the LCD Update task.

The most critical time for the system is when all three tasks must be performed within the same Minor Loop. This occurs at the Least Common Denominator of the periods of tasks: 200ms, in our example. This is referred to as the Major Loop.

Now, to add a dose of reality, we must consider the impact of servicing interrupts. Let’s suppose we have 3 interrupts which we must handle. One of them, Timer Tick, is periodic – it occurs every 1.0 ms. It can be treated just like another task.

The other two interrupts are asynchronous – we don’t know when they’ll arrive. For such Asynchronous Interrupts, we have to determine a worst-case (shortest) inter-arrival time – the fastest that we could ever have to service subsequent interrupt requests. This, in effect, then turns these asynchronous interrupts into a periodic task for our analysis. For our example, the Async Serial Comm interrupt won’t arrive any faster than once in 10ms, and the other Async Interrupt won’t arrive any faster than once every 20ms.

Putting all these together allows us to compute our Utilization as shown in the table. Our analysis shows that we have 32% of the processor’s “horsepower” free – that’s a very comfortable cushion! … Or is it?

In testing, we always must consider the worst case. What happens in the Minor Loop in which all the tasks and all the interrupts coincide, and must be completed with that 10ms time? This answers the question: “Is my system of tasks Schedulable?” As you can see in the chart, during the most critical Minor Loop, we’re much closer to the edge – only a 7% Schedulability cushion! That’s a far cry from the 32% Utilization figure!

In testing real-time systems, computing Utilization may be all that is required for soft deadlines, where the work must be completed on schedule most of the time, or on average. But for hard real-time requirements, computing Utilization is insufficient – you must prove that the critical tasks will always complete on time in the worst case. This requires that a detailed Schedulability analysis is performed. For a simple design like the Cyclic Executive presented here, Schedulability is very straightforward and easily computed. For more complicated systems, such as those using preemptive multitasking designs, the analysis can be much more involved.

For all systems, the usefulness of the analysis is dependent on accurate worst-case execution time data for every task and interrupt in the system. It’s also common to disable interrupts for brief periods, and/or prevent switching to a different task. These “blocking times” also must be accounted for in the Schedulability analysis. Does all of this sound daunting? It needn’t be …. The key is understanding what’s required to analyze your real-time system, design it appropriately, and measure the execution time accurately. Then you’ll be able to declare with confidence that the system will always meet it’s real-time requirements – and that’s a great statement for a Tester to be able to make, isn’t it!