This paper presents a novel methodology to develop scheduling algorithms. The scheduling problem is phrased as a control problem, and control-theoretical techniques are used to design a scheduling algorithm that meets specific requirements. Unlike most approaches to feedback scheduling, where a controller integrates a "basic" scheduling algorithm and dynamically tunes its parameters and hence its performances, our methodology essentially reduces the design of a scheduling algorithm to the synthesis of a controller that closes the feedback loop. This approach allows the re-use of control-theoretical techniques to design efficient scheduling algorithms; it frames and solves the scheduling problem in a general setting; and it can naturally tackle certain peculiar requirements such as robustness and dynamic performance tuning. A few experiments demonstrate the feasibility of the approach on a real-time benchmark.
A remarkable research activity has been carried out in the past few years to support real-time applications with appropriate scheduling solutions. Unfortunately, most of such techniques can be used only if real-time applications use a specialized API, and if some important information (such as the worst-case execution-time) are known a priori. In this paper, we present a novel technique, the legacy feedback scheduler (LFS), for a class of legacy applications that need the support of a real-time scheduler but are not written using a specialized API and have unknown or varying execution requirements. The approach is based on the combination of a resource reservation scheduler and a feedback-based adaptation mechanism for identifying the correct scheduling parameters. In this paper, we develop an adaptive scheduling framework for changing the processor shares of tasks - a process called reweighting - on real-time multiprocessor platforms. Our particular focus is adaptive frameworks that are deployed in environments in which tasks may frequently require significant share changes. Prior work on enabling real-time adaptivity on multiprocessors has focused exclusively on scheduling algorithms that can enact needed adaptations. The algorithm proposed in this paper uses both feedback and optimization techniques to determine at runtime which adaptations are needed. When executing soft real-time tasks in a shared processor, it is important to properly allocate the computational resources such that the quality of service requirements of each task are satisfied. In this paper we propose Adaptive Reservations, based on applying a feedback scheme to a reservation based scheduler After providing a precise mathematical model of the scheduler, we describe how this model can be used for synthesising the controller by applying results from control theory. Finally, we show the effectiveness of our method by simulation and by experiments with an MPEG player running on a modified Linux kernel.