Design and Evaluation of a Feedback Control EDF SchedulingAlgorithm**Supported in part by NSF grant CCR-9901706 and contract IJRP-9803-6 from the Ministry of Information and Communication ofKorea.Chenyang Lu John A. Stankovic Gang Tao†Sang H. SonDepartment of Computer Science,†Department of Electrical EngineeringUniversity of Virginia, Charlottesville, VA22903e-mail: {cl7v, stankovic, son}@cs.virginia.edu,†[email protected] the significant body of results in real-timescheduling, many real world problems are not easilysupported. While algorithms such as Earliest DeadlineFirst, Rate Monotonic, and the Spring scheduling algorithmcan support sophisticated task set characteristics (such asdeadlines, precedence constraints, shared resources, jitter,etc.), they are all "open loop" scheduling algorithms. Openloop refers to the fact that once schedules are created theyare not "adjusted" based on continuous feedback. Whileopen-loop scheduling algorithms can perform well in staticor dynamic systems in which the workloads can beaccurately modeled, they can perform poorly inunpredictable dynamic systems. In this paper, we present afeedback control real-time scheduling algorithm and itsevaluation. Performance results demonstrate theeffectiveness of the algorithm when execution times varyfrom the worst case and when there are major shifts of totalload in the system. A key part of this feedback solution is itsexplicit use of deadline based metrics.1. Motivation and IntroductionReal-time scheduling algorithms fall into two categories:static and dynamic scheduling. In static scheduling, thescheduling algorithm has complete knowledge of the taskset and its constraints, such as deadlines, computationtimes, precedence constraints, and future release times. TheRate Monotonic (RM) algorithm and its extensions[Liu73][Leho89] are static scheduling algorithms andrepresent one major paradigm for real-time scheduling. Indynamic scheduling, however, the scheduling algorithmdoes not have the complete knowledge of the task set or itstiming constraints. For example, new task activations, notknown to the algorithm when it is scheduling the currenttask set, may arrive at a future unknown time. Dynamicscheduling can be further divided into two categories:scheduling algorithms that work in resource sufficientenvironments and those that work in resource insufficientenvironments. Resource sufficient environments aresystems where the system resources are sufficient to apriori guarantee that, even though tasks arrive dynamically,at any given time all the tasks are schedulable. Undercertain conditions, Earliest Deadline First (EDF) [Liu73] isan optimal dynamic scheduling algorithm in resourcesufficient environments. EDF is a second major paradigmfor real-time scheduling [Stan98]. While real-time systemdesigners try to design the system with sufficient resources,because of cost and highly unpredictable environments, it issometimes impossible to guarantee that the systemresources are sufficient. In this case, EDF’s performancedegrades rapidly in overload situations. The Springscheduling algorithm [Rama84][Zhao87] can dynamicallyguarantee incoming tasks via on-line admission control andplanning and thus is applicable in resource insufficientenvironments. Many other algorithms (e.g., RED algorithm[Butt95]) have also been developed to operate in this way.This planning-based set of algorithms represents the thirdmajor paradigm for real-time scheduling. However, despitethe significant body of results in these three paradigms ofreal-time scheduling, many real world problems are noteasily supported. While algorithms such as EDF, RM andthe Spring scheduling algorithm can support sophisticatedtask set characteristics (such as deadlines, precedenceconstraints, shared resources, jitter, etc.), they are all "openloop" scheduling algorithms. Open loop refers to the factthat once schedules are created they are not "adjusted"based on continuous feedback. While open-loop schedulingalgorithms can perform well in static or dynamic systems inwhich the workloads (i.e., task sets) can be accuratelymodeled, they can perform poorly in unpredictabledynamic systems, i.e., systems whose workloads cannot beaccurately modeled. For example, the Spring schedulingalgorithm assumes complete knowledge of the task setexcept for their future release times. Systems with open-loop schedulers such as the Spring scheduling algorithm areusually designed based on worst-case workload parameters.When accurate system workload models are not available,such an approach can result in a highly underutilizedsystem based on extremely pessimistic estimation ofworkload.Unfortunately, many real-world complex problemssuch as agile manufacturing, robotics, adaptive faulttolerance, and C4I and other defense applications are notpredictable. Because of this, it is impossible to meet everytask deadline. The objective of the system is to meet asmany deadlines as possible1. For example, autonomousrobotic systems always suffer from sudden variations incomputational load and overload situations due to highlyvariable execution times in robot control algorithms (e.g.,sensor interpretation, motion planning, inverse kinematicsand inverse dynamics algorithms) [Becc99]. For anotherexample, in information and decision support systems,accurate knowledge about transaction resource and datarequirements is usually not known apriori. The executiontime and resource requirements of a transaction may bedependent on user input or dependent on sensor values. Forthese applications, a design based on the estimation ofworst case execution times will result in extremelyexpensive and underutilized system. It is more costeffective to design for less than worst case, but sometimesmiss deadlines.Another important issue is that these schedulingparadigms all assume that timing requirements are knownand fixed. The assumption is that control engineers designthe system front-end control loops and generate resultingtiming requirements for tasks. The scheduling algorithmsthen work with this fixed set of timing requirements. Realcontrol systems, in general, are much more flexible androbust, e.g., instead of choosing a single deadline for a taskwhich is passed on to the scheduling system, a deadlinerange might be acceptable to the physical system. If thisrange was passed to the scheduling system, the on-linescheduling might be more robust.We believe that due to all these problems,