A weak simulation relation for real-time schedulability analysis of Global Fixed Priority scheduling using Linear Hybrid Automata

Youcheng Sun, Giuseppe Lipari

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

Abstract

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. The proposed schedulability analysis has been implemented in a software tool. And we show that the use of the proposed model permits to analyse more complex systems than other exact algorithms in the literature. Moreover, we assess the pessimism of state-of-the-art approximate schedulability test through experiments. To the best of our knowledge, this is the first comparison between the approximate analysis and the exact analysis for G-FP scheduling.

Original languageEnglish
Title of host publicationProceedings of the 22nd International Conference on Real-Time Networks and Systems, RTNS 2014
PublisherAssociation for Computing Machinery
Pages35-44
Number of pages10
ISBN (Electronic)9781450327275
DOIs
Publication statusPublished - 8 Oct 2014
Event22nd International Conference on Real-Time Networks and Systems, RTNS 2014 - Versailles, France
Duration: 8 Oct 201410 Oct 2014

Publication series

NameACM International Conference Proceeding Series
Volume08-10-October-2014

Conference

Conference22nd International Conference on Real-Time Networks and Systems, RTNS 2014
Country/TerritoryFrance
CityVersailles
Period8/10/1410/10/14

Fingerprint

Dive into the research topics of 'A weak simulation relation for real-time schedulability analysis of Global Fixed Priority scheduling using Linear Hybrid Automata'. Together they form a unique fingerprint.

Cite this