Schedulability Analysis of Tasks with Corunner-Dependent Execution Times

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.
2. B. Andersson and J. Jonsson. 2002. Preemptive multiprocessor scheduling anomalies. In International Parallel and Distributed Processing Symposium (IPDPS’02).
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).
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.
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).
7. R. Graham. 1969. Bounds on multiprocessing timing anomalies. SIAM J. Appl. Math. 17 (1969), 416--429.
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).
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).
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).
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).
17. C. L. Liu and J. W. Layland. 1973. Scheduling algorithms for multiprogramming in a hard real-time environment. JACM 20 (1973), 46--61.
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).
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).
21. A. Mok. 1983. Fundamental Design Problems of Distributed Systems for the Hard-real-time Environment. Ph.D. Dissertation. MIT.
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).
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).
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).
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).
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.
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).
29. S. Schliecker, M. Negrean, and R. Ernst. 2010. Bounding the shared resource load for the performance analysis of multiprocessor systems. In DATE’10.
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.
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).

Index Terms

• Computer systems organization

  • Embedded and cyber-physical systems

    • Embedded systems

• Mathematics of computing

  • Mathematical software

• Software and its engineering

  • Software organization and properties

    • Software system structures

      • Embedded software

      • Real-time systems software