A traditional multiprocessor real-time scheduling partition a task set and applies uniprocessor scheduling on each processor. For architectures where the penalty of migration is low, such as uniform-memory access shared-memory multiprocessors, the nonpartitioned method becomes a viable alternative. By allowing a task to resume on another processor than the task was preempted on, some task sets can be scheduled where the partitioned method fails. We address fixed-priority scheduling of periodically arriving tasks on equally powerful processors having a non-partitioned ready queue. We propose a new priority-assignment scheme for the non-partitioned method. Using an extensive simulation study, we show that the priority-assignment scheme has equivalent performance to the best existing partitioning algorithms, and outperforms existing fixed-priority assignment schemes for the non-partitioned method.

1. K. Diefendorff and P. K. Dubey. How multimedia workloads will change processor design. IEEE Computer, 30(9):43-45, September 1997.
2. S. Dhall. Scheduling Periodic-Time-Critical Jobs on Single Processor and Multiprocessor Computing Systems. PhD thesis, Department of Computer Science, University of Illinois at Urbana-Champain, 1977.
3. S. K. Dhall and C. L. Liu. On a real-time scheduling problem. Operations Research, 26(1):127-140, January/February 1978.
4. S. Davari and S. K. Dhall. On a real-time task allocation problem. In 19th Annual Hawaii International Conference on System Sciences, pages 8-10, Honolulu, Hawaii, 1985.
5. S. Davari and S. K. Dhall. An on-line algorithm for real-time task allocation. In Proc. of the IEEE Real-Time Systems Symposium, volume 7, pages 194-200, New Orleans, LA, December 1986.
6. S. Lauzac, R. Melhem, and D. Mossé. An efficient RMS admission control and its application to multiprocessor scheduling. In Proc. of the IEEE Int'l Parallel Processing Symposium, pages 511-518, Orlando, Florida, March 1998.
7. J. Y. -T. Leung and J. Whitehead. On the complexity of fixed-priority scheduling of periodic, real-time tasks. Performance Evaluation, 2(4):237-250, December 1982.
8. A. Burchard, J. Liebeherr, Y. Oh, and S. H. Son. New strategies for assigning real-time tasks to multiprocessor systems. IEEE Transactions on Computers, 44(12):1429-1442, December 1995.
9. S. Sáez, J. Vila, and A. Crespo. Using exact feasibility tests for allocating real-time tasks in multiprocessor systems. In 10th Euromicro Workshop on Real Time Systems, pages 53-60, Berlin, Germany, June 17-19, 1998.
10. Y. Oh and S. H. Son. Allocating fixed-priority periodic tasks on multiprocessor systems. Real-Time Systems, 9(3):207-239, November 1995.
11. Y. Oh and S. H. Son. Fixed-priority scheduling of periodic tasks on multiprocessor systems. Technical Report 95-16, Department of Computer Science, University of Virginia, March 1995. Available at ftp://ftp. cs. virginia. edu/pub/techreports/CS-95-16. ps. Z.
12. C. L. Liu and J. W. Layland. Scheduling algorithms for multiprogramming in a hard-real-time environment. Journal of the Association for Computing Machinery, 20(1):46-61, January 1973.
13. J. Y. -T. Leung. A new algorithm for scheduling periodic, real-time tasks. Algorithmica, 4(2):209-219, 1989.
14. C. L. Liu. Scheduling algorithms for multiprocessors in a hard real-time environment. In JPL Space Programs Summary 37-60, volume II, pages 28-31. 1969.
15. B. Andersson. Adaption of time-sensitive tasks on shared memory multiprocessors: A frame work suggestion. Master's thesis, Department of Computer Engineering, Chalmers University of Technology, January 1999.
16. S. Lauzac, R. Melhem, and D. Mossé. Comparison of global and partitioning schemes for scheduling rate monotonic tasks on a multiprocessor. In 10th Euromicro Workshop on Real Time Systems, pages 188-195, Berlin, Germany, June 17-19, 1998.
17. L. Lundberg. Multiprocessor scheduling of age contraint processes. In 5th International Conference on Real-Time Computing Systems and Applications, Hiroshima, Japan, October 27-29, 1998.
18. J. A. Stankovic, C. Lu, and S. H. Son. The case for feedback control real-time scheduling. Technical Report 98-35, Dept. Of Computer Science, University of Virginia, November 1998. Available at ftp://ftp. cs. virginia. edu/pub/techreports/CS-98-35. ps. Z.
19. J. A. Stankovic, C. Lu, S. H. Son, and G. Tao. The case for feedback control real-time scheduling. In Proc. of the EuroMicro Conference on Real-Time Systems, volume 11, pages 11-20, York, England, June 9-11, 1999.
20. C. Lu, J. A. Stankovic, G. Tao, and S. H. Son. Design and evaluation of a feedback control EDF scheduling algorithm. In Proc. of the IEEE Real-Time Systems Symposium, Phoenix, Arizona, December 1-3, 1995.
21. S. Brandt and G. Nutt. A dynamic quality of service middleware agent for mediating application resource usage. In Proc. of the IEEE Real-Time Systems Symposium, volume 19, pages 307-317, Madrid, Spain, 1998.
22. J. C. Mogul and A. Borg. Effect of context switches on cache performance. In International Conference on Architectural Support for Programming Languages and Operating Systems, pages 75-84, Santa Clara, CA USA, April 8-11, 1991.
23. N. C. Audsley. Optimal priority assignment and feasibility of static priority tasks with arbitrary start times. Technical Report YCS 164, Dept. of Computer Science, University of York, York, England Y01 5DD, December 1991.
24. S. K. Baruah. Static-priority scheduling of recurring real-time tasks. Technical report, Department of Computer Science, The University of North Carolina at Chapel Hill, 1999. Available at http://www. cs. unc. edu/˜baruah/Papers/staticdag. ps.
25. B. Andersson and J. Jonsson. Fixed-priority preemptive scheduling: To partition or not to partition. Technical Report No. 00-1, Dept. of Computer Engineering, Chalmers University of Technology, S-412 96 Göteborg, Sweden, January 2000. Available at http://www. ce. chalmers. se/staff/ba/TR/TR-00-1. ps.
26. Bj örn Andersson and Jan Jonsson, "Fixed-priority preemptive multiprocessor scheduling: to partition or not to partition," rtcsa, pp. 337, Seventh International Conference on Real-Time Computing Systems and Applications (RTCSA'00), 2000.

Hared-memory Multiprocessor