Hard Real-Time Systems with Stochastic Execution Times: Deterministic and Probabilistic Guarantees

R. Santos, J. Santos, and J. Orozco


  1. [1] C.L. Liu & J.W. Layland, Scheduling algorithms for multiprogramming in a hard real-time environment, Journal ACM, 20(1), 1973, 46–61. doi:10.1145/321738.321743
  2. [2] M. Joseph & P. Pandya, Finding response times in a real-time system, The Computer Journal, 29(5), 1986, 390–395. doi:10.1093/comjnl/29.5.390
  3. [3] J.P. Lehoczky, L. Sha, & Y. Ding, The rate monotonic scheduling algorithm: Exact characterization and average case behaviour, Proc. 10th IEEE Real-Time Systems Symp., Santa Monica, CA, 1989, 166–171. doi:10.1109/REAL.1989.63567
  4. [4] J. Santos, M.L. Gastaminza, J. Orozco, D. Picardi, & O. Alimenti, Priorities and protocols in hard real-time LANs: Implementing a crisis-free system, Computer Communications, 14(9), 1991, 507–514. doi:10.1016/0140-3664(91)90108-D
  5. [5] K. Ramamritham, Allocation and scheduling of complex periodic tasks, Proc. 10th Int. Conf. on Distributed Computing Systems, Paris, France, 1990, 108–115. doi:10.1109/ICDCS.1990.89256
  6. [6] K. Tindell, A. Burns, & A. Wellings, Allocating hard-real time tasks: An NP-hard problem made easy, Real-Time Systems, 4(2), 1992, 145–165. doi:10.1007/BF00365407
  7. [7] J. Santos, E. Ferro, J. Orozco, & R. Cayssials, A heuristic approach to the multitask-multiprocessor assignment problem using the empty-slots method and rate monotonic scheduling, Real-Time Systems, 13(2), 1997, 167–199. doi:10.1023/A:1007933607293
  8. [8] R.J. Davis, K.W. Tindell, & A. Burns, Scheduling slack time mixed priority preemptive systems, Proc. 14th IEEE Real-Time Systems Symp., Raleigh-Durham, NC, 1993, 222–231. doi:10.1109/REAL.1993.393496
  9. [9] J.P. Lehockzky & S. Ramos-Thuel, An optimal algorithm for scheduling soft-aperiodic tasks fixed-priority preemptive systems, Proc. 13th IEEE Real-Time Systems Symp., Phoenix, AZ, 1992, 110–123. doi:10.1109/REAL.1992.242671
  10. [10] G. Bernat, A. Burns, & A. Llamos´ı, Weakly hard real-time systems, IEEE Trans. on Computers, 50(4), 2001, 308–321. doi:10.1109/12.919277
  11. [11] H. Aydin, R. Melhem, D. Mossé, & P. Mej´ıa-Alvarez, Optimal reward-based scheduling for periodic real-time tasks, IEEE Trans. on Computers, 50(2), 2001, 131–146. doi:10.1109/12.908988
  12. [12] J. Dey, J. Kurose, & D. Towsley, On-line scheduling policies for a class of IRIS (increasing reward with increasing service real-time tasks), IEEE Trans. on Computers, 46(7), 1996, 802–813. doi:10.1109/12.508319
  13. [13] R. Santos, J. Santos, & J. Orozco, Scheduling heterogeneous multimedia servers: Different QoS for hard, soft and non realtime clients, 12th Euromicro Conf. on Real-Time Systems, Stockholm, Sweden, 2000, 247–253.
  14. [14] T.-S. Tia, Z. Deng, M. Shankar, M. Storch, J. Sun, L.-C. Wu, & J.W.-S. Liu, Probabilistic performance guarantee for real-time tasks with varying computation times, Proc. 1st IEEE RealTime Technology and Applications Symp., Chicago, IL, 1995, 164–173. doi:10.1109/RTTAS.1995.516213
  15. [15] A. Atlas & A. Bestavros, Statistical rate monotonic scheduling, Proc. 19th IEEE Real-Time Systems Symp., Madrid, Spain, 1998, 123–132. doi:10.1109/REAL.1998.739737
  16. [16] M. Gardner, Probabilistic analysis and scheduling of critical soft real-time systems, doctoral diss., University of Illinois at Urbana-Champaign, 1999.
  17. [17] N.C. Audsley, A. Burns, M.F. Richardson, & J. Wellings, Incorporating unbounded algorithms into predictable real-time systems, Computer Systems Science and Engineering, 8(3), 1993, 80–89.
  18. [18] A. León Garcia, Probability and random processes for electrical engineering, 2nd ed. (Reading, MA:Addison-Wesley, 1994).

Important Links:

Go Back