Real-time system design using preemption thresholds

As the real-time embedded systems encountered in applications such as telecommunications, aerospace, defense, and automatic control demand large, complex and multi-tasked software development, a new challenge has emerged for adopting the state-of-the-art software engineering technologies. Object-oriented design provides a scalable methodology with appropriate CASE tools for the design of software systems. Although these tools provides support for visual object-oriented modeling, design, simulation and code generation for general real-time systems, timing analysis is only available after the software is constructed. Consequently, the design-development process involving these tools in real-time systems becomes iterative and time-consuming. Introducing timing analysis in the design stage encounters a new problem. Traditional scheduling theory assumes a single level of task granularity. However, in industrial practice, common wisdom requires several design level tasks map into one run-time thread to reduce scheduling costs. This warrants a dual-level scheduling: preemptive scheduling between threads and non-preemptive scheduling between tasks in the same thread. Extending the scheduling theory to such an environment forms the scope of this thesis. Preemption threshold is introduced to control undesirable preemptions. Via a novel application of this concept, this thesis proposes a general scheduling model that subsumes both preemptive and non-preemptive scheduling models as special cases. The new theory deals with both independent and dependent tasks derivable from an object-oriented system model. Motivated by UML-RT modeling, the dependencies in our model include inter-task communication, resource sharing, and precedence. Important design issues covered include task priority and preemption threshold assignment and optimized task to thread mapping with respect of minimum scheduling cost and memory requirement. Quantitative performance evaluation is also conducted via simulation to validate the theory propose