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 multi-programming 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-timesystem, 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 monotonicscheduling algorithm: Exact characterization and average casebehaviour, Proc. 10th IEEE Real-Time Systems Symp., SantaMonica, 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 complexperiodic tasks, Proc. 10th Int. Conf. on Distributed ComputingSystems, Paris, France, 1990, 108–115. doi:10.1109/ICDCS.1990.89256
  6. [6] K. Tindell, A. Burns, & A. Wellings, Allocating hard-real timetasks: 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 heuristicapproach to the multitask-multiprocessor assignment problemusing 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 timemixed priority preemptive systems, Proc. 14th IEEE Real-TimeSystems Symp., Raleigh-Durham, NC, 1993, 222–231. doi:10.1109/REAL.1993.393496
  9. [9] J.P. Lehockzky & S. Ramos-Thuel, An optimal algorithmfor scheduling soft-aperiodic tasks fixed-priority preemptivesystems, 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-timesystems, IEEE Trans. on Computers, 50(4), 2001, 308–321. doi:10.1109/12.919277
  11. [11] H. Aydin, R. Melhem, D. Moss´e, & P. Mej´ıa-Alvarez, Optimalreward-based scheduling for periodic real-time tasks, IEEETrans. on Computers, 50(2), 2001, 131–146. doi:10.1109/12.908988
  12. [12] J. Dey, J. Kurose, & D. Towsley, On-line scheduling policiesfor a class of IRIS (increasing reward with increasing servicereal-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 heterogeneousmultimedia servers: Different QoS for hard, soft and non real-time 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-timetasks with varying computation times, Proc. 1st IEEE Real-Time 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 criticalsoft real-time systems, doctoral diss., University of Illinois atUrbana-Champaign, 1999.
  17. [17] N.C. Audsley, A. Burns, M.F. Richardson, & J. Wellings,Incorporating unbounded algorithms into predictable real-timesystems, 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