The main reason for investigating adaptive real-time systems is to provide predictability and flexibility for systems and environments where requirements on resources are inherently unstable and difficult to predict in advance. Such a difficulty is due to different causes. First of all, modern computer architectures include several low-level mechanisms that are designed to enhance the average performance of applications, but unfortunately introduce high variations on tasks’ execution times. In other situations, as in multimedia systems, processes can have highly variable execution times that also depend on input data. As a consequence, the overall workload of a computing system is subject to significant variations, which can produce an overload and degrade the performance of the entire system in an unpredictable fashion. This situation is particularly critical for small embedded devices used in consumer electronics, telecommunication systems, industrial automation, and automotive systems. In fact, in order to satisfy a set of constraints related to weight, space, and energy consumption, these systems are typically built using small microprocessors with low processing power and limited resources.
For most of these systems, the classical real-time approach based on a rigid off-line design, worst-case assumptions and a priori guarantee would keep resources unused for most of the time, therefore is not acceptable for efficiency reasons. When resources are scarce, they cannot be wasted. On the other hand, an off-line design based on average-case behavior is also critical, because it would be difficult to guarantee timing constraints when resources are overloaded.
To prevent unpredictable performance degradations due to overloads, a real-time system must react to load variations, degrading its performance in a controlled fashion acting on system, as well as application parameters. The process of controlling the performance of a system as a function of workload variations is referred to as Quality of Service (QoS) Management. Performing efficient QoS management requires specific support at different levels of the system architecture. Hence, new software methodologies are emerging in Embedded Systems, which strictly relate to Real-Time Operating Systems (RTOS), Middleware, and Networks.
Real-time scheduling is the kernel mechanism having the most impact on RTOS performance. Most scheduling algorithms have been developed around one of three basic schemes: table driven, fixed priority, or dynamic priority. Depending on whether scheduling decisions are resolved before or during runtime, they are classified as offline or online.
Table driven methods are capable of managing distributed applications with complex constraints, such as precedence, jitter, and end-to-end deadlines. As only a table lookup is necessary to execute the schedule, process dispatching is very simple and does not introduce large runtime overhead. On the other hand, the a priori knowledge about all system activities and events may be hard or impossible to obtain. Its rigidity enables deterministic behavior, but limits flexibility drastically. This approach is the one usually associated with a Time-Triggered architecture, such as TTP, which is commercially available.
Online methods overcome these shortcomings and provide flexibility for partially or non-specified activities. A large number of schemes have been described in the literature. These scheduling methods can efficiently reclaim any spare time coming from early completions and allow handling overload situations according to actual workload conditions. They can be distinguished into two main classes: fixed-priority and dynamic-priority algorithms. Fixed priority scheduling (FPS) is adopted in many standard operating systems and consists in assigning priorities to tasks once for all, before system execution, and executing the task with the highest priority among the tasks ready to run. In dynamic priority scheduling, priorities are typically assigned based on absolute deadlines, hence they do not follow a fixed pattern, but change dynamically at runtime. To keep feasibility analysis computationally tractable, however, tasks cannot have arbitrary constraints.
Adapting to changing environmental situations may involve changes to task parameters at runtime. System wide changes, e.g., for changing operational modes in the system, have been addressed by mode change algorithms.
Feedback scheduling changes task parameters, in particular periods, to respond to online variations in the environment and current load conditions of the system. As both conditions can vary frequently, too frequent responses, which in turn influence the conditions, can introduce instability in the system. Feedback control scheduling applies control theory to estimate effects of changes and to choose parameters to provide for smooth responses and avoid instability.
Each of the basic scheduling paradigms has specific advantages. When advantages of different schemes are demanded in the same system, more than one scheme could be used for different tasks. For example, in a complex system including hard periodic and soft aperiodic tasks, two scheduling schemes need to be integrated for satisfying the different requirements of each task class.
In hierarchical scheduling a meta algorithm arbitrates between a set of diverse scheduling algorithms. Thus, it can appear to the individual scheduling algorithms and their applications that they execute alone in the system. Furthermore, the amount of the CPU portion can be set individually for each scheduler and application. Special attention has to be given to shared resources.
In those systems subject to higly varialble workload, an overload condition could degrade the system performance in an unpredictable fashion. Novel scheduling methodologies have been recently proposed to cope with transient and permanent overload conditions. Transient overloads due to execution overruns can be effectively handled using resource reservation techniques, according to which each activity consumes a fraction of the processing resource, independently of the actual execution demand. Permanent overload conditions, typically occurring in a periodic environment, can be efficiently handled by sporadic job skipping or by rate adaptation techniques (like elastic scheduling), which keep the load below a given threshold by acting on task periods.
Flexible scheduling is an underlying theme to most novel scheduling trends which goes beyond the standard model of completely known tasks with timing constraints expressed as periods and deadline, providing “yes or no” answers whether all tasks meet their deadlines. Issues addressed include probabilistic parameters, handling of applications with only partially known properties, relaxed constraints and such that cannot be expressed solely by periods and deadlines, coexistence of activities with diverse properties and demands in a system, combinations of scheduling schemes, and adaptation or changes to scheduling schemes used at run-time.
Major needs for flexible scheduling techniques are typical of industries working in consumer electronics, industrial automation, and telecommunications, as resulted from a study carried out within the ARTIST 5FP project.
For example, mobile terminals today are getting more and more advanced and their source code consists of several million lines of code involving a large number of parallel activities. For these applications, the use of flexible real-time scheduling techniologies would allow to safely mix real-time and non real-time processes. The benefit of such a solution would be a much more scalable platform. Adding and removing features would become predictable and less hazardous, allowing configuring the system without worrying about unpleasant surprises.
In the area of Industrial Automation, the continuous increment in processing power and memory capacity in local processors gives the opportunity to add new tasks into them, increasing system complexity in terms of supervision, diagnostics, presentation, communication, etc. Adaptive tasks scheduling that preserves the real-time constraints is a possible way to handle such situation and to give insight about how manage the complexity of the tight execution of the different tasks in the real-time processing. Adaptive real-time systems technologies are very much used in many applications in the area of Industrial Automation.
In telecommunication companies, embedded systems are mainly targeted to the interfaces between communication technologies or media and to coding/decoding operations. Most of them work at the telecommunications company side, although some are also installed in customer facilities. They may be considered real-time as they have timeliness requirements for some of the critical operations they must perform. Although it is not a key issue at the management level of the companies, real-time operation is a concern for telecommunications embedded systems designers. The main current interest seems to be in exploring the use of real-time extensions for the Linux OS. It also seems that QoS mechanisms are starting to be recognized as important for these embedded applications, namely in order to increase the efficiency of subsystems and to support the possibility to serve more clients with similar levels of resources.