多處理器即時系統之EDZL排程演算法的效能評估

Performance Evaluation of EDZL Scheduling Algorithm for Multiprocessor Real-Time Systems

劉伊玲(I-Ling Liu)

指導教授 ： 石維寬

國立清華大學/電機資訊學院/資訊工程學系/碩士(2008年)

摘要

近年來，隨著多處理器、多核心系統等硬體技術的快速發展，與多處理器即時系統相關的研究議題也越來越普遍。

其中，排程演算法一向是個重要的議題。在單處理器即時系統上，過去的研究已經明確地指出有最佳解，如EDF或是LLA演算法。然而多處理器系統需要考慮的因素比單處理器系統多，排程問題也複雜許多，至今仍未證實有任何有效率的最佳解。因此，在這篇論文中，我們希望能夠在多處理器系統的環境下，給定限制的處理器個數、tasks個數或task period範圍等條件，找出次佳的即時排程演算法。

在仔細研讀RM、EDF、LLA等基本的演算法，以及排程相關問題及演算法的分析之後，我們發現EDZL擁有不錯的schedulability屬性。因此，我們將主軸放在EDZL 演算法，進一步以Zero Laxity的概念為基礎，設計了REZL、UTZL、SRCZL、LRCZL以及MLRCZL這五個ZL-based排程演算法。

我們以亂數隨機產生大量的task sets，分別測量這些演算法的平均成功排程的比例和平均中斷次數。藉由分析模擬實驗的數據，來針對多處理器即時系統上的EDZL排程演算法和其他ZL-based排程演算法的效能評估做出結論。

關鍵字

多處理器 ； 即時系統 ； 排程演算法

並列摘要

Recently, as the rapid development of hardware technology of multiprocessor and multi-core systems, research issues related to multiprocessor real-time systems become more and more popular.
Scheduling algorithm is a very important topic in this domain. It has been proved that there are optimal solutions for single processor real-time systems, such as EDF and LLA algorithm. However, on multiprocessor systems, there are more factors have to be considered and the scheduling problems are more complex than on single processor systems. In this thesis, we want to find a sub-optimal real-time scheduling algorithm for a restricted condition, such as the number of processors, the number of tasks in a task set or the task period, in the environment of multiprocessor systems.
After studying RM, EDF, and LLA algorithms, and a lot of analysis for scheduling problems and algorithms, we found that EDZL has a good schedulability property. We focus on EDZL algorithm, and designed five ZL-based scheduling algorithms－REZL, UTZL, SRCZL, LRCZL and MLRCZL, based on the concept of Zero Laxity.
We generated a lot of task sets randomly, and measured the average successful ratio and the average number of preemptions for these algorithms. According to the analysis of the simulation results, we make some conclusions for the performance evaluation of EDZL and other ZL-based scheduling algorithms for multiprocessor real-time systems.

並列關鍵字

multiprocessor ； real-time systems ； scheduling algorithms

參考文獻

[2] M. Park, S. Han, H. Kim, S. Cho, and Y. Cho, “Comparison of Tie-Breaking Policies for Real-Time Scheduling on Multiprocessor”, Lecture Notes in Computer Science, Vol. 3207, pp.174-182, 2004.

[3] C. L. Liu and J. W. Layland, “Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment”, Journal of the ACM, 20(1):46-61, 1973.

[6] T. P. Baker, “Multiprocessor EDF and Deadline Monotonic Schedulability Analysis”, In Proceedings of the 24th IEEE International Real-Time Systems Symposium, pp.120-129, 2003.

[8] M. Cirinei and T. P. Baker, “EDZL scheduling analysis”, In Proceedings of the 19th Euromicro Conference on Real-Time Systems, pp.9-18, 2007.

[11] H. Cho, B. Ravindran, and E. D. Jensen, “An Optimal Real-Time Scheduling Algorithm for Multiprocessors”, In Proceedings of the 27th IEEE International Real-Time Systems Symposium, pp.101-110, Dec. 2006.