Jinghao Sun
Abstract
In the formal analysis of real-time systems, modeling of branching codes and modeling of intratask parallelism structures are two of the most important research topics. These two real-time properties are combined, resulting in the fork-join real-time task (FJRT) model, which extends the digraph-based task model with forking and joining semantics. We prove that the EDF schedulability problem on a preemptive uniprocessor for the FJRT model is coNP-hard in the strong sense, even if the utilization of the task system is bounded by a constant strictly less than 1. Then, we show that the problem becomes tractable with some slight structural restrictions on parallel sections, for which we propose an exact schedulability test with pseudo-polynomial time complexity. Our results thus establish a borderline between the tractable and intractable FJRT models.
- Anne Angermann. 2007. Matlab-Simulink-Stateflow: Grundlagen, Toolboxen, Beispiele {mit CD-ROM}. Oldenbourg Verlag.Google Scholar
- Philip Axer, Sophie Quinton, Moritz Neukirchner, Rolf Ernst, Bjorn Dobel, and Hermann Hartig. 2013. Response-time analysis of parallel fork-join workloads with real-time constraints. In 2013 25th Euromicro Conference on Real-Time Systems (ECRTS’13). IEEE, 215--224. Google ScholarDigital Library
- Sanjoy Baruah. 2010a. The non-cyclic recurring real-time task model. In 2010 IEEE 31st Real-Time Systems Symposium (RTSS’10). IEEE, 173--182. Google ScholarDigital Library
- Sanjoy Baruah. 2010b. Preemptive uniprocessor scheduling of non-cyclic GMF task systems. In 2010 IEEE 16th International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA’10). IEEE, 195--202. Google ScholarDigital Library
- Sanjoy Baruah. 2014. Improved multiprocessor global schedulability analysis of sporadic DAG task systems. In 2014 26th Euromicro Conference on Real-Time Systems (ECRTS’14). IEEE, 97--105. Google ScholarDigital Library
- Sanjoy Baruah, Vincenzo Bonifaci, Alberto Marchetti-Spaccamela, Leen Stougie, and Andreas Wiese. 2012. A generalized parallel task model for recurrent real-time processes. In 2012 IEEE 33rd Real-Time Systems Symposium (RTSS’12). IEEE, 63--72. Google ScholarDigital Library
- Sanjoy Baruah, Deji Chen, Sergey Gorinsky, and Aloysius Mok. 1999. Generalized multiframe tasks. Real-Time Systems 17, 1, 5--22. Google ScholarDigital Library
- Sanjoy Baruah and Nathan Fisher. 2005. The partitioned multiprocessor scheduling of sporadic task systems. In 26th IEEE International Real-Time Systems Symposium, 2005 (RTSS’05).. IEEE, 9--pp. Google ScholarDigital Library
- Sanjoy K. Baruah. 2003. Dynamic-and static-priority scheduling of recurring real-time tasks. Real-Time Systems 24, 1, 93--128. Google ScholarDigital Library
- Sanjoy K. Baruah and Theodore P. Baker. 2008. Global EDF schedulability analysis of arbitrary sporadic task systems. In ECRTS. 3--12. Google ScholarDigital Library
- Sanjoy K. Baruah, Aloysius K. Mok, and Louis E. Rosier. 1990. Preemptively scheduling hard-real-time sporadic tasks on one processor. In Proceedings of the 11th Real-Time Systems Symposium, 1990.IEEE, 182--190.Google ScholarCross Ref
- Hoon Sung Chwa, Jinkyu Lee, Kieu-My Phan, Arvind Easwaran, and Insik Shin. 2013. Global EDF schedulability analysis for synchronous parallel tasks on multicore platforms. In 2013 25th Euromicro Conference on Real-Time Systems (ECRTS’13). IEEE, 24--34. Google ScholarDigital Library
- Stephen A. Cook. 1971. The complexity of theorem-proving procedures. In Proceedings of the 3rd Annual ACM Symposium on Theory of Computing. ACM, New York, NY, 151--158. Google ScholarDigital Library
- Daniel Ejsing-Duun, Lisa Fontani, Jonas Finnemann Jensen, Jacob Haubach, and Lars Kærlund Østergaard Smedegård. 2013. The concurrent real-time task model. Aalborg University, Denmark, Tech. Rep, 2014, 1--35. Retrieved December 17, 2015 from http://www.lets.dk/downloads/CRT.pdf.Google Scholar
- David Ferry, Jing Li, Mahesh Mahadevan, Kunal Agrawal, Christopher Gill, and Chenyang Lu. 2013. A real-time scheduling service for parallel tasks. In 2013 IEEE 19th Real-Time and Embedded Technology and Applications Symposium (RTAS’13). IEEE, 261--272. Google ScholarDigital Library
- Aloysius Ka and Lau Mok. 1983. Fundamental design problems of distributed systems for the hard-real-time environment. Vol. 1. MIT Thesis, Cambridge, MA.Google Scholar
- Shinpei Kato and Yutaka Ishikawa. 2009. Gang EDF scheduling of parallel task systems. In 30th IEEE Real-Time Systems Symposium, 2009 (RTSS’09). IEEE, 459--468. Google ScholarDigital Library
- Karthik Lakshmanan, Shinpei Kato, and Ragunathan Rajkumar. 2010. Scheduling parallel real-time tasks on multi-core processors. In 2010 IEEE 31st Real-Time Systems Symposium (RTSS’10). IEEE, 259--268. Google ScholarDigital Library
- Chung Laung Liu and James W. Layland. 1973. Scheduling algorithms for multiprogramming in a hard-real-time environment. Journal of the ACM 20, 1, 46--61. Google ScholarDigital Library
- Aloysius K. Mok and Deji Chen. 1997. A multiframe model for real-time tasks. IEEE Transactions on Software Engineering 23, 10, 635--645. Google ScholarDigital Library
- Geoffrey Nelissen, Vandy Berten, Joël Goossens, and Dragomir Milojevic. 2012. Techniques optimizing the number of processors to schedule multi-threaded tasks. In 2012 24th Euromicro Conference on Real-Time Systems (ECRTS’12). IEEE, 321--330. Google ScholarDigital Library
- Abusayeed Saifullah, Kunal Agrawal, Chenyang Lu, and Christopher Gill. 2011. Multi-core real-time scheduling for generalized parallel task models. In 2011 IEEE 32nd Real-Time Systems Symposium (RTSS’11). IEEE, 217--226. Google ScholarDigital Library
- Abusayeed Saifullah, David Ferry, Kunal Agrawal, Chenyang Lu, and Christopher Gill. 2012. Real-time scheduling of parallel tasks under general DAG model. Washington University in St Louis, USA, Tech. Rep. WUCSE-2012-14, 2012.Google Scholar
- Martin Stigge, Pontus Ekberg, Nan Guan, and Wang Yi. 2011. The digraph real-time task model. In 2011 17th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS’11). IEEE, 71--80. Google ScholarDigital Library
- Martin Stigge, Pontus Ekberg, and Wang Yi. 2013. The fork-join real-time task model. ACM SIGBED Review 10, 2, 20--20. Google ScholarDigital Library
- Martin Stigge and Wang Yi. 2013. Combinatorial abstraction refinement for feasibility analysis. In 2013 IEEE 34th Real-Time Systems Symposium (RTSS’13). IEEE, 340--349. Google ScholarDigital Library
Index Terms
- Feasibility of Fork-Join Real-Time Task Graph Models: Hardness and Algorithms
Recommendations
Uniform weak tractability
We introduce a new notion of tractability which is called uniform weak tractability. A problem is uniformly weakly tractable if the information complexity n(@e,d) of its d-variate component to be solved to within @e is not exponential in any positive ...
On the Tractability of Digraph-Based Task Models
ECRTS '11: Proceedings of the 2011 23rd Euromicro Conference on Real-Time SystemsIn formal analysis of real-time systems, a major concern is the analysis efficiency. As the expressiveness of models grows, so grows the complexity of their analysis. A recently proposed model, the digraph real-time task model (DRT), offers high ...
Quantifying Energy Consumption for Practical Fork-Join Parallelism on an Embedded Real-Time Operating System
RTNS '16: Proceedings of the 24th International Conference on Real-Time Networks and SystemsIn this work, we present the experimental assessment of a parallel framework that allows to reduce the energy consumption of MPSoC platforms running hard real-time systems. We use a power-aware Fork-Join task model based on primitives of the OpenMP ...
Comments