嵌入式操作系统的设计与实现
|
摘要
嵌入式实时操作系统是嵌入式系统的基础软件平台,它必须具有实时性好,稳定性高,可移植性强,通用性好并且针对具体的应用可裁减可配置的特点。本论文的研究工作在于设计并实现一个高性能的嵌入式实时操作系统——Skernel。
本论文在研究嵌入式操作系统设计理论的基础上,分析了具体的设计问题,并根据嵌入式系统应用的特点,提出了一个相比同类嵌入式操作系统较优的内核设计方案:基于微内核构架,实时性好,系统服务完备,支持多达256个任务,支持多处理器,兼容标准操作系统调用接口规范,可裁减可配置。在设计过程中,引入了面向对象的思想,内核中的许多模块被看作同一个对象——事件,这使得内核的抽象程度更好,结构更清晰。
为了验证Skernel的实际运行特性,本论文在FPGA平台上构建了准对称NiosⅡ双核系统,并对多核处理器启动、处理器间通讯、互斥等方面的问题进行了探索和研究。
在Skernel的实现过程中,对Bitmap算法进行了改进和优化,使得Skernel支持的任务数达到了256个,但却没有增加系统开销,也不影响系统调度的实时性;引入了老化算法,解决了优先级调度中的饥饿问题;使用优先级天花板策略解决了优先级反转问题,而这些问题是现今大多数嵌入式操作系统所没有解决的。经过裁减,Skernel的最小代码量(32位处理器)不到3.5KB,这在同类操作系统中算是非常小的。另外,Skernel的中断处理器方式简单高效,使得Skernel的中断响应时间在微秒级,这表明Skernel的实时性在同类操作系统中是非常好的。
最后,Skernel成功的移植到NiosⅡ处理器上,并在NiosⅡ上实现了非对称多处理的任务调度,实现了预期的设计构想。
The Embedded Real-Time Operating System (RTOS) is the most important basic software platform for the embedded system, which has such typical characteristics as deterministic performance, high stability, portability, scalability and configurability. The thesis presents the design and implementation of an RTOS—Skernel.After analyzing some design problems and the requirements of embedded sytem application, a scheme of Skernel has been proposed, which is better than most of RTOS kernels. In the design, Skernel is based on the micro kernel architecture, adopts preemptive priority based scheduling algorithm, supports up to 256 tasks, has complete system services, supports multiprocessor system, TRON and POSIX compatible, scalable and portable.Object-Oriented method has been introduced in the process of designing Skernel. Most modules of Skernel are viewed as a common object Event, so that it simplies the complex relations among Skernel's modules.A quasi symmetric dual NiosII core system has been built on the FPGA experiment system in order to supply a platform for Skernel running and testing. Some researches on the multiprocessor system have been done as well, including how to start up a multiprocessor system, how to do the communication among multiprocessors and mutual exclusion in the multiprocessor enrionment.In the process of developing Skernel, the bitmap algorithm has been improved and optimized to meet the requirements of application, so Skernel can support 256 tasks without loss of the performance. Aging algorithm was designed and implemented for solving the starvation problem which the most RTOSs have not solved. Priority ceiling policy is applied to solve the priority inversion problem.The minimum code size of Skernel is as few as 3.5KB, if only allowed the basic multi-tasking function, so Skernel is suitable for the memory limited application. In addition, the interrupt handling mechanism of Skemel is so simple and efficient that the interrupt handling latency is in the micro second level. In other words, Skernel has a good real-time characteristic.At last, Skernel has been ported to NiosII uniprocessor and dual-core system separately, and asymmetric task scheduling is implemented too.The goal of this thesis has been achieved.
本论文在研究嵌入式操作系统设计理论的基础上,分析了具体的设计问题,并根据嵌入式系统应用的特点,提出了一个相比同类嵌入式操作系统较优的内核设计方案:基于微内核构架,实时性好,系统服务完备,支持多达256个任务,支持多处理器,兼容标准操作系统调用接口规范,可裁减可配置。在设计过程中,引入了面向对象的思想,内核中的许多模块被看作同一个对象——事件,这使得内核的抽象程度更好,结构更清晰。
为了验证Skernel的实际运行特性,本论文在FPGA平台上构建了准对称NiosⅡ双核系统,并对多核处理器启动、处理器间通讯、互斥等方面的问题进行了探索和研究。
在Skernel的实现过程中,对Bitmap算法进行了改进和优化,使得Skernel支持的任务数达到了256个,但却没有增加系统开销,也不影响系统调度的实时性;引入了老化算法,解决了优先级调度中的饥饿问题;使用优先级天花板策略解决了优先级反转问题,而这些问题是现今大多数嵌入式操作系统所没有解决的。经过裁减,Skernel的最小代码量(32位处理器)不到3.5KB,这在同类操作系统中算是非常小的。另外,Skernel的中断处理器方式简单高效,使得Skernel的中断响应时间在微秒级,这表明Skernel的实时性在同类操作系统中是非常好的。
最后,Skernel成功的移植到NiosⅡ处理器上,并在NiosⅡ上实现了非对称多处理的任务调度,实现了预期的设计构想。
The Embedded Real-Time Operating System (RTOS) is the most important basic software platform for the embedded system, which has such typical characteristics as deterministic performance, high stability, portability, scalability and configurability. The thesis presents the design and implementation of an RTOS—Skernel.After analyzing some design problems and the requirements of embedded sytem application, a scheme of Skernel has been proposed, which is better than most of RTOS kernels. In the design, Skernel is based on the micro kernel architecture, adopts preemptive priority based scheduling algorithm, supports up to 256 tasks, has complete system services, supports multiprocessor system, TRON and POSIX compatible, scalable and portable.Object-Oriented method has been introduced in the process of designing Skernel. Most modules of Skernel are viewed as a common object Event, so that it simplies the complex relations among Skernel's modules.A quasi symmetric dual NiosII core system has been built on the FPGA experiment system in order to supply a platform for Skernel running and testing. Some researches on the multiprocessor system have been done as well, including how to start up a multiprocessor system, how to do the communication among multiprocessors and mutual exclusion in the multiprocessor enrionment.In the process of developing Skernel, the bitmap algorithm has been improved and optimized to meet the requirements of application, so Skernel can support 256 tasks without loss of the performance. Aging algorithm was designed and implemented for solving the starvation problem which the most RTOSs have not solved. Priority ceiling policy is applied to solve the priority inversion problem.The minimum code size of Skernel is as few as 3.5KB, if only allowed the basic multi-tasking function, so Skernel is suitable for the memory limited application. In addition, the interrupt handling mechanism of Skemel is so simple and efficient that the interrupt handling latency is in the micro second level. In other words, Skernel has a good real-time characteristic.At last, Skernel has been ported to NiosII uniprocessor and dual-core system separately, and asymmetric task scheduling is implemented too.The goal of this thesis has been achieved.
引文
[1] "Ubiquitous computing", http://sandbox.xerox.com/ubicomp/
[2] Abraham Silberschatz, Peter Baer Calvin, Greg Gagne, "Operating System Concepts (Sixth Edition)", Higher Education Press, 2002
[3] Andrew S.Tanenbaum,“Modern Operating Systems(Second Edition)”,机械工业出版社,2002
[4] Liedtke, J. "Toword Real MicroKernels", Communications of the ACM, September 1996
[5] William Stallings,“Operating Systems Internals and Design Principles(Fourth Edition)”,电子工业出版社 2005
[6] David B. Stewart, "Intruduction to real time", www.embedded.com
[7] ITRON Committee, "μITRON Specification V4.00", www.assoc.tron.org
[8] IEEE "POSIX Standard" http://standards.ieee.org/regauth/posix/
[9] C.L.Liu, J.W.,Layland, "Scheduling Algorithms for Multiprogramming in a Hard Real-Time Environment", Journal of the Association for Computing Machinery, 1973.
[10] Ken Frazer, "Scheduling Algorithms for Real-Time Operating Systems", 2003.4
[11] "IEEE Standard for information Technology—Portable Operating System Interface Part Ⅰ: System Application Program Interface."
[12] Neeraj Suri, "Synchronization Issues in Real-Time Systems", Proceedings of the IEEE, Vol1. 82, Jan 1994
[13] Brain.W.Kemigllan,Dermis.M.Richie,“The C Programming Language 2nd”(影印版),清华大学出版社,2000
[14] Randal E.Bryant,David O'Hallaron著,龚奕利,雷迎春译《深入理解计算机系统(修订版)》,中国电力出版社,2004
[15] Edsger Dijkstra, "Co-operating Sequential Processes", in Programming Languages, Genuys, Academic Press, 1965
[16] Edward Lamio著,张炯等译,“Real-time Embedded Multithreading:Using ThreadX and ARM”,北京航空航天大学出版社,2006
[17] Jean J.Labrosse著,邵贝贝等译,《嵌入式实时操作系统μC/OS-Ⅱ(第2 版)》,北京航天航空大学出版社,2003
[18] "How to write reentrant safe code" http://www.unet.univie.ac.at/aixdaixprggd/genprogc/writing reentrant thread safe code.htm
[19] Coffman, Elphick and Shoshani, "System Deadlocks", Computing Surveys, vol.3, June 1971
[20] Michael Barr, "Introduction to Priority inversion", Embedded system design, Jun 2004
[21] Lui Sha, Ragunathan Rajkumar, John P. Lehoczky, "Priority Inheritance Protocols: An Approach to Real-Time Synchronization", IEEE Transactions on computers, vol 39, Sept, 1990
[22] Goodenough and L. Sha, "The priority ceiling protocol: A method for minimizing the blocking of high priority Ada tasks". Workshop Real-Time Aria Issues, 1988.
[23] Curt Schimmel著,张辉译,《现代体系结构上的UNIX系统——内核程序员的SMP和Caching技术》,人民邮电出版社,2003年4月
[24] John Coodacre,《理解嵌入式多重处理技术的选择》,Information Quarterly中文版 2004年秋第一期
[25] "MultiProcessor Specification version 1.4", Intel Corporation, May 1997
[26] John Coodacre, Andrew N.Sloss, "Parallelism and the ARM Instruction Set Architecture", Computer Archive Volume 38, July 2005
[27] "Nios Ⅱ Processor Reference Handbook", Altera Corporation, May 2005
[28] Andrew N.Sloss等著,沈建华译,《ARM嵌入式系统开发——软件设计与优化》,北京航空航天大学出版社
[29] Kirk Zurell著,艾克武等译,“嵌入式系统的C程序设计”,机械工业出版社
[30] "Creating Multiprocessor NiosⅡ System Tutorial", Altera Corporation, April 2005
[31] "Altera Embedded Peripherals Handbook", Altera Corporation, May 2005
[32] Roger S.Pressman, Software Engineering: A Practitioner's Approach, Sixth Edition, McGraw-Hill, 2004
[2] Abraham Silberschatz, Peter Baer Calvin, Greg Gagne, "Operating System Concepts (Sixth Edition)", Higher Education Press, 2002
[3] Andrew S.Tanenbaum,“Modern Operating Systems(Second Edition)”,机械工业出版社,2002
[4] Liedtke, J. "Toword Real MicroKernels", Communications of the ACM, September 1996
[5] William Stallings,“Operating Systems Internals and Design Principles(Fourth Edition)”,电子工业出版社 2005
[6] David B. Stewart, "Intruduction to real time", www.embedded.com
[7] ITRON Committee, "μITRON Specification V4.00", www.assoc.tron.org
[8] IEEE "POSIX Standard" http://standards.ieee.org/regauth/posix/
[9] C.L.Liu, J.W.,Layland, "Scheduling Algorithms for Multiprogramming in a Hard Real-Time Environment", Journal of the Association for Computing Machinery, 1973.
[10] Ken Frazer, "Scheduling Algorithms for Real-Time Operating Systems", 2003.4
[11] "IEEE Standard for information Technology—Portable Operating System Interface Part Ⅰ: System Application Program Interface."
[12] Neeraj Suri, "Synchronization Issues in Real-Time Systems", Proceedings of the IEEE, Vol1. 82, Jan 1994
[13] Brain.W.Kemigllan,Dermis.M.Richie,“The C Programming Language 2nd”(影印版),清华大学出版社,2000
[14] Randal E.Bryant,David O'Hallaron著,龚奕利,雷迎春译《深入理解计算机系统(修订版)》,中国电力出版社,2004
[15] Edsger Dijkstra, "Co-operating Sequential Processes", in Programming Languages, Genuys, Academic Press, 1965
[16] Edward Lamio著,张炯等译,“Real-time Embedded Multithreading:Using ThreadX and ARM”,北京航空航天大学出版社,2006
[17] Jean J.Labrosse著,邵贝贝等译,《嵌入式实时操作系统μC/OS-Ⅱ(第2 版)》,北京航天航空大学出版社,2003
[18] "How to write reentrant safe code" http://www.unet.univie.ac.at/aixdaixprggd/genprogc/writing reentrant thread safe code.htm
[19] Coffman, Elphick and Shoshani, "System Deadlocks", Computing Surveys, vol.3, June 1971
[20] Michael Barr, "Introduction to Priority inversion", Embedded system design, Jun 2004
[21] Lui Sha, Ragunathan Rajkumar, John P. Lehoczky, "Priority Inheritance Protocols: An Approach to Real-Time Synchronization", IEEE Transactions on computers, vol 39, Sept, 1990
[22] Goodenough and L. Sha, "The priority ceiling protocol: A method for minimizing the blocking of high priority Ada tasks". Workshop Real-Time Aria Issues, 1988.
[23] Curt Schimmel著,张辉译,《现代体系结构上的UNIX系统——内核程序员的SMP和Caching技术》,人民邮电出版社,2003年4月
[24] John Coodacre,《理解嵌入式多重处理技术的选择》,Information Quarterly中文版 2004年秋第一期
[25] "MultiProcessor Specification version 1.4", Intel Corporation, May 1997
[26] John Coodacre, Andrew N.Sloss, "Parallelism and the ARM Instruction Set Architecture", Computer Archive Volume 38, July 2005
[27] "Nios Ⅱ Processor Reference Handbook", Altera Corporation, May 2005
[28] Andrew N.Sloss等著,沈建华译,《ARM嵌入式系统开发——软件设计与优化》,北京航空航天大学出版社
[29] Kirk Zurell著,艾克武等译,“嵌入式系统的C程序设计”,机械工业出版社
[30] "Creating Multiprocessor NiosⅡ System Tutorial", Altera Corporation, April 2005
[31] "Altera Embedded Peripherals Handbook", Altera Corporation, May 2005
[32] Roger S.Pressman, Software Engineering: A Practitioner's Approach, Sixth Edition, McGraw-Hill, 2004