research-article

Multi-core fixed-priority scheduling of real-time tasks with statistical deadline guarantee

Authors:

Gang QuanAuthors Info & Claims

DATE '15: Proceedings of the 2015 Design, Automation & Test in Europe Conference & Exhibition

Pages 1335 - 1340

Published: 09 March 2015 Publication History

Abstract

The rising performance variance of IC chips and increased resource sharing in multi-core platforms have significantly degraded the predictability of real-time systems. The traditional deterministic approaches can be extremely pessimistic, if not infeasible at all. In this paper, we adopt a probabilistic approach for fixed-priority preemptive scheduling of real-time tasks on multi-core platforms with statistical deadline miss probability guarantee. Rather than a single-valued worst-case execution time (WCET), we formulate the task execution time as a probabilistic distribution. We develop a novel algorithm to partition real-time tasks on multiple homogenous cores, which takes not only task execution time distributions but their period relationships into considerations. Our extensive experimental results show that our proposed methods can greatly improve the schedulability of real-time tasks when compared with the traditional bin packing approaches.

References

[1]

S. Borkar, T. Karnik, S. Narendra, J. Tschanz, A. Keshavarzi, and V. De, "Parameter variations and impact on circuits and microarchitecture," in Proceedings of the 40th annual Design Automation Conference, 2003, pp. 338--342.

Digital Library

[2]

L. Wanner, C. Apte, R. Balani, P. Gupta, and M. Srivastava, "Hardware variability-aware duty cycling for embedded sensors," vol. PP, no. 99, 2012, pp. 1--1.

[3]

C. L. Liu and J. W. Layland, "Scheduling algorithms for multiprogramming in a hard-real-time environment," J. ACM, vol. 20, no. 1, pp. 46--61, Jan. 1973. {Online}. Available: http://doi.acm.org/10.1145/321738.321743

Digital Library

[4]

J. Lehoczky, L. Sha, and Y. Ding, "The rate monotonic scheduling algorithm: exact characterization and average case behavior," in Real Time Systems Symposium, 1989., Proceedings., Dec 1989, pp. 166--171.

[5]

J. Lehoczky, "Fixed priority scheduling of periodic task sets with arbitrary deadlines," in Real-Time Systems Symposium, 1990. Proceedings., 11th, Dec 1990, pp. 201--209.

[6]

A. 653, "An avionics standard for safe, partitioned systems," in Wind River Systems/IEEE Seminar, 2008.

[7]

S. Edgar and A. Burns, "Statistical analysis of wcet for scheduling," in Real-Time Systems Symposium, 2001. (RTSS 2001). Proceedings. 22nd IEEE, Dec 2001, pp. 215--224.

Digital Library

[8]

T.-S. Tia, Z. Deng, M. Shankar, M. Storch, J. Sun, L.-C. Wu, and J. W. S. Liu, "Probabilistic performance guarantee for real-time tasks with varying computation times," in Real-Time Technology and Applications Symposium, 1995. Proceedings, May 1995, pp. 164--173.

Digital Library

[9]

A. Atlas and A. Bestavros, "Statistical rate monotonic scheduling," in Real-Time Systems Symposium, 1998. Proceedings., The 19th IEEE, Dec 1998, pp. 123--132.

Digital Library

[10]

D. Maxim, O. Buffet, L. Santinelli, L. Cucu-Grosjean, and R. I. Davis, "Optimal priority assignment algorithms for probabilistic real-time systems." in RTNS. Citeseer, 2011, pp. 129--138.

[11]

D. Maxim, M. Houston, L. Santinelli, G. Bernat, R. I. Davis, and L. Cucu-Grosjean, "Re-sampling for statistical timing analysis of real-time systems," in Proceedings of the 20th International Conference on Real-Time and Network Systems, ser. RTNS '12. New York, NY, USA: ACM, 2012, pp. 111--120.

Digital Library

[12]

Y. Lu, T. Nolte, I. Bate, and L. Cucu-Grosjean, "A statistical response-time analysis of real-time embedded systems," in Real-Time Systems Symposium (RTSS), 2012 IEEE 33rd, Dec 2012, pp. 351--362.

Digital Library

[13]

K. Kim, J. Diaz, L. Lo Bello, J. Lopez, C.-G. Lee, and S.-L. Min, "An exact stochastic analysis of priority-driven periodic real-time systems and its approximations," Computers, IEEE Transactions on, vol. 54, no. 11, pp. 1460--1466, Nov 2005.

Digital Library

[14]

D. Maxim and L. Cucu-Grosjean, "Response time analysis for fixed-priority tasks with multiple probabilistic parameters," in Real-Time Systems Symposium (RTSS), 2013 IEEE 34th, Dec 2013, pp. 224--235.

Digital Library

[15]

P. Axer and R. Ernst, "Stochastic response-time guarantee for non-preemptive, fixed-priority scheduling under errors," in Design Automation Conference (DAC), 2013 50th ACM / EDAC / IEEE, May 2013, pp. 1--7.

Digital Library

[16]

E. Bini and G. C. Buttazzo, "Measuring the performance of schedulability tests," Real-Time Syst., vol. 30, no. 1--2, pp. 129--154, May 2005.

Digital Library

[17]

M. R. Garey and D. S. Johnson, Computers and Intractability; A Guide to the Theory of NP-Completeness. New York, NY, USA: W. H. Freeman & Co., 1990.

Digital Library

[18]

D. Johnson, A. Demers, J. Ullman, M. Garey, and R. Graham, "Worst-case performance bounds for simple one-dimensional packing algorithms," SIAM Journal on Computing, vol. 3, no. 4, pp. 299--325, 1974.

Digital Library

[19]

M. Fan and G. Quan, "Harmonic semi-partitioned scheduling for fixed-priority real-time tasks on multi-core platform," in Design, Automation Test in Europe Conference Exhibition (DATE), 2012, March 2012, pp. 503--508.

Digital Library

[20]

M. Fan and G. Quan, "Harmonic-aware multi-core scheduling for fixed-priority real-time systems," Parallel and Distributed Systems, IEEE Transactions on, vol. 25, no. 6, pp. 1476--1488, June 2014.

Digital Library

[21]

J. Lpez, J. Daz, J. Entrialgo, and D. Garca, "Stochastic analysis of real-time systems under preemptive priority-driven scheduling," Real-Time Systems, vol. 40, no. 2, pp. 180--207, 2008.

Digital Library

[22]

C.-C. Han, K.-J. Lin, and C.-J. Hou, "Distance-constrained scheduling and its applications to real-time systems," IEEE Trans. Comput., vol. 45, no. 7, pp. 814--826, Jul. 1996. {Online}. Available: http://dx.doi.org/10.1109/12.508320

Digital Library

[23]

C.-C. Han and H. ying Tyan, "A better polynomial-time schedulability test for real-time fixed-priority scheduling algorithms," in Real-Time Systems Symposium, 1997. Proceedings., The 18th IEEE, Dec 1997, pp. 36--45.

Digital Library

Cited By

Ren JSu XXie GYu CTan GWu G(2019)Workload-Aware Harmonic Partitioned Scheduling of Periodic Real-Time Tasks with Constrained DeadlinesProceedings of the 56th Annual Design Automation Conference 201910.1145/3316781.3317932(1-6)Online publication date: 2-Jun-2019
https://dl.acm.org/doi/10.1145/3316781.3317932
Wang THan QSha SWen WQuan GQiu M(2016)On harmonic fixed-priority scheduling of periodic real-time tasks with constrained deadlinesProceedings of the 53rd Annual Design Automation Conference10.1145/2897937.2898055(1-6)Online publication date: 5-Jun-2016
https://dl.acm.org/doi/10.1145/2897937.2898055
Yang XWu NAndrian J(2016)A novel bus transfer mode (AS transfer) and a performance evaluation methodologyIntegration, the VLSI Journal10.1016/j.vlsi.2015.07.01252:C(23-33)Online publication date: 1-Jan-2016
https://dl.acm.org/doi/10.1016/j.vlsi.2015.07.012

Index Terms

Multi-core fixed-priority scheduling of real-time tasks with statistical deadline guarantee
1. Computer systems organization
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
      1. Scheduling algorithms
    2. Online algorithms
      1. Online learning algorithms
        Scheduling algorithms
  2. Theory and algorithms for application domains
    1. Machine learning theory
      1. Reinforcement learning
        Sequential decision making

Recommendations

Harmonicity-Aware Task Partitioning for Fixed Priority Scheduling of Probabilistic Real-Time Tasks on Multi-Core Platforms
Special Issue on Secure and Fault-Tolerant Embedded Computing and Regular Papers

The uncertainty due to performance variations of IC chips and resource sharing on multi-core platforms have significantly degraded the predictability of real-time systems. Traditional deterministic approaches based on the worst-case assumptions become ...
Quality of service capabilities for hard real-time applications on multi-core processors
RTNS '13: Proceedings of the 21st International conference on Real-Time Networks and Systems

Computing Worst-Case Execution Times (WCETs) for applications executed on multi-core processors is a challenging topic since possible interferences on shared resources need to be considered. Some approaches are already proposed in literature, but the ...
Preference-oriented fixed-priority scheduling for periodic real-time tasks

A preference priority assignment (PPA) scheme that explicitly incorporates the ASAP and ALAP execution preferences of periodic real-time tasks is proposed.An online dual-queue based preference-oriented fixed- priority (POFP) scheduler is proposed 4, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

DATE '15: Proceedings of the 2015 Design, Automation & Test in Europe Conference & Exhibition

March 2015

1827 pages

ISBN:9783981537048

General Chair:
Wolfgang Nebel
OFFIS & University of Oldenburg, DE
,
Program Chair:
David Atienza
EPFL, CH

Sponsors

EDAA: European Design Automation Association
ECSI
EDAC: Electronic Design Automation Consortium
SIGDA: ACM Special Interest Group on Design Automation
Russian Acadamy of Sciences: Russian Acadamy of Sciences
IEEE Council on Electronic Design Automation (CEDA)

Publisher

EDA Consortium

San Jose, CA, United States

Publication History

Published: 09 March 2015

Check for updates

Author Tags

Qualifiers

Research-article

Conference

DATE '15

Sponsor:

EDAA
EDAC
SIGDA
Russian Acadamy of Sciences

DATE '15: Design, Automation and Test in Europe

March 9 - 13, 2015

Grenoble, France

Acceptance Rates

DATE '15 Paper Acceptance Rate 206 of 915 submissions, 23%;

Overall Acceptance Rate 518 of 1,794 submissions, 29%

Upcoming Conference

DATE '25

Sponsor:
sigda

Design, Automation and Test in Europe

March 31 - April 2, 2025

Lyon , France

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
131
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ren JSu XXie GYu CTan GWu G(2019)Workload-Aware Harmonic Partitioned Scheduling of Periodic Real-Time Tasks with Constrained DeadlinesProceedings of the 56th Annual Design Automation Conference 201910.1145/3316781.3317932(1-6)Online publication date: 2-Jun-2019
https://dl.acm.org/doi/10.1145/3316781.3317932
Wang THan QSha SWen WQuan GQiu M(2016)On harmonic fixed-priority scheduling of periodic real-time tasks with constrained deadlinesProceedings of the 53rd Annual Design Automation Conference10.1145/2897937.2898055(1-6)Online publication date: 5-Jun-2016
https://dl.acm.org/doi/10.1145/2897937.2898055
Yang XWu NAndrian J(2016)A novel bus transfer mode (AS transfer) and a performance evaluation methodologyIntegration, the VLSI Journal10.1016/j.vlsi.2015.07.01252:C(23-33)Online publication date: 1-Jan-2016
https://dl.acm.org/doi/10.1016/j.vlsi.2015.07.012

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents