Abstract
In this paper, we extend Liu and Layland's utilization bound for fixed priority scheduling on uniprocessors to homogeneous multiprocessor systems under a partitioning strategy. Assuming that tasks are pre-emptively scheduled on each processor according to fixed priorities assigned by the Rate-Monotonic policy, and allocated to processors by the First Fit algorithm, we prove that the utilization bound is (n−1)(21/2−1)+(m−n+1)(21/(m−n+1)−1), where m and n are the number of tasks and processors, respectively. This bound is valid for arbitrary utilization factors. Moreover, if all the tasks have utilization factors under a value α, the previous bound is raised and the new utilization bound considering α is calculated. Finally, simulation provides the average-case behavior.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Burchard, A., Liebeherr, J., Oh, Y., and Son, S. 1995. New strategies for assigning real-time tasks to multiprocessor systems. IEEE Transactions on Computers 44(12).
Dall, S., and Liu, C. 1978. On a real-time scheduling problem. Operations Research 6(1): 127-140.
Garey, M., and Johnson, D. 1979. Computers and Intractability. New York: W. H. Freeman, pp. 121-127.
Liu, C. L., and Layland, J. 1973. Scheduling algorithms for multiprogramming in a hard-real-time environment. Journal of the ACM 20(1): 46-61.
Oh, D., and Baker, T. 1998. Utilization bounds for N-processor rate monotone scheduling with static processor assignment. Real-Time Systems 15(2): 183-193.
Oh, Y., and Son, S. 1995. Allocating fixed-priority periodic tasks on multiprocessor systems. Real-Time Systems 9(3): 207-239.
Sáez, S. J. V., and Crespo, A. 1998. Using exact feasibility tests for allocating real-time tasks in multiprocessor systems. In Proceedings of the 10th Euromicro Workshop on Real-Time Systems, pp. 53-60.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
López, J.M., García, M., Díaz, J.L. et al. Utilization Bounds for Multiprocessor Rate-Monotonic Scheduling. Real-Time Systems 24, 5–28 (2003). https://doi.org/10.1023/A:1021749005009
Issue Date:
DOI: https://doi.org/10.1023/A:1021749005009