Charles B. Allison has been working with microprocessor hardware and firmware in embedded systems since 1975. He has a B.S. in physics and an M.B.A.. Charles has a microprocessor consulting business, Allison Technical Services, where he has been developing embedded control and monitoring products since 1984. Charles can be reached through his BBS/FAX line at (713) 777-4746 or his company, ATS, 8343 Carvel, Houston, TX 77036.
Introduction
Many programmers use commercial real-time executives. Some use public domain execs while others use in-house systems developed over the years. Few programmers still try to roll their own. The presence of exec debugging tools and factory support virtually dictate the use of commercial real-time executives when feasible.
Still, there are two factors in favor of the home grown. First, it is often a very good idea to understand what is inside that little black box and building one can be very instructive. Second, one size of anything never truly fits all. That size will be too small for some applications and too large for others.
The purpose of this article is to introduce the reader to the basic concepts behind a real-time task executive by providing a very simple preemptive task executive. Tiny Exec (Listing 1 and Listing 2) is written in C. It is useful for many low-complexity applications using either standalone or MS-DOS-based platforms. Understanding this executive can help you to understand the much more complex commercially-available executives. I will attempt to accomplish this feat by first describing Tiny Exec, contrasting its approach with more complex commercial execs, and then discuss some of the considerations of using MS-DOS and its typical C compilers for real-time programming applications.
Real-time programming is based on a preemptive programming approach. Preemptive means that the processor can decide to pause execution of a section of the code and begin running another section.
The simplest example of a preemptive program is a main loop with a hardware interrupt. Whenever an interrupt occurs, the processor will stop executing the main loop and start the interrupt routine. The interrupt routine will run until completion and then return to the point in the main program where it left off. The processor will automatically save its internal flags to the stack. The interrupt program will then execute instructions that save to the stack any registers that may be modified during the interrupt routine.
Tiny Exec
Tiny Exec is a very small and rudimentary real-time executive. It is easy to rewrite in assembly language because of its simplicity. Tiny Exec may be run using a faster interrupt time than the normal MS-DOS 18.2 Hz clock rate. In some MS-DOS-based cases it may be run at rates up to around 180 Hz. In non-DOS embedded designs it is possible to run beyond 200 Hz. In Tiny Exec, this interrupt routine is based upon the hardware timer at interrupt vector 0x08.
Rather than running multiple programs, Tiny Exec runs multiple routines inside a single program. A routine may consist of a single C function or one that calls other C functions. There are two basic types of routines, task routines and timer routines. They differ only slightly.
Timer routines must be short since they are run as extensions to the timer interrupt and run while interrupts are disabled. Task routines are executed with interrupts enabled. They do not have the severe time constraints of the timer routines. Often, a timer routine is used to request that a task be run. Timer and task routines are defined by their presence in the timer and task arrays, respectively.
The task and timer lists each consist of two arrays. The first array for tasks consists of task flags, which indicate the state of the task, and integer down-counters for timers. The second arrays are function pointers containing the execution addresses of the various tasks and timers. Tiny Exec hard codes the number of tasks and timers along with their execution addresses. This hard coding eliminates much complexity.
Timer operation consists of setting the counter to a non-zero value. The counter is then decremented once each interrupt until it reaches zero. During the interrupt in which a timer decrements from one to zero, the associated timer routine is executed as a part of the timer interrupt.
Task routines do the processing work. These are run with interrupts enabled and may run many clock ticks. Each task has a priority which is its position in the task list. A lower priority task will be preempted and the higher priority task run whenever that higher priority task is ready to run. A higher priority task must be run to completion before Tiny Exec returns back to start or finishes a lower priority task.
The lowest priority task is called the background. In Tiny Exec, it is a loop in the main function that is permanantly in the run state. The background task may do nothing or may be used to do a multitude of operations that are not as time critical as those of higher priority tasks. I have often used the background task as a timing loop to determine the percentage of time still available for additional processing functions. This timing function is processor speed dependent since it relies on execution times for a counting loop and delay loop.
Task States
Tasks may exist in one of three states: REQUESTED, INPROCESS, and SUSPENDED. Requested indicates that the task will be started at the first available opportunity, i.e., no other higher priority tasks in operation. SUSPENDED means that the task is neither REQUESTED nor is it currently being run. INPROCESS indicates that the task has been started but not yet finished execution. More than one task may be INPROCESS at any point in time. Only the highest priority task whose state is INPROCESS will be executing at that particular moment.
Tasks, except for the background task, are normally in the SUSPENDED state. A task is REQUESTED by setting its REQUESTED bit. During each timer interrupt, the task list is scanned from highest priority to lowest looking for either the REQUESTED task bit or the INPROCESS task bit. The first time either one is found causes the exec to end its search and take the appropriate action.
For a task INPROCESS, the appropriate action is to return to that task. By definition, doing an interrupt return from the timer interrupt will return the program to that point. Since it was currently running the highest priority task which was INPROCESS when the timer interrupt occurred, the program simply does an interrupt return to where it was before the interrupt.
If the task exec finds a REQUESTED task before it finds an INPROCESS flag, the program has a higher priority task that must be executed before it can return to the lower priority task, which was INPROCESS. At this point, it saves the current task number, enables interrupts, and calls the newly REQUESTED higher priority task.
This new higher priority task may or may not run to completion before the next timer interrupt. If it finishes before the next interrupt, it returns back to the timer interrupt at the point where it was called. This point is in the exec loop that will continue to look at lower priority tasks for REQUESTED and INPROCESS flag bits. If the new task does not complete before the next timer interrupt then it will be interrupted and the process described above begins again.
At some point in time, the task executive will again reach the original task which was INPROCESS and the executive will do a return interrupt to continue its execution. Eventually, the task exec will return to the background loop which is always INPROCESS.
This approach allows the C compiler's stack and interrupt handling abilities to be used to take care of all the context switching necessary for the preemptive multi-tasking. Contexts of all preempted lower priority tasks reside on the system stack, waiting to be popped back off on a return interrupt to that task.
Commercial Execs
There are several significant differences between Tiny Exec and the common real-time execs available today. Many common features found in most execs are not in Tiny Exec. Some of these features are missing because the fundamental approach is a bit different from the typical real-time executive. Others are not included in an attempt to keep the presentation simple.
Commercial real-time executives offer many functions. There are so many features and functions that often there are several different ways to do most anything. Having so many options can be a joy or a nightmare.
The most fundamental difference between Tiny Exec and the typical real-time exec deals with context switching. All information from preempted tasks resides on the main program stack. Because of this, Tiny Exec is a "last in first out," or LIFO, application. Only the most recent preempted task on the stack may be continued and no lower priority tasks may be run until all higher priority tasks have completed. Also, the task wait function must be handled differently.
Typical real-time executives have a more sophisticated preemptive approach. Either separate stacks are used with the different tasks or adequate space on the program stack is initially reserved for each task. During the exec's operation, context switching from one task to another will include switching the stack pointer besides the usual registers. This approach exceeds the capability of an interrupt function and enters the realm of assembly-language subroutines and compiler-specific coding.
Most commercial executives are much more elegant than Tiny Exec in their handling of tasks and timers. In Tiny Exec, all timers and tasks are tested during the interrupt. That can be a significant waste of time in larger applications. Commercial executives normally create dynamic lists for active tasks and timers. Their approach makes great sense for these larger applications, but it can become a burden to the simple ones. It also makes for more difficulty in understanding.
Programming With Tiny Exec
Programming with Tiny Exec requires a little bit of planning and design. Real-time programs tend to be more complex than the usual big loop programs.
A real-time system has two types of processing-time constraints. It has an average processing ability, which is what can be processed during a long period of time compared to the length of instruction times and interrupt routines. It also has an instantaneous-peak-processing requirement associated with latency times for interrupts and for time-critical task execution. A workable design must meet both of these criteria.
The basic design requirement is to break the overall problem into tasks and timers suitable for running under Tiny Exec. The main function contains program setup actions and the background task. This background task contains functions that either have minimal real-time significance or contain operations that are long compared to other activities. Calculations and setup for printing hourly reports is an example of a task well suited for the background.
Higher priority tasks should be much shorter and have much more stringent time requirements than do lower priority ones. The typical real-time exec provides a wait function for tasks that cannot simply execute from beginning to end without delays. Because of the context-switch design of Tiny Exec, tasks that need to wait, either for time or external events, must be broken apart. The break up may be either into tasks or subtasks. Using subtasks keeps the number of task flags low and reduces the amount of timer-interrupt overhead necessary to return to lower priority tasks. In very simple applications this may not be of concern so multiple tasks and flags may be used instead of an internal breakup of the task into subtasks.
Another resource saving idea is to run slower timers in a task. Every timer in the system probably does not require the immediate access to execution as do the high speed timers. These slower ones can be done as high priority tasks with much reduced timing constraints. Depending on the speed requirements, hundreds of slower speed timers may be implemented.
One serious programming consideration is stack size. Since, in principle, most of the tasks could all be INPROCESS, there can be a much larger burden placed on its size than in simple big loop programs. You can estimate stack size by adding the memory used by local variables and function levels together for all tasks that could be running simultaneously and then adding extra stack memory for interrupt routines.
A Tiny Exec application consists of one linked object module. This means there is only one copy of the runtime library functions used. Most compilers have runtime library functions that are not reentrant. None of the floating-point math routines or I/O routines should be assumed to be reentrant. Those items that are not reentrant should be used in only one task.
Borland C++ documentation states that their floating-point operations can be used in interrupt routines in all memory models. If a floating-point processor chip is used, the chip's registers must be saved on entry and restored on exit for any task that uses floating point. Microsoft's C does not appear to have reentrant floating-point capabilities except possibly with specific compiler options when using the coprocessor.
Program Description
The bulk of Tiny Exec is in the timer interrupt routine, rtcint. init_rtc, close_rtc, and init_cntr provide the startup and shut down activities necessary for the timer chip and interrupt vectors. #define macros create three inline functions used for task and timer control:
- req_task to request task execution
- resume_task to continue a task at the next subtask
- set_timer to start or modify a timer.
rtcint is the real-time clock routine and exec scheduler. It is the interrupt routine generated by the 8253 real-time clock chip. rtcint can be run at the standard 18.2 Hz PC interrupt rate or can easily be any multiple of that rate. Using values other than integer multiples will result in loss of accurate time-of-day clock information. Running at higher rates can also cause loss of time through the missing of interrupt requests.
There are three parts to rtcint. The first runs Tiny Execs timers where all nonzero timers are decremented. The second section tests for the 18.2 Hz clock tick and calls the original PC clock interrupt if it is time. The third section runs the task exec if it is time. The task exec runs through all task flag words searching for the first INPROCESS or REQUESTED flag bit. Finding an INPROCESS bit indicates that this timer interrupt came from the highest priority task currently scheduled to run. A return interrupt is used to continue it. Finding a REQUESTED bit indicates that a new higher priority task has been requested to run so interrupts are enabled and the task function is called.
Programming Example
An example main is provided with several tasks and timers. It is strictly instructive as it accomplishes no useful purpose. The job of providing MS-DOS I/O has been allocated to the loop in main which is the lowest priority task.
main begins with initialization of Tiny Exec. It then kicks off timer0 and timer1 and requests task0 to execute. The loop in function main monitors your keystrokes to test for the escape key or the space bar. Pressing the escape key ends the infinite loop and terminates the program. Pressing the space bar requests execution of task1. Additionally, main outputs data to the screen during each loop when t0_flag, controlled by task0, indicates that task0 has run.
task0 is our highest priority task. Each time task0 is run, it copies the current state of all timers and task flags to arrays which are displayed to the screen by main. Having access to this information can be very helpful when you are trying to debug real-time applications. task0 requests are handled by timer0 after the first request made in main.
task1 is the second highest priority task. It consists of two subtasks, tsk1sub1 and tsk1sub2. This approach is Tiny Exec's equivalent of a wait function. When task1 is first REQUESTED, it runs tsk1sub1, the first subtask. When task1 is told to resume, then it runs the second subtask, tsk1sub2.
task1 controls the PC's speaker. When tsk1sub1 executes, it turns the speaker on, starting a beep. tsk1sub1 sets timer2 to run for beep_len ticks. At the end of beep_len ticks, timer2 requests task1 to resume with tsk1sub2 which shuts off the PC speaker's tone.
There are three timers used in this example. timer2 is dedicated to beep length. timer1 is used to periodically schedule task0. timer0 just sits there and reschedules itself about once per second. It is monitored by main to determine when to get and display the current clock time.
Problems and Considerations
Fate has ways of dealing with those who venture where the brave fear to tread. The number of ways to suffer from real-time bugs is far greater than the typical program. Not only do you have those potential bugs, there are now many more. BIOS and MS-DOS were designed to be single tasking. Also, your compiler and runtime library were intended to be single tasking.
Variables used at more than one task level, or at the task and interrupt level, are at special risk. Not only must you be careful in handling them so as to prevent those most insidious "once in a blue moon" bugs, but the compiler must not be allowed to tinker with these variables in the name of optimization. The volatile keyword may not have any effect in some older compilers.
Beware of debugger-induced problems. While it is possible to use debuggers to test your application, problems may occur. A debugger may not recapture interrupt vectors when it hits a breakpoint. Initial testing is usually accomplished without taking over the interrupt, using a call to the timer function in the main loop instead.
When replacing interrupt vectors, never restart the program without running it to completion. Doing so will fail to restore the interrupt vectors modified by the program. This usually causes the computer to eventually crash.
Conclusions
Despite its simplicity, Tiny Exec is a powerful tool for many low-end applications. Its apparent weaknesses, the lack of sophistication and features, can also be its strongest assets. Porting Tiny Exec to other languages and platforms usually is neither complicated nor time-consuming.
I have used Tiny Exec for years in embedded systems. It has been totally adequate for many applications and has become more of an approach to solving a problem than a specific set of functions. Extending its features to handle more difficult applications is often easily accomplished because of its fundamental simplicity. For sophisticated applications, a commercial executive is highly recommended.
Sidebar: Real-Time Resources
Sidebar: Floating-Point and Coprocessors
Sidebar: DOS and Multitasking
Sidebar: Reentrant Function Lists
