research-article

Schedulability Analysis of Tasks with Corunner-Dependent Execution Times

Authors:

BJörn Andersson,

Dionisio De Niz,

Ragunathan (Raj) Rajkumar,

John LehoczkyAuthors Info & Claims

ACM Transactions on Embedded Computing Systems (TECS), Volume 17, Issue 3

Article No.: 71, Pages 1 - 29

https://doi.org/10.1145/3203407

Published: 22 May 2018 Publication History

Abstract

Consider fixed-priority preemptive partitioned scheduling of constrained-deadline sporadic tasks on a multiprocessor. A task generates a sequence of jobs and each job has a deadline that must be met. Assume tasks have Corunner-dependent execution times; i.e., the execution time of a job J depends on the set of jobs that happen to execute (on other processors) at instants when J executes. We present a model that describes Corunner-dependent execution times. For this model, we show that exact schedulability testing is co-NP-hard in the strong sense. Facing this complexity, we present a sufficient schedulability test, which has pseudo-polynomial-time complexity if the number of processors is fixed. We ran experiments with synthetic software benchmarks on a quad-core Intel multicore processor with the Linux/RK operating system and found that for each task, its maximum measured response time was bounded by the upper bound computed by our theory.

References

[1]

B. Andersson, A. Easwaran, and J. Lee. 2010. Finding an upper bound on the increase in execution time due to contention on the memory bus in COTS-based multicore systems. SIGBED Rev. 7, 1 (2010), 4.

Digital Library

[2]

B. Andersson and J. Jonsson. 2002. Preemptive multiprocessor scheduling anomalies. In International Parallel and Distributed Processing Symposium (IPDPS’02).

Digital Library

[3]

B. Andersson, H. Kim, D. de Niz, M. Klein, R. Rajkumar, and J. Lehoczky. 2016. Schedulability Analysis of Tasks with Co-Runner-Dependent Execution Times. Technical Report. Carnegie Mellon University. Retrieved from http://www.andrew.cmu.edu/user/banderss/papers/schedanalysiscorunner/co-runners_long_version.pdf.

[4]

S. Baruah and A. Burns. 2006. Sustainable scheduling analysis. In IEEE Real-Time Systems Symposium (RTSS’06).

Digital Library

[5]

M. R. Garey and D. S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company.

Digital Library

[6]

G. Giannopoulou, K. Lampka, N. Stoimenov, and L. Thiele. 2012. Timed model checking with abstractions: Towards worst-case response time analysis in resource-sharing manycore systems. ACM SIGBED International Conference on Embedded Software (EMSOFT’12).

Digital Library

[7]

R. Graham. 1969. Bounds on multiprocessing timing anomalies. SIAM J. Appl. Math. 17 (1969), 416--429.

Digital Library

[8]

M. Joseph and P. Pandya. 1986. Finding response times in a real-time system. Comput. J. 29 (1986), 390--395.

[9]

S. Kato and N. Yamasaki. 2006. Extended u-link scheduling to increase the execution efficiency for SMT real-time systems. In IEEE International Conference on Embedded and Real-Time Computing and Applications (RTCSA’06).

Digital Library

[10]

T. Kelter. 2015. WCET Analysis and Optimization for Multi-Core Real-Time Systems. Ph.D. Dissertation. Technical University of Dortmund.

[11]

H. Kim, D. de Niz, B. Andersson, M. Klein, O. Mutlu, and R. Rajkumar. 2014. Bounding memory interference delay in COTS-based multi-core systems. In IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS’14).

[12]

H. Kim, A. Kandhalu, and R. Rajkumar. 2013. A coordinated approach for practical OS-level cache management in multi-core real-time systems. In Euromicro Conference on Real-Time Systems (ECRTS’13).

Digital Library

[13]

P. Krčál and W. Yi. 2004. Decidable and undecidable problems in schedulability analysis using timed automata. In International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS’04).

[14]

K. Lampka, S. Perathoner, and L. Thiele. 2009. Analytic real-time analysis and timed automata: A hybrid method for analyzing embedded real-time systems. In ACM SIGBED International Conference on Embedded Software (EMSOFT’09).

Digital Library

[15]

J. Lehoczky, L. Sha, and Y. Ding. 1990. The rate monotonic scheduling algorithm: Exact characterization and average case behavior. In IEEE Real-Time Systems Symposium (RTSS’90).

[16]

Y. Li, V. Suhendra, Y. Liang, T. Mitra, and A. Roychoudhury. 2009. Timing analysis of concurrent programs running on shared cache multi-cores. In IEEE Real-Time Systems Symposium (RTSS’09).

Digital Library

[17]

C. L. Liu and J. W. Layland. 1973. Scheduling algorithms for multiprogramming in a hard real-time environment. JACM 20 (1973), 46--61.

Digital Library

[18]

J. Liu and R. Ha. 1994. Efficient methods of validating timing constraints. In International Conference on Distributed Computing Systems (ICDCS’94).

[19]

T. Lundqvist and P. Stenström. 1999. Timing anomalies in dynamically scheduled microprocessors. In IEEE Real-Time Systems Symposium (RTSS’99).

Digital Library

[20]

M. Lv, G. Nan, W. Yi, and G. Yu. 2010. Combining abstract interpretation with model checking for timing analysis of multicore software. In IEEE Real-Time Systems Symposium (RTSS’10).

Digital Library

[21]

A. Mok. 1983. Fundamental Design Problems of Distributed Systems for the Hard-real-time Environment. Ph.D. Dissertation. MIT.

Digital Library

[22]

C. Norström, A. Wall, and W. Yi. 1999. Timed automata as task models for event-driven systems. In IEEE International Conference on Embedded and Real-Time Computing and Applications (RTCSA’99).

Digital Library

[23]

J. Nowotsch, M. Paulitsch, D. Bühler, H. Theiling, S. Wegener, and M. Schmidt. 2014. Multi-core interference-sensitive WCET analysis leveraging runtime resource capacity enforcement. In Euromicro Conference on Real-Time Systems (ECRTS’14).

Digital Library

[24]

R. Pellizzoni, A. Schranzhofer, J. J. Chen, M. Caccamo, and L. Thiele. 2010. Worst case delay analysis for memory interference in multicore systems. In Design, Automation and Test in Europe (DATE’10).

Digital Library

[25]

L. T. X. Phan, S. Chakraborty, P. S. Thiagarajan, and L. Thiele. 2007. Composing functional and state-based performance models for analyzing heterogeneous real-time systems. In IEEE Real-Time Systems Symposium (RTSS’07).

Digital Library

[26]

P. Radojkovic, S. Girbal, A. Grasset, E. Quinones, S. Yehia, and F. J. Cazorla. 2012. On the evaluation of the impact of shared resources in multithreaded COTS processors in time-critical environments. ACM Trans. Archit. Code Optim. 8 (2012), 1--25.

Digital Library

[27]

J. Reineke, B. Wachter, S. Thesing, R. Wilhelm, I. Polian, J. Eisinger, and B. Becker. 2006. A definition and classification of timing anomalies. In International Workshop on Worst-Case Execution Time Analysis (WCET’06).

[28]

S. Schliecker and R. Ernst. 2009. A recursive approach to end-to-end path latency computation in heterogeneous multiprocessor systems. In International Conference on Hardware/Software Codesign and System Synthesis (CODES+ISSS’09).

Digital Library

[29]

S. Schliecker, M. Negrean, and R. Ernst. 2010. Bounding the shared resource load for the performance analysis of multiprocessor systems. In DATE’10.

Digital Library

[30]

L. Sha, M. Caccamo, R. Mancuso, J.-E. Kim, M.-K. Yoon, R. Pellizzoni, H. Yun, R. B. Kegley, D. Perlman, G. Arundale, and R. Bradford. 2016. Real-time computing on multicore processors. Computer 49 (2016), 69--77.

[31]

H. Shah, K. Huang, and A. Knoll. 2014. Timing anomalies in multi-core architectures due to the interference on the shared resources. In Design Automation Conference (DAC’14).

[32]

L. Thiele, S. Chakraborty, and M. Naedele. 2000. Real-time calculus for scheduling hard real-time systems. In International Symposium on Circuits and Systems (ISCAS’00).

[33]

R. Wilhelm, J. Engblom, A. Ermedahl, N. Holsti, S. Thesing, D. Whalley, G. Bernat, C. Ferdinand, R. Heckmann, T. Mitra, F. Mueller, I. Puaut, P. Puschner, J. Staschulat, and P. Stenström. 2008. The worst-case execution-time problem—Overview of methods and survey of tools. ACM Trans. Embedded Comput. Syst. 7 (2008), 1--53.

Digital Library

[34]

H. Yun and P. K. Valsan. 2015. Evaluating the isolation effect of cache partitioning on COTS multicore platforms. In Workshop on Operating Systems Platforms for Embedded Real-Time Application (OSPERT’15).

Cited By

Ortiz LGuasque ABalbastre PSimó JCrespo A(2024)Schedulability Analysis in Fixed-Priority Real-Time Multicore Systems with ContentionApplied Sciences10.3390/app1410403314:10(4033)Online publication date: 9-May-2024
https://doi.org/10.3390/app14104033
Andersson Bde Niz DKlein M(2023)A Tool for Satisfying Real-Time Requirements of Software Executing on ARINC 653 with Undocumented Multicore2023 IEEE/AIAA 42nd Digital Avionics Systems Conference (DASC)10.1109/DASC58513.2023.10311291(1-10)Online publication date: 1-Oct-2023
https://doi.org/10.1109/DASC58513.2023.10311291
Andersson Bde Niz DVance WRoss JWotell MBui T(2023)Methodology of Combining Empirical Stress Testing and Formal-Methods Based Schedulability Analysis for Real-Time Multicore Software2023 IEEE/AIAA 42nd Digital Avionics Systems Conference (DASC)10.1109/DASC58513.2023.10311104(1-10)Online publication date: 1-Oct-2023
https://doi.org/10.1109/DASC58513.2023.10311104
Show More Cited By

Index Terms

Schedulability Analysis of Tasks with Corunner-Dependent Execution Times

Recommendations

LLF Schedulability Analysis on Multiprocessor Platforms
RTSS '10: Proceedings of the 2010 31st IEEE Real-Time Systems Symposium

LLF (Least Laxity First) scheduling, which assigns a higher priority to a task with smaller laxity, has been known as an optimal preemptive scheduling algorithm on a single processor platform. However, its characteristics upon multiprocessor platforms ...
Periodicity of real-time schedules for dependent periodic tasks on identical multiprocessor platforms

This paper gives and proves correct a simulation interval for any schedule generated by a deterministic and memoryless scheduler (i.e., one where the scheduling decision is the same and unique for any two identical system states) for identical ...
Laxity dynamics and LLF schedulability analysis on multiprocessor platforms

LLF (Least Laxity First) scheduling, which assigns a higher priority to a task with a smaller laxity, has been known as an optimal preemptive scheduling algorithm on a single processor platform. However, little work has been made to illuminate its ...

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Embedded Computing Systems

ACM Transactions on Embedded Computing Systems Volume 17, Issue 3

May 2018

309 pages

ISSN:1539-9087

EISSN:1558-3465

DOI:10.1145/3185335

Editor:
Sandeep K. Shukla
Indian Institute of Technology, India

Issue’s Table of Contents

Copyright © 2018 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Journal Family

ACM Journals for the Design of Smart and Connected Systems

Publication History

Published: 22 May 2018

Accepted: 01 March 2018

Revised: 01 November 2017

Received: 01 December 2016

Published in TECS Volume 17, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
258
Total Downloads

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

Reflects downloads up to 05 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Ortiz LGuasque ABalbastre PSimó JCrespo A(2024)Schedulability Analysis in Fixed-Priority Real-Time Multicore Systems with ContentionApplied Sciences10.3390/app1410403314:10(4033)Online publication date: 9-May-2024
https://doi.org/10.3390/app14104033
Andersson Bde Niz DKlein M(2023)A Tool for Satisfying Real-Time Requirements of Software Executing on ARINC 653 with Undocumented Multicore2023 IEEE/AIAA 42nd Digital Avionics Systems Conference (DASC)10.1109/DASC58513.2023.10311291(1-10)Online publication date: 1-Oct-2023
https://doi.org/10.1109/DASC58513.2023.10311291
Andersson Bde Niz DVance WRoss JWotell MBui T(2023)Methodology of Combining Empirical Stress Testing and Formal-Methods Based Schedulability Analysis for Real-Time Multicore Software2023 IEEE/AIAA 42nd Digital Avionics Systems Conference (DASC)10.1109/DASC58513.2023.10311104(1-10)Online publication date: 1-Oct-2023
https://doi.org/10.1109/DASC58513.2023.10311104
Aceituno JGuasque ABalbastre PBlanes FPomante L(2023)Optimized Scheduling of Periodic Hard Real-Time Multicore SystemsIEEE Access10.1109/ACCESS.2023.326113011(30027-30039)Online publication date: 2023
https://doi.org/10.1109/ACCESS.2023.3261130
Davis RBate I(2022)Mixed Criticality on Multi-cores Accounting for Resource Stress and Resource SensitivityProceedings of the 30th International Conference on Real-Time Networks and Systems10.1145/3534879.3534883(103-115)Online publication date: 7-Jun-2022
https://dl.acm.org/doi/10.1145/3534879.3534883
Bankar ASha SBhimani JChaturvedi VQuan G(2022)Thermal Aware System-Wide Reliability Optimization for Automotive Distributed Computing ApplicationsIEEE Transactions on Vehicular Technology10.1109/TVT.2022.318597871:10(10442-10457)Online publication date: Oct-2022
https://doi.org/10.1109/TVT.2022.3185978
Lugo TLozano SFernandez JCarretero J(2022)A Survey of Techniques for Reducing Interference in Real-Time Applications on Multicore PlatformsIEEE Access10.1109/ACCESS.2022.315189110(21853-21882)Online publication date: 2022
https://doi.org/10.1109/ACCESS.2022.3151891
Davis RGriffin DBate I(2022)A framework for multi-core schedulability analysis accounting for resource stress and sensitivityReal-Time Systems10.1007/s11241-022-09377-858:4(456-508)Online publication date: 1-Dec-2022
https://dl.acm.org/doi/10.1007/s11241-022-09377-8
Guasque AAceituno JBalbastre PSimó JCrespo A(2022)Schedulability analysis of dynamic priority real-time systems with contentionThe Journal of Supercomputing10.1007/s11227-022-04446-y78:12(14703-14725)Online publication date: 1-Aug-2022
https://dl.acm.org/doi/10.1007/s11227-022-04446-y
Kim Hde Niz DAndersson BKlein MLehoczky J(2021)Addressing Multi-core Timing Interference using Co-Runner Locking2021 IEEE Real-Time Systems Symposium (RTSS)10.1109/RTSS52674.2021.00017(54-67)Online publication date: Dec-2021
https://doi.org/10.1109/RTSS52674.2021.00017
Show More Cited By

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 Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents