Creating Time-Consistent Loops for Embedded Systems

In an embedded system there are typically four main ways to architect the code: Simple loop, foreground-background, cyclic executive, and RTOS. In this article I will look at how to create a simple main loop with a time-consistent execution period, similar to what a cyclic executive does.

A cyclic executive uses the concept of major and minor cycles to insure that tasks execute within specific time intervals and at consistent rates. In a cyclic executive there is usually a primary time interval, called the major cycle, and within the major cycle there may be multiple minor cycles. The minor cycles may execute the same set of task for each iteration of the major cycle, or they may be different tasks, depending on the current state of the system. The minimum execution time is determined by the shortest minor cycle, and the maximum allowable time is the duration of the major cycle. It can get a lot more complicated than this, with task selection tables and deferred operations spanning multiple minor cycles, but I won’t delve into that here.

If you look up “cyclic executive” on Wikipedia what you will find is an article that claims that the main loop scheme employed for programming an Arduino is a cyclic executive. Well, no, not really. The example is just a simple loop with some time delays. As presented it may, or may not, be able to hold a consistent cycle time, depending on what is going on in the loop. A cyclic executive is designed to hold consistent timing–it is a hard real-time programming paradigm. A simple loop with a time delay does not meet that criteria.

The figure below shows the situation with a loop that uses only a fixed time delay:

cycle_times1

Each iteration of the loop, the t1, t2, and t3 sections, will call functions f1, f2, and f3 in turn. The t1, t2, and t3 “frames” are iterations of the major cycle. Because the delay at the end of the loop is fixed any variation in the execution times of the functions will change the total time of the major cycle, as you can see when the time used for the functions varies. This arrangement is not time stable.

In some real-time systems, such as control or instrumentation applications, it is essential that the system perform some operation (or operations) at a specific rate, and that the time between the actions does not vary (in other words, it is not “late”). A system that digitizes an analog input is a good example of this type of application. If the data is read and converted at inconsistent times, then the resulting data will contain time errors. When the data is read back at a consistent rate the output will appear to exhibit “jitter” or “flutter”. Another example is a sensor for stopping a system should an error condition arise. If the input data acquisition is inconsistent, then the error event might be missed or occur too late, and bad things could result because of the missed deadline.

Now, in reality, we would want to use a timer-generated interrupt to do analog input conversion, and for a simple system that may be fine (this would fall into the foreground-background class of real-time systems–the interrupt is the foreground, and the background is the whatever happens when the data acquisition interrupt isn’t active–I’ll cover those in another article). But in some cases we may want to make sure that other things happen with a consistent time period, such as updating a display.

One way to make a loop more robust in terms of timing is to employ a variable length delay in the loop. This works by loading a variable with the maximum permissible time (in milliseconds or maybe microseconds) at the start of the loop, and then subtracting the current time from that value at the end of the loop after all the functions within the loop have been called. The remainder is the amount of the time to delay before starting the loop again so the major cycle time is constant (assuming, of course, that no function exhibits a latency that causes the major cycle to miss its deadline). Assuming no interrupts are active, this results in the first function in the loop should always occur at a fixed rate.

Here’s an example in pseudo-code:

variable end-loop
variable time-start
variable time-end

constant major-time

WHILE NOT end-loop DO
    time-start = CALL current-time() + major-time

    CALL function1()
    CALL function2()
    CALL function3()

    time-end = CALL current-time() - time-start
    DELAY time-end
ENDWHILE

The constant “major-time” is the target time period for the loop. I used a variable for the remaining time (time-end) because you might want to do something with that value. For example, if time-end <= 0 then the loop has exceeded its allowable time interval. Perhaps you might want to discard an acquired data value if the overrun is greater than some allowable tolerance, or perhaps you could reduce the time of the next iteration of the main loop to compensate for the overrun and attempt to restore the synchronization of the system.

Graphically the situation described above looks like this:

cycle_times2

You can take things a step further by incorporating the notion of minor cycles into the loop. This, in effect, increases the granularity of the timing, and it works like this:

variable end-loop
variable time-start
variable time-end
variable time-cycle1
variable time-cycle2
variable time-cycle3

constant major-time
constant minor-time1
constant minor-time2
constant minor-time3

WHILE NOT end-loop DO
    time-start = CALL current-time() + major-time
    time-cycle1 = CALL current-time() + minor-time1
    time-cycle2 = CALL current-time() + minor-time2
    time-cycle3 = CALL current-time() + minor-time3

    CALL function1()
    time-sub = CALL current-time() - time-cycle1
    IF time-sub > 0 THEN
        DELAY time-sub
    ENDIF

    CALL function2()
    time-sub = CALL current-time() - time-cycle2
    IF time-sub > 0 THEN
        DELAY time-sub
    ENDIF

    CALL function3()
    time-sub = CALL current-time() - time-cycle3
    IF time-sub > 0 THEN
        DELAY time-sub
    ENDIF

    time-end = CALL current-time() - time-start
    DELAY time-end
ENDWHILE

The constants minor-time1, minor-time2, and minor-time3 define the maximum allowable times for each of the functions. Now the major cycle time is simply the sum of the minor cycle times. Graphically the result would look like this:

cycle_times3

tc1, tc2, and tc3 are the minor cycles within the major cycle (t1, t2, and t3). Note that the end delays, td1, td2, and td3, are all equal in this example so long as none of the minor cycles is late. The tricky part is selecting minor cycle times that are long enough to allow for variations in the execution latency of each of the functions. If the system needs to handle interrupts then the minor cycle times can be increased slightly and the interrupt handlers made to execute as quickly as possible. They would typically do little more than set a flag and perhaps save an input value, and then a fourth minor cycle, tc4, would become active in the td space if a flag is set. As long as the major cycle time is sufficient to allow a timely response to the interrupt it can all fit within the major cycle time.

I usually place the least time-variant function first (f1), and the function most likely to exhibit variable latency at the end of the execution order (f3). This helps to keep the execution start points (the vertical arrows) consistent, with the delay at the end of the loop serving as a buffer so that the odds of overrunning the major cycle time are reduced.

At this point we now have the basics of a cyclic executive. It will execute a set of tasks (functions) with consistent timing, and with some minor modifications it can handle interrupts on an as-needed basis. It does not support dynamic task selection, where tasks may be exchanged with others within the major cycle based on the current execution state, nor does it employ rate-monotonic priority assignments. For many small embedded systems those capabilities are not often called for, and just having consistent timing is sufficient.

Advertisements

0 Responses to “Creating Time-Consistent Loops for Embedded Systems”



  1. Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s





%d bloggers like this: