Hierarchical Scheduling and Feedback Control

Abstract: Hierarchical scheduling provides predictable timing and temporal isolation; two properties desirable in real-time embedded systems. In hierarchically scheduled systems, subsystems should receive a sufficient amount of CPU resources in order to be able to guarantee timing constraints of its internal parts (tasks). In static systems, an exact amount of CPU resource can be allocated to a subsystem. However, in dynamic systems, where execution times of tasks vary considerably during run-time, it is desirable to give a dynamic portion of the CPU given the current load situation. In this thesis we present a feedback control approach for adapting the amount of CPU resource that is allocated to subsystems during run-time such that each subsystem receives sufficient resources while keeping the number of deadline violations to a minimum. We also show some example simulations where the controller adapts the budget of a subsystems.If we allocate CPU only based on subsystems demand and don't take into account the availability of the resource, timing guarantees of the lower priority subsystems (using a priority based scheduler in the global level) will be violated in the overload situations. In such a situation the high criticality modules should be superior to the low criticality modules in receiving resources. In this thesis, in the extension of our adaptive framework, we propose two techniques for controlling the CPU distribution among modules in an overload circumstance. First we introduce the notion of subsystem criticality and then distribute CPU portions based on the criticality level of subsystems.