1. Field of the Invention
This invention relates generally to computer multitasking, specifically to a multitasking method for microcomputers that support a call stack, either in hardware or via software.
2. Description of Related Art
Multitasking methods are widely used in the industry of software development. These methods are often packaged as a software library, whose services are available to software applications via an application programming interface (API). They enable software developers to divide and conquer complex problems into several manageable tasks. They allow a microcomputer to perform several tasks seemingly simultaneously by switching back and forth between tasks. The prior art includes (1) preemptive, task-driven multitasking methods, (2) non-preemptive, task-driven multitasking methods, and (3) preemptive, event-driven multitasking methods. Examples of each of these methods are presented, and their call stack usage and respective disadvantages are explained.
A typical real-time operating system (RTOS) is an example of a preemptive, task-driven multitasking method. Preemptive means lower priority tasks may be interrupted in order to service higher priority tasks. And task-driven means the flow of an application is specified by its application code (the program using the RTOS). An introduction to RTOS theory and design is provided by Jean Labrosse in his book, MicroC/OS-II: The Real-Time Kernel, 2nd Edition, CMP Books 2002.
Coroutines are used to implement non-preemptive, task-driven multitasking methods. Non-preemptive means that lower priority tasks cannot be interrupted to service higher priority tasks. Rather, a higher priority task scheduled while a lower priority task is executing must wait until the lower priority task has completed. Another term often used to describe coroutines is cooperative. An introduction and implementation of coroutines is provided in the article, “Coroutines in C” by Simon Tatham in 2000 (www.chiark.greenend.org.uk/˜sgtatham/coroutines.html).
A run-to-completion (RTC) kernel is an example of a preemptive, event-driven multitasking method. (For the purposes of this document, the terms kernel and operating system may be used interchangeably.) Run-to-completion means the task code cannot suspend its own execution prior to completion. Event-driven means the flow of an application is determined by the occurrence of events. For example, when an event occurs, it drives the execution of certain task code. An introduction and explanation of a typical RTC kernel is provided by Miro Samek and Robert Ward in their article “Build a Super Simple Tasker,” Embedded Systems Programming, July 2006.
Multitasking methods typically employ a call stack to store return addresses and local variables for hierarchal functions and subroutines called for in software. Call stack usage varies considerably, depending on the multitasking method employed. An RTOS typically allocates a call stack for each and every task, whereas coroutines or an RTC kernel may employ a single call stack for use by all tasks. Another component required to support a call stack is an execution context. For each call stack supported by a multitasking method, a corresponding execution context maintains where each task is currently operating within its call stack.
Disadvantages of using a typical RTOS include having to maintain a separate call stack and for each and every task and having to specify upfront how much memory is dedicated to each call stack. FIG. 1 shows three tasks supported by an RTOS, each with its own call stack (108, 110, and 112) and each with its own execution context (102, 104, and 106). Allocating too little memory for a task can cause unpredictable behavior that can be difficult to troubleshoot. Furthermore, significant overhead is required to save and restore execution contexts when switching from one task context to another. Saving and restoring execution contexts, moreover, is dependent on microcomputer architecture, and thus processor specific code must be written for each processor supported by a typical RTOS.
The obvious disadvantage for coroutines is non-deterministic response time. A small, deterministic response time for high priority events and/or tasks is a critical performance measure for multitasking methods. As such, preemptive methods typically outperform cooperative methods. Moreover, coroutines that employ a single stack typically constrain task switching to occur at the task level, not from within subroutines. Two such methods exploited for memory constrained applications include Protothreads, explained by Adam Dunkels, et al. in “Using Protothreads for Sensor Node Programming,” from Proc. of the Workshop on Real-World Wireless Sensor Networks (REALWSN 2005) and the method shown in U.S. Pat. No. 6,823,517 to Kalman (2004).
The primary disadvantage of using an RTC kernel is added complexity for application code. Although deterministic task handling may be achieved for event-driven systems via hierarchal state handling, the onus for this is passed to the application code. An analysis of the advantages and disadvantages of implementing task-driven vs. event-driven code is provided by Dunkels, et al., in “Protothreads: Simplifying Event-Driven Programming of Memory-Constrained Embedded Systems.” The analysis shows that while execution overhead and code size grow slightly for task-driven code, reduction in transition states and lines of code is significant.
What is clearly needed is a multitasking method that supports the benefits of preemption, without the execution overhead introduced by a traditional RTOS and without the complexity for application code introduced by event-driven methods. The following definitions are provided for terms or concepts relevant to describing a solution to this need:                1. application code—software that is not part of a multitasking method, but that is developed for an application that may employ a multitasking method.        2. call stack—memory used for storing return addresses and local variables for hierarchal functions and subroutines called for in software.        3. event occurrence—a notable occurrence or happening within a software application, triggered either internally or externally to the application, upon which task processing depends.        4. execution context—a combination of one or more microcomputer processor registers, including a stack pointer, that determines the execution point within a call stack.        5. event-driven—a descriptor for multitasking methods for which the flow of execution is determined by events.        6. execution overhead—processing that supports a multitasking capability employed by an application, but that is not part of the application code.        7. interrupt—a synchronous or asynchronous event requiring attention in software.        8. mutual exclusion—exclusive access to data that is shared among multiple tasks.        9. nested tail-call—a final subroutine called prior to returning from a tail-call.        10. pend-on-event service—a service that ensures further processing for a task, pending an event occurrence, without supporting task suspension.        11. pending task—a task that is pending on an event occurrence.        12. ready task—a task that is ready to execute.        13. response time—the amount of time that a system takes to respond to an event or signal.        14. running task—a task that is currently executing.        15. semaphore—a task synchronization primitive.        16. signaling—a form of inter-task or interrupt-to-task communication, employed to communicate event occurrences.        17. tail-call—a final subroutine called prior to returning from a function.        18. task completion—a return from a task that preserves neither call stack nor execution context, such that subsequent task processing starts anew.        19. task-driven—a descriptor for multitasking methods whose services allow the flow of execution to be controlled by application code.        20. task handler (or task handling function)—application code that is specified for a task to execute when the task runs.        21. task level—the execution context of a task handler, not including execution within subroutines called from the task handler.        22. task preemption—suspension of a lower priority task such that a higher priority task can be serviced in a timely manner.        23. task scheduler—a multitasking method component responsible for executing tasks.        24. task suspension—preserving an execution context and call stack such that a task may be subsequently resumed.        
The foregoing examples of the related art and limitations related therewith are intended to be illustrative and not exclusive. Other limitations of the related art will become apparent to those skilled in the art upon a reading of the specification and a study of the drawings.