制式多處理器下的最佳動態優先即時排程演算法

Optimal Dynamic-priority Real-Time Scheduling Algorithms for Uniform Multiprocessors

陳士穎(Chih-Ying Chen)

指導教授 ： 薛智文

國立臺灣大學/電機資訊學院/資訊工程學研究所/碩士(2008年)

https://doi.org/10.6342/NTU.2008.01095

摘要

週期性任務在多處理器上的排程是硬性即時環境下其中一個最受
矚目的問題，而其中包括令人熟知的制式多處理器排程，在制式多處理器環境下，每個任務在一個處理器上的執行時間是等比例於該處理器的運算能力，在以往的成果中，制式多處理器的線上排程只有合適的近似解；在這篇論文，隨著任務可以遷移到不同的處理器，我們首度提出 T-Ler 平面這個嶄新的模型，用來描述任務和處理器的行為，並在T-Ler 平面上提出兩種最佳演算法以在制式多處理器上排程動態優先即時任務，為了讓演算法更符合真實並減少本文切換，我們提出了複雜度在多項式時間以內的演算法來保證一個 T-Ler 平面裡重新排程的次數，由於任務遷移在 SOC 多核心平台下較為容易達成，我們的結果也許可以應用到非對稱的多核心平台。

關鍵字

即時 ； 制式 ； 多處理器 ； 最佳 ； 線上 ； 演算法,預防 ； 貪婪 ； 切

並列摘要

In hard-real-time environment, scheduling periodic tasks upon multiprocessors is one of the most popular problems where uniform multiprocessor scheduling is a well-known one. In uniform multiprocessor scheduling, execution
time of each task in one processor is proportional to the computing capacity of this processor. From previous works, there are only approximate feasible solutions for on-line scheduling on uniform multiprocessors. In this thesis, with task migration, we first present a novel model called T-Ler plane for uniform multiprocessors to describe the behavior of tasks and processors, and two optimal algorithms based on T-Ler plane to schedule dynamic-priority real-time tasks on uniform multiprocessors. To make it practical and reduce context switches, we also present a polynomial-time algorithm to bound the times of rescheduling or task migration in a T-Ler plane and give an experimental evaluation for it. Since task migration is easier in SOC multicore processors, our result might be applicable and adapted to many asymmetric multicore platforms.

並列關鍵字

real-time ； uniform ； multiprocessors ； optimal ； on-line ； algorithm,precaution ； greedy ； cut

參考文獻

[1] Advanced Micro Devices (AMD). Multi-core processors - the next evolution in computing.

[2] S.K. Baruah, N.K. Cohen, C.G. Plaxton, and D.A. Varvel. Proportionate progress: A notion of fairness in resource allocation. Algorithmica, 15(6):600–625, June 1996.

[3] S.K. Baruah and J. Goossens. Preemptive scheduling of uniform processor systems. Journal of the ACM, 25(1):92–101, Jan. 1978.

[4] S.K. Baruah and J. Goossens. Rate-monotonic scheduling on uniform multiprocessors. IEEE Transactions on Computers, 52(7):966–970, Jul 2003.

[5] J.M. Calandrino, D. Baumberger, S. Tong Li, Hahn, and J.H. Anderson. Soft real-time scheduling on performance asymmetric multicore platforms.Real Time and Embedded Technology and Applications Symposium, April 2007.