| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
An Exact Stochastic Analysis of Priority-Driven Periodic Real-Time Systems and Its Approximations
November 2005 (vol. 54 no. 11)
pp. 1460-1466
This paper describes a stochastic analysis framework which computes the response time distribution and the deadline miss probability of individual tasks, even for systems with a maximum utilization greater than one. The framework is uniformly applied to fixed-priority and dynamic-priority systems and can handle tasks with arbitrary relative deadlines and execution time distributions.
[1] 1460 L. Liu and J. Layland, “Scheduling Algorithms for Multiprogramming in a Hard Real-Time Environment,” J. ACM, vol. 20, no. 1, pp. 46-61, 1973.[2] J.P. Lehoczky, L. Sha, and Y. Ding, “The Rate-Monotonic Scheduling Algorithm: Exact Characterization and Average Case Behavior,” Proc. 10th IEEE Real-Time Systems Symp., 1989.[3] J.P. Lehoczky, “Fixed Priority Scheduling of Periodic Task Sets with Arbitrary Deadlines,” Proc. 11th IEEE Real-Time Systems Symp., pp. 201-209, 1990.[4] G. Bernat, A. Colin, and S. Petters, “WCET Analysis of Probabilistic Hard Real-Time Systems,” Proc. 23rd IEEE Real-Time Systems Symp., 2002.[5] M.K. Gardner and J.W. Liu, “Analyzing Stochastic Fixed-Priority Real-Time Systems,” Proc. Fifth Int'l Conf. Tools and Algorithms for the Construction and Analysis of Systems, Mar. 1999[6] J. Leung and J. Whitehead, “On the Complexity of Fixed Priority Scheduling of Periodic Real-Time Tasks,” Performance Evaluation, vol. 2, no. 4, pp. 237-250, 1982.[7] S. Manolache, P. Eles, and Z. Peng, “Memory and Time-Efficient Schedulability Analysis of Task Sets with Stochastic Execution Times,” Proc. 13th Euromicro Conf. Real-Time Systems, pp. 19-26, June 2001.[8] A. Leulseged and N. Nissanke, “Probabilistic Analysis of Multi-Processor Scheduling of Tasks with Uncertain Parameter,” Proc. Ninth Int'l Conf. Real-Time and Embedded Computing Systems and Applications, Feb. 2003.[9] J.P. Lehoczky, “Real-Time Queueing Theory,” Proc. 17th IEEE Real-Time Systems Symp., pp. 186-195, 1996.[10] L. Abeni and G. Buttazzo, “Stochastic Analysis of a Reservation Based System,” Proc. Ninth Int'l Workshop Parallel and Distributed Real-Time Systems, Apr. 2001.[11] A.K. Atlas and A. Bestavros, “Statistical Rate Monotonic Scheduling,” Proc. 19th IEEE Real-Time Systems Symp., pp. 123-132, 1998.[12] J.W.S. Liu, Real-Time Systems. Prentice Hall, 2000.[13] J.L. Díaz, D.F. García, K. Kim, C.-G. Lee, L. LoBello, J.M. López, S.L. Min, and O. Mirabella, “Stochastic Analysis of Periodic Real-Time Systems,” Proc. 23rd Real-Time Systems Symp., pp. 289-300, 2002.[14] J.L. Díaz, D.F. García, K. Kim, C.-G. Lee, L. LoBello, J.M. López, S.L. Min, and O. Mirabella, “An Exact Stochastic Analysis of Priority-Driven Periodic Real-Time Systems,” technical report, Departamento de Informática, Univ. of Oviedo, 2003, http://www.atc.uniovi.es/researchAESA04.pdf .[15] N.C. Audsley, “Optimal Priority Assignment and Feasibility of Static Priority Tasks with Arbitrary Start Times,” Technical Report YCS 164, Dept. of Computer Science, Univ. of York, Dec. 1991.[16] J.L. Díaz, J.M. López, M. García, A.M. Campos, K. Kim, and L. LoBello, “Pessimism in the Stochastic Analysis of Real-Time Systems: Concept and Applications,” Proc. 25th Real-Time Systems Symp., pp. 197-207, 2004.
Index Terms:
Index Terms- Real-time and embedded systems, scheduling, stochastic analysis, Markov processes.
Citation:
Kanghee Kim, Jos? Luis D?az, Lucia Lo Bello, Jos? Mar? L?pez, Chang-Gun Lee, Sang Lyul Min, "An Exact Stochastic Analysis of Priority-Driven Periodic Real-Time Systems and Its Approximations," IEEE Transactions on Computers, vol. 54, no. 11, pp. 1460-1466, Nov. 2005, doi:10.1109/TC.2005.174
