基于LINUX的调度机制及其实时性研究
|
摘要
作为类UNIX操作系统，Linux操作系统除了保持UNIX稳定、高效等优势之外，系统自身的功能更是不断发展、日益成熟。相对于其他操作系统而言，Linux可以按照需要修改源代码，并且具有支持多种硬件平台、功能可剪裁等诸多优点，在实时领域内也有着广泛的潜在应用前景。
Linux设计之初并没有过多关注系统实时性的问题，因此在将2.4内核或早期版本的Linux应用到实时领域中，由于延迟时间过长均无法满足实时应用的需要。为此一些针对2.4及更早版本内核的修改工作得到了众多Linux程序员及研究机构的支持，这些工作对提高Linux的实时性都有积极的推动作用。在最新的2.6内核中，实时性能的大幅提高更是令Linux的发展步入了全新的时代。
本文首先简单分析了2.4及2.6内核，选取了不同的实时性测量方法及系统负载，在此基础上试验了改进2.4内核实时性的几种权威方法，证实了所选测量方法的正确性以及系统负载的合理性，并借鉴这些改进方法，明确了进一步提高2.6内核实时性的基本方向。
区别于众多增强Linux实时性能的方法，本文在研究提高2.6内核实时性的方法时，同时从整体与局部两种角度探讨增强实时性的方法，不同于常规修改、删减内核源代码以提高实时性的途径，本文将视角转移至内核外部，通过编写抢占模块进行实时抢占的新思想，进一步提高2.6内核的实时性能。同时本文结合新版内核的全新特性，从内核的新功能中探寻实时性的改进方法。实验显示，在同等负载条件下，这些方法均不同程度的提高了Linux的实时性能。
As a category of UNIX operating system, Linux obtains some features like stability and high efficiency which are features of UNIX operating system; meanwhile, the capabilities of Linux become more progress and mature. Compare with other operating systems, Linux can revise its source codes according to different demands, support some architecture platforms and customize some functions. These features make Linux have a potential prospect in real-time application.
At the beginning of system design, Linux had not thought over the problem of real-time performance; hence kernel 2.4 and the earlier Linux versions cannot meet the demand of real-time application because the latency time of system is too long. For this reason, some work on these kernel versions have supported by numerous Linux programmers and research institutions. This work has an influence on enhancing the real-time performance of Linux. In kernel 2.6, the latest version, the improvements in real-time performance start a new era of Linux.
Firstly, kernel 2.4 and kernel 2.6 have been analyzed; some methods and system workloads have been chosen to measure the real-time performance. Moreover, some authoritative methods that enhancing the real-time performance of kernel 2.4 have been try out to prove the measuring methods. By using the reference of these authoritative methods, the fundamental direction of improving the real-time performance of kernel 2.6 has been decided.
Different from the others, some methods that enhancing the real-time performance of kernel 2.6 have been present from the integral angle and the partial angle. Distinct from some normal methods which usually focus on revising, adding and deleting some kernel source codes, a fresh method which uses the kernel module to preempt tasks in order to ensure the execute resolution of high-priority task has been presented. Other methods have linked up with some new features of kernel 2.6. The results show that on the same system workloads, the real-time performance has been improved in different degrees by these methods.
Linux设计之初并没有过多关注系统实时性的问题，因此在将2.4内核或早期版本的Linux应用到实时领域中，由于延迟时间过长均无法满足实时应用的需要。为此一些针对2.4及更早版本内核的修改工作得到了众多Linux程序员及研究机构的支持，这些工作对提高Linux的实时性都有积极的推动作用。在最新的2.6内核中，实时性能的大幅提高更是令Linux的发展步入了全新的时代。
本文首先简单分析了2.4及2.6内核，选取了不同的实时性测量方法及系统负载，在此基础上试验了改进2.4内核实时性的几种权威方法，证实了所选测量方法的正确性以及系统负载的合理性，并借鉴这些改进方法，明确了进一步提高2.6内核实时性的基本方向。
区别于众多增强Linux实时性能的方法，本文在研究提高2.6内核实时性的方法时，同时从整体与局部两种角度探讨增强实时性的方法，不同于常规修改、删减内核源代码以提高实时性的途径，本文将视角转移至内核外部，通过编写抢占模块进行实时抢占的新思想，进一步提高2.6内核的实时性能。同时本文结合新版内核的全新特性，从内核的新功能中探寻实时性的改进方法。实验显示，在同等负载条件下，这些方法均不同程度的提高了Linux的实时性能。
As a category of UNIX operating system, Linux obtains some features like stability and high efficiency which are features of UNIX operating system; meanwhile, the capabilities of Linux become more progress and mature. Compare with other operating systems, Linux can revise its source codes according to different demands, support some architecture platforms and customize some functions. These features make Linux have a potential prospect in real-time application.
At the beginning of system design, Linux had not thought over the problem of real-time performance; hence kernel 2.4 and the earlier Linux versions cannot meet the demand of real-time application because the latency time of system is too long. For this reason, some work on these kernel versions have supported by numerous Linux programmers and research institutions. This work has an influence on enhancing the real-time performance of Linux. In kernel 2.6, the latest version, the improvements in real-time performance start a new era of Linux.
Firstly, kernel 2.4 and kernel 2.6 have been analyzed; some methods and system workloads have been chosen to measure the real-time performance. Moreover, some authoritative methods that enhancing the real-time performance of kernel 2.4 have been try out to prove the measuring methods. By using the reference of these authoritative methods, the fundamental direction of improving the real-time performance of kernel 2.6 has been decided.
Different from the others, some methods that enhancing the real-time performance of kernel 2.6 have been present from the integral angle and the partial angle. Distinct from some normal methods which usually focus on revising, adding and deleting some kernel source codes, a fresh method which uses the kernel module to preempt tasks in order to ensure the execute resolution of high-priority task has been presented. Other methods have linked up with some new features of kernel 2.6. The results show that on the same system workloads, the real-time performance has been improved in different degrees by these methods.
引文
1 Darrick Addison. Embedded Linux applications: An overview - From wrist watches to cluster-based supercomputers [J]. IBM developerWorks. 2001.8
2 Jane W.S.Lin. Real-Time Systems[M]. New Jersey Prentice Hall. 2000:32-37
3 Jae-Ho Lee, Heung-Nam Kim. Implementing priority inheritance semaphore on μs/os real-time kernel[J]. Software Technologies for Future Embedded Systems, 2003, IEEE. 2003.5:83-86
4 Reddy.V.Kumar, Janakiram D. Cohesion Analysis in Linux Kernel[J]. Software Engineering Conference, APSEC 2006. 2006.12:461-466
5 Ramamritham K, Stankovic J A. Schduling Algrithms and Operation System support for real-time systems [J]. Software Engineering Journal, 1994, 83(1) :55-67
6 罗蕾．嵌入式实时操作系统及应用开发[M1．北京航空航天大学出版社，2005．6：10．123-137
7 Andrew Tanenbaum,Albert Woodhull著．操作系统：设计与实现[M1．王鹏，尤晋元等译．第二版．电子工业出版社，2001．4：65
8 任哲，潘树林，房红征．嵌入式操作系统基础与uc/OS-Ⅱ和Linux[M]．北京航空航天大学出版社，2006．8：40-46，65-66
9 En-Nouaary A, Khendek F, Dossonli R. Fault coverage in testing real-time systems[J]. Real-Time Computing Systems and Applications, 1999, RTESA'99. 1999.12:150-157
10 Scott J.M. A Method for modeling and verific, ation of real-time, systems[J]. Southeastcon'98. Pr0cee.dings IEEE. 1998.4: 53-56
11 张大波．嵌入式系统原理、设计与应用[M]．机械工业出版社，2005．7：276，285-286
12 Yu-Chuang Wang, Kwei-Jay Lin. Implementing a General Real:Time scheduling Framework in the RED-Linux "Real-Tim6 Kernel [J]. IEEE Real-Time Systems Symposium. 1999: 23-49
13 Jean J.Labrosse. μC/OS-Ⅱ : the Real Time Kernel [J]. Miller Freeman, Inc. 2000
14 Anon. Alternative operation systems. Part I. The QNX operation system[J]. Byte. 1990.8:281-283
15 Wilner David N, Fiddler Jerry. Vxworks: A Unix/VRTX real-time systems development environment[J]. Conference Record-Electro. v10. 1985.8:8-9
16 Labs Wayne. Microsoft thins, down Win .,CE to compete for Embedded applications[J]. Control solutions International. 2003..5:52
17 Yu-Chuang Wang, Kwei-Jay Lin. The Design and Implementation of Real-Time Schedulers in RED-Linux [J]. IEEE Real-Time Systems Symposium. 2003: 1114-1130
18 Merchesin Armand. Using Linux for Real-Time applications[J]. IEEE software. v21.2004.10:18-20
19 Kay A Robbins, Steven Robbins. Unix System Programming: Communication, Concurrency and Threads[M]. Prentice Hall PTR, 2005.5:2-21
20 Arnd C Heursch, Phelmut Rzehak. Rapid-Reaction Linux:Linux with Low Latency and high timing accuracy[J]. Proceedings of the fifth annual conference on Linux showcase&conference. 2001.11
21 Daniel P Bovet，Marco Cesati著．深入理解Linux内核[M]．陈莉君，冯锐，牛欣源译．第二版．中国电力出版社，2004．7：78-90
22 杜旭，胥海鹏．Linux操作系统调度器实时性能的研究与改进[J]．计算机工程．第10期，2005．5：100-102
23 Fang Lin-B, Huang Zhang-Qin, Hou Y-Bin. Analysis on the mechanism of Linux process scheduler[J]. Journal of BeiJing Unicersity of Technology. v31. 2005.7: 415-419
24 Leung K.K, Du Zhang. Animation of Linux processor scheduling algorithm[J]. Multimedia, Seventh IEEE International Symposium. 2005.12:8
25 Robert Love著．Linux内核设计与实现[M]．陈莉君，康华，张波译．第二版．机械工业出版社，2006，1：35-38
26 Xiaohua Hu, Lin T.Y. Bitmap technologies for o'ptimizing decision support queries and association rule algorithm[J]. Database Engiheering and Applications Symposium, 2003 proceedings. 2003.7:34-43
27 Randy Appleton. Understanding a context switching benchmark: A look at the Linux Kernel Scheduler[J]. Linux Journal, 1999.57es. 1999.1
28 Chi Wang, Huaibei Zhou, Nian Chen. A modified O(1) scheduling Algorithm for real-time tasks[J]. Wireless communications, Networking and Mobile computing, WICOM. 2006.9:1-4
29 Abeni L, Goel A, Krasic C, .Snow J, Walpole J. A Measurement-based analysis of the Real-time performance of Linux[J]. Real-Time and Embedded Technology- and Applications Symposium, 2002 Proceedings, eighth IEEE. 2002.9:133-142
30 杨玉平，芦东昕，白英杰等．一种测试嵌入式Linux调度延迟的方法[J]．计算机工程．第29卷，第22期，2003．12：86-88
31 Jiang Yang, Yu Chen, Huayong Wang, Bibo Wang. A Linux Kernel with fixed interrupt latency for embedded real-time system[J]. Embedded software and systems, 2005, Second International conference. 2005.12:8
32 Yu-Chung Wang, Kwei-Jay Lin. Enhancing the real-time capability of the Linux kernel [J]. Real-Time Computing Systems and Applications, 1998. Proceedings. Fifth International Conference. 1998.10:27-29
33 Kyong J Jung, Seok G Jung, Chanik Park. Stabilizing execution time of user processes by bottom half scheduling in Linux[J]. Real-Time systems, 2004, ECRTS 2004 proceedings. 2004.7:71-75
34 Richard Stevens著．UNIX环境高级编程[M]．尤晋元等译．机械工业出版社， 2006．2：303-304
35 INTEL CORPORATION. Intel Architecture Software Developer's Manual. 1999
36 王继刚，顾国昌，徐立峰等．强实时性Linux内核的研究与设计[J]．系统工程与电子技术．第28卷，第12期，2006．12：1932-1934
37 Clark Williams. Linux Scheduler Latency[J]. Red Hat, Inc. 2002.3
38 Robert Love. MontaVista. Preemption patch for the Linux Kernel. http://www.kernel.org/pub/linux/kernel/people/rml/preempt-kernel/v2.4/
39 Lamport L. The mutual exclusion.problem[J]. Journhl of the ACM. 1986,33: 327-367
40 厉海燕，李新明．Linux抢占式内核的研究与实现[J]．计算机工程与设计．第26卷，第9期，2005．9：2395-2399
41 Yu-Chung Wang, Kwei-Jay Lin. Some Discussion on the Low Latency Patch for Linux [J]. Orlando, Florida:Proc of RTSS'00. 2000.11
42 Andrew Morton. Low Latency patch. University of Wollongong, Australia. 2001 http://www.zip.com.au/～akpm/linux/schedlat.html
43 Amos Waterland. Stress Project Page. http://weather.ou.edu/～apw/projects/stress/ 2005.6
44 Steven L Pratt, .Dominique A Heger. Workload Dependent Performance Evaluation of the Linux 2.6 I/O schedulers[J]. Linux Symposium 2004. v2. 2004: 425-450
45 Seetharami Seelam, Jayaraman Suresh Babu, Patricia Teller. Automatic I/O Scheduler Selection for Latency and Bandwidth Optimization [J]. Department of Computer Science., The University of Texas. 2005
46 Seetharami Seelam, Rodrigo Romero, Patricia Teller. Enhancements to Linux I/O scheduling[J]. Proceedings of the Linux Symposium. 2005.7:175-192
47 Axboe J. Deadline I/O scheduler tunables[J]. SUSE EDF R&D. 2003
48 Iyer S, Drushel P. Anticipatory scheduling-A disk Scheduling framework to overcome deceptive idleness in synchronous[J]. SOSP. 2001
49 Robert Love. Kernel Korner:I/O schedulers[J]. Linux Journal, 2004(118). 2004
50 Jonathan Corbet，Alessandro Rubini，Greg Kroah-Hartman．Linux设备驱动程序[M]．魏永明，耿岳，钟书毅译．第三版．中国电力出版社，2006．7：195-196
51 张勇，郭嘉葳．嵌入式Linux实时性分析与实时性改进[J]．沈阳师范大学学报(自然科学版)．第24卷，第4期，2006．10：457—459
52 Marc Ballarin. Power. Consumption. HZ .100,250,1000: New numbers. 2005.8 http://lwn.net/Articles/145980/
53 Lin Chen, Schott R. Optimal operatigns on red,black trees[J]. Computing;and Information, 1993, proceedings ICCI'93, Fifth International conference. 1993.5: 529-533
2 Jane W.S.Lin. Real-Time Systems[M]. New Jersey Prentice Hall. 2000:32-37
3 Jae-Ho Lee, Heung-Nam Kim. Implementing priority inheritance semaphore on μs/os real-time kernel[J]. Software Technologies for Future Embedded Systems, 2003, IEEE. 2003.5:83-86
4 Reddy.V.Kumar, Janakiram D. Cohesion Analysis in Linux Kernel[J]. Software Engineering Conference, APSEC 2006. 2006.12:461-466
5 Ramamritham K, Stankovic J A. Schduling Algrithms and Operation System support for real-time systems [J]. Software Engineering Journal, 1994, 83(1) :55-67
6 罗蕾．嵌入式实时操作系统及应用开发[M1．北京航空航天大学出版社，2005．6：10．123-137
7 Andrew Tanenbaum,Albert Woodhull著．操作系统：设计与实现[M1．王鹏，尤晋元等译．第二版．电子工业出版社，2001．4：65
8 任哲，潘树林，房红征．嵌入式操作系统基础与uc/OS-Ⅱ和Linux[M]．北京航空航天大学出版社，2006．8：40-46，65-66
9 En-Nouaary A, Khendek F, Dossonli R. Fault coverage in testing real-time systems[J]. Real-Time Computing Systems and Applications, 1999, RTESA'99. 1999.12:150-157
10 Scott J.M. A Method for modeling and verific, ation of real-time, systems[J]. Southeastcon'98. Pr0cee.dings IEEE. 1998.4: 53-56
11 张大波．嵌入式系统原理、设计与应用[M]．机械工业出版社，2005．7：276，285-286
12 Yu-Chuang Wang, Kwei-Jay Lin. Implementing a General Real:Time scheduling Framework in the RED-Linux "Real-Tim6 Kernel [J]. IEEE Real-Time Systems Symposium. 1999: 23-49
13 Jean J.Labrosse. μC/OS-Ⅱ : the Real Time Kernel [J]. Miller Freeman, Inc. 2000
14 Anon. Alternative operation systems. Part I. The QNX operation system[J]. Byte. 1990.8:281-283
15 Wilner David N, Fiddler Jerry. Vxworks: A Unix/VRTX real-time systems development environment[J]. Conference Record-Electro. v10. 1985.8:8-9
16 Labs Wayne. Microsoft thins, down Win .,CE to compete for Embedded applications[J]. Control solutions International. 2003..5:52
17 Yu-Chuang Wang, Kwei-Jay Lin. The Design and Implementation of Real-Time Schedulers in RED-Linux [J]. IEEE Real-Time Systems Symposium. 2003: 1114-1130
18 Merchesin Armand. Using Linux for Real-Time applications[J]. IEEE software. v21.2004.10:18-20
19 Kay A Robbins, Steven Robbins. Unix System Programming: Communication, Concurrency and Threads[M]. Prentice Hall PTR, 2005.5:2-21
20 Arnd C Heursch, Phelmut Rzehak. Rapid-Reaction Linux:Linux with Low Latency and high timing accuracy[J]. Proceedings of the fifth annual conference on Linux showcase&conference. 2001.11
21 Daniel P Bovet，Marco Cesati著．深入理解Linux内核[M]．陈莉君，冯锐，牛欣源译．第二版．中国电力出版社，2004．7：78-90
22 杜旭，胥海鹏．Linux操作系统调度器实时性能的研究与改进[J]．计算机工程．第10期，2005．5：100-102
23 Fang Lin-B, Huang Zhang-Qin, Hou Y-Bin. Analysis on the mechanism of Linux process scheduler[J]. Journal of BeiJing Unicersity of Technology. v31. 2005.7: 415-419
24 Leung K.K, Du Zhang. Animation of Linux processor scheduling algorithm[J]. Multimedia, Seventh IEEE International Symposium. 2005.12:8
25 Robert Love著．Linux内核设计与实现[M]．陈莉君，康华，张波译．第二版．机械工业出版社，2006，1：35-38
26 Xiaohua Hu, Lin T.Y. Bitmap technologies for o'ptimizing decision support queries and association rule algorithm[J]. Database Engiheering and Applications Symposium, 2003 proceedings. 2003.7:34-43
27 Randy Appleton. Understanding a context switching benchmark: A look at the Linux Kernel Scheduler[J]. Linux Journal, 1999.57es. 1999.1
28 Chi Wang, Huaibei Zhou, Nian Chen. A modified O(1) scheduling Algorithm for real-time tasks[J]. Wireless communications, Networking and Mobile computing, WICOM. 2006.9:1-4
29 Abeni L, Goel A, Krasic C, .Snow J, Walpole J. A Measurement-based analysis of the Real-time performance of Linux[J]. Real-Time and Embedded Technology- and Applications Symposium, 2002 Proceedings, eighth IEEE. 2002.9:133-142
30 杨玉平，芦东昕，白英杰等．一种测试嵌入式Linux调度延迟的方法[J]．计算机工程．第29卷，第22期，2003．12：86-88
31 Jiang Yang, Yu Chen, Huayong Wang, Bibo Wang. A Linux Kernel with fixed interrupt latency for embedded real-time system[J]. Embedded software and systems, 2005, Second International conference. 2005.12:8
32 Yu-Chung Wang, Kwei-Jay Lin. Enhancing the real-time capability of the Linux kernel [J]. Real-Time Computing Systems and Applications, 1998. Proceedings. Fifth International Conference. 1998.10:27-29
33 Kyong J Jung, Seok G Jung, Chanik Park. Stabilizing execution time of user processes by bottom half scheduling in Linux[J]. Real-Time systems, 2004, ECRTS 2004 proceedings. 2004.7:71-75
34 Richard Stevens著．UNIX环境高级编程[M]．尤晋元等译．机械工业出版社， 2006．2：303-304
35 INTEL CORPORATION. Intel Architecture Software Developer's Manual. 1999
36 王继刚，顾国昌，徐立峰等．强实时性Linux内核的研究与设计[J]．系统工程与电子技术．第28卷，第12期，2006．12：1932-1934
37 Clark Williams. Linux Scheduler Latency[J]. Red Hat, Inc. 2002.3
38 Robert Love. MontaVista. Preemption patch for the Linux Kernel. http://www.kernel.org/pub/linux/kernel/people/rml/preempt-kernel/v2.4/
39 Lamport L. The mutual exclusion.problem[J]. Journhl of the ACM. 1986,33: 327-367
40 厉海燕，李新明．Linux抢占式内核的研究与实现[J]．计算机工程与设计．第26卷，第9期，2005．9：2395-2399
41 Yu-Chung Wang, Kwei-Jay Lin. Some Discussion on the Low Latency Patch for Linux [J]. Orlando, Florida:Proc of RTSS'00. 2000.11
42 Andrew Morton. Low Latency patch. University of Wollongong, Australia. 2001 http://www.zip.com.au/～akpm/linux/schedlat.html
43 Amos Waterland. Stress Project Page. http://weather.ou.edu/～apw/projects/stress/ 2005.6
44 Steven L Pratt, .Dominique A Heger. Workload Dependent Performance Evaluation of the Linux 2.6 I/O schedulers[J]. Linux Symposium 2004. v2. 2004: 425-450
45 Seetharami Seelam, Jayaraman Suresh Babu, Patricia Teller. Automatic I/O Scheduler Selection for Latency and Bandwidth Optimization [J]. Department of Computer Science., The University of Texas. 2005
46 Seetharami Seelam, Rodrigo Romero, Patricia Teller. Enhancements to Linux I/O scheduling[J]. Proceedings of the Linux Symposium. 2005.7:175-192
47 Axboe J. Deadline I/O scheduler tunables[J]. SUSE EDF R&D. 2003
48 Iyer S, Drushel P. Anticipatory scheduling-A disk Scheduling framework to overcome deceptive idleness in synchronous[J]. SOSP. 2001
49 Robert Love. Kernel Korner:I/O schedulers[J]. Linux Journal, 2004(118). 2004
50 Jonathan Corbet，Alessandro Rubini，Greg Kroah-Hartman．Linux设备驱动程序[M]．魏永明，耿岳，钟书毅译．第三版．中国电力出版社，2006．7：195-196
51 张勇，郭嘉葳．嵌入式Linux实时性分析与实时性改进[J]．沈阳师范大学学报(自然科学版)．第24卷，第4期，2006．10：457—459
52 Marc Ballarin. Power. Consumption. HZ .100,250,1000: New numbers. 2005.8 http://lwn.net/Articles/145980/
53 Lin Chen, Schott R. Optimal operatigns on red,black trees[J]. Computing;and Information, 1993, proceedings ICCI'93, Fifth International conference. 1993.5: 529-533