在即時系統中，硬即時任務（不接受逾期發生）需要特別的排程器，先討論目前在硬即時排程器中所使用的排程演算法：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.