成功大學博碩士論文系統

簡易檢索 / 詳目顯示

回結果列表

研究生：	余明澤 Yu, Ming-Tsu
論文名稱：	建構於即時Linux之多階層排程器 A Multi-level Scheduler in Real-time Linux
指導教授：	陳　敬 Chen, Jing
學位類別：	碩士 Master
系所名稱：	電機資訊學院 - 電機工程學系 Department of Electrical Engineering
論文出版年：	2002
畢業學年度：	90
語文別：	英文
論文頁數：	55
外文關鍵詞：	Priority Exchange, Earliest Deadline First, Rate Monotonic Scheduling, Priority Ceiling Protocol, Deferrable Server, Stack Resource Policy, Sporadic Server
相關次數：	點閱：104 下載：1
分享至:	分享至facebook 分享至twitter

查詢本校圖書館目錄查詢臺灣博碩士論文知識加值系統勘誤回報

none

In the domain of real-time systems, there are systems that run a mixture of hard and soft deadline tasks. A traditional way to provide service to soft tasks while guarantee to meet deadlines of hard tasks is to use aperiodic server. Although these aperiodic servers try to get better average response time of soft task, they do not take into account the deadline of each soft task individually. In this paper we present a multi-level scheduler which makes use of the aperiodic server model to schedule hard deadline tasks by RMS policy, soft deadline tasks by EDF policy, and non real-time tasks by Linux native scheduling policy. The multi-level real-time scheduler model take advantage of the useful research results that are suitable for practical use and support most kinds of real-time applications including the hard and soft deadline applications which may share resources among tasks, and can be treated as a refinement of traditional aperiodic server. Based on RTLinux, which is a real-time extension to Linux, this architecture is suitable for applications that consist of tasks with different timing requirements, and can exploit the powerful API and utility of Linux. When combing with a schedulability test utility, it will provide a suitable environment for most kinds of real-time applications.

List of Tables................................................................................................................iv
List of Figures...............................................................................................................v
List of Abbreviations...................................................................................................vi
Abstract.......................................................................................................................vii
INTRODUCTION................................................................................................1
1	Real-time systems..........................................................................................1
2	Motivation......................................................................................................1
3	Thesis organization.........................................................................................3
RELATED WORK...............................................................................................5
1	Real-time Linux..............................................................................................5
2	Support for hard and soft tasks.......................................................................6
3	Protocols for bounding blocking time............................................................7
CHARACTERISTIC ANALYSIS.......................................................................8
1	The objectives of real-time schedulers...........................................................8
2	Hard real-time schedulers...............................................................................8
3	Soft real-time schedulers................................................................................9
4	Non-real-time schedulers...............................................................................9
5	Apreiodic servers review..............................................................................10
6	Stack Resource Policy (SRP) ......................................................................18
THE MULTI-LEVEL SCHEDULER...............................................................21
1	Architecture..................................................................................................21
2	State machine...............................................................................................23
OTHER ISSUES.................................................................................................27
1	Schedulability test........................................................................................27
2	Parameter selection.......................................................................................28
IMPLEMENTATION........................................................................................30
1	Overview......................................................................................................30
2	RM................................................................................................................31
3	EDF...............................................................................................................32
4	Sporadic server.............................................................................................33
5	SRP...............................................................................................................34
6	Programmming example..............................................................................34
PERFORMANCE TEST...................................................................................37
1	Scheduling overhead....................................................................................37
CONCLUSIONS AND FUTURE WORK........................................................39
1	Conclusions..................................................................................................39
2	Future Work..................................................................................................39
REFERENCES...........................................................................................................40
APPENDICES............................................................................................................43
A.	IMPLEMENTATION CODE............................................................................43
A.1	Modification in rtl_sched.h..........................................................................43
A.2	Modification in rtl_sched. ...........................................................................44

                                    

[1] B. Sprunt, “Aperiodic task scheduling for real-time systems,” Ph.D. thesis, Carnegie Mellon University, 1990.
[2] J. P. Lehoczky, L. Sha, and J. Strosnider, “Ehanced aperiodic responsiveness in hard real-time environment,” in proc. 8th IEEE Real-Time Systems Symposium, pp. 110-123, San Jose. California, December 1987.
[3] J. Strosnider, J. P. Lehoczky, and L. Sha, “The deferrable server algorithm for enhanced aperiodic responsiveness in hard real-time environments,” IEEE Transactions on Computers, 44(1):73-91, 1995.
[4] IEEE Std.1003.1. Information technology – portable operating system interface (POSIX) 2001.
[5] G. Bernat, A. Burns, “New Results on Fixed Priority Aperiodic Servers,” In proceedings of the 20th IEEE Real-Time Systems Symposium, pp. 68-78, December 1999.
[6] Yu-Chung Wang, Kwei-Jay Lin, “Implementing a General Real-Time Scheduling Framework in the RED-Linux Real-Time Kernel,” In proceedings of the 20th IEEE Real-Time Systems Symposium, pp. 246-255, December 1999.
[7] Giorgio Buttazzo and Giuseppe Lipari, “Scheduling Analysis of Hybrid Real-Time Task Sets,” Real-Time System, 1997. Proceedings. , 9th Euromicro Workshop on Real-Time Systems, pp. 200-206, 1997.
[8] T.P. Baker, “Stack-Based Scheduling of Real-Time Processes,” The Journal of Real-Time Systems 3(1), pp.76-100, 1991.
[9] M.I.Chen and K.J. Lin, “Dynamic Priority Ceilings: A Concurrency Control Protocol for Real-Time Systems,” Real-Time Systems Journal, Vol. 2, No. 4, pp. 325-346, November 1990.
[10] L. Sha, R. Rajkumar, and J.P. Lehoczky, “Priority Inheritance Protocols, An Approach to Real-Time Synchronization”, IEEE Transactions on Computers, Vol. 39, NO. 9, pp. 1175-1185, September 1990.
[11] C.L. Liu and J. W. Layland, “Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment,” JACM 20.1, pp. 46-61, January 1973.
[12] J. P. Lehoczky and S. Ramos-Thuel, “An optimal algorithm for scheduling soft-aperiodic tasks fixed priority preemptive systems,” in porc. 13th IEEE Real-time Systems Symposium, pp. 110-123, Phoenix, Arizona, December 1992.
[13] S. Ramos-Thuel and P. Lehoczky, “On-line scheduling of hard deadline aperiodic tasks in fixed-priority systems,” in proc. 14th IEEE Real-Time Systems Symposium, pp. 160-171, North Carolina, USA, December 1993.
[14] R. Davis, K. W. Tindell, and A. Burns, “Scheduling slack time in fixed priority pre-emptive systems,” in Proc. 14th IEEE Real-Time Systems Symposium, pp. 100-109, December 1995.
[14] T. M. Ghazalie and T. P. Baker, “Aperiodic servers in a deadline scheduling environment. Real-time Systems,” pp. 31-67, 1995.
[15] A. Burns, “Scheduling hard real-time systems: A review,” Software Engineering Journal, 6(3), pp. 116-128, 1991.
[16] Michael Barabanov, “A Linux-Based Real-Time Operating system,” Master’s thesis, New Mexico Institute of Mining and Technology, 1997.
[17] S. K. Baruah, L. E. Rosier, and R. R. Howell, “Algorithms and Complexity Concerning the Preemptive Scheduling of Periodic Real-Time Tasks on One Process,” The Journal of Real-Time Systems 2, pp. 301-324, 1990.
[18] RTAI, http://www.rtai.org/
[19] KURT, http://www.ittc.ukans.edu/kurt/
[20] REDLinux, http://linux.ece.uci.edu/RED-Linux/
[21] Z. Deng, J. W.-S. Liu, and J. Sun, “A Scheme for scheduling Hard Real-Time Applications in Open System Environment,” in Proc. 9th Euromicro Workshop on Real-Time Systems, pp. 191-199, June 1997.
[22] Z. Deng and J. W.-S. Liu, “Scheduling Real-Time Applications in an Open System Environment,” in Proc. IEEE 18th Real-Time Systems Symposium, pp. 308-319, December 1997.
[23] Tei-Wei Kuo and Ching-Hui Li, “A Fixed-Priority-Driven Open Environment for Real-Time Applications,” in Proc. IEEE 20th Real-Time Systems Symposium, pp. 256-267, December, 1999.

校內：2003-08-12公開
校外：2003-08-12公開

簡易檢索 / 詳目顯示

相關論文