A Weak Simulation Relation for Real-Time Schedulability Analysis of Global Fixed Priority Scheduling Using Linear Hybrid Automata
Youcheng Sun, Giuseppe Lipari · 2014
In this paper we present an exact schedulability test for sporadic real-time tasks scheduled by the Global Fixed Priority (G-FP) Fully Preemptive Scheduler on a multiprocessor system. The analysis consists in modelling the system as a Linear Hybrid Automaton, and in performing a reachability analysis for states representing deadline miss conditions. To further mitigate the problem of state space explosion, we propose a partial order relationship over the symbolic states of the model and we prove that this is a weak simulation relation. States that are simulated by others can be safely eliminated from the state space without interfering with the schedulability analysis.