| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Minimum and Maximum Utilization Bounds for Multiprocessor Rate Monotonic Scheduling
July 2004 (vol. 15 no. 7)
pp. 642-653
Abstract—The utilization bound for real-time Rate Monotonic (RM) scheduling on uniprocessors is extended to multiprocessors with partitioning-based scheduling. This allows fast schedulability tests to be performed on multiprocessors and quantifies the influence of key parameters, such as the number of processors and task sizes on the schedulability of the system. The multiprocessor utilization bound is a function of the allocation algorithm, so among all the allocation algorithms there exists at least one allocation algorithm providing the minimum multiprocessor utilization bound, and one allocation algorithm providing the maximum multiprocessor utilization bound. We prove that the multiprocessor utilization bound associated with the allocation heuristic Worst Fit (WF) coincides with that minimum if we use Liu and Layland's bound (LLB) as the uniprocessor schedulability condition. In addition, we present a class of allocation algorithms sharing the same multiprocessor utilization bound which coincides with the aforementioned maximum using LLB. The heuristics First Fit Decreasing (FFD) and Best Fit Decreasing (BFD) belong to this class. Thus, not even an optimal allocation algorithm can guarantee a higher multiprocessor utilization bound than that of FFD and BFD using LLB. Finally, the pessimism of the multiprocessor utilization bounds is estimated through extensive simulations.
[1] Y. Oh and S.H. Son, Allocating Fixed-Priority Periodic Tasks on Multiprocessor Systems Real-Time Systems, vol. 9, no. 3, pp. 207-239, 1995.
[2] C.L. Liu and J.W. Layland, Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment J. ACM, vol. 20, no. 1, pp. 46-61, 1973.
[3] S.K. Dall and C.L. Liu, On a Real-Time Scheduling Problem Operations Research, vol. 6, no. 1, pp. 127-140, 1978.
[4] B. Andersson, S. Baruah, and J. Jonsson, Static-Priority Scheduling on Multiprocessors Proc. IEEE Real-Time Systems Symp., pp. 193-202, 2001.
[5] J. Goossens, S. Funk, and S. Baruah, Priority-Driven Scheduling of Periodic Task Systems on Multiprocessors Real-Time Systems, vol. 25, nos. 2-3, pp. 187-205, 2003.
[6] M.R. Garey and D.S. Johnson, Computers and Intractability. New York: W.H. Freman, 1979.
[7] A. Burchard, J. Liebeherr, Y. Oh, and S.H. Son, “Assigning Real-Time Tasks to Homogeneous Multiprocessor Systems,” IEEE Trans. Computers, vol. 44, no. 12, pp. 1429-1442, Dec. 1995.
[8] D.-T. Peng, K.G. Shin, and T.F. Abdelzaher, “Assignment and Scheduling Communicating Periodic tasks in Distributed Real Time Systems,” IEEE Trans. Software Eng., vol. 23, no. 12, pp. 745-758, Dec. 1997.
[9] K. Tindell, A. Burns, and A. Wellings, Allocating Hard Real-Time Tasks (an NP-Hard Problem Made Easy) Real-Time Systems, vol. 4, no. 2, pp. 145-165, 1992.
[10] S. Sáez, J. Vila, and A. Crespo, Using Exact Feasibility Tests for Allocating Real-Time Tasks in Multiprocessor Systems Proc. 10th Euromicro Workshop Real-Time Systems, pp. 53-60, 1998.
[11] S. Lauzac, R. Melhem, and D. Mosse, “An Efficient RMS Admission Control and Its Application to Multiprocessor Scheduling,” Proc. Int'l Parallel Processing Symp., pp. 511-518, 1998.
[12] S. Davari and S. Dhall, On a Periodic Real-Time Task Allocation Problem Proc. Ann. Int'l Conf. Systems Sciences, pp. 133-141, 1986.
[13] S. Davari and S. Dhall, An On Line Algorithm for Real Time Tasks Allocation Proc. IEEE Real-Time Systems Symp., pp. 194-200, 1986.
[14] D. Oh and T.P. Baker, Utilization Bounds for N-Processor Rate Monotone Scheduling with Static Processor Assignment Real-Time Systems, vol. 15, no. 2, pp. 183-193, 1998.
[15] J.M. López, M. García, J.L. Díaz, and D.F. García, Utilization Bounds for Multiprocessor Rate-Monotonic Scheduling Real-Time Systems, vol. 24, no. 1, pp. 5-28, 2003.
[16] S.K. Baruah and J. Goossens, Rate-Monotonic Scheduling on Uniform Multiprocessors IEEE Trans. Computers, vol. 52, no. 7, pp. 966-970, July 2003.
[17] J.M. López, J.L. Díaz, M. García, and D.F. García, Worst-Case Utilization Bound for EDF Scheduling on Real-Time Multiprocessor Systems Proc. Euromicro Conf. Real-Time Systems, pp. 25-33, 2000.
[18] J. Lehoczky, L. Sha, and Y. Ding, The Rate Monotonic Scheduling Algorithm: Exact Characterization and Average Case Behavior Proc. IEEE Real-Time Systems Symp., pp. 166-171, 1989.
[19] P. Pedro and A. Burns, Schedulability Changes for Mode Changes in Flexible Real-Time Systems Proc. Euromicro Workshop Real Time Systems, pp. 172-179, 1998.
[20] G. Bernat and A. Burns, New Results on Fixed Priority Aperiodic Servers Proc. Real-Time Systems Symp., pp. 68-78, 1999.
Index Terms:
Real-time systems, multiprocessors, Rate Monotonic scheduling, allocation, utilization bounds.
Citation:
Jos? M. L?pez, Jos? L. D?az, Daniel F. Garc?, "Minimum and Maximum Utilization Bounds for Multiprocessor Rate Monotonic Scheduling," IEEE Transactions on Parallel and Distributed Systems, vol. 15, no. 7, pp. 642-653, July 2004, doi:10.1109/TPDS.2004.25
