Document Open Access Logo

Safe and Optimal Scheduling for Hard and Soft Tasks

Authors Gilles Geeraerts, Shibashis Guha, Jean-François Raskin

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2018.36.pdf
  • Filesize: 0.59 MB
  • 22 pages

Document Identifiers

Author Details

Gilles Geeraerts
  • Université libre de Bruxelles, Brussels, Belgium
Shibashis Guha
  • Université libre de Bruxelles, Brussels, Belgium
Jean-François Raskin
  • Université libre de Bruxelles, Brussels, Belgium

Cite As Get BibTex

Gilles Geeraerts, Shibashis Guha, and Jean-François Raskin. Safe and Optimal Scheduling for Hard and Soft Tasks. In 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 122, pp. 36:1-36:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.FSTTCS.2018.36

Abstract

We consider a stochastic scheduling problem with both hard and soft tasks on a single machine. Each task is described by a discrete probability distribution over possible execution times, and possible inter-arrival times of the job, and a fixed deadline. Soft tasks also carry a penalty cost to be paid when they miss a deadline. We ask to compute an online and non-clairvoyant scheduler (i.e. one that must take decisions without knowing the future evolution of the system) that is safe and efficient. Safety imposes that deadline of hard tasks are never violated while efficient means that we want to minimise the mean cost of missing deadlines by soft tasks.
First, we show that the dynamics of such a system can be modelled as a finite Markov Decision Process (MDP). Second, we show that our scheduling problem is PP-hard and in EXPTime. Third, we report on a prototype tool that solves our scheduling problem by relying on the Storm tool to analyse the corresponding MDP. We show how antichain techniques can be used as a potential heuristic.

Subject Classification

ACM Subject Classification
  • Theory of computation → Probabilistic computation
  • Computer systems organization → Real-time system specification
  • Computer systems organization → Embedded systems
Keywords
  • Non-clairvoyant scheduling
  • hard and soft tasks
  • automatic synthesis
  • Markov decision processes

Metrics

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

References

  1. L. Abeni and G. Buttazzo. Integrating Multimedia Applications in Hard Real-Time Systems. In Proceedings of the IEEE Real-Time Systems Symposium, RTSS '98, pages 4-13, Washington, DC, USA, 1998. IEEE Computer Society. Google Scholar
  2. L. Abeni and G. C. Buttazzo. Stochastic Analysis of a Reseveration Based System. In Proceedings of the 15th International Parallel & Distributed Processing Symposium (IPDPS-01), San Francisco, CA, April 23-27, 2001, pages 92-98, 2001. Google Scholar
  3. S. Almagor, O. Kupferman, and Y. Velner. Minimizing Expected Cost Under Hard Boolean Constraints, with Applications to Quantitative Synthesis. In Proc. 27th Int. Conf. on Concurrency Theory, volume 59 of LIPIcs, pages 9:1-9:15, 2016. Google Scholar
  4. R. Alur, T.A. Henzinger, O. Kupferman, and M.Y. Vardi. Alternating refinement relations. In Proc. 9th Int. Conf. on Concurrency Theory, volume 1466 of Lecture Notes in Computer Science, pages 163-178. Springer, 1998. Google Scholar
  5. A. Atlas and A. Bestavros. Statistical Rate Monotonic Scheduling. In Proceedings of the 19th IEEE Real-Time Systems Symposium, Madrid, Spain, December 2-4, 1998, pages 123-132, 1998. Google Scholar
  6. H. Aydin, R. G. Melhem, D. Mossé, and P. Mejía-Alvarez. Optimal Reward-Based Scheduling of Periodic Real-Time Tasks. In Proceedings of the 20th IEEE Real-Time Systems Symposium, Phoenix, AZ, USA, December 1-3, 1999, pages 79-89, 1999. Google Scholar
  7. S. K. Baruah, A. K. Mok, and L. E. Rosier. Preemptively Scheduling Hard-Real-Time Sporadic Tasks on One Processor. In Proceedings of the Real-Time Systems Symposium - 1990, Lake Buena Vista, Florida, USA, December 1990, pages 182-190, 1990. Google Scholar
  8. S. K. Baruah, L. E. Rosier, and R. R. Howell. Algorithms and Complexity Concerning the Preemptive Scheduling of Periodic, Real-Time Tasks on One Processor. Real-Time Systems, 2(4):301-324, 1990. Google Scholar
  9. V. Bruyère, E. Filiot, M. Randour, and J-F. Raskin. Meet Your Expectations With Guarantees: Beyond Worst-Case Synthesis in Quantitative Games. In Proc. 31th Symp. on Theoretical Aspects of Computer Science, volume 25 of LIPIcs, pages 199-213, 2014. Google Scholar
  10. G. Buttazzo. Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications. Springer Publishing Company, Incorporated, 3rd edition, 2011. Google Scholar
  11. H. Chetto and M. Chetto. Some Results of the Earliest Deadline Scheduling Algorithm. IEEE Trans. Software Eng., 15(10):1261-1269, 1989. Google Scholar
  12. L. Clemente and J-F. Raskin. Multidimensional beyond Worst-Case and Almost-Sure Problems for Mean-Payoff Objectives. In Proc. 30th IEEE Symp. on Logic in Computer Science, pages 257-268, 2015. Google Scholar
  13. C. Dehnert, S. Junges, J-P. Katoen, and M. Volk. A Storm is Coming: A Modern Probabilistic Model Checker. In Computer Aided Verification - 29th International Conference, CAV 2017, Heidelberg, Germany, Proceedings, Part II, pages 592-600, 2017. Google Scholar
  14. S. K. Dhall and C. L. Liu. On a Real-Time Scheduling Problem. Oper. Res., 26(1):127-140, February 1978. Google Scholar
  15. J. L. Díaz, D. F. García, K. Kim, C-G. Lee, L. L. Bello, J. M. López, S. L. Min, and O. Mirabella. Stochastic Analysis of Periodic Real-Time Systems. In Proceedings of the 23rd IEEE Real-Time Systems Symposium, RTSS '02, pages 289-300, Washington, DC, USA, 2002. IEEE Computer Society. Google Scholar
  16. L. Doyen and J.-F. Raskin. Antichains for the Automata-Based Approach to Model-Checking. Logical Methods in Computer Science, 5(1), 2009. Google Scholar
  17. J. Filar and K. Vrieze. Competitive Markov decision processes. Springer, 1997. Google Scholar
  18. M. K. Gardner. Probabilistic Analysis and Scheduling of Critical Soft Real-Time Systems. PhD thesis, University of Illinois at Urbana-Champaign, Champaign, IL, USA, 1999. Google Scholar
  19. M. K. Gardner and J. W.-S. Liu. Analyzing Stochastic Fixed-Priority Real-Time Systems. In Proceedings of the 5th International Conference on Tools and Algorithms for Construction and Analysis of Systems, TACAS '99, pages 44-58, London, UK, UK, 1999. Springer-Verlag. Google Scholar
  20. G. Geeraerts, J. Goossens, T-V-A Nguyen, and A. Stainer. Synthesising succinct strategies in safety games with an application to real-time scheduling. Theoretical Computer Science, 735:24-49, 2018. Google Scholar
  21. John Gill. Computational Complexity of Probabilistic Turing Machines. SIAM Journal on Computing, 6(4):675-695, 1977. Google Scholar
  22. C. Haase and S. Kiefer. The complexity of the Kth largest subset problem and related problems. Information Processing Letters, 116(2):111-115, 2016. Google Scholar
  23. A. A. Hagberg, D. A. Schult, and P. J. Swart. Exploring Network Structure, Dynamics, and Function Using NetworkX. In Proceedings of the 7th Python in Science Conference, pages 11-15, 2008. Google Scholar
  24. K. S. Hong and J. Y.-T. Leung. On-Line Scheduling of Real-Time Tasks. In Proceedings of the 9th IEEE Real-Time Systems Symposium (RTSS '88), December 6-8, 1988, Huntsville, Alabama, USA, pages 244-250, 1988. Google Scholar
  25. J. P. Lehoczky, L. Sha, and I. Strosnider. Enhanced aperiodic responsiveness in a hard real-time environment. In Real-Time Systems Symposium, pages 261-270, 1987. Google Scholar
  26. J. Y.-T. Leung and M. L. Merrill. A Note on Preemptive Scheduling of Periodic, Real-Time Tasks. Information Processing Letters, 11(3):115-118, 1980. Google Scholar
  27. J. Y.-T. Leung and J. Whitehead. On the complexity of fixed-priority scheduling of periodic, real-time tasks. Perform. Eval., 2(4):237-250, 1982. Google Scholar
  28. K-J Lin, S. Natarajan, and J. W.-S. Liu. Imprecise Results: Utilizing Partial Comptuations in Real-Time Systems. In Proceedings of the 8th IEEE Real-Time Systems Symposium (RTSS '87), December 1-3, 1987, San Jose, Califorinia, USA, pages 210-217, 1987. Google Scholar
  29. C. L. Liu and J. W. Layland. Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment. Journal of the ACM, 20(1):46-61, January 1973. Google Scholar
  30. J. W. S. Liu, K. J. Lin, W. K. Shih, A. C. Yu, J. Y. Chung, and W. Zhao. Algorithms for Scheduling Imprecise Computations, pages 203-249. Springer US, Boston, MA, 1991. Google Scholar
  31. Y. Lu, T. Nolte, I. Bate, and L. Cucu-Grosjean. A Statistical Response-Time Analysis of Real-Time Embedded Systems. In Proceedings of the 33rd IEEE Real-Time Systems Symposium, RTSS 2012, San Juan, PR, USA, December 4-7, 2012, pages 351-362, 2012. Google Scholar
  32. Y. Lu, T. Nolte, J. Kraft, and C. Norström. A Statistical Approach to Response-Time Analysis of Complex Embedded Real-Time Systems. In 16th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2010, Macau, SAR, China, 23-25 August 2010, pages 153-160, 2010. Google Scholar
  33. D. Maxim, R. I. Davis, L. Cucu-Grosjean, and A. Easwaran. Probabilistic analysis for mixed criticality systems using fixed priority preemptive scheduling. In Proceedings of the 25th International Conference on Real-Time Networks and Systems, RTNS 2017, Grenoble, France, October 04 - 06, 2017, pages 237-246, 2017. Google Scholar
  34. A. K. Mok. Fundamental design problems of distributed systems for the hard-real-time environment. PhD thesis, Massachusetts Institute of Technology, Cambridge, MA, USA, 1983. Google Scholar
  35. C. H. Papadimitriou and J. N. Tsitsiklis. The Complexity of Markov Decision Processes. Math. Oper. Res., 12(3):441-450, 1987. Google Scholar
  36. M.L. Puterman. Markov Decision Processes. Wiley, 1994. Google Scholar
  37. J. Simon. On Some Central Problems in Computational Complexity. PhD thesis, Cornell University, Ithaca, NY, USA, 1975. Google Scholar
  38. B. Sprunt, L. Sha, and J. Lehoczky. Aperiodic task scheduling for Hard-Real-Time systems. Real-Time Systems, 1(1):27-60, June 1989. Google Scholar
  39. M. Spuri and G. Buttazzo. Efficient Aperiodic Service Under Earliest Deadline Scheduling. In Proceedings of the 15th IEEE Real-Time Systems Symposium (RTSS '94), San Juan, Puerto Rico, December 7-9, 1994, pages 2-11, 1994. Google Scholar
  40. M. Spuri and G. Buttazzo. Scheduling aperiodic tasks in dynamic priority systems. Real-Time Systems, 10(2):179-210, 1996. Google Scholar
  41. A. Srinivasan and J. H. Anderson. Efficient Scheduling of Soft Real-time Applications on Multiprocessors. J. Embedded Comput., 1(2):285-302, April 2005. Google Scholar
  42. Wolfgang Thomas. On the Synthesis of Strategies in Infinite Games. In STACS, pages 1-13, 1995. URL: http://dx.doi.org/10.1007/3-540-59042-0_57.
  43. 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 Proceedings of the Real-Time Technology and Applications Symposium, RTAS '95, pages 164-173, Washington, DC, USA, 1995. IEEE Computer Society. Google Scholar
  44. M. Wen and U. Topcu. Probably Approximately Correct Learning in Stochastic Games with Temporal Logic Specifications. In Proc. 25th Int. Joint Conf. on Artificial Intelligence, pages 3630-3636. IJCAI/AAAI Press, 2016. Google Scholar
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