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

Robert I. Davis, Liliana Cucu-Grosjean

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 outlines
fundamental 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.


Keywords


Probabilistic; real-time; schedulability analysis; scheduling;

Full Text:

PDF

References


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.

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

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

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

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

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

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

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.

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.

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

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.

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

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

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.

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

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

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

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

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

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

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

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.

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

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

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

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.

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.

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

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

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

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

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

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

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

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

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

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.

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

S. Coles.An Introduction to Statistical Modeling of Extreme Values. Springer, 2001. URL: http://dx.doi.org/10.1007/978-1-4471-3675-0

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

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

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.

L. Cucu-Grosjean.Probabilistic real-time scheduling. In ETR 2013-Ecole d'été temps réel, 2013.

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

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.

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

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

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

R. I Davis and A. Burns.A survey of hard real-time scheduling for multiprocessor systems. ACM Computing Surveys (CSUR), 43(4):35, 2011.

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.

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

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

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

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

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

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

S. Draskovic, P. Huang, and L. Thiele.On the Safety of Mixed-Criticality Scheduling. In Proceedings of Workshop on Mixed Criticality (WMC), 2016.

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

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.

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

S. Gopalakrishnan.Sharp utilization thresholds for some real-time scheduling problems. CoRR, abs/0912.3852, 2009. URL: http://arxiv.org/abs/0912.3852.

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.

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

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.

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

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.

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.

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

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.

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

M. Joseph and P. Pandya.Finding response times in a real-time system. The Computer Journal, 29(5):390-395, 1986.

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

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

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

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

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

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.

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

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

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.

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

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

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

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

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

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

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.

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.

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

Jane W. S. W. Liu.Real-Time Systems. Prentice Hall, 1st edition, 2000.

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

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

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

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

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

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

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.

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

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

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.

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

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

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

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.

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.

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

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.

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.

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

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.

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

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

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

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

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

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.

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

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

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

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.

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

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

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

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.

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

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

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

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

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

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

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

L. Santinelli and L. George.Probabilities and Mixed-Criticalities: the Probabilistic C-Space. In Proceedings of Workshop on Mixed Criticality (WMC), 2015.

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.

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

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

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

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.

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

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

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

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

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

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

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

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

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

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

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.

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.

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

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

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

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

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




DOI: https://doi.org/10.4230/LITES-v006-i001-a004

URN (PDF): http://nbn-resolving.de/urn:nbn:de:0030-lites-v006-i001-a004-pdf8

Copyright (c) 2019 Robert I. Davis and Liliana Cucu-Grosjean

Creative Commons License CC BY
This work is licensed under a Creative Commons Attribution 3.0 Germany License (CC BY 3.0 DE).

License URL: http://creativecommons.org/licenses/by/3.0/de/deed.en
To make this site work properly, we sometimes place small data files called cookies on your device. Cookies are only here to manage user sessions. Cookies aren’t required for simply visiting the site and read content.
OK




Published by the European Design and Automation Association (EDAA) \ EMbedded Systems Special Interest Group (EMSIG) and Schloss Dagstuhl -- Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing. | Imprint | Data Privacy Policy