請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/9532
標題: | 制式多處理器下的最佳動態優先即時排程演算法 Optimal Dynamic-priority Real-Time Scheduling Algorithms for Uniform Multiprocessors |
作者: | Chih-Ying Chen 陳士穎 |
指導教授: | 薛智文(Chih-Wen Hsueh 薛智文) |
關鍵字: | 即時,制式,多處理,器,最佳,線上,演算法,預防,貪婪,切, real-time,uniform,multiprocessors,optimal,on-line,algorithm,precaution,greedy,cut, |
出版年 : | 2008 |
學位: | 碩士 |
摘要: | 週期性任務在多處理器上的排程是硬性即時環境下其中一個最受
矚目的問題,而其中包括令人熟知的制式多處理器排程,在制式多處理器環境下,每個任務在一個處理器上的執行時間是等比例於該處理器的運算能力,在以往的成果中,制式多處理器的線上排程只有合適的近似解;在這篇論文,隨著任務可以遷移到不同的處理器,我們首度提出 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. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/9532 |
全文授權: | 同意授權(全球公開) |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-97-1.pdf | 526.01 kB | Adobe PDF | 檢視/開啟 |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。