Document Open Access Logo

Packing Sporadic Real-Time Tasks on Identical Multiprocessor Systems

Authors Jian-Jia Chen , Nikhil Bansal, Samarjit Chakraborty , Georg von der Brüggen

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2018.71.pdf
  • Filesize: 0.49 MB
  • 14 pages

Document Identifiers

Author Details

Jian-Jia Chen
  • Department of Computer Science, TU Dortmund University, Germany
Nikhil Bansal
  • Eindhoven University of Technology, The Netherlands
Samarjit Chakraborty
  • Technical University of Munich (TUM), Germany
Georg von der Brüggen
  • Department of Computer Science, TU Dortmund University, Germany

Cite As Get BibTex

Jian-Jia Chen, Nikhil Bansal, Samarjit Chakraborty, and Georg von der Brüggen. Packing Sporadic Real-Time Tasks on Identical Multiprocessor Systems. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 71:1-71:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ISAAC.2018.71

Abstract

In real-time systems, in addition to the functional correctness recurrent tasks must fulfill timing constraints to ensure the correct behavior of the system. Partitioned scheduling is widely used in real-time systems, i.e., the tasks are statically assigned onto processors while ensuring that all timing constraints are met. The decision version of the problem, which is to check whether the deadline constraints of tasks can be satisfied on a given number of identical processors, has been known NP-complete in the strong sense. Several studies on this problem are based on approximations involving resource augmentation, i.e., speeding up individual processors. This paper studies another type of resource augmentation by allocating additional processors, a topic that has not been explored until recently. We provide polynomial-time algorithms and analysis, in which the approximation factors are dependent upon the input instances. Specifically, the factors are related to the maximum ratio of the period to the relative deadline of a task in the given task set. We also show that these algorithms unfortunately cannot achieve a constant approximation factor for general cases. Furthermore, we prove that the problem does not admit any asymptotic polynomial-time approximation scheme (APTAS) unless P=NP when the task set has constrained deadlines, i.e., the relative deadline of a task is no more than the period of the task.

Subject Classification

ACM Subject Classification
  • Computer systems organization → Real-time systems
Keywords
  • multiprocessor partitioned scheduling
  • approximation factors

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Nikhil Bansal, Cyriel Rutten, Suzanne van der Ster, Tjark Vredeveld, and Ruben van der Zwaan. Approximating Real-Time Scheduling on Identical Machines. In LATIN: Theoretical Informatics - 11th Latin American Symposium, pages 550-561, 2014. Google Scholar
  2. Sanjoy Baruah. The Partitioned EDF Scheduling of Sporadic Task Systems. In Real-Time Systems Symposium (RTSS), pages 116-125, 2011. Google Scholar
  3. Sanjoy K. Baruah and Nathan Fisher. The Partitioned Multiprocessor Scheduling of Sporadic Task Systems. In Real-Time Systems Symposium (RTSS), pages 321-329, 2005. Google Scholar
  4. Sanjoy K. Baruah and Nathan Fisher. The Partitioned Multiprocessor Scheduling of Deadline-Constrained Sporadic Task Systems. IEEE Trans. Computers, 55(7):918-923, 2006. Google Scholar
  5. Sanjoy K. Baruah, Aloysius K. Mok, and Louis E. Rosier. Preemptively scheduling hard-real-time sporadic tasks on one processor. In Real-Time Systems Symposium (RTSS), pages 182-190, 1990. Google Scholar
  6. Almut Burchard, Jörg Liebeherr, Yingfeng Oh, and Sang Hyuk Son. New Strategies for Assigning Real-Time Tasks to Multiprocessor Systems. IEEE Trans. Computers, 44(12):1429-1442, 1995. Google Scholar
  7. Chandra Chekuri and Sanjeev Khanna. On Multidimensional Packing Problems. SIAM J. Comput., 33(4):837-851, 2004. URL: http://dx.doi.org/10.1137/S0097539799356265.
  8. Jian-Jia Chen. Partitioned Multiprocessor Fixed-Priority Scheduling of Sporadic Real-Time Tasks. In Euromicro Conference on Real-Time Systems (ECRTS), pages 251-261, 2016. Google Scholar
  9. Jian-Jia Chen, Nikhil Bansal, Samarjit Chakraborty, and Georg von der Brüggen. Packing Sporadic Real-Time Tasks on Identical Multiprocessor Systems. Computing Research Repository (CoRR), 2018. http://arxiv.org/abs/1809.04355. Google Scholar
  10. Jian-Jia Chen and Samarjit Chakraborty. Resource Augmentation Bounds for Approximate Demand Bound Functions. In IEEE Real-Time Systems Symposium, pages 272-281, 2011. Google Scholar
  11. Jian-Jia Chen and Samarjit Chakraborty. Partitioned Packing and Scheduling for Sporadic Real-Time Tasks in Identical Multiprocessor Systems. In ECRTS, pages 24-33, 2012. Google Scholar
  12. Jian-Jia Chen, Georg von der Brüggen, Wen-Hung Huang, and Robert I Davis. On the Pitfalls of Resource Augmentation Factors and Utilization Bounds in Real-Time Scheduling. In Euromicro Conference on Real-Time Systems, ECRTS, pages 9:1-9:25, 2017. Google Scholar
  13. Lin Chen, Nicole Megow, and Kevin Schewior. An O(log m)-Competitive Algorithm for Online Machine Minimization. In Symposium on Discrete Algorithms, SODA, pages 155-163, 2016. Google Scholar
  14. Lin Chen, Nicole Megow, and Kevin Schewior. The Power of Migration in Online Machine Minimization. In Symposium on Parallelism in Algorithms and Architectures, pages 175-184, 2016. Google Scholar
  15. Robert I. Davis and Alan Burns. A survey of hard real-time scheduling for multiprocessor systems. ACM Comput. Surv., 43(4):35, 2011. Google Scholar
  16. Wenceslas Fernandez de la Vega and George S. Lueker. Bin packing can be solved within 1+epsilon in linear time. Combinatorica, 1(4):349-355, 1981. URL: http://dx.doi.org/10.1007/BF02579456.
  17. Friedrich Eisenbrand and Thomas Rothvoß. EDF-schedulability of synchronous periodic task systems is coNP-hard. In Symposium on Discrete Algorithms (SODA), pages 1029-1034, 2010. URL: http://www.siam.org/proceedings/soda/2010/SODA10_083_eisenbrandf.pdf.
  18. Pontus Ekberg and Wang Yi. Uniprocessor Feasibility of Sporadic Tasks Remains coNP-Complete under Bounded Utilization. In IEEE Real-Time Systems Symposium, RTSS, pages 87-95, 2015. Google Scholar
  19. Pontus Ekberg and Wang Yi. Uniprocessor Feasibility of Sporadic Tasks with Constrained Deadlines Is Strongly coNP-Complete. In Euromicro Conference on Real-Time Systems, ECRTS, pages 281-286, 2015. Google Scholar
  20. M. R. Garey and D. S. Johnson. Computers and intractability: A guide to the theory of NP-completeness. W. H. Freeman and Co., 1979. Google Scholar
  21. Ronald L. Graham. Bounds on Multiprocessing Timing Anomalies. SIAM Journal of Applied Mathematics, 17(2):416-429, 1969. Google Scholar
  22. Dorit S. Hochbaum and David B. Shmoys. Using dual approximation algorithms for scheduling problems theoretical and practical results. J. ACM, 34(1):144-162, 1987. URL: http://dx.doi.org/10.1145/7531.7535.
  23. Sungjin Im, Benjamin Moseley, Kirk Pruhs, and Clifford Stein. An O(log log m)-competitive Algorithm for Online Machine Minimization. In Real-Time Systems Symposium, (RTSS), pages 343-350, 2017. Google Scholar
  24. Viggo Kann. Maximum bounded 3-dimensional matching is MAX SNP-complete. Inf. Process. Lett., 37(1):27-35, January 1991. Google Scholar
  25. N. Karmarkar and R. M. Karp. An Efficient Approximation Scheme for the One-Dimensional Bin-Packing Problem. In Symp. on Foundations of Computer Science (FOCS), pages 312-320, 1982. Google Scholar
  26. Andreas Karrenbauer and Thomas Rothvoß. A 3/2-Approximation Algorithm for Rate-Monotonic Multiprocessor Scheduling of Implicit-Deadline Tasks. In International Workshop of Approximation and Online Algorithms WAOA, pages 166-177, 2010. URL: http://dx.doi.org/10.1007/978-3-642-18318-8_15.
  27. C. L. Liu and James W. Layland. Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment. Journal of the ACM, 20(1):46-61, 1973. Google Scholar
  28. A. K. Mok. Fundamental design problems of distributed systems for the hard-real-time environment. Technical report, Massachusetts Institute of Technology, Cambridge, MA, USA, 1983. Google Scholar
  29. K. Pruhs, E. Torng, and J. Sgall. Online scheduling. In Joseph Y. T. Leung, editor, Handbook of Scheduling: Algorithms, Models, and Performance Analysis, chapter 15, pages 15:1-15:41. Chapman and Hall/CRC, 2004. Google Scholar
  30. Vijay V. Vazirani. Approximation Algorithms. Springer, 2001. Google Scholar
  31. Gerhard J. Woeginger. There is no Asymptotic PTAS for Two-Dimensional Vector Packing. Inf. Process. Lett., 64(6):293-297, 1997. URL: http://dx.doi.org/10.1016/S0020-0190(97)00179-8.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact