Integration of hard real-time schedulers

Over the last few decades, numerous research results have been obtained on scheduling specific real-time workloads to run on dedicated resources. In the last few years, research in scheduler composition on shared resources has attracted increasing attention for the following reasons. The capacities of resources in real-time embedded systems, such as processors, communications channels, have been growing rapidly. These hardware advances create possibilities for more complex and integrated functionalities that share the same resources. Heterogeneous workloads are now allocated to shared resources in contemporary designs. The complexity of the scheduler is accordingly increased. Approaches in scheduler composition have been proposed as a divide-and-conquer strategy to deal with the complexity of scheduler design for these integrated systems. Most of the scheduler composition approaches that have been proposed an be treated within a framework of two-layers: coordinator and components. This dissertation overs our contributions in these two layers, namely, Class-based Component Composition (CCC) approach in the layer of coordinating mechanisms and pre-scheduling in the layer of component construction. We propose CCC for composing independent components in an open environment. CCC uses a workload classification scheme to guarantee that the supply of shared resource always meets the hard-real-time constraints for on-budget workloads. It also aims to achieve a balance over multiple design objectives including composition overhead, overload handling and accommodating the range of real-time applications. A pre-schedule is a static schedule that does not require constant and completely predictable rate of resource supply. We present a sound, complete, and PTIME basic pre-scheduler based on Linear Programming (LP). Since in finitely small slices of time are not implementable in time-domain multiplexing for resources with non-negligible context switch overheads, it is desirable to de ne and solve the pre-scheduling problem on the domain of integers. We construct a rational-to-integral pre-schedule transformer based on a novel technique which we all "round-and-compensate". This transformer is sound, complete and runs in PTIME. We also present an extension of the basic pre-scheduler for solving precedence constraints, and show two examples on how to do resource supply analysis in our framework.