The case for feedback control real-time scheduling

Publisher Website
Google Scholar
Abstract
Despite the significant body of results in real-time scheduling, many real world problems are not easily supported. While algorithms such as Earliest Deadline First, Rate Monotonic, and the Spring scheduling algorithm can support sophisticated task set characteristics (such as deadlines, precedence constraints, shared resources, jitter, etc.), they are all "open loop" scheduling algorithms. Open loop refers to the fact that once schedules are created they are not "adjusted" based on continuous feedback. While open-loop scheduling algorithms can perform well in static or dynamic systems in which the workloads can be accurately modeled, they can perform poorly in unpredictable dynamic systems, i.e., systems whose workloads cannot be accurately modeled. Unfortunately, many real-world complex systems are dynamic and unpredictable. In addition, most scheduling paradigms assume that timing requirements are known and fixed, while in real systems timing requirements are more flexible. For example, instead of a single fixed deadline for a task, a deadline range might be acceptable to the physical system. If this range was passed to the scheduling system, more robust scheduling could be possible. In this paper, we present a new scheduling paradigm, which we call feedback control real-time scheduling. Feedback control real-time scheduling will define error terms for schedules, monitor the error, and continuously adjust the schedules to maintain stable performance. Feedback control real-time scheduling will be able to deal with dynamic systems that are both resource insufficient and with unpredictable workload. It can also be integrated with flexible real-time requirements. In this paradigm, the scheduling algorithms regard the computer system as a control system with the scheduler as the controller, and integrate practical feedback control techniques into scheduling algorithms. This paper presents a practical feedback control real-time scheduling algorithm, FC-EDF, which is a starting point in the long-term endeavor of creating a theory and practice of feedback control scheduling. Research results will apply to many real world systems including real-time database applications, defense applications, agile manufacturing, and distributed multimedia.

This publication has 12 references indexed in Scilit: