淡江大學覺生紀念圖書館 (TKU Library)
進階搜尋


下載電子全文限經由淡江IP使用) 
系統識別號 U0002-1806200819401000
中文論文名稱 在RTOS上加入硬即時排程器之研討與實作
英文論文名稱 A study and implementation to incorporate a hard Real-Time scheduler into RTOS
校院名稱 淡江大學
系所名稱(中) 資訊工程學系碩士班
系所名稱(英) Department of Computer Science and Information Engineering
學年度 96
學期 2
出版年 97
研究生中文姓名 蘇信豪
研究生英文姓名 Hsin-Hao Su
學號 695410083
學位類別 碩士
語文別 中文
第二語文別 英文
口試日期 2008-06-04
論文頁數 71頁
口試委員 指導教授-汪柏
委員-洪文斌
委員-郭更生
中文關鍵字 EDF  Preemptive  scheduling 
英文關鍵字 EDF  Preemptive  scheduling 
學科別分類 學科別應用科學資訊工程
中文摘要 在即時系統中,硬即時任務(不接受逾期發生)需要特別的排程器,先討論目前在硬即時排程器中所使用的排程演算法:RM、DM、EDF、LST。再進一步針對 EDF 所衍生的排程演算法做詳細的分析、討論,並提出一種我們改良的排程演算法。
我們實作一個排程模擬器並且用此模擬器來分析EDF 所衍生的排程演算法與我們的方法,最後分別將各排程演算法實作於嵌入式即時系統中,分析結果。
透過在排程模擬器和嵌入式即時系統的排程結果,我們的方法可以維持 Preemptive EDF scheduling 一樣的optimal,也同時因為降低Preemptive EDF scheduling 的overheads,使得feasibility 的成功機率會高於Preemptive EDF scheduling。
英文摘要 In a Real-Time system, hard Real-Time tasks (do not accept delay) need a special scheduler. To discuss current hard Real-Time schedulers which are RM, DM, EDF, LST.
We focus on different derived EDF scheduling algorithms. Then we propose a hybrid cooperative and preemptive EDF scheduling algorithm.
A detailed analysis on those EDF scheduling algorithms by using our scheduler simulator and a Real-Time embedded system verifies our proposed solution.
According to results of our scheduler simulator and a Real-Time embedded system, our solution remains optimal as Preemptive EDF scheduling. And because our solution's
overheads are less than Preemptive EDF scheduling algorithm's overheads, so ratio of feasibility of our solution is better than ratio of feasibility of Preemptive EDF scheduling.
論文目次 目錄 I
圖目錄 III
表目錄 V


第一章 緒論 1
1.1 研究動機及目的 2
1.2 組織架構 4
第二章 背景知識和相關研究 7
2.1 任務的特性分類介紹 7
2.2 排程器和硬即時排程器的介紹 9
2.3 排程器分類的介紹 11
2.4 排程演算法的介紹 13
2.5 硬即時排程器量測的依據 18
2.6 排程模擬器產生圖形符號的意義 19
2.7 相關研究 22
第三章 我們方法 31
第四章 排程模擬器的結果與分析 34
第五章 嵌入式即時系統的實驗結果與分析 42
第六章 結論和未來展望 54
參考文獻 56
Pseudo code 附件 58
英文論文 61

圖目錄
圖2.1 非週期硬即時任務的時限定義 19
圖2.2 週期硬即時任務的時限定義 20
圖2.3 使用 Preemptive EDF scheduling 所得的模擬結果 20
圖2.4 另一種表示圖2.3 的模擬結果 21
圖2.5 使用 preemptive EDF scheduling 所得的模擬結果 21
圖2.6 使用 our EDF scheduling 所得的模擬結果 22
圖2.7 固定間隔外部中斷的時間長度設定成1,使滿足PEDFscheduling 的規則 23
圖2.8 使用 CEDF scheduling 所得的模擬結果 25
圖2.9 使用 CCEDF scheduling 所得的模擬結果 26
圖2.10 條件一成立時 27
圖2.11 調整 Smini 28
圖2.12 調整 Smaxj 28
圖2.13 PEDF scheduling 可滿足所有時限,而CCEDF scheduling 會導致逾期發生 29
圖3.1 我們方法流程步驟1和2 32
圖3.2 PEDF、CEDF、CCEDF、PGCEDF scheduling 的模擬結果 32
圖4.1 實驗一的結果 ratio of overheads 36
圖4.2 實驗一的結果 overflows 37
圖4.3 Ratio of feasibility when processor utilization is more than 80% 39
圖5.1 嵌入式系統回傳 PGEDF scheduling 的紀錄資料片段 46
圖5.2 嵌入式系統回傳 PGEDF scheduling 的紀錄資料片段 46
圖5.3 嵌入式系統的排程結果 47
圖5.4 Table 5-1 的 ratio of overheads(*) 圖表 48
圖5.5 Table 5-1 的 overflow 圖表 49
圖5.6 嵌入式即時系統中PEDF、CEDF、CCEDF、PGCEDF scheduling分派硬即時任務的執行狀況 49
圖5.7 嵌入式即時系統的紀錄結果與排程模擬器的模擬結果 52


表目錄
表4.1 硬即時任務的參數35
表4.2 實驗一的結果 36
表4.3 Ratio of feasibility when processor utilization is lessthan 40% 38
表4.4 Ratio of feasibility when processor utilization is between 40~80% 38
表4.5 Ratio of feasibility when processor utilization is more than 80% 39
表5.1 實驗一的結果 48
表5.2 實驗二的結果 51
參考文獻 [1]. Cecilia Ekelin,“Clairvoyant non-preemptive EDF scheduling”,Proceedings of the 18th Euromicro Conference on Real-Time Systems, pp. 23-32, 2006.
[2]. D. B. Stewart, and P. k. Khosla ,“Real-Time Scheduling of Sensor-Based Control Systems”, in Proc. Eighth IEEE Workshop on Real-Time Operating Systems and Software, in conjunction with 17th IFAC/IFIP Workshop on Real-Time Programming, Atlanta, GA, pp. 144-150, May 1991.
[3]. ISOVIC D, FOHLER G.,“Efficient scheduling sporadic,aperiodic, and periodic tasks with complex constraints”,Real-Time Systems Symposium The 21 st IEEE, pp. 207-216, 2000.
[4]. C. L. Liu and J. W. Layland,“Scheduling algorithms for multiprogramming in a hard-real-time environment”,Journal of the ACM, vol. 20, no. 1, pp. 46-61, Jan. 1973.
[5]. Dong-Zhi He,Fei-Yue Wang,Wei Li,Xiang-Wen Zhang,“Hybrid earliest deadline first/preemption threshold scheduling for real-time systems”,Machine Learning and Cybernetics Proceedings of 2004 International Conference on Volume 1, pp. 433-438, Aug. 2004.
[6]. Lehoczky, J. P., L. Sha, and Y. Ding,“The rate monotonic scheduling algorithm: exact characterization and average case behavior”,in Proceedings of the 10th IEEE Real-Time System Symposium, pp.166-171, 1989.
[7]. Introduction to Rate Monotonic Scheduling, http://www.netrino.com/Embedded-Systems/How-To/RMARate- Monotonic-Algorithm.
[8]. The FreeRTOS.org Project,http://www.freertos.org/
[9]. NXP semiconductor company, http://www.nxp.com/
[10]. Deadline-monotonic scheduling, http://en.wikipedia.org/wiki/Deadline-monotonic_scheduling
[11]. Least slack time scheduling, http://en.wikipedia.org/wiki/Least_slack_time_scheduling.
[12]. ARM7 Family, http://www.arm.com/products/CPUs/families/ARM7Family.html.
[13]. Qt Cross-Platform Application Framework, http://trolltech.com/products/qt/
[14]. HUANG Yue Man, "embedded systems design - to ARM processor based soc platform", the sea Press, chapter 12, 2006.
[15]. Earliest deadline first scheduling, http://en.wikipedia.org/wiki/Earliest_deadline_first_scheduling
[16]. HUANG Yue Man, "embedded systems design - to ARM processor based soc platform", the sea Press, chapter 5.4.5, 2006.
[17]. Jean J. Labrosse,“MicroC/OS-II:The Real-Time Kernel Second Edition”, Publisher CMP Books, April 2002.
[18]. Giorgio C. Buttazzo,“Rate monotonic vs. EDF: judgment day”, Real-Time Systems archive Volume 29 Issue 1, pp. 5-26, January 2005.
[19]. Qing Li and Carolyn Yao ,“Real-Time Concepts for Embedded Systems”, Publisher CMP Book, chapter 1.2, 2003.
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2008-07-02公開。
  • 同意授權瀏覽/列印電子全文服務,於2008-07-02起公開。


  • 若您有任何疑問,請與我們聯絡!
    圖書館: 請來電 (02)2621-5656 轉 2281 或 來信