Columns

How To Do It... In C

Practical Schedulers For Real-Time Applications

Robert Ward

Robert Ward is president of R&D Publications and author of Debugging C, an introduction to scientific debugging. He has done consulting work in software engineering and data communications and holds an M.S.C.S. from the University of Kansas.

What Is Real Time?

Real-time is not a synonym for "real-fast". Contrary to popular opinion, making everything "real fast" won't necessarily make a real-time program work correctly. A much better synonym is "on time" since, in a real-time program, certain events must happen at a specific time.

Making input and output events happen "on time" is pretty straightforward if you have only one I/O path to worry about. But real-time programs, especially embedded real-time systems, are often also multi-tasking programs. Most real-world, real-time programs are expected to simulate several pieces of simultaneously operating hardware.

When analyzing a project that is both multi-tasking and real-time, the designer must recognize that some tasks are less urgent than others. For each real-time task, "on time" may have a different meaning, depending upon the time constraints associated with that particular task. A continuously running built-in self-test, for example, usually runs without any time constraints, even if it is testing a real-time system. Some real-time events may need to happen at a specific wall-time; others at a specific interval from some external event. The real-time program must properly balance these varying needs at every instant, under every imaginable combination of input conditions.

This article will show how an appropriate general purpose scheduler can significantly reduce the design complexity in such programs and also significantly increase your confidence in the feasibility of the design even before you write any significant amount of code.

What Is A Scheduler?

A scheduler is simply code that decides which task to perform next. Thus a scheduler can be as simple as the loop in Listing 1. This "slop-cyclic" scheduler cycles repeatedly through each task (cyclic) at a rate that may vary depending upon the time required to execute each task (slop). A "rate-cyclic" scheduler can be almost as simple, as shown in Listing 2. The rate cyclic scheduler cycles through all the tasks at a constant rate of once per clock tick.

If you are accustomed to writing real-time systems as one large loop with input polling and capture code sprinkled throughout the system, it may seem pretentious to describe Listing 1 as a "scheduler." After all, one could argue, the execution sequence is, like the polling loop, just a hard-wired loop — the so-called scheduler just adds calling overhead.

Even this trivial scheduler, though, offers several important advantages. First, all the scheduling information is in one place. If you must alter the code (and the timing relationships between the pieces), you know just where to look to make the necessary scheduling adjustments. For example, if after writing the project, you found that task3() and task4() didn't execute as rapidly as expected, causing task1() to "miss events", you might solve the problem by making the change in Listing 3. Now task1() gets scheduled more than once during the cycle. You can even drop one task into the "middle" of another by breaking one task into several subparts (see task2a() and task2b() in Listing 4) .

With the scheduling code isolated in a single module, the designer also reserves the option to completely change the scheduling mechanism. For example, instead of splitting task2 into two parts (as in Listing 4) , you might obtain the same effect by installing a more sophisticated pre-emptive scheduler like the one we'll develop later in this article.

A distinctly separate scheduler can also make development and testing much easier. You might plan to use a simple loop like Listing 1 to perform initial testing and characterization of your task code and then install a more sophisticated scheduler for final test and production.

Priority & Pre-emption

In the trivial schedulers of Listing 1 - Listing 4, all tasks are of equal importance and the order of task execution is statically determined by how the code is written. This egalitarian approach forces the programmer to adjust for differences among the tasks by adjusting the code, for example by making multiple calls to task1() and by splitting task2() into two parts. If the scheduler were more competent, we wouldn't need to make these coding compromises. What we need is a scheduler that can recognize that some tasks (task1() for example) are more important than others (have higher priority) and that sometimes long tasks like task2() may need to be interrupted (be pre-empted) so that some shorter, more important task can run "on-time". The scheduler should not only recognize these differences, it should be able to dynamically adjust the execution order to accommodate them.

Prioritized scheduling can be accomplished by augmenting the simple slop cyclic scheduler so that it uses a different control structure driven by several "ready" lists. Listing 5 presents the basic structure for a very simple environment where each task is assigned to a different priority level and each ready list consists of a separate flag in the structure ready.

The ready flags are set by an interrupt service routine that captures related input, or by some other task (for example, task2a() would set task2b()'s flag, thereby "scheduling" task2b()).

Listing 5 will schedule events dynamically based on their readiness, but it still lets each task run to completion. The next level of scheduler sophistication, pre-emption, complicates matters considerably, but is still easy to implement once the calling conventions are understood.

The pre-emptive scheduler pre-supposes an environment where virtually all events are serviced by interrupts. These interrupts create natural "break points" at which other tasks can be pre-empted. (Actually, you can get the same effect by sprinkling special calls, gotos and stack manipulations throughout each task, but you won't want to maintain the result.) Each interrupt service routine ends with a call to the scheduler. The scheduler then examines all higher priority ready lists to see if some more urgent task needs to run. If not, the scheduler simply returns, allowing the interrupted task to continue. If there is a more urgent task waiting, the scheduler calls it (see Listing 6) .

This scheduler treats LEVEL1 as the highest level of priority. IDLE tests greater than all other levels.

Listing 6 assumes several conventions and data structures not explicitly shown. The functions push() and pop() manipulate a stack of current priority levels. If you are willing to pass the current priority level as a parameter to every task, and to accept responsibility for always calling the scheduler with the current level's priority as a parameter, you can stack this information implicitly as function parameters.

The function getnext() searches a linked ready list for actions more urgent than the action just interrupted. If a more urgent task is found, getnext() copies its descriptor from the ready list to the next structure. The task is then invoked via a pointer to function.

The assignments marked /*lock*/ in Listing 6 must be executed with interrupts disabled to avoid potential synchronization errors. Before using this code, you must at least bracket these lines with code to disable and enable interrupts. The scheduler must always be called with interrupts enabled — otherwise it will provide only one level of pre-emption and may cause some interrupts to be missed.

This implementation is very stack-intensive. Each interrupt can potentially generate three stack frames for each interrupt (interrupt, interrupt's call to scheduler, scheduler's call to task). In an environment where many interrupts can arrive simultaneously, the stack may expand very rapidly.

Some Design Advice

A real-time design should begin with a careful analysis of the possible events and the relationship among them. The goal is to decouple (with respect to time) as many actions as possible. Decoupling will often greatly increase your ability to service critical events, by allowing the great bulk of the processing to occur in the time between critical events. This analysis should identify the time-critical events (those that really must be done NOW), and prioritize the other events according to their relative criticality. Generally, actions subject to similar constraints should be made members of a priority class and broken into execution units that are small relative to the time-tolerance of the next, more urgent class.

Early in the design analysis, you should compute the probable CPU utilization. If the tasks assigned to the system will consume more than 70 percent of the CPU throughput, you should probably consider the design impractical and either find faster algorithms for certain modules, add additional hardware, or run on a faster CPU. In truly asynchronous environments, a processor utilization of greater than 70 percent greatly increases the likelihood that one of your ready queues will grow to an unmanageable length. You can make an exception to the 70 percent rule if you can prove that your waiting lists will never grow beyond some small fixed length.

The structure of the program will mirror the classification of events. Critical events will be serviced by interrupt handlers, non-critical events will be processed according to their priority by a general-purpose scheduler, and queues will handle communication among the pieces. Since these systems are almost always concurrent, it is imperative that the programmer be comfortable with the issues of deadlock avoidance and shared resource management.

With careful analysis of events and adequate throughput, a simple cyclic scheduler is often adequate. In some applications where some actions consume very large amounts of time compared to the time-tolerance of higher-priority tasks, it may be necessary to implement a pre-emptive scheduler.

A Case Study

Suppose you are to build a real-time system with four major functions:

Table 1 summarizes these specifications and adds estimates for each task's execution time. These execution time estimates can be based on expected code size for each task, on prior experience with similar problems, on padded measurements of execution speeds for certain critical inner loops, or on measurements taken from "prototype" implementations for each task (perhaps written in a high-level language). Since adding a scheduler to the design makes each task a piece of stand-alone code, time spent coding each task for these measurements isn't just wasted. Most of your characterization code can be used in the finished design.

Critical Operations

Capturing a keystroke and (because it shares an interrupt with the keyboard) capturing a block ready indication are the only critical tasks in the system. These will be processed by an interrupt handler with interrupts turned out throughout the service.

Priorities

Level 1. Capturing a data sample, capturing a clock tick and initiating a block write are "nearly" critical. It also makes sense for all three to be handled in the same interrupt service routine. Since they have lower priority than the critical events, interrupts will be enabled during as much of the service routine as possible. Thus the data sampling interrupt routine could be interrupted during its execution. We'll assume that the first 15 µs of this process can't be interrupted. Note that this priority level isn't recognized in the scheduler because it is fully processed in the interrupt handler — I just wanted to show that even interrupt handlers differ in their urgency.

Level 2. The block checksum and sample analysis will be grouped at the next level of priority. The checksum has been broken into several short parts so that it can't "block out" the input analysis for more than a few milliseconds. Each part will schedule its successor after it completes. This ensures the sample analysis will be able to "sneak" in between two parts (the sample analysis is scheduled by an interrupt routine, possibly while the checksum is executing).

Level 3. All clock control and keystroke parsing will be performed at level 3 (or background) activities. Notice that even though none of these events consumes more than 10 ms, if three such events were allowed to be interspersed with level 2 events, the block check would miss its "output deadline."

Level 4. This level is reserved for pure "waiting" activities, such as waiting for the clock stepping motor to time-out.

Listing 7 presents the structure of the entire application in a C-like psuedo code. This code would use the scheduler of Listing 6.

Throughput Requirements

Processor utilization is computed by combining the frequency estimates and time consumed estimates from Table 1. Table 2 shows that this design falls well within the 70 percent rule, and should probably be feasible.

Total utilization isn't the only prerequisite to feasibility, however. The design must also meet the response time restrictions. Response time performance is evaluated by calculating the worst time performance for each event. Worst case analysis should always include the possibility that the program has just responded to some interrupt or that multiple copies of the analyzed interrupt arrive at the closest interval possible. Table 3 analyzes the design's latency when performing a process control cycle.

Additional Ideas

When a variety of events happen at non-harmonic intervals, consider implementing a timer scheduling queue. Events can specify the timing of other events by putting a timer programming request in a special queue.

If your system has multiple interrupting events and no vectored interrupts, restrict the interrupt handler to just capturing the interrupt and queueing it. The highest priority task then examines the information in this queue and schedules other work.

To make certain two tasks of equal priority get fair scheduling, partition them into pieces (as with the checksum above) and let each piece upon completion schedule its successor. This scheme will allow the shorter tasks to be scheduled. This trick can often eliminate the need for a pre-emptive scheduler.

Conclusion

An appropriate scheduler can greatly simplify real-time designs by allowing the individual task modules to remain ignorant of their interaction with other real-time tasks. A distinct scheduler also simplifies debugging and performance analysis. If you aren't comfortable with the concurrency issues implicit with handling the ready queues and other shared resources in the dynamic schedulers, you can still use the static versions and preserve the option of incorporating a more complex scheduler when the project eventually demands it.

Little schedulers like those developed here are usually all the real-time support a controller needs. They offer distinct advantages over a commercial real-time kernel: the scheduler is smaller, simpler to understand, comes complete with source code, and is much less expensive.