Document Open Access Logo

A Survey of Probabilistic Schedulability Analysis Techniques for Real-Time Systems

Authors Robert I. Davis , Liliana Cucu-Grosjean

PDF
Thumbnail PDF

File

LITES-v006-i001-a004.pdf
  • Filesize: 0.93 MB
  • 53 pages

Document Identifiers

Author Details

Robert I. Davis
  • University of York, UK
  • Inria, France
Liliana Cucu-Grosjean
  • Inria, France

Cite AsGet BibTex

Robert I. Davis and Liliana Cucu-Grosjean. A Survey of Probabilistic Schedulability Analysis Techniques for Real-Time Systems. In LITES, Volume 6, Issue 1 (2019). Leibniz Transactions on Embedded Systems, Volume 6, Issue 1, pp. 04:1-04:53, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LITES-v006-i001-a004

Abstract

This survey covers schedulability analysis techniques for probabilistic real-time systems. It reviews the key results in the field from its origins in the late 1980s to the latest research published up to the end of August 2018. The survey outlinesfundamental concepts and highlights key issues. It provides a taxonomy of the different methods used, and a classification of existing research. A detailed review is provided covering the main subject areas as well as research on supporting techniques. The survey concludes by identifying open issues, key challenges and possible directions for future research.

Subject Classification

ACM Subject Classification
  • Computer systems organization
  • Computer systems organization → Real-time systems
Keywords
  • Probabilistic
  • real-time
  • schedulability analysis
  • scheduling

Metrics

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

References

  1. Y. Abdeddaim and D. Maxim.Probabilistic Schedulability Analysis for Fixed Priority Mixed Criticality Real-Time Systems. In Proceedings of the Conference on Design, Automation and Test in Europe (DATE), 2017. Google Scholar
  2. L. Abeni and G. Buttazzo.Integrating multimedia applications in hard real-time systems. In Proceedings of the IEEE Real-Time Systems Symposium (RTSS), pages 4-13, December 1998. URL: http://dx.doi.org/10.1109/REAL.1998.739726
  3. L. Abeni and G. Buttazzo.QoS guarantee using probabilistic deadlines. In Proceedings of the Euromicro Conference on Real-Time Systems (ECRTS), pages 242-249, 1999. URL: http://dx.doi.org/10.1109/EMRTS.1999.777471
  4. L. Abeni and G. Buttazzo.Stochastic analysis of a reservation based system. In Proceedings 15th International Parallel and Distributed Processing Symposium. IPDPS 2001, pages 946-952, April 2001. URL: http://dx.doi.org/10.1109/IPDPS.2001.925049
  5. L. Abeni, D. Fontanelli, L. Palopoli, and B. Villalba Frías.A Markovian model for the computation time of real-time applications. In Proceedings of IEEE International Instrumentation and Measurement Technology Conference (I2MTC), pages 1-6, May 2017. URL: http://dx.doi.org/10.1109/I2MTC.2017.7969878
  6. L. Abeni, N. Manica, and L. Palopoli.Efficient and Robust Probabilistic Guarantees for Real-time Tasks. J. Syst. Softw., 85(5):1147-1156, May 2012. URL: http://dx.doi.org/10.1016/j.jss.2011.12.042
  7. Z. Alabedin, H. Hammadeh, S. Quinton, and R. Ernst.Extending typical worst-case analysis using response-time dependencies to bound deadline misses. In Proceedings of the IEEE & ACM International Conference on Embedded Software (EMSOFT), pages 10:1-10:10, 2014. URL: http://dx.doi.org/10.1145/2656045.2656059
  8. B. Alahmad and S. Gopalakrishnan.A Risk-Constrained Markov Decision Process Approach to Scheduling Mixed-Criticality Job Sets. In Proceedings of Workshop on Mixed Criticality (WMC), 2016. Google Scholar
  9. B. Alahmad and S. Gopalakrishnan.Risk-aware scheduling of dual criticality job systems using demand distributions. Leibniz Transactions on Embedded Systems. In Leibniz Transactions on Embedded Systems (LITES), 2016. Google Scholar
  10. S. Altmeyer, L. Cucu-Grosjean, and R. I. Davis.Static probabilistic timing analysis for real-time systems using random replacement caches.Springer Real-Time Systems, 51(1):77-123, 2015. URL: http://dx.doi.org/10.1007/s11241-014-9218-4
  11. S. Altmeyer and R. I. Davis.On the Correctness, Optimality and Precision of Static Probabilistic Timing Analysis. In Proceedings of the Conference on Design, Automation and Test in Europe (DATE), pages 26:1-26:6, 2014. URL: http://dl.acm.org/citation.cfm?id=2616606.2616638.
  12. S. Altmeyer, R. I. Davis, L. Indrusiak, C. Maiza, V. Nelis, and J. Reineke.A Generic and Compositional Framework for Multicore Response Time Analysis. In Proceedings of the International Conference on Real-Time Networks and Systems (RTNS), pages 129-138, 2015. URL: http://dx.doi.org/10.1145/2834848.2834862
  13. A. Atlas and A. Bestavros.Statistical rate monotonic scheduling. In Real-Time Systems Symposium, 1998. Proceedings., The 19th IEEE, pages 123-132, December 1998. URL: http://dx.doi.org/10.1109/REAL.1998.739737
  14. N. Audsley, A. Burns, M. Richardson, K. Tindell, and A. J. Wellings.Applying new scheduling theory to static priority pre-emptive scheduling. Software Engineering Journal, 8(5):284-292, 1993. Google Scholar
  15. N.C. Audsley.On priority assignment in fixed priority scheduling. Information Processing Letters, 79(1):39-44, 2001. URL: http://dx.doi.org/10.1016/S0020-0190(00)00165-4
  16. P. Axer and R. Ernst.Stochastic response-time guarantee for non-preemptive fixed-priority scheduling under errors. In Proceedings of the Design Automation Conference (DAC), pages 1-7, May 2013. URL: http://dx.doi.org/10.1145/2463209.2488946
  17. P. Axer, M. Sebastian, and R. Ernst.Probabilistic response time bound for CAN messages with arbitrary deadlines. In Proceedings of the Conference on Design, Automation and Test in Europe (DATE), pages 1114-1117, March 2012. URL: http://dx.doi.org/10.1109/DATE.2012.6176662
  18. H. Aysan, R. Dobrin, S. Punnekkat, and R. Johansson.Probabilistic Schedulability Guarantees for Dependable Real-Time Systems under Error Bursts. In Proceedings of IEEE International Conference on Trust, Security and Privacy in Computing and Communications, pages 1154-1163, November 2011. URL: http://dx.doi.org/10.1109/TrustCom.2011.157
  19. H. Aysan, R. Dobrin, S. Punnekkat, and J. Proenza.Probabilistic scheduling guarantees in distributed real-time systems under error bursts. In Proceedings of the IEEE Conference on Emerging Technologies Factory Automation (ETFA), pages 1-9, September 2012. URL: http://dx.doi.org/10.1109/ETFA.2012.6489644
  20. D. Y. Barrer.Queuing with Impatient Customers and Ordered Service. Operations Research, 5(5):650-656, 1957. URL: http://dx.doi.org/10.1287/opre.5.5.650
  21. S. Baruah and A. Burns.Sustainable Scheduling Analysis. In Proceedings of the IEEE Real-Time Systems Symposium (RTSS), pages 159-168, 2006. URL: http://dx.doi.org/10.1109/RTSS.2006.47
  22. S. K. Baruah, A. Burns, and R. I. Davis.Response-time analysis for mixed criticality systems. In Proceedings of the IEEE Real-Time Systems Symposium (RTSS), pages 34-43. IEEE, 2011. Google Scholar
  23. S. Ben-Amor, D. Maxim, and L. Cucu-Grosjean.Schedulability Analysis of Dependent Probabilistic Real-time Tasks. In Proceedings of the International Conference on Real-Time Networks and Systems (RTNS), pages 99-107. ACM, 2016. URL: http://dx.doi.org/10.1145/2997465.2997499
  24. G. Bernat, A Burns, and A Liamosi.Weakly hard real-time systems.IEEE Transactions on Computers, 50(4):308-321, April 2001. URL: http://dx.doi.org/10.1109/12.919277
  25. G. Bernat and R. Cayssials.Guaranteed on-line weakly-hard real-time systems. In Proceedings of the IEEE Real-Time Systems Symposium (RTSS), pages 25-35, December 2001. URL: http://dx.doi.org/10.1109/REAL.2001.990593
  26. I. Broster and A. Burns.1st International Workshop on Probabilistic Analysis Techniques for Real-Time and Embedded Systems (PARTES). In Random Arrivals in Fixed Priority Analysis, 2004. Google Scholar
  27. I. Broster and A. Burns.Work-in-Progress of the IEEE Real-Time Systems Symposium. In Applying Random Arrival Models to Fixed Priority Analysis, December 2004. Google Scholar
  28. I. Broster, A. Burns, and G. Rodriguez-Navas.Probabilistic analysis of CAN with faults. In Proceedings of the IEEE Real-Time Systems Symposium (RTSS), pages 269-278, 2002. URL: http://dx.doi.org/10.1109/REAL.2002.1181581
  29. I. Broster, A. Burns, and G. RodrÍguez-Navas.Timing Analysis of Real-Time Communication Under Electromagnetic Interference.Springer Real-Time Systems, 30(1):55-81, 2005. URL: http://dx.doi.org/10.1007/s11241-005-0504-z
  30. A. Burns, G. Bernat, and I. Broster.A Probabilistic Framework for Schedulability Analysis, pages 1-15. Springer Berlin Heidelberg, Berlin, Heidelberg, 2003. URL: http://dx.doi.org/10.1007/978-3-540-45212-6_1
  31. A. Burns and R. I. Davis.A Survey of Research into Mixed Criticality Systems. ACM Comput. Surv., 50(6):82:1-82:37, November 2017. URL: http://dx.doi.org/10.1145/3131347
  32. A. Burns and S. Edgar.Predicting computation time for advanced processor architectures. In Proceedings of the Euromicro Conference on Real-Time Systems (ECRTS), pages 89-96, 2000. URL: http://dx.doi.org/10.1109/EMRTS.2000.853996
  33. A. Burns, S. Punnekkat, L. Strigini, and D. R. Wright.Probabilistic scheduling guarantees for fault-tolerant real-time systems. In Dependable Computing for Critical Applications 7, 1999, pages 361-378, November 1999. URL: http://dx.doi.org/10.1109/DCFTS.1999.814306
  34. L. Carnevali, A. Melani, L. Santinelli, and G. Lipari.Probabilistic Deadline Miss Analysis of Real-Time Systems Using Regenerative Transient Analysis. In Proceedings of the International Conference on Real-Time Networks and Systems (RTNS), pages 299:299-299:308, 2014. URL: http://dx.doi.org/10.1145/2659787.2659823
  35. F. J. Cazorla, E. Quiñones, T. Vardanega, L. Cucu, B. Triquet, G. Bernat, E. Berger, J. Abella, F. Wartel, M. Houston, L. Santinelli, L. Kosmidis, C. Lo, and D. Maxim.PROARTIS: Probabilistically Analyzable Real-Time Systems.ACM Transactions on Embedded Computing Systems, 12(2s):94:1-94:26, May 2013. URL: http://dx.doi.org/10.1145/2465787.2465796
  36. K. H. Chen and J. J. Chen.Probabilistic schedulability tests for uniprocessor fixed-priority scheduling under soft errors. In Proceedings of the IEEE International Symposium on Industrial Embedded Systems (SIES), pages 1-8, June 2017. URL: http://dx.doi.org/10.1109/SIES.2017.7993392
  37. Kuan-Hsun Chen, Georg von der Bruggen, and Jian-Jia Chen.Analysis of Deadline Miss Rates for Uniprocessor Fixed-Priority Scheduling. In Proceedings of the IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA), August 2018. Google Scholar
  38. H. Chetto, M. Silly, and T. Bouchentouf.Dynamic Scheduling of Real-time Tasks Under Precedence Constraints.Springer Real-Time Systems, 2(3):181-194, September 1990. URL: http://dx.doi.org/10.1007/BF00365326
  39. S. Coles.An Introduction to Statistical Modeling of Extreme Values. Springer, 2001. URL: http://dx.doi.org/10.1007/978-1-4471-3675-0
  40. L. Cucu.Preliminary results for introducing dependent random variables in stochastic feasibility analysis on CAN. In Proceedings of IEEE International Workshop on Factory Communication Systems (WFCS), pages 271-274, Dresden, Germany, May 2008. IEEE. URL: http://dx.doi.org/10.1109/WFCS.2008.4638759
  41. L. Cucu and E. Tovar.A Framework for the Response Time Analysis of Fixed-priority Tasks with Stochastic Inter-arrival Times. SIGBED Rev., 3(1):7-12, January 2006. URL: http://dx.doi.org/10.1145/1279711.1279714
  42. L. Cucu-Grosjean.Independence a misunderstood property of and for probabilistic real-time systems. In Real-Time Systems: the past, the present and the future, pages 29-37, 2013. Google Scholar
  43. L. Cucu-Grosjean.Probabilistic real-time scheduling. In ETR 2013-Ecole d'été temps réel, 2013. Google Scholar
  44. L. Cucu-Grosjean, L. Santinelli, M. Houston, C. Lo, T. Vardanega, L. Kosmidis, J. Abella, E. Mezzetti, E. Quiñones, and F. J. Cazorla.Measurement-Based Probabilistic Timing Analysis for Multi-path Programs. In Proceedings of the Euromicro Conference on Real-Time Systems (ECRTS), pages 91-101, July 2012. URL: http://dx.doi.org/10.1109/ECRTS.2012.31
  45. R. I. Davis.A review of fixed priority and EDF scheduling for hard real-time uniprocessor systems. ACM SIGBED Review, 11(1):8-19, 2014. Google Scholar
  46. R. I. Davis, S. Altmeyer, L. S. Indrusiak, C. Maiza, V. Nelis, and J. Reineke.An extensible framework for multicore response time analysis.Springer Real-Time Systems, 54(3):607-661, July 2018. URL: http://dx.doi.org/10.1007/s11241-017-9285-4
  47. R. I. Davis and A. Burns.Robust Priority Assignment for Fixed Priority Real-Time Systems. In Proceedings of the IEEE Real-Time Systems Symposium (RTSS), pages 3-14, December 2007. URL: http://dx.doi.org/10.1109/RTSS.2007.11
  48. R. I. Davis and A. Burns.Robust priority assignment for messages on Controller Area Network (CAN).Springer Real-Time Systems, 41(2):152-180, 2009. URL: http://dx.doi.org/10.1007/s11241-008-9065-2
  49. R. I Davis and A. Burns.A survey of hard real-time scheduling for multiprocessor systems. ACM Computing Surveys (CSUR), 43(4):35, 2011. Google Scholar
  50. R. I Davis, A. Burns, R. J. Bril, and J. J. Lukkien.Controller Area Network (CAN) schedulability analysis: Refuted, revisited and revised.Springer Real-Time Systems, 35(3):239-272, 2007. Google Scholar
  51. R. I. Davis, A. Burns, R. J. Bril, and J. J. Lukkien.Controller Area Network (CAN) schedulability analysis: Refuted, revisited and revised. Real-Time Systems, 35(3):239-272, 2007. URL: http://dx.doi.org/10.1007/s11241-007-9012-7
  52. R. I. Davis and L. Cucu-Grosjean.A Survey of Probabilistic Timing Analysis Techniques for Hard Real-Time Systems. Leibniz Transactions on Embedded Systems (LITES), 6(1):03:1-03:60, May 2019. URL: http://dx.doi.org/10.4230/LITES-v006-i001-a003
  53. R. I. Davis, L. Santinelli, S. Altmeyer, C. Maiza, and L. Cucu-Grosjean.Analysis of Probabilistic Cache Related Pre-emption Delays. In Proceedings of the Euromicro Conference on Real-Time Systems (ECRTS), pages 168-179, July 2013. URL: http://dx.doi.org/10.1109/ECRTS.2013.27
  54. J. L. Diaz, D. F. Garcia, K. Kim, C-G. Lee, L. Lo Bello, J. M. Lopez, S. L. Min, and O. Mirabella.Stochastic analysis of periodic real-time systems. In Proceedings of the IEEE Real-Time Systems Symposium (RTSS), pages 289-300, 2002. URL: http://dx.doi.org/10.1109/REAL.2002.1181583
  55. J. L. Diaz, J. M. Lopez, M. Garcia, A. M. Campos, Kanghee Kim, and L. L. Bello.Pessimism in the stochastic analysis of real-time systems: concept and applications. In Proceedings of the IEEE Real-Time Systems Symposium (RTSS), pages 197-207, December 2004. URL: http://dx.doi.org/10.1109/REAL.2004.41
  56. B. Doytchinov, J. Lehoczky, and S. Shreve.Real-time queues in heavy traffic with earliest-deadline-first queue discipline. The Annals of Applied Probability, 11(2):332-378, 2001. URL: http://dx.doi.org/10.1214/aoap/1015345295
  57. S. Draskovic, P. Huang, and L. Thiele.On the Safety of Mixed-Criticality Scheduling. In Proceedings of Workshop on Mixed Criticality (WMC), 2016. Google Scholar
  58. S. Edgar and A. Burns.Statistical analysis of WCET for scheduling. In Proceedings of the IEEE Real-Time Systems Symposium (RTSS), pages 215-224, December 2001. URL: http://dx.doi.org/10.1109/REAL.2001.990614
  59. B. Frias, L. Palopoli, L. Abeni, and D. Fontanelli.Probabilistic Real-Time Guarantees: There is Life Beyond the i.i.d. Assumption. In Proceedings of the IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), April 2017. Google Scholar
  60. M. K. Gardner and J. W. S. Liu.Analyzing Stochastic Fixed-Priority Real-Time Systems, pages 44-58. Springer Berlin Heidelberg, Berlin, Heidelberg, 1999. URL: http://dx.doi.org/10.1007/3-540-49059-0_4
  61. S. Gopalakrishnan.Sharp utilization thresholds for some real-time scheduling problems. CoRR, abs/0912.3852, 2009. URL: http://arxiv.org/abs/0912.3852.
  62. D. Griffin, I. Bate, B. Lesage, and F. Soboczenski.Evaluating Mixed Criticality Scheduling Algorithms with Realistic Workloads. In Proceedings of Workshop on Mixed Criticality (WMC), 2015. Google Scholar
  63. H. Christian Gromoll and Łukasz Kruk.Heavy traffic limit for a processor sharing queue with soft deadlines. The Annals of Applied Probability, 17(3):1049-1101, June 2007. URL: http://dx.doi.org/10.1214/105051607000000014
  64. Z. Guo, L. Santinalli, and K. Yang.EDF Schedulability Analysis on Mixed-Criticality Systems with Permitted Failure Probability. In Proceedings of the IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA), 2015. Google Scholar
  65. C. J. Hamann, J. Loser, L. Reuther, S. Schonberg, J. Wolter, and H. Hartig.Quality-assuring scheduling-using stochastic behavior to improve resource utilization. In Proceedings of the IEEE Real-Time Systems Symposium (RTSS), pages 119-128, December 2001. URL: http://dx.doi.org/10.1109/REAL.2001.990603
  66. J. Hansen, S. A. Hissam, and G. A. Moreno. Statistical-based WCET estimation and validation . In Proceedings of the Workshop on Worst-Case Execution Time Analysis (WCET), volume 252, 2009. Google Scholar
  67. J. P. Hansen, J. P. Lehoczky, H. Zhu, and R. Rajkumar.Quantized EDF Scheduling in a Stochastic Environment. In Proceedings of the 16th International Parallel and Distributed Processing Symposium, IPDPS '02, pages 279-, Washington, DC, USA, 2002. IEEE Computer Society. URL: http://dl.acm.org/citation.cfm?id=645610.660905.
  68. X. S. Hu, Tao Zhou, and E. H. M. Sha.Estimating probabilistic timing performance for real-time embedded systems. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 9(6):833-844, December 2001. URL: http://dx.doi.org/10.1109/92.974897
  69. S. Hua, G. Qu, and S. S. Bhattacharyya.Exploring the probabilistic design space of multimedia systems. In in IEEE International Workshop on Rapid System Prototyping, 2003, pages 233-240, 2003. Google Scholar
  70. M. Ivers and R. Ernst.Probabilistic Network Loads with Dependencies and the Effect on Queue Sojourn Times, pages 280-296. Springer Berlin Heidelberg, 2009. URL: http://dx.doi.org/10.1007/978-3-642-10625-5_18
  71. M. Joseph and P. Pandya.Finding response times in a real-time system. The Computer Journal, 29(5):390-395, 1986. Google Scholar
  72. G. A. Kaczynski, L. Lo Bello, and T. Nolte.Deriving exact stochastic response times of periodic tasks in hybrid priority-driven soft real-time systems. In Proceedings of the IEEE Conference on Emerging Technologies Factory Automation (ETFA), pages 101-110, September 2007. URL: http://dx.doi.org/10.1109/EFTA.2007.4416759
  73. D. G. Kendall.Stochastic Processes Occurring in the Theory of Queues and their Analysis by the Method of the Imbedded Markov Chain. The Annals of Mathematical Statistics, 24(3):338-354, September 1953. URL: http://dx.doi.org/10.1214/aoms/1177728975
  74. D. A. Khan, L. Santinelli, and L. Cucu-Grosjean.Modeling uncertainties in safety-critical real-time systems: A probabilistic component-based analysis. In Proceedings of the IEEE International Symposium on Industrial Embedded Systems (SIES), pages 166-175, June 2012. URL: http://dx.doi.org/10.1109/SIES.2012.6356582
  75. J. K. Kim and B. K. Kim.Probabilistic Schedulability Analysis of Harmonic Multi-Task Systems with Dual-Modular Temporal Redundancy.Springer Real-Time Systems, 26(2):199-222, March 2004. URL: http://dx.doi.org/10.1023/B:TIME.0000016130.91111.75
  76. K. Kim, J. L. Diaz, L. Lo Bello, J. M. Lopez, C-G. Lee, and S. L. Min.An Exact Stochastic Analysis of Priority-Driven Periodic Real-Time Systems and Its Approximations. IEEE Trans. Comput., 54(11):1460-1466, November 2005. URL: http://dx.doi.org/10.1109/TC.2005.174
  77. K. Kim, L. Lo Bello, S. L. Min, and O. Mirabella.On Relaxing Task Isolation in Overrun Handling to Provide Probabilistic Guarantees to Soft Real-Time Tasks with Varying Execution Times. In Proceedings of the Euromicro Conference on Real-Time Systems (ECRTS), pages 193-, Washington, DC, USA, 2002. IEEE Computer Society. URL: http://dl.acm.org/citation.cfm?id=787256.787354.
  78. G. Koren and D. Shasha.Skip-Over: algorithms and complexity for overloaded systems that allow skips. In Proceedings of the IEEE Real-Time Systems Symposium (RTSS), pages 110-117, December 1995. URL: http://dx.doi.org/10.1109/REAL.1995.495201
  79. L. Kruk, J. Lehoczky, K. Ramanan, and S. Shreve.Heavy traffic analysis for EDF queues with reneging. The Annals of Applied Probability, 21(2):484-545, 2011. URL: http://dx.doi.org/10.1214/10-AAP681
  80. M. Kuttler, M. Roitzsch, C-J Hamann, and Marcus Volp.Probabilistic Analysis of Low-Criticality Execution. In Proceedings of Workshop on Mixed Criticality (WMC), 2017. Google Scholar
  81. J. Lehoczky, L. Sha, and Y. Ding.The rate monotonic scheduling algorithm: exact characterization and average case behavior. In Proceedings of the IEEE Real-Time Systems Symposium (RTSS), pages 166-171, December 1989. URL: http://dx.doi.org/10.1109/REAL.1989.63567
  82. J. P. Lehoczky.Fixed priority scheduling of periodic task sets with arbitrary deadlines. In Proceedings of the IEEE Real-Time Systems Symposium (RTSS), pages 201-209, December 1990. URL: http://dx.doi.org/10.1109/REAL.1990.128748
  83. J. P. Lehoczky.Real-time queueing theory. In Proceedings of the IEEE Real-Time Systems Symposium (RTSS), pages 186-195, December 1996. URL: http://dx.doi.org/10.1109/REAL.1996.563715
  84. B. Lesage, D. Griffin, S. Altmeyer, L. Cucu-Grosjean, and R. I. Davis.On the analysis of random replacement caches using static probabilistic timing methods for multi-path programs. Real-Time Systems, December 2017. URL: http://dx.doi.org/10.1007/s11241-017-9295-2
  85. B. Lesage, D. Griffin, S. Altmeyer, and R. I. Davis.Static Probabilistic Timing Analysis for Multi-path Programs. In Proceedings of the IEEE Real-Time Systems Symposium (RTSS), pages 361-372, December 2015. URL: http://dx.doi.org/10.1109/RTSS.2015.41
  86. A. Leulseged and N. Nissanke.Probabilistic Analysis of Multi-processor Scheduling of Tasks with Uncertain Parameters. In Proceedings of the IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA), pages 103-122, 2003. URL: http://dx.doi.org/10.1007/978-3-540-24686-2_7
  87. G. Lima and I. Bate.Valid Application of EVT in Timing Analysis by Randomising Execution Time Measurements. In Proceedings of the IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), April 2017. Google Scholar
  88. G. Lima, D. Dias, and E. Barros.Extreme Value Theory for Estimating Task Execution Time Bounds: A Careful Look. In Proceedings of the Euromicro Conference on Real-Time Systems (ECRTS), July 2016. Google Scholar
  89. C. L. Liu and J. W. Layland.Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment. J. ACM, 20(1):46-61, January 1973. URL: http://dx.doi.org/10.1145/321738.321743
  90. Jane W. S. W. Liu.Real-Time Systems. Prentice Hall, 1st edition, 2000. Google Scholar
  91. M. Liu, M. Behnam, and T. Nolte.An EVT-based worst-case Response Time Analysis of complex real-time systems. In Proceedings of the IEEE International Symposium on Industrial Embedded Systems (SIES), pages 249-258, June 2013. URL: http://dx.doi.org/10.1109/SIES.2013.6601498
  92. R. Liu, A. F. Mills, and J. H. Anderson.Independence Thresholds: Balancing Tractability and Practicality in Soft Real-Time Stochastic Analysis. In Proceedings of the IEEE Real-Time Systems Symposium (RTSS), pages 314-323, December 2014. URL: http://dx.doi.org/10.1109/RTSS.2014.38
  93. J. M. López, J. L. Díaz, J. Entrialgo, and D. García.Stochastic analysis of real-time systems under preemptive priority-driven scheduling.Springer Real-Time Systems, 40(2):180-207, 2008. URL: http://dx.doi.org/10.1007/s11241-008-9053-6
  94. Y. Lu, T. Nolte, I. Bate, and L. Cucu-Grosjean.A statistical response-time analysis of complex real-time embedded systems by using timing traces. In Proceedings of the IEEE International Symposium on Industrial Embedded Systems (SIES), pages 43-46, June 2011. URL: http://dx.doi.org/10.1109/SIES.2011.5953676
  95. Y. Lu, T. Nolte, I. Bate, and L. Cucu-Grosjean.A Statistical Response-Time Analysis of Real-Time Embedded Systems. In Proceedings of the IEEE Real-Time Systems Symposium (RTSS), pages 351-362, December 2012. URL: http://dx.doi.org/10.1109/RTSS.2012.85
  96. Y. Lu, T. Nolte, J. Kraft, and C. Norstrom.Statistical-Based Response-Time Analysis of Systems with Execution Dependencies between Tasks. In Proceedings of the IEEE International Conference on Engineering of Complex Computer Systems (ICECCS), pages 169-179, March 2010. URL: http://dx.doi.org/10.1109/ICECCS.2010.55
  97. Y. Lu, T. Nolte, J. Kraft, and C. Norström.A Statistical Approach to Response-Time Analysis of Complex Embedded Real-Time Systems. In Proceedings of the IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA), pages 153-160, August 2010. Google Scholar
  98. R. Mancuso, R. Pellizzoni, M. Caccamo, L. Sha, and H. Yun.WCET(m) Estimation in Multi-core Systems Using Single Core Equivalence. In Proceedings of the Euromicro Conference on Real-Time Systems (ECRTS), pages 174-183, July 2015. URL: http://dx.doi.org/10.1109/ECRTS.2015.23
  99. N. Manica, L. Palopoli, and L. Abeni.Numerically efficient probabilistic guarantees for resource reservations. In Proceedings of the IEEE Conference on Emerging Technologies Factory Automation (ETFA), pages 1-8, September 2012. URL: http://dx.doi.org/10.1109/ETFA.2012.6489566
  100. S. Manolache, P. Eles, and Z. Peng.Memory and Time-Efficient Schedulability Analysis of Task Sets with Stochastic Execution Time. In Proceedings of the Euromicro Conference on Real-Time Systems (ECRTS), pages 19-, Washington, DC, USA, 2001. IEEE Computer Society. URL: http://dl.acm.org/citation.cfm?id=871910.871936.
  101. S. Manolache, P. Eles, and Z. Peng.Schedulability Analysis of Applications with Stochastic Task Execution Times.ACM Transactions on Embedded Computing Systems, 3(4):706-735, November 2004. URL: http://dx.doi.org/10.1145/1027794.1027797
  102. S. Manolache, P. Eles, and Z. Peng.Task Mapping and Priority Assignment for Soft Real-time Applications Under Deadline Miss Ratio Constraints.ACM Transactions on Embedded Computing Systems, 7(2):19:1-19:35, January 2008. URL: http://dx.doi.org/10.1145/1331331.1331343
  103. F. Markovic, J. Carlson, R. Dobrin, B. Lisper, and A. Thekkilakattil.Probabilistic Response Time Analysis for Fixed Preemption Point Selection. In Proceedings of the IEEE International Symposium on Industrial Embedded Systems (SIES), pages 1-10, June 2018. URL: http://dx.doi.org/10.1109/SIES.2018.8442099
  104. D. Maxim and A. Bertout.Analysis and Simulation Tools for Probabilistic Real-Time Systems. In Proceedings of International Workshop on Analysis Tools and Methodologies for Embedded and Real-time Systems (WATERS), 2017. Google Scholar
  105. D. Maxim, O. Buffet, L. Santinelli, L. Cucu-Grosjean, and R. I. Davis.Optimal Priority Assignment Algorithms for Probabilistic Real-Time Systems. In Proceedings of the International Conference on Real-Time Networks and Systems (RTNS), pages 129-138, 2011. Google Scholar
  106. D. Maxim and L. Cucu-Grosjean.Response Time Analysis for Fixed-Priority Tasks with Multiple Probabilistic Parameters. In Proceedings of the IEEE Real-Time Systems Symposium (RTSS), pages 224-235, December 2013. URL: http://dx.doi.org/10.1109/RTSS.2013.30
  107. D. Maxim, R. I. Davis, L. Cucu-Grosjean, and A. Easwaran.Probabilistic Analysis for Mixed Criticality Scheduling with SMC and AMC. In Proceedings of Workshop on Mixed Criticality (WMC). York, 2016. Google Scholar
  108. 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 International Conference on Real-Time Networks and Systems (RTNS), 2017. Google Scholar
  109. D. Maxim, M. Houston, L. Santinelli, G. Bernat, R. I. Davis, and L. Cucu-Grosjean.Re-sampling for Statistical Timing Analysis of Real-time Systems. In Proceedings of the International Conference on Real-Time Networks and Systems (RTNS), pages 111-120, 2012. URL: http://dx.doi.org/10.1145/2392987.2393001
  110. D. Maxim, L. Santinelli, and L. Cucu-Grosjean.Improved sampling for statistical timing analysis of real-time systems. In the 4th Junior Researcher Workshop on Real-Time Computing, Toulouse, France, November 2010. URL: https://hal.inria.fr/inria-00544651.
  111. D. Maxim, F. Soboczenski, I. Bate, and E. Tovar.Study of the Reliability of Statistical Timing Analysis for Real-time Systems. In Proceedings of the International Conference on Real-Time Networks and Systems (RTNS), pages 55-64, 2015. URL: http://dx.doi.org/10.1145/2834848.2834878
  112. A. F. Mills and J. H. Anderson.A Stochastic Framework for Multiprocessor Soft Real-Time Scheduling. In Proceedings of the IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), pages 311-320, April 2010. URL: http://dx.doi.org/10.1109/RTAS.2010.33
  113. A. F. Mills and J. H. Anderson.A Multiprocessor Server-Based Scheduler for Soft Real-Time Tasks with Stochastic Execution Demand. In Proceedings of the IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA), volume 1, pages 207-217, August 2011. URL: http://dx.doi.org/10.1109/RTCSA.2011.30
  114. S. Milutinovic, J. Abella, D. Hardy, E. Quiñones, I. Puaut, and F. J. Cazorla.Speeding up Static Probabilistic Timing Analysis. In Proceedings of the International Conference on the Architecture of Computing Systems (ARCS), pages 236-247, March 2015. URL: http://dx.doi.org/10.1007/978-3-319-16086-3_19
  115. N. Tchidjo Moyo, E. Nicollet, F. Lafaye, and C. Moy.On Schedulability Analysis of Non-cyclic Generalized Multiframe Tasks. In Proceedings of the Euromicro Conference on Real-Time Systems (ECRTS), pages 271-278, July 2010. URL: http://dx.doi.org/10.1109/ECRTS.2010.24
  116. N. Navet, L. Cucu, and R. Schott.Probabilistic Estimation of Response Times Through Large Deviations. In Work-in Progress of the 28th IEEE Real-Time Systems Symposium (RTSS'2007 WiP), Tucson, United States, December 2007. URL: https://hal.inria.fr/inria-00191163.
  117. N. Navet, Y.-Q. Song, and F. Simonot.Worst-case Deadline Failure Probability in Real-time Applications Distributed over Controller Area Network. J. Syst. Archit., 46(7):607-617, April 2000. URL: http://dx.doi.org/10.1016/S1383-7621(99)00016-8
  118. N. Nissanke, A. Leulseged, and S. Chillara.Probabilistic performance analysis in multiprocessor scheduling. Computing Control Engineering Journal, 13(4):171-179, August 2002. URL: http://dx.doi.org/10.1049/cce:20020403
  119. T. Nolte, H. Hansson, and C. Norstrom.Probabilistic worst-case response-time analysis for the controller area network. In Proceedings of the IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), pages 200-207, May 2003. URL: http://dx.doi.org/10.1109/RTTAS.2003.1203052
  120. L. Palopoli, L. Abeni, and D. Fontanelli.A tool for the optimal design of soft real–time systems. In Proceedings of International Workshop on Analysis Tools and Methodologies for Embedded and Real-time Systems (WATERS), pages 31-36, 2014. Google Scholar
  121. L. Palopoli, D. Fontanelli, L. Abeni, and B. V. Frías.An Analytical Solution for Probabilistic Guarantees of Reservation Based Soft Real-Time Systems. IEEE Transactions on Parallel and Distributed Systems, 27(3):640-653, March 2016. URL: http://dx.doi.org/10.1109/TPDS.2015.2416732
  122. L. Palopoli, D. Fontanelli, N. Manica, and L. Abeni.An Analytical Bound for Probabilistic Deadlines. In Proceedings of the Euromicro Conference on Real-Time Systems (ECRTS), pages 179-188, July 2012. URL: http://dx.doi.org/10.1109/ECRTS.2012.19
  123. S. S. Panwar, D. Towsley, and J. K. Wolf.Optimal Scheduling Policies for a Class of Queues with Customer Deadlines to the Beginning of Service. J. ACM, 35(4):832-844, October 1988. URL: http://dx.doi.org/10.1145/48014.48019
  124. S. Punnekkat, R. I. Davis, and A. Burns.Sensitivity analysis of real-time task sets. In Annual Asian Computing Science Conference, pages 72-82. Springer Berlin Heidelberg, 1997. Google Scholar
  125. S. Quinton, R. Ernst, D. Bertrand, and P. Meumeu Yomsi.Challenges and new trends in probabilistic timing analysis. In Proceedings of the Conference on Design, Automation and Test in Europe (DATE), pages 810-815, March 2012. URL: http://dx.doi.org/10.1109/DATE.2012.6176605
  126. P. Ramanathan and M. Hamdaoui.A Dynamic Priority Assignment Technique for Streams with (M, K)-Firm Deadlines.IEEE Transactions on Computers, 44(12):1443-1451, December 1995. URL: http://dx.doi.org/10.1109/12.477249
  127. K. S. Refaat and P. E. Hladik.Efficient Stochastic Analysis of Real-Time Systems via Random Sampling. In Proceedings of the Euromicro Conference on Real-Time Systems (ECRTS), pages 175-183, July 2010. URL: http://dx.doi.org/10.1109/ECRTS.2010.29
  128. J. Ren, R. Bi, X. Su, Q. Liu, G. Wu, and G. Tan.Workload-aware harmonic partitioned scheduling for probabilistic real-time systems. In Proceedings of the Conference on Design, Automation and Test in Europe (DATE), pages 213-218, March 2018. URL: http://dx.doi.org/10.23919/DATE.2018.8342005
  129. L. Santinelli.Probabilistic Component-based Analysis for Networks: Invited Paper. SIGBED Rev., 13(3):65-72, August 2016. URL: http://dx.doi.org/10.1145/2983185.2983197
  130. L. Santinelli and L. Cucu-Grosjean.Toward Probabilistic Real-time Calculus. SIGBED Rev., 8(1):54-61, March 2011. URL: http://dx.doi.org/10.1145/1967021.1967028
  131. L. Santinelli and L. Cucu-Grosjean.A Probabilistic Calculus for Probabilistic Real-Time Systems.ACM Transactions on Embedded Computing Systems, 14(3):52:1-52:30, April 2015. URL: http://dx.doi.org/10.1145/2717113
  132. L. Santinelli and L. George.Probabilities and Mixed-Criticalities: the Probabilistic C-Space. In Proceedings of Workshop on Mixed Criticality (WMC), 2015. Google Scholar
  133. L. Santinelli, F. Guet, and J. Morio.Revising Measurement-Based Probabilistic Timing Analysis. In Proceedings of the IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), April 2017. Google Scholar
  134. L. Santinelli, Z. Guo, and L. George.Fault-aware sensitivity analysis for probabilistic real-time systems. In Proceedings of IEEE International Symposium on Defect and Fault Tolerance in VLSI and Nanotechnology Systems (DFT), pages 69-74, September 2016. URL: http://dx.doi.org/10.1109/DFT.2016.7684072
  135. L. Santinelli, J. Morio, G. Dufour, and D. Jacquemart.On the Sustainability of the Extreme Value Theory for WCET Estimation. In Proceedings of the Workshop on Worst-Case Execution Time Analysis (WCET), pages 21-30, 2014. URL: http://dx.doi.org/10.4230/OASIcs.WCET.2014.21
  136. L. Santinelli, P. M. Yomsi, D. Maxim, and L. Cucu-Grosjean.A component-based framework for modeling and analyzing probabilistic real-time systems. In Proceedings of the IEEE Conference on Emerging Technologies Factory Automation (ETFA), pages 1-8, September 2011. URL: http://dx.doi.org/10.1109/ETFA.2011.6059013
  137. L. Sha, T. Abdelzaher, K-E. Årzén, A. Cervin, T. Baker, A. Burns, G. Buttazzo, M. Caccamo, J. Lehoczky, and A. K. Mok.Real time scheduling theory: A historical perspective. RTSJ, 28(2-3):101-155, 2004. Google Scholar
  138. M. Short and J. Proenza.Towards Efficient Probabilistic Scheduling Guarantees for Real-Time Systems Subject to Random Errors and Random Bursts of Errors. In Proceedings of the Euromicro Conference on Real-Time Systems (ECRTS), pages 259-268, July 2013. URL: http://dx.doi.org/10.1109/ECRTS.2013.35
  139. B. Sprunt, L. Sha, and J. Lehoczky.Aperiodic task scheduling for Hard-Real-Time systems.Springer Real-Time Systems, 1(1):27-60, 1989. URL: http://dx.doi.org/10.1007/BF02341920
  140. B. Tanasa, U. D. Bordoloi, P. Eles, and Z. Peng.Probabilistic Timing Analysis for the Dynamic Segment of FlexRay. In Proceedings of the Euromicro Conference on Real-Time Systems (ECRTS), pages 135-144, July 2013. URL: http://dx.doi.org/10.1109/ECRTS.2013.24
  141. B. Tanasa, U. D. Bordoloi, P. Eles, and Z. Peng.Probabilistic Response Time and Joint Analysis of Periodic Tasks. In Proceedings of the Euromicro Conference on Real-Time Systems (ECRTS), pages 235-246, July 2015. URL: http://dx.doi.org/10.1109/ECRTS.2015.28
  142. L. Thiele, S. Chakraborty, and M. Naedele.Real-time calculus for scheduling hard real-time systems. In IEEE International Symposium on Circuits and Systems. Emerging Technologies for the 21st Century, volume 4, pages 101-104 vol.4, May 2000. URL: http://dx.doi.org/10.1109/ISCAS.2000.858698
  143. 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 IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), pages 164-173, May 1995. URL: http://dx.doi.org/10.1109/RTTAS.1995.516213
  144. S. R. S. Varadhan.Large deviations. The Annals of Probability, 36(2):397-419, March 2008. URL: http://dx.doi.org/10.1214/07-AOP348
  145. S. Vestal.Preemptive Scheduling of Multi-criticality Systems with Varying Degrees of Execution Time Assurance. In Proceedings of the IEEE Real-Time Systems Symposium (RTSS), pages 239-243, 2007. URL: http://dx.doi.org/10.1109/RTSS.2007.47
  146. B. Villalba Frías, L. Palopoli, L. Abeni, and D. Fontanelli.The PROSIT tool: Toward the optimal design of probabilistic soft real-time systems. Software: Practice and Experience, 0(0), 2018. URL: http://dx.doi.org/10.1002/spe.2604
  147. G. von der Brüggen, N. Piatkowski, K-H. Chen, J. J. Chen, and K. Morik.Efficiently Approximating the Probability of Deadline Misses in Real-Time Systems. In Proceedings of the Euromicro Conference on Real-Time Systems (ECRTS), volume 106, pages 6:1-6:22, 2018. URL: http://dx.doi.org/10.4230/LIPIcs.ECRTS.2018.6
  148. T. Wang, S. Homsi, L. Nui, S. Ren, O. Bai, G. Quan, and M. Qiu.Harmonicity Aware Task Partitioning for Fixed Priority Scheduling of Probabilistic Real-Time Tasks on Multi-Core Platforms.ACM Transactions on Embedded Computing Systems, 2016. Google Scholar
  149. T. Wang, L. Niu, S. Ren, and G. Quan.Multi-core fixed-priority scheduling of real-time tasks with statistical deadline guarantee. In Proceedings of the Conference on Design, Automation and Test in Europe (DATE), pages 1335-1340, March 2015. Google Scholar
  150. F. Wartel, L. Kosmidis, C. Lo, B. Triquet, E. Quiñones, J. Abella, A. Gogonel, A. Baldovin, E. Mezzetti, L. Cucu, T. Vardanega, and F. J. Cazorla.Measurement-based probabilistic timing analysis: Lessons from an integrated-modular avionics case study. In Proceedings of the IEEE International Symposium on Industrial Embedded Systems (SIES), pages 241-248, June 2013. URL: http://dx.doi.org/10.1109/SIES.2013.6601497
  151. R. C. Williamson and T. Downs.Probabilistic arithmetic. I. Numerical methods for calculating convolutions and dependency bounds. International Journal of Approximate Reasoning, 4(2):89-158, 1990. URL: http://dx.doi.org/10.1016/0888-613X(90)90022-T
  152. M. H. Woodbury and K. G. Shin.Evaluation of the probability of dynamic failure and processor utilization for real-time systems. In Proceedings of the IEEE Real-Time Systems Symposium (RTSS), pages 222-231, December 1988. URL: http://dx.doi.org/10.1109/REAL.1988.51117
  153. H. Zeng, M. Di Natale, P. Giusto, and A. Sangiovanni-Vincentelli.Stochastic Analysis of CAN-Based Real-Time Automotive Systems. IEEE Transactions on Industrial Informatics, 5(4):388-401, November 2009. URL: http://dx.doi.org/10.1109/TII.2009.2032067
  154. H. Zhu, J. P. Hansen, J. P. Lehoczky, and R. Rajkumar.Optimal partitioning for quantized EDF scheduling. In Proceedings of the IEEE Real-Time Systems Symposium (RTSS), pages 212-222, 2002. URL: http://dx.doi.org/10.1109/REAL.2002.1181576
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 Imprint Privacy Contact