跳到主要內容

臺灣博碩士論文加值系統

(44.192.38.49) 您好!臺灣時間:2023/02/09 14:16
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:余明澤
研究生(外文):Ming-Tsu Yu
論文名稱:建構於即時Linux之多階層排程器
論文名稱(外文):A Multi-level Scheduler in Real-time Linux
指導教授:陳敬陳敬引用關係
指導教授(外文):Jing Chen
學位類別:碩士
校院名稱:國立成功大學
系所名稱:電機工程學系碩博士班
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:英文
論文頁數:55
外文關鍵詞:Priority ExchangeEarliest Deadline FirstRate Monotonic SchedulingPriority Ceiling ProtocolDeferrable ServerStack Resource PolicySporadic Server
相關次數:
  • 被引用被引用:0
  • 點閱點閱:338
  • 評分評分:
  • 下載下載:43
  • 收藏至我的研究室書目清單書目收藏:0
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
1. INTRODUCTION................................................................................................1
1.1 Real-time systems..........................................................................................1
1.2 Motivation......................................................................................................1
1.3 Thesis organization.........................................................................................3
2. RELATED WORK...............................................................................................5
2.1 Real-time Linux..............................................................................................5
2.2 Support for hard and soft tasks.......................................................................6
2.3 Protocols for bounding blocking time............................................................7
3. CHARACTERISTIC ANALYSIS.......................................................................8
3.1 The objectives of real-time schedulers...........................................................8
3.2 Hard real-time schedulers...............................................................................8
3.3 Soft real-time schedulers................................................................................9
3.4 Non-real-time schedulers...............................................................................9
3.5 Apreiodic servers review..............................................................................10
3.6 Stack Resource Policy (SRP) ......................................................................18
4. THE MULTI-LEVEL SCHEDULER...............................................................21
4.1 Architecture..................................................................................................21
4.2 State machine...............................................................................................23
5. OTHER ISSUES.................................................................................................27
5.1 Schedulability test........................................................................................27
5.2 Parameter selection.......................................................................................28
6. IMPLEMENTATION........................................................................................30
6.1 Overview......................................................................................................30
6.2 RM................................................................................................................31
6.3 EDF...............................................................................................................32
6.4 Sporadic server.............................................................................................33
6.5 SRP...............................................................................................................34
6.6 Programmming example..............................................................................34
7. PERFORMANCE TEST...................................................................................37
7.1 Scheduling overhead....................................................................................37
8. CONCLUSIONS AND FUTURE WORK........................................................39
8.1 Conclusions..................................................................................................39
8.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.
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關論文
 
1. 王正(1994)「社會救助、家庭人口規模與貧窮水準測定之研究」,《經社法制論叢》第十三期。
2. 王正(2000)保險、救助及津貼:老年經濟安全制度財務體系配合之探討,經社法制論叢,第廿六期,行政院經建會。
3. 林宜輝 (1998) 「家庭政策支持育兒婦女就業制度之探討一兼論臺灣相關制度之改革」,《社區發展季刊》第八四期
4. 郝鳳鳴 (1996)「我國社會救助法之現況分析與檢討」,《東海大學法學研究》第十期。
5. 陳美珠、楊智雯、洪嘉璐 (1999)「中美貧窮家庭兒童福利服務之比較」,《兒童福利論叢》第三期
6. 萬育維(1994)「社會救助與福利國家的探討」,《社會建設》第八九期
7. 盧政春 (1996)「德國子女津貼制度之研究一兼論我國相關制度之建立」,《東吳社會學報》第五期。
8. 鄭麗嬌 (1999)「美、德與法三國兒童照顧與家庭政策之比較研究」,《理論與政策》第十三期。
9. 鄭清風(1993)「談家庭津貼與家庭政策」,《勞工之友》第五一二期:14-19。
10. 簡宏光、楊葆茨 (1997)「中美單親家庭兒童福利服務之比較」,《兒童福利論叢》第一期。
11. 謝秀芬 (1997)「現代婦女的家庭價值觀與家庭期待之研究」,《東吳社會工作學報》第三期。
12. 蕭芳華(1999)「幼兒教育券政策分析之研究」,中國行政評論,第九卷第1期。