Whereas fairness can be the basis for general-purpose operating system scheduling policies, timeliness is the primary concern for real-time systems. As such, real-time schedulers permit uninterrupted, exclusive access to the CPU by a specific task to ensure its timely completion of execution. Only a subset of tasks, however, can satisfy their timing constraints during processor overload conditions in a real-time system. Utility accrual (UA) scheduling disciplines assure scalability and graceful performance degradation by identifying Πbased on a pre-defined set of criteria Πthe subset of tasks to be granted the heavily contended system resources.
Furthermore, whereas general-purpose operating systems treat memory monolithically and indiscriminately service dynamic allocation requests, UA-schedulers can benefit from special memory management considerations during memory over-load conditions. MSA, the scheduling algorithm here presented is the first of its kind to treat memory as a UA-schedulermanaged resource. The scheduler is made aware of memory allocation requirements of each task throughout runtime and accordingly makes appropriate CPU and resource scheduling decisions. The algorithm is well-suited for use in resourceconstrained embedded systems in a soft real-time environment.
We have implemented MSA in a POSIX real-time operating environment and measured its performance under various load conditions. Our experimental results show overall performance gains over other memory-unaware UA scheduling algorithms during memory overload.
Real-time systems are, by definition, those designed to predictably adhere to a predefined set of timeliness constraints. Hard real-time systems, for instance, must necessarily always satisfy all timing requirements. Soft real-time systems, by contrast, operate in environments where it is known that all timing constraints cannot or need not always be satisfied. Real-time systems enter overload conditions as the aggregate demand for the CPU exceeds the processor™s bandwidth making it impossible to satisfy all timing constraints. Soft real-time scheduling disciplines are often invoked during such overload conditions with the broadly defined objective of figraceful degradation.fl The utility accrual model is one method of defining graceful degradation by specifying customizable and predictable temporal system behavior during overload.
The existing UA algorithms [5], however, do not consider the mutual impact of memory management and scheduling. Under the current practice, memory is allocated statically and a task is denied admission into the system if sufficient memory is not available at load-time. This coarse-grain constraint prevents, at the outset, the entry of potentially valuable tasks. It thereby excludes them from competition for system resources in favor of those already memory-resident. MSA addresses this problem by allowing finer-grain explicit memory management at run-time. All tasks are now admitted into the system and scheduling decisions are made in light of their respective memory requirements as they dynamically arise.
Various aspects of the utility accrual model, central to our overload scheduling scheme, are elaborated below.
Figure 1: Examples of Time/Utility Functions.
A deadlines is the most widely utilized form of a timing constraint. It offers a binary view of the usefulness of a task™s completion with respect to a singular point in time: the hard deadline. The completion of a task is of no value beyond the deadline, and conversely, would yield full benefit any time prior to the deadline. Such deadline-based systems have a wide range of application, and sufficiently address the requirements of a large sector of the real-time industry. The notion of deadline is particularly well-suited for hard real-time environments where the modes of system operations are mutually exclusive and likewise binary in nature: the system operates correctly if all deadlines are always met, incorrectly otherwise; a task succeeds if it meets its deadline and fails otherwise [4, 1]. For example, the task of deploying parachutes of the Martian Lander by its controller systems must be completed by a hard deadline, else the entire system catastrophically fails. Throughout this paper the term fitaskfl refers to a CPU-schedulable single flow of execution: a process, a thread, or a job.
There exist application domains where the binary vision of a deadline-based system does not offer the wider range of expression required to describe the semantics of specific temporal system behavior. For instance, the late appearance of a radar blip due to delayed computations in a refresh cycle is preferable to no displayed data during that cycle. A Time/Utility Function (TUF) [5], accommodates the shades of gray absent from the hard deadline paradigm. The completion of a task is assumed to yield a precisely quantifiable amount of utility over a continuous range of possible values. The utility curve is predefined for each task and is highly application-specific.
The TUF expresses the utility of a task as a function of its completion time [5, 4]. The semantics of a hard deadline can be expressed using TUFs as yielding full utility prior to the deadline, and zero afterwards. Figure 1(a) depicts the rectangular TUF for one such hard deadline. The gray blocks in the figure represents the execution time of the task staring at ts and completing execution at tc, and can be anywhere between the task arrival time ta and the task deadline td.
We denote as optimal completion time, t opt , the time at which a task yields maximal utility upon completion. Figure 1(b) represents an application-specific TUF example. Test flights of unmanned aircraft, for instance, must include a remote self-destruct mechanism in case of a catastrophic systems malfunction. Should the craft™s flight path cross two popu-