Advances in hierarchical real-time systems: Incrementality, optimality, and multiprocessor clustering

Component-based engineering is a popular design strategy for multi-functional and complex real-time systems; it decomposes the system into simpler components and then composes them using interfaces that hide internal complexities. Since components also have time-constrained resource demand, this design leads to hierarchical real-time systems that share resources under a scheduling hierarchy. Due to resource-constrained operating environments, schedulability analysis of such hierarchical systems - analysis to verify satisfaction of component timing constraints - is an important problem that must be addressed in the design phase. Additionally, to preserve the principles of component-based engineering, this analysis must be compositional, i.e., system schedulability must be determined by composing interfaces that abstractly represent component resource requirements.;This dissertation addresses two problems pertaining to compositional schedulability analysis. First, it develops analysis techniques that are also incremental; analysis is independent of the order in which component interfaces are composed. This allows interfaces to be reused for efficient, on-the-fly verification of changes to components. Second, it addresses the problem of resource wastage in compositional analysis. It develops a new component interface whose resource utilization is better than existing interfaces. It also characterizes the notion of optimal resource utilization for hierarchical systems, and determines conditions under which this optimality can be achieved. Finally, it demonstrates the effectiveness of these techniques on data sets obtained from avionics systems.;With increasing popularity of multiprocessor-based embedded real-time systems, development of scheduling algorithms for multiprocessors is gaining importance. Algorithms that manage platform parallelism either by splitting it into multiple uniprocessors (partitioned scheduling), or by allowing demand to freely migrate across the platform (global scheduling), have been developed. In-spite of a reasonable success with these algorithms, many scheduling problems still remain open. Towards addressing them, this dissertation proposes a novel scheduling technique that virtualizes demand allocation through a two-level scheduling hierarchy. This technique supports more general demand distributions across the platform in comparison to existing algorithms, and hence provides a finer control over platform parallelism.