|
Published Articles >> Table of Contents >> Abstract
November 2005 (Vol. 54, No. 11)
pp. 1460-1466
An Exact Stochastic Analysis of Priority-Driven Periodic Real-Time Systems and Its Approximations
Kanghee Kim
Jose Luis Diaz
Lucia Lo Bello, IEEE
Jose Maria Lopez
Chang-Gun Lee, IEEE
Sang Lyul Min, IEEE
Full Article Text:
   
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/TC.2005.174
Send link to a friend
| Abstract |
|
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.
|
 References
|
[1] 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.
|
 Additional Information
|
Index Terms- Index Terms- Real-time and embedded systems, scheduling, stochastic analysis, Markov processes.
Citation:
Kanghee Kim, Jose Luis Diaz, Lucia Lo Bello, Jose Maria Lopez, 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
|
|
RSS Feed