近幾年來，針對多重處理器即時排程的需求變得越來越多；隨著硬體成本的降低，使用多重處理器架構的即時系統已經變得非常普遍。也就因為如此，在這樣的系統當中，工作排程是一個有挑戰性的問題，如果排程方式不佳，雖然使用較多的處理器，卻反而沒有得到該有的加乘效率。本論文主要研究一些有效率的多重處理器即時排程方法，首先是 EDZL ( Earliest Deadline first until Zero Laxity)，為了改善效率，我們從Zero laxity再推廣到 k 個laxities的情況來分析，並且嘗試以其它的經驗法則來取代EDZL當中的EDF成為主要的排程模組。在本篇論文當中，經由實驗發現EDZL仍是一個很有效率的排程演算法；EDkL並沒辦法增加多少處理器使用率；以其它經驗法則取代EDF的方式表現並不如意；先前已有研究者猜測EDZL的可排程使用率為 ，我們分析一類特殊工作集合的無法排程的特性，以反證法證明 這個猜測是錯誤的；並由分析的過程證明EDZL的可排程使用率無法超過m(1-1/e)；雖然這個可排程使用率的邊界條件不甚理想，不過這種低處理器使用率僅出現在特殊的工作集合，針對一般工作集合來說，EDZL仍是一個實用且有效率的排程演算法。

There has been an increasing demand for real-time scheduling on multiprocessor systems. With the decreasing cost of hardware, multiprocessor architecture becomes more popular nowadays. However, a multiprocessor real-time system may not provide a performance speedup proportional to the number of processors. Choosing a suitable scheduling algorithm is very important in order to get good performance. In this paper, we study some efficient real-time scheduling algorithms for multiprocessor systems. The first is EDZL (Earliest Deadline first until Zero Laxity). Then we extend the cases to the condition of k laxities. We also try to replace the EDF module with other heuristics in EDZL algorithm. We find that EDkL could not improve processor utilization and other heuristics are not good enough as EDF in EDZL. Using a special task set we got from experiments, we disprove the conjecture that the utilization bound of EDZL is 3m/4. Finally, we also get a property that the utilization bound of EDZL is not greater than m(1-1/e) where e is the natural logarithm. Although the bound of EDZL is not ideal enough, EDZL is still an efficient and practical scheduling algorithm for real-time multiprocessor systems.

[1] S. K. Lee, “On-line multiprocessor scheduling algorithms for real-time tasks,” IEEE Regions 10's Ninth Annual International Conference, pp. 607-611, 1994.
[2] S. Baruah, J. Goossens, “Scheduling real-time tasks: algorithms and complexity, ” In Handbook of Scheduling: Algorithms, Models, and Performance Anaysis, Joseph Y-T Leung(ed). Chapman Hall/CRC Press, 2004.
[3] J. Carpenter, S. Funk, P. Holman, A. Srinivasan, J. Anderson, S. Baruah, “A categorization of real-time multiprocessor scheduling problems and algorithms, ” In Handbook of Scheduling: Algorithms, Models, and Performance Analysis, Joseph Y-T Leung (ed). Chapman Hall/ CRC Press. 2004.
[4] J. Goossens, P. Richard, “Overview of real-time scheduling problems, ” Proceedings of the ninth international conference on project management and scheduling, 2004.
[5] J. Goossens, S. Funk, S. Baruah, “Priority driven scheduling of periodic task systems on multiprocessors, ” Real-time Systems, v. 25, n. 2, pp. 187-205, 2003.
[7] J. M. Lopez, M. Garcia, J. L. Diaz, D. F. Garcia, “Worst case utilization bound for EDF scheduling on real-time multiprocessor systems, ” Proceedings of the 12th Euromicro Conference on Real-time Systems, pp. 25-33, 2000.
[8] S. Baruah, “Optimal utilization bounds for the fixed-priority scheduling of periodic task systems on identical Multiprocessors. ” IEEE Transactions on Computers, v. 53, n. 6, pp. 781-784, 2004.
[9] K. Ramamritham, J. A. Stankovic, “Efficient scheduling algorithms for real-time multiprocessor systems, ” IEEE Transactions on Parallel and Distributed Systems, v. 1, n. 2, pp. 184-194, 1990.
[10] B. Andersson, J. Jonsson, “ Preemptive multiprocessor scheduling anomalies, ” Proceedings of IPDPS, pp. 12-19, 2002.
[11] S. Baruah, G. Koren, D. Mao, B. Mishra, A. Raghunathan, L. Rosier, D. Shasha, F. Wang, “On the competitiveness of on-line real-time task scheduling, ” Real-Time Systems, v. 4, pp. 125-144. 1992.
[12] A. Srinivasan, P. Holman, J. Anderson, S. Baruah. “The case for fair multiprocessor scheduling, ” Proceedings of the 11th International Workshop on Parallel and Distributed Real-Time Systems, 2003.
[13] M. L. Dertouzos and A. K. Mok, “Multiprocessor on-line scheduling of hard-real-time tasks,” IEEE Transactions on Software Engineering, v. 15, n. 12, pp. 1497-1506, 1989.
[14] A. Srinivasan, S. Baruah, “Deadline-based scheduling of periodic task systems on multiprocessors, ” Information Processing Letters, v. 84, n. 2, pp. 93-98, 2002.
[15] C. D. Locke, “Best-effort decision making for real-time scheduling, ” PhD. Thesis, Dept. CS, CMU, USA, 1986.
[16] K. J. Lin, Y. C. Wang, T. H. Chien, Y. J. Yeh, “Designing multimedia applications on real-time systems with SMP architecture, ” 4th International Symposium on Multimedia Software Engineering, pp. 17-24, 2002.
[17] T. Y. Kuan and K. J. Lin, “An efficient on-line algorithm for real-time scheduling on multiprocessor, ” unpublished manuscript, 2005.
[18] D. J. Chen, A. K. Mok, T. W. Kuo, “Utilization bound revisited, ” IEEE Transactions on Computers , v. 52, n. 3, pp. 351-361, 2003.
[19] M. Park, S. Han, H. Kim, S. Cho, Y. Cho, “Comparison of deadline-based scheduling algorithms for periodic real-time tasks on multiprocessor, ” IEICE Transactions, v. 88-D, n. 3, pp. 658-661, 2005.
[20] X. Piao, S. Han, H. Kim, M. Park,Y. Cho, S. Cho, “Predictability of earliest deadline zero laxity algorithm for multiprocessor real-time systems, ” Ninth IEEE International Symposium Object and Component-Oriented Real-Time Distributed Computing, pp. 359-364, 2006.