臺灣博碩士論文加值系統

在即時系統的領域中，系統通常同時執行混雜著硬即時和軟即時的任務集。在傳統的研究上，即時作業系統中之任務排程，一般均使用優先順序之設定，以保證在硬即時任務可於期限內完成的前提下，提供服務給軟即時任務。雖然這些排程方法試圖提供較佳的平均反應時間給軟即時任務，但是他們並沒有個別考慮每個軟即時任務的期限。在這篇論文中我們提出一個適應性排程器，這個支援多處理器即時系統之適應性排程器考量了現實世界中之即時作業系統運作環境。模擬結果顯示，所提出的適應性排程器改善了系統效能，且適用於大部份即時應用程式的排程架構。

In the real-time system, the system usually supports the application that includes the task set with hard and soft real-time tasks. The traditional researches on the task scheduling in real-time operating systems were setting the priority for providing service to soft tasks after that can promise meet deadline of hard tasks. Therefore, those scheduling schemes were trying to provide better average meet ratio for soft tasks, but did not consider the deadline of each task. In this thesis, an adaptive scheduler has been proposed. The proposed adaptive scheduler for the real-time multiprocessor systems considers the operating environment in the real world. The simulation results show that the proposed adaptive scheduler can improve the system performance and fit for almost all real-time applications.

ACKNOWLEDGEMENT
ABSTRACT in ENGLISH
ABSTRACT in CHINESE
TABLE OF CONTENTS
LIST OF FIGURES
LIST OF TABLES
CHAPTER 1 INTRODUCTION
CHAPTER 2 BACKGROUND
2.1 Single Processor Scheduling Algorithm
2.1.1 Static Scheduling Algorithm in the Uniprocessor
2.1.2 Dynamic Scheduling Algorithm in the Uniprocessor
2.2 Multiprocessor Scheduling Algorithm
2.2.1 Partitioning Multiprocessor Scheduling Algorithm
2.2.2 Global Multiprocessor Scheduling Algorithm
2.3 Hierarchical Scheduling
CHAPTER 3 PROPOSED ADAPTIVE SCHEDULER IN MULTIPROCESSOR REAL-TIME SYSTEMS
3.1 Proposed Adaptive Scheduler
3.2 Allocation
CHAPTER 4 SIMULATION AND PERFORMANCE EVALUATION
4.1 Simulation
4.2 Performance Evaluation
CHAPTER 5 CONCLUSIONS
REFERENCES
APPENDIX

[1]J.E. Cooling, “Software Design for Real-Time Systems,” Chapman & Hall, 1991.
[2]C. M. Krishna and Kang G. Shin, “Real-Time Systems,” McGraw-Hill, 1997.
[3]Liu, C. L., and J. W. Layland, “Scheduling Algorithms for Multiprogramming in a Hard Real Time Environment,”Journal of the Association for Computing Machinery, vol.20, no.1, pp. 44-61, January 1973.
[4]David B. Stewart and Pradeep K Khosla, “Real-Time Scheduling of Dynamically Reconfigurable System,”Proceedings of the IEEE International Conference on Systems Engineering, pp. 139-142, August 1991.
[5]Lopez J.M., Diaz, J.L., Garcia D.F, “Minimum and Maximum Utilization Bounds for Multiprocessor Rate Monotonic Scheduling,”IEEE Transactions on Parallel and Distributed Systems, vol. 15, no. 7, pp. 642 – 653, July 2004.
[6]A. Khemka and R. K. Shyamasunda., “Multiprocessor scheduling of periodic tasks in a hard real-time environment,” Proceedings of the IEEE International Conference on Parallel Processing Symposium, pp. 76-81, March 1992.
[7]Paolo Valente and Giuseppe Lipari, “An Upper Bound to the Lateness of Soft Real-time Tasks Scheduled by EDF on Multiprocessor,”Proceedings of the 25th IEEE International Real-Time Systems Symposium, 10 pp. Dec. 2005.
[8]Theodore P. Baker, ”An Analysis of EDF Schedulability on a Multiprocessor,” IEEE Transactions on Parallel and Distributed Systems, vol.16, no. 8, pp.760 – 768, Aug. 2005.
[9]Joel Goossens, Shelby Funk, Sanjoy Baruah, “Priority-Driven Scheduling of Periodic Task Systems on Multiprocessor,”Real-Time Systems, vol. 25, no. 2-3, pp. 187 – 205, Sep. 2003

[10]Shanmuga Priya Marimuthu and Samarjit Chakraborty, ”A Framework for Compositional and Hierarchical Real-Time Scheduling,”Proceedings of the 12th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, pp. 91-96, Aug. 2006.
[11]Lorente J.L, Lipari G., Bini E., “A Hierarchical Scheduling Model for Component-Based Real-Time Systems,”Proceedings of the 20th IEEE International Parallel and Distributed Processing Symposium, 8 pp., Apr. 2006.
[12]Liang-Teh Lee, Chia-Ying Tseng, Yu-Chieh Li, and Shieh-Jie Hsu, “Design and Implementation of an Adaptive Multilevel Scheduler,”Proceedings of International Computer Symposiums (ICS), vol 1, pp.219-223, Dec. 2006.
[13]Shaoxiong Hua, Pari P.R., Gang Qu, “Dual-Processor Design of Energy Efficient Fault-Tolerant System,” Proceedings of the IEEE International Conference on Application-specific Systems, Architectures and Processors, pp. 239-244, 2006.
[14]C. Locke, D. Vogel, and T. Mesler., “Building a Predictable Avionics Platform in Ada: a Case Study,” Proceedings of IEEE Real-Time Systems Symposium, pp. 181-189, 1991.
[15]A. Burns, K. Tindell, and A. Wellings., “Effective analysis for engineering real-time fixed priority schedulers,” IEEE Transactions on Software Eng., Vol. 21, pp. 475-480, 1995.
[16]D. Shin, J. Kim, and S. Lee. “Intra-Task Voltage Scheduling for Low-Energy Hard Real-Time Applications”, IEEE Design and Test of Computers, Vol. 18, No. 2, pp. 20-30, 2001.