Schedulability analysis of globally scheduled preemptive applications

Abstract

For any real-time system, being predictable with respect to time is a basic necessity. The combination of a preemptive execution model and a multiprocessor platform poses a challenge when analysing the predictability of a system. In this thesis, we present a new type of framework for the worst-case response time analysis for preemptive tasks scheduled on multiprocessor platforms. The proposed framework analyses this worst-case response time by building a schedule abstraction graph that abstracts all the execution scenarios that occur in the system. Since preemptive tasks scheduled on a multiprocessor platform creates a large state space of execution scenarios to explore, a schedule abstraction graph can easily face a state space explosion problem. A novel methodology has been introduced in this thesis, that allows us to eliminate state space explosion altogether. We used this new schedule abstraction graph framework to initially develop an analysis for uniprocessor platforms and compare it to the state-of-the-art. We then explain how the analysis can be extended from uniprocessor to multiprocessor platforms.