摘要
近年来,嵌入式系统在军事、工业、航天等重要领域得到了广泛应用,同时这些领域对系统的实时性也提出了越来越高的要求。相对于其它嵌入式操作系统,Linux具有开放源代码、可裁剪、性能稳定、可靠性高、支持SMP体系结构等特点,目前基于Linux的嵌入式系统应用案例越来越丰富。
本文对嵌入式Linux中的时钟机制、计时系统、时间戳系统、定时器系统以及调度框架和调度算法进行了深入的分析。在此基础上,针对嵌入式Linux在实时性能上所面临的问题,基于单触发时钟对其进行了实时优化。
在时钟系统方面,本文首先实现了单触发时钟,并基于单触发时钟设计了资源控制器OTRC(One-shot Timer Based Resource Controller,OTRC)。OTRC主要用于管理系统中的资源(如CPU等),并根据具体的实时需求来控制时钟中断的时间。另外,改造了计时系统,保证了系统在单触发时钟下计时的正确性。
在定时器系统方面,设计了高精度定时器系统。该系统基于OTRC对定时器队列的管理,可以得到微秒级的时钟精度。另外利用时间戳计数器设计了细粒度的时间戳系统,为高精度定时器系统提供了准确的时间度量。改造后的高精度定时器系统能够达到微秒级的定时精度。
在调度算法上,提出了OBED(OTRC Based EDF Scheduling,OBED)实时调度算法,并设计了新的实时调度框架。该框架将实时进程和非实时进程分开管理,对实时进程使用EDF调度算法,而对非实时进程使用Linux原有的调度算法,并利用OTRC对进程的执行进行管理和控制。OBED算法综合了两种算法的优点,既能够保证实时进程的时间约束条件,又可以提高非实时进程的性能,达到了提高系统吞吐率的目的。
最后,本文在PowerPC嵌入式平台上实现了单触发时钟系统、细粒度时间戳系统、OTRC资源控制器和高精度定时器系统,并实现了OBED实时调度框架的原型系统。测试结果显示,改进后的系统在实时性方面有了很大的提高。
In recent years, embedded systems have been widely applied in the military, industrial, aerospace and other important areas. At the same time, the real-time also raised higher and higher requirements in these areas. Compared with other embedded operating systems, Linux has many advantages which can be cutting, stable performance, high reliability, support for SMP architecture, and so on. In view of these, this article emphasizes on how to improve the real time technology of embedded Linux.
This paper has deeply analysised the clock mechanism, timing system, time stamp system, timer system, scheduler, and scheduling algorithm. Then it presents the corresponding solutions against these key problems based on the one-shot timer for embedded real-time Linux.
In the clock system, this article designs the resource controller OTRC (One-shot Timer Based Resource Controller, OTRC) based on the one-shot timer. OTRC is used to control the interrupt of the one-shot clock, manage the resource in the system, and control the one-shot clock according to the specific needs of real-time requjirements. In order to maintain the accuracy of timing, the timing system is rebuilt.
In the timer system, the high resolution timer is designed. The high resolution timer system can require microsecond-level clock accuracy based on the OTRC which manage the queue of timer. In addition, the time stamp system which can provide accurate time measurement to high resolution timer system is designed, and it works based on the time stamp counter. The high resolution timer system can achieve microsecond-level timing accuracy.
In the scheduling algorithm, the OBED (OTRC Based EDF Scheduling, OBED) real-time scheduling algorithm is designed, and the real-time scheduling framework based on OTRC is designed. The framework separates the real-time process and general process. The real-time process is scheduled with EDF algorithm, while the general process is scheduled with the traditional Linux scheduling algorithm. OBED algorithm combines the advantages of the two algorithms, and controls the preemption of processes. The OBED scheduling framework can not only guarantee the time constraints of real-time process, but also improve the performance of non-real-time process. So, this framework can improve the throughput in the real-time system.
Finally, this paper implements the one-shot clock system, time-stamp system, OTRC, and high resolution timer system, and then implement a simple system of OBED scheduling framework in Linux kernel. The experimental results show that the improved system is greatly improved in the real-time performance.
引文
[1] UTIME-Miicro-Second Resolution Timers for Linux [EB/OL]. 2001. www.ittc.ku.edu/utime.
[2] J. Mehaffey. MontaVista Linux Open Source Real Time Project Whitepaper [Z]. 2004. MontaVista Software/ www.mvista.com/dswp.
[3] K. Gopalan. Real-time Support in General Purpose Operating Systems [R]. ECSL Technical Report TR92, Experimental Computer System Labs, Computer Science Dept, Stony Brook University, Stony Brook, 2001.
[4] R. Love. Linux Kernel Development [M]. Indiamapolis: Sams Publishing, 2004.
[5] W. Jane, S. Liu. Real-Time Systems. New Jersey: Prentice Hall, 2000.
[6] Marshall. K. McKusick. The Design and Implementation of the 4.4 BSD Operation Systems. Boston: Addison-Wesley, 1996.
[7] Bochs IA-32 Emulator Project. http://bochs.sourceforge.net.
[8] Michael, Barabanov, Victor Yodiken. Introducing real-time Linux. Linux Journal, 1997.
[9] Victor Yodaiken. The RT-Linux approach to hard real-time. 1997. http://rtlinux.lzu.edu.cn/documents/papers/whitpaper/html.
[10] Thomas Tsou, Philip Balister, Jeffrey Reed. Laatency profiling for SCA software radio. SDR Forum Technical Conference, 2007.
[11] Naobing Dai, Toshihiro Matsui, Yutaka Ishikawa. A light lock management mechanism for optimizing real-time and no-real-time performance in embedded Linux. IEEE International conference on embedded and ubiquitous conputing, 2008.
[12] Morten Engen. Better real-time capabilities for the AVR32 Linux Kernel. Trondheim, Norwegian University of Science and Technology, 2007.
[13] Jupyung Lee, Kyu H Park. Delayed locking technique for improving real-time performance of embedded Linux by prediction of timer interrupt. IEEE Real Time and Embedded Technology and Applications Symposium, 2005.
[14] Janno Grobler, Derrick Kourie. Design of a high resolution soft real-time timer under a Win32 operating. Proceedings of SAICSIT, 2005.
[15] Xue-yu Hong, Ling Zhang, Jim-long Hu. New scheme of implementing real-time Linux. IEEE Proceeding of International Conference on Software Engineering Advances, 2006.
[16]李小群,赵慧斌,叶以民等.一种基于时钟粒度细化的Linux实时化方案.计算机研究与发展,2003,40(5):734~740.
[17]李小群,赵慧斌,叶以民等.Linux实时调度方案的设计与实现.计算机研究与发展,2003,40(5):728~733.
[18]李小群,赵慧斌,叶以民等.RFRTOS:基于Linux的实时操作系统.软件学报,2003,14(7):1203~1210.
[19] John Stultz, Nishanth Aravamudan, Darren Hart. We are not getting any younger: A new approach to time and timers [C]. Ontario, Canada: Proceedings of the 21nd Linux Symposium, 2005.
[20] T. Gleixner, D. Niehaus. Hrtimers and Beyond Transforming the Linux Timer subsystems [C]. Ontario, Canada: Proceedings of the 22nd Linux Symposium, 2006.
[21]王小英,赵海,张文波等.自适应SR-RM调度算法.东北大学学报,2005.
[22] Chung Laung Liu, James W. Layland. Scheduling algorithms for multiprogramming in a hard real-time environment. Journal of the ACM, 1973, 20(1):46~61.
[23] Balaji Srinivasan, R. Hill, S. Pather. A firm real-time system implementation using commercial off-the-shelf hardware and free software. The Real-Time Techonology and Applications Symposium, Denver, 1998.
[24] R. Hill, B. Srinivasan, S. Pather. Temporal resolution and real-time extension to Linux. Information and Telecommunication Technology Center, Electrical Engineering and Computer Science Department, University of Kansas, Tech Rep, 1998.
[25] Balaji Srinivasan, R. Hill, S. Pather. A firm real-time system implementation using commercial off-the shelf hardware and free software. The Real-Time Techonology and Applications Symposium, Denver, 1998.
[26] K. Kwon, M. Sugaya, T. Nakajima. Analysis of High Resolution Timer Latency using Kernel Analysis System in Emdedded System[C]. Janan: STFSSD IEEE, 2009.
[27] Bala Kalyanasundaram, Kirk R. Pruhs. Speed is as powerful as clairvoyance. 36th Annual Symposium on Foundations of Computer Science, 1995.
[28] G. Gracioli, D. M. Santos, R. D. Matos. One-Shot Time Management Analysis in EPOS[C]. Chile: SCCC IEEE, 2008.
[29] Rhan Ha, Jane W. Liu. Validating timing constraints in multiprocessor and distributed real-time systems. 14th International Conference on Distributed Computing Systems, 1994.
[30] C. Edward. Horvath, Shui Lam, Ravi Sethi. A level algorithm for preemptive scheduling. Journal of the ACM, 1977, 24(1): 32~43.
[31] Ravindra Jejurikar, Rajesh K. Gupta. Energy Aware EDF Scheduling with Task Synchronization for Embedded Real Time Systems. CECS TechnicalReport, 2002.
[32] Ajay Dudani, Frank Mueller, Yifan Zhu. Energy conserving feedback EDF scheduling for embedded systems with real-time constraints. LCTES, 2002.
[33] Scott A. Brandt, Scott Banachowski, Caixue Lin. Dynamic Integrated Scheduling of Hard Real-Time Soft Real-Time and Non-Real-Time Processes.IEEE International Real-Time Systems Symposium, 2003.
[34] Scott Banachowski, Timothy Bisson, Scott A. Brandt. Integrating best-effort scheduling into a real-time system. IEEE International Real-Time Systems Symposium, 2004.
[35] Caixue Lin, Tim Kaldewey, Anna Povzner. Diverse soft real-time processing in an integrated system. IEEE International Real-Time Systems Symposium, 2006.
[36] Samarjit Chakraborty, Simon Kunali, Lothar Thiele. Approximate schedulability analysis. IEEE Real-Time Systems Symposium, 2002.
[37] A. Tanenbaum. Operating Systems: Design and Implementation. Prentice-Hall, 2nd edition, 1997.
[38] Zhang Shi-jun, Yu Xin, Yu Shao-hua. A DMA fair algoritm for real-time scheduler. IEEE Future Generation Communication and Networking, 2008.
[39] Hyeonjoong Cho, Member, Binoy Ravindran. Garbage Collector Scheduling in Dynamic Multiprocessor Real-Time Systems. IEEE Parallel and Distributed Systems, 2009.
[40] Momtchil Momtchev, Philippe Marquet. An asymmetric real-time scheduling for Linux. IEEE International Parallel and Distributed Processing Symposium, 2002.
[41] M. J. Bach. The design of the UNIX operating system. Prentice-Hall, 1986.
[42] D. A. Rusling. The Linux Kernel. Linux Documentation Project, 1999.