臺灣博碩士論文加值系統

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.