Abstract
An increasing trend in embedded system design is to integrate components with different levels of criticality into a shared hardware platform for better cost and power efficiency. Such mixed-criticality systems are subject to certifications at different levels of rigorousness, for validating the correctness of different subsystems on various confidence levels. The real-time scheduling of certifiable mixed-criticality systems has been recognized to be a challenging problem, where using traditional scheduling techniques may result in unacceptable resource waste. In this paper we present an algorithm called PLRS to schedule certifiable mixed-criticality sporadic tasks systems. PLRS uses fixed-job-priority scheduling, and assigns job priorities by exploring and balancing the asymmetric effects between the workload on different criticality levels. Comparing with the state-of-the-art algorithm by Li and Baruah for such systems, which we refer to as LB, PLRS is both more effective and more efficient: (i) The schedulability test of PLRS not only theoretically dominates, but also on average significantly outperforms LB's. (ii) The run-time complexity of PLRS is polynomial (quadratic in the number of tasks), which is much more efficient than the pseudo-polynomial run-time complexity of LB.
Original language | English |
---|---|
Title of host publication | Proceedings - 2011 32nd IEEE Real-Time Systems Symposium, RTSS 2011 |
Pages | 13-23 |
Number of pages | 11 |
DOIs | |
Publication status | Published - 1 Dec 2011 |
Externally published | Yes |
Event | 2011 32nd IEEE Real-Time Systems Symposium, RTSS 2011 - Vienna, Austria Duration: 29 Nov 2011 → 2 Dec 2011 |
Conference
Conference | 2011 32nd IEEE Real-Time Systems Symposium, RTSS 2011 |
---|---|
Country/Territory | Austria |
City | Vienna |
Period | 29/11/11 → 2/12/11 |
ASJC Scopus subject areas
- Software
- Hardware and Architecture
- Computer Networks and Communications