（计算机系统结构专业论文）嵌入式linux的实时性研究与改进.pdf

c l a s s i f i e di n d e x ： u d c ： ad i s s e r t a t i o nf o rt h ed e g r e eo f m e n g r e s e a r c ha n di m p r o v e m e n to fe m b e d d e d l i n u xr e a l t i m ep e r f o r m a n c e c a n d i d a t e ：j i a n gx i w a n g s u p e r v i s o r ：p r o f z h a n gr u b o a c a d e m i cd e g r e e a p p l i e df o r ：m a s t e ro fe n g i n e e r i n g s p e c i a l i t y ：c o m p u t e rs y s t e ma r c h i t e c t u r e d a t eo fs u b m i s s i o n ：d e c e m b e r , 2 0 0 9 d a t eo f o r a le x a m i n a l i o n ：m a r c h , 2 0 1 0 u n i v e r s i t y ：h a r b i ne n g i n e e r i n gu n i v e r s i t y 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下，由 作者本人独立完成的。有关观点、方法、数据和文献的引用已在 文中指出，并与参考文献相对应。除文中已注明引用的内容外， 本论文不包含任何其他个人或集体已经公开发表的作品成果。对 本文的研究做出重要贡献的个人和集体，均已在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。 作者( 签字) ：督习虹 日期：2 每弓月7 日 哈尔滨工程大学 学位论文授权使用声明 本人完全了解学校保护知识产权的有关规定，即研究生在校 攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈尔滨 工程大学有权保留并向国家有关部门或机构送交论文的复印件。 本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据 库进行检索，可采用影印、缩印或扫描等复制手段保存和汇编本 学位论文，可以公布论文的全部内容。同时本人保证毕业后结合 学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈 尔滨工程大学。涉密学位论文待解密后适用本声明。 本论文心佐授予学位后即可口在授予学位1 2 个月后口解 密后) 由哈尔滨工程大学送交有关部门进行保存、汇编等。 作者( 签字) ：粥翻旺导师( 签字) ：豸昆语少头 日期：2 ，矿每3 月9 日二夕年留月矿日 | 哈尔滨工程大学硕士学位论文 摘要 操作系统是计算机中最重要的组成部分之一，它不仅为用户提供友好的 交互接口，还要合理的组织、分配计算机的硬软件资源，使整个计算机系统 有条不紊的运行。而嵌入式系统领域所使用的操作系统除具备通用操作系统 所必备的功能外，还应具有一定的实时性。随着嵌入式系统研究的深入，嵌 入式操作系统实时性也成为当前的热门研究对象。本文便是以嵌入式系统实 耐性为着眼点，针对l i n u x 操作系统的进程调度进行实时性改造，并将改进 后的操作系统移植到相应的硬件处理平台上。 首先，论文介绍了课题研究的背景与意义，分析了l i n u x 实时性的缺陷， 并对国内外实时l i n u x 改造现状及实时化改造成果进行分析总结。其后，论文 以l i n u x 2 6 2 2 内核版本为依据，分析了2 6 内核的调度机制、调度策略和一些 与调度相关的数据结构。着重对l i n u x 2 6 内核中的经典调度算法o ( 1 ) 算法 和系统自带的三种基本的调度策略进行分析，同时也分析了这三种调度策略在 实时性方面的不足。在此基础之上，本文对实时调度理论中的两个经典算法 r m 调度算法和l s f 调度算法，进行了研究、改进与实现。在分析了r m 算法的可调度性和实现r m 算法的假设条件后，提出了r m 算法实现想法， 并根据该想法对l i n u x 2 6 2 2 内核调度器进行了实时性改造，使l i n u x 2 6 2 2 内 核能更好的调度周期任务。l s f 是基于“裕度”的经典动态优先级调度算法。但 该算法本身存在的“颠簸”的缺陷，这影响了算法的效率。本文在对l s f 算法深 入分析的基础之上针对算法的缺陷进行了改进，提出了基于跃变期的l s f 算 法，并在l i n u x 2 6 2 2 内核中实现了改进后的算法，使改进后的内核具有了动 态实时调度策略。对内核调度器进行修改后，本文又对l i n u x 内核文件和启动 过程进行了详细分析，配置了嵌入式文件系统，对内核裁剪、编译，最终将改 进后的l i n u x 内核移植到工控器开发板上。最后，论文利用流行的内核测试工 具l t t ( l i n u xt r a c et o o l k i t ) 来完成对修改后的l i n u x 内核实时性指标的测试， 并设计了相关实验来说明系统的调度性能的提高。 关键字：嵌入式l i n u x ；进程调度；l s f 算法改进；r m 算法 哈尔滨工程大学硕士学位论文 | 葺i 膏i i i 置| i _ i 皇i 薯i 宣i i 萱i | i 宣| 葺墨i i 一 a b s t r a c t 1 o p e r a t i n gs y s t e m ，a l li m p o r t a n tc o m p o n e n ti nc o m p u t e rs y s t e m , n o to n l y p r o v i d e su s e r sw i t hf r i e n d l ys e r v i c ee n v i r o n m e n tb u ta l s oc o n t r o lt h ec o m p u t e r h a r d w a r e s o f t w a r er e s o u r c e st oo r d e r l yo p e r a t e b u ti nt h ef i e l do fe m b e d d e d s y s t e m , e m b e d d e do p e r a t i n gs y s t e m i s c o m m o n l y w i t hf u n c t i o n so f g e n e r a l - p u r p o s e o p e r a t i n gs y s t e ma sw e l l 鹪w i t hac e r t a i nd e g r e eo fr e a l - t i m e p e r f o r m a n c e r e a l t i m ee m b e d d e do p e r a t i n gs y s t e mh a sb e c o m eah o tr e s e a r c h f i e l d t i f f sp a p e re l a b o r a t e so nt h er e a l - t i m ep e r f o r m a n c eo fe m b e d d e ds y s t e m s a n du s el i n u xo p e r a t i n gs y s t e ma so b j e c tt oa l t e ri t ss c h e d u l e rf o rb e t t e rr e a l - t i m e f i r s t l y , t h i sp a p e ri n t r o d u c e st h eb a c k g r o u n da n ds i g n i f i c a n c eo ft h es t u d y , a n a l y s e st h er e a s o n qf o rr e a l - t i m ed e f e c t so fl i n u x ，s u m m a r i z et h er e s e a r c ho f r e a l - t i m el i n u xa n dm e t h o d sf o rt r a n s p l a n t a t i o no fl i n u xo p e r a t i n gs y s t e m a f t e r , t h ep a p e r st a k ek e r n e lo fl i n u x 2 6 2 2e d i t i o nf o re x a m p l et oi l l u s t r a t es c h e d u l i n g m e c h a n i s m , s c h e d u l i n gp o l i c ya n ds o m ed a t as t r u c t u r es c h e d u l i n g - r e l a t e do f k e r n e lo fl i n u x 2 6e d i t i o n , a n dp l a c ee m p h a s i so na n a l y s i so ft h ec l a s s i cl i n u x 2 6 k e r n e l s c h e d u l i n ga l g o r i t h m 一0 ( 1 ) a l g o r i t h ma n dt h r e eb a s i cs c h e d u l i n g s t r a t e g yc o m i n gw i t ht h es y s t e m a f t e rt h a t ，t h r e es c h e d u l i n gs t r a t e g ys h o r t a g ei n r e a l t i m ew e r eg i v e n b a s e do nt h ea b o v e ，t h ep a p e rs t u d i e st w oc l a s s i c a lr e a l - t i m e s c h e d u l i n ga l g o r i t h m s ( 刚s c h e d u l i n ga l g o r i t h ma n dt h el s fs c h e d u l i n g a l g o r i t h m ) ， s t u d i e st h e s c h e d u l a b i l i t y o fr m a l g o r i t h m a n d g i v e s a s s u m e d c o n d i t i o nf o ra p p l y i n gt h er m a l g o r i t h m t h ei d e ao nh o w t oa p p l yr m a l g o r i t h mi n t ol i n u x 2 6 2 2k e r n e ls c h e d u l e ri sp r o p o s e d a n dp a p e ru s et h i si d e a t oa c h i e v ea l t e r i n gl i n u xk e r n e lf o rb e t t e rr e a l - t i m e a n o t h e rs c h e d u l i n ga l g o r i t h m ( l s f ) b a s e do nt h e ”m a r g i n ”i st h ec l a s s i cd y n a m i cp r i o r i t ys c h e d u l i n ga l g o r i t h m t h i sa l g o r i t h mc o u l dd y n a m i c a l l ya c c o m p l i s hs c h e d u l i n gf o rp r o c e s sa c c o r d i n gt o t h ep r o c e s s m a r g i nv a l u e b u tt h ea l g o r i t h mi t s e l fh a sd e f e c tw h i c ha f f e c tt h e e f f i c i e n c yo ft h ea l g o r i t h m i nt h i sp a p e r , t h es h o r t c o m i n go ft r a d i t i o n a ll s f a l g o r i t h mw a si m p r o v e dt o f o r mn e wl s f a l g o r i t h mw h i c hi sn a m e dt h e ， ， ，l f 哈尔滨工程大学硕士学位论文 j u m p p h a s e b a s e dl s f t h e n , t h en o wl s fa l g o r i t h mi sp u ti n t ot h ek e r n e lo f l i n u x2 6e d i t i o n a f t e rm o d i f i c a t i o i l so ft h ek e m e ls c h e d u l c r , t h ep a p e ra l s o a n a l y z et h ek e r n e lf i l ea n dt h ep r o c e s so f t h el i n u xk e m e lb o o t i n g ，c o n s t r u c taf i l e s y s t e m ，a n dt h e nc o m p l e t et h ew o r ko fc u t t i n ga n dt r a n s p l a n t i n gl i n u xk e r n e l i n t h ee n d ，t h ep a p e ru s ek e r n e lt e s t i n gt o o ll 1 t ( l i n u xt r a c et o o l k i t ) t ot e s tt h e p a r a m e t e r so ft h er e v i s e dl i n u xk e r n e l ，a n dd e s i g ne x p e r i m e n tt o i l l u s t r a t et h e p r o v e m e n to fs y s t e mp e r f o r m a n c e k e y w o r d s ：e m b e d d e dl i n u x ；p r o c e s ss c h e d u l e ；l s fa l g o r i t h m ；r ma l g o r i t h m - 一 哈尔滨工程大学硕士学位论文 目录 第1 章绪论1 1 1 课题研究的背景与意义”l 1 2 本课题相关技术的国内外研究现状”1 1 2 1 实时l i n u x 操作系统的研究现状1 1 2 2l i n u x 操作系统移植研究现状_ 5 1 3 课题所使用到的硬件平台概述”6 + 1 4 论文主要工作和论文组织”7 第2 章l i n u x 2 6 进程调度分析与研究”9 2 1 实现2 6 内核进程调度的基本数据结构9 2 1 1t a s ks t r u c t 结构9 2 1 2s t r u c tr u n q u e q u e 1 0 2 2o ( 1 ) 调度算法1 2 2 3 进程调度的基本过程1 3 2 4l i n u x 的三种调度策略及不足1 4 2 5 本章小结1 5 第3 章实时调度器的设计与实现1 6 3 1r m 算法分析1 6 3 1 1r m 算法及可调度性分析1 6 3 1 2r m 算法应用的约束条件1 8 3 2 基于r m 算法的调度器实现1 9 3 2 1 添加r m 算法的数据结构”1 9 3 2 2r m 调度的设计实现2 0 3 3l s f 算法的分析与改进2 5 3 3 1l s f 算法的不足2 5 3 3 2 基于跃变期的l s f 算法改进2 7 3 4 基于跃变的l s f 算法的调度器设计2 8 3 4 1 基于跃变期的l s f 算法的设计与分析2 8 手 - - l 1 哈尔滨工程大学硕士学位论文 3 4 2 基于跃变期的l s f 算法的实现”31 3 5 本章小结3 6 第4 章l i n u x 操作系统移植3 7 4 1u b o o t 的分析与移植3 7 4 1 1u o b o o t 结构分析。3 7 4 1 2u b o o t 启动过程分析38 4 1 3u b o o t 的结构裁剪与移植3 8 4 2l i n u x 内核裁剪与移植“4 0 4 2 1l i n u x 内核文件目录4 0 4 2 2 内核的启动过程分析4 1 4 2 _ 3 配置文件系统4 2 4 2 4 内核移植实现”4 4 4 3 本章小结5 0 第5 章系统测试5 1 5 1 实时操作系统评价指标5 1 5 2 使用l t t 工具测试5 2 5 2 1l 1 广r 安装5 2 5 2 2 使用l 丌测试”5 4 5 3 测试系统时延5 5 5 4 测试l s f 调度方式5 9 结论。6 2 参考文献6 3 攻读硕士期间发表的论文和取得的科研成果6 7 致 射6 8 哈尔滨t 程大学硕七学位论文 第1 章绪论 1 1 课题研究的背景与意义 嵌入式系统的研究始于上世纪6 0 年代末，经过近四十多年的发展，目前 它已渗透到了军事、工业控制、航天技术、医疗器械、消费电子等诸多领域。 嵌入式技术已经触及到了现代社会的每个角落，它为我们提供了舒适便利的 生活环境，提高了我们的工作效率，加快了社会发展的脚步。由于嵌入式技 术的广泛应用，嵌入式系统已成为计算机领域的热门研究领域。 嵌入式操作系统作为嵌入式系统中核心的部分，在系统中起着相当重要 的作用。目前比较流行的几款嵌入式操作系统有v x w o r k s 、q n x 、p a l m o s 、 w i n d o w sc e 等。它们都是商业性的嵌入式操作系统。使用这些操作系统需 要承担昂贵的费用，并且这些系统的内核源码是不公开的，这些都是阻碍嵌 入式技术普及的问题。l i n u x 作为一款开源、免费、高效的操作系统已经在 众多操作系统中脱颖而出。但由于l i n u x 是一款分时操作系统，它难以满足 嵌入式实时使用环境的需要，因此，开展l i n u x 操作系统的实时性研究具有 重要的应用价值。目前国内外许多科研和应用机构纷纷加入到嵌入式l i n u x 研究的行列中，希望能将l i n u x 改造成为更适合嵌入式环境的操作系统。 本文所研究的“嵌入式l i n u x 的实时性研究与改进”是基于北京某公司 “工业控器的实时l i n u x 操作系统研究”课题的一部分。针对具体的工作环 境，本文完成了基于实时性的调度机改造。为l i n u x 内核添加了完成周期任 务和动态优先级任务调度的两种实时调度策略。并对l i n u x 的操作系统的裁 剪和移植进行了研究，实现了修改后l i n u x 的移植工作。这些研究和工作对 于嵌入式l i n u x 操作系统应用于实时工业控制有着积极的作用和意义。 1 2 本课题相关技术的国内外研究现状 1 2 1 实时l i n u x 操作系统的研究现状 1 l i n u x 实时性分析 随着科学技术的发展，嵌入式也正经历着由低级向高级、由简单向复杂 发展的过程。嵌入式系统硬软件资源也随之庞大，因此系统中需要引入管理 哈尔滨工程大学硕七学何论文 系统资源的软件嵌入式操作系统。通常嵌入式操作系统应具有一定的实 时性，即嵌入式操作系统一般为实时操作系统。实时操作系统r t o s ( r e a l t i m eo p e r a t i o ns y s t e m ) 是指一款能够在特定时间范围内完成相应功能、能对 外部事件作出及时响应的操作系统【l 】。这类操作系统的运行结果不仅与计算 的逻辑关而且还与计算的时间相关。 l i n u x 操作系统自上个世纪9 0 年代问世至今，在短短的十几年时间里以 惊人速度发展。目前它己成为一款功能完善、通用性强的操作系统。l i n u x 操作系统设计完善、性能稳定，并且在它上面运行的软件绝大部分是免费。 l i n u x 操作系统还具有源码开放、安全性高、支持多任务、支持多种体系结 构等特点【2 3 1 。更重要的是l i n u x 操作系统的内核和其上运行的软件可以自由 的修改，这就是l i n u x 倡导的“自由 ，这种“自由才l i n u x 操作系统真正 的优势【4 】。以上所述的这些优秀特性无疑会成为将l i n u x 改造成嵌入式操作 系统的巨大动力。 虽然l i n u x 与许多商业嵌入式操作系统相比有很大的优势，但它也存在 着一些先天的缺陷。l i n u x 并不是针对嵌入式使用环境来设计的。究其本质， 它是一款分时的类u n i x 通用型操作系统 5 】。因此将l i n u x 直接引入到嵌入 式中必将会产生一些“水土不服的问题。在这些问题中，最为突出的就是 实时问题- i i n u x 对实时任务的响应不能达到嵌入式应用需要。以下是对 l i n u x 实时性不足原因的具体分析： ( 1 ) 调度方面：传统的l i n u x 操作系统为了实现系统吞吐率和平均任务 响应周期最小的目的，系统调度通常采用了分时方式来实现。这样做可使进 程公平的使用处理器和其他系统资源，但系统对任务的实时响应的能力便会 下降。虽然较新版本的l i n u x 进行一些实时性改进【6 】，并在调度方面添加了 一些简单的实时调度策略7 1 ，但l i n u x 的实时性始终不是令人满意。 ( 2 ) 时钟机制：时钟机制是计算机系统中主要的组成部分，它为整个系 统提供了时间基准。l i n u x 中的时钟机制是基于硬件时钟来实现的【引。标准 l i n u x 时钟中断周期是1 0 m s ，在对实时性要求严格的环境中，这样大的中断 周期是难以满足实时性的要求的。 ( 3 ) 中断机制：通常l i n u x 在进入中断处理后要关闭中断。因此在这段 时间内即使有非常急迫的实时任务请求，系统也无法对该任务进行响应，只 2 - k - 哈尔滨工程大学硕士学位论文 能等中断处理结束之后再做处理【9 】。这样可能会使一些非常重要的实时任务 因无法及时响应而导致系统严重错误。这也大大减弱了l i n u x 操作系统的实 时性。 ( 4 ) 虚拟内存：为了扩展系统可用内存，l i n u x 采用了虚拟内存技术。 但随之而来的虚拟内存的管理却为系统实时性带来许多实时性问题。并且虚 拟存储技术的引入也增加了进程服务时间的不确定性【1 0 1 。这些问题都是引入 虚拟内存导致的l i n u x 操作系统实时性不高的原因。 2 l i n u x 实时性的改进 为使l i n u x 操作系统具有更好的实时性，许多研究机构和个人就l i n u x 实时性改进问题提出了很有建设性的想法并做了大量工作，同时也取得了相 应的成果。目前，l i n u x 实时改进主要是围绕着两种方法来进行的【l 。以下 是对l i n u x 内核实时性改进的两种方法分析和相应成果介绍： ( 1 ) 双核法： 双核法是指l i n u x 系统中的内核是用两个不同内核来实现的。其中一个 是用来完成实时任务的响应，另一个是用来完成非实时性任务的处理，这两 个内核相互配合实现系统的全部功能。该方法的具体思路是在原有的l i n u x 操作系统内核之下、操作系统的最底层增加一个用于完成实时任务调度的内 核。这个实时内核是用来管理硬件、响应实时任务的。在双核法中，使用l i n u x 动态加载技术，将实时内核作为动态可加载模块添加到原来的系统中 1 z - 1 3 。 这样，便实现了l i n u x 操作系统的实时性改造。当系统内有实时任务请求时， 便采用实时内核进行调度，当系统内的所有实时任务都执行结束后，才将标 准l i n u x 内核作为一个最低优先级的任务来调度。这样既完成了操作系统对 实时任务的响应，同时也保证了标准l i n u x 内核独立性，使系统避免因标准 l i n u x 内核更新而导致对系统大规模的改动。 双核法中，在实时内核中使用了“模拟中断 技术来实现底层硬件的中 断使能【1 4 1 ，使系统不必真正操作中断控制器来完成对非实时内核的开关中断 操作的支持。实时内核始终没有真正关闭硬中断，所以当有更高优先级的实 时进程来到时，便可以抢占处理器运行。在双核法中，还使用了标准l i n u x 中的一些进程通信技术，如进程共享内存、f i f o 等来实现实时进程和非实时 进程的通信。 3 l - 下增加一层所谓的“虚拟 机层【1 7 1 。这一层就是实时内核，用来调度实时任 务和完成底层相关操作。r t l i n u x 的一个设计理念就是尽最大可能保持原有 的l i n u x 内核不被修改，这样可以提高r t l i n u x 其他部分对标准l i n u x 兼容 性。当标准l i n u x 内核内部发生改变时，不需要对r t l i n u x 的其他部分做大 幅度修改。由于r t l i n u x 将标准l i n u x 强大的功能和对硬实时支持进行融合， 目前它以得到了许多学者和机构的认可。 使用双核法改造后的l i n u x 通常能很好满足嵌入式系统的硬实时需求， 但它也存在着一些不足。首先，在实时任务的开发过程中，开发人员不能充 分利用标准l i n u x 开发相关的已成熟技术和资源。实时任务的开发是基于实 时内核的 1 8 】，而不是面向原有的标准l i n u x 内核的。因此在开发过程中，原 有的在标准l i n u x 下比较成熟技术和资源都不能被充分利用。其次，实时进 程会引起了内存安全问题。实时进程是运行在系统的核心层，而在核心层没 有内存保护功能。因此，当有实时任务发生错误时，很有可能会引起系统的 严重问题1 9 1 。 ( 2 ) 直接修改内核法： 所谓直接修改法就是直接修改内核源代码来改进标准l i n u x 内核的不 足。为了提高l i n u x 内核的实时性，可将一些成熟的实时方法、理念引入到 l i n u x 内核中，根据这些方法和理念直接针对l i n u x 内核的进程调度、内存管 理、中断处理的不足进行修改【2 0 1 。 在进程调度方面的改进主要集中在修改标准l i n u x 内核调度器上。可以 通过修改调度器来减小操作系统的调度时延，提高l i n u x 的实时性能，从而 达到软实时标准的要求 2 l 】。为了实现这一目的，可以重新为l i n u x 内核设计 和编写一个实时调度器。但这样做可能会破坏掉原有系统的一些特性，并且 重头设计、编写调度器的工作量也是十分大的。当然，完全重写调度器也不 是必要的，也可以修改标准l i n u x 内核调度器，添加一些实时调度策略，如 基于优先级、基于时间驱动、基于比例共享的调度策略等 2 2 2 4 1 。这样调度器 便可以根据任务的实时性来为任务选择相应的调度策略。本课题正是将静态 4 哈尔滨工程大学硕士学位论文 优先级r m 算法和改进后的动态优先级l s f 算法添加到标准l i n u x 内核中改 进l i n u x 的实时性。 在中断处理方面可以采用中断线程化 2 5 】、增加可抢占点 2 6 1 、中断模拟【2 7 】 等方法来改进标准l i n u x 内核中断实时性的不足。对于l i n u x 内核的时钟粒 度大的问题，可以通过将时钟设置为单次触发状态，这样处理器的时钟精度 便会有很大的提高。为了实现增强系统的可抢占性，可以在系统调用函数中 增加抢占点【z 引。 直接修改内核法来增强实时性已经有了很广泛应用，其中m o n t a v i s t a l i n u x 和k u r t 就是使用这种方法较为成功的案例 2 9 1 。其中m o n t a v i s t al i n u x 是由m o n t a v i s t a 公司对标准l i n u x 内核进行修改后推出的一款嵌入式实时操 作系统。针对嵌入式应用环境需要，m o n t a v i s t a 对原有的l i n u x 内核进行了 大量的裁剪工作，并修改了内核调度器，使内核支持基于优先级驱动的实时 调度方式。在可抢占性方面，m o n t a v i s t al i n u x 使用了标准的l i n u x 多处理器 版本，并在此基础上进行了修改，从而内核具有了更好的抢占性。k u r t 是 由k a n s a s 大学开发的实时l i n u x 操作系统。它主要是通过修改系统的时钟机 制，将时钟芯片设置为单次触发状态提高了系统的时钟精度。同时k u r t 也 针对进程的调度等方面做了一些有益的改进。k u r t 将系统分为常态、实时 态、混合态三种状态。在常态下内核使用标准内核调度策略，在实时态下内 核将使用实时调度策略，而在混合态下既可以实现实时任务的调度也可以实 现非实时任务调度。 直接修改内核法就是对标准l i n u x 内核进行相应修改写，这样做可以相 对减小系统开发的工作量，但这种方法也存在着不足。使用这种方法进行开 发，首先要求开发的人员精通l i n u x 内核，只有对l i n u x 内核完全了解的后 才能对内核进行修改，否则可能会发生“牵一发动全身的”错误。再有就是 由于标准l i n u x 的一些固有原因，使得改进后的l i n u x 很难达到硬实时标准。 1 2 2l i n u x 操作系统移植研究现状 嵌入式设备硬件资源有限，因此对软件的体积要求就比较苛刻【3 0 1 。标准 l i n u x 体积庞大，不适合在嵌入式系统中应用【3 1 1 。这些问题都是影响l i n u x 内核可移植性的问题。l i n u x 又采用各个部分紧密相关的单内核结构，并且 5 h 哈尔滨工程大学硕士学位论文 为了实现系统的高效的目的，根据具体硬件对内核进行了优化。这样更进一 步减弱了内核的可移植性。但l i n u x 内核使的分层结构、面向对象、可加载 模块等技术化解了以上这些内核可移植性不强的缺点。采用分层结构引入了 硬件抽象层h a l 3 2 】，使得硬件和操作系统分离，增强了操作系统的独立性， 这样便提高了l i n u x 的可移植性。而采用面向对象思想将内核的一些操作封 装在结构体中【3 3 1 ，这样可使内核结构变的更清晰，同时也提高内核代码的内 聚，最终实现提高内核可移植性。采用可加载技术使内核独立于具体的硬件 结构，同时也减少了反复编译内核的工作，也提高了内核的可移植性。 在经历的十几年的发展后，l i n u x 内核已经成功移植到许多硬件平台上。 但仍有一些不能直接运行l i n u x ，为了使这些硬件平台上能支持l i n u x ，需要 进行l i n u x 内核进行移植工作。目前，实现内核移植是通过从头设计和修改 现有代码两种方式来实现的 3 4 1 。从头设计就是针对新的硬件进行l i n u x 内核 代码添加工作。它是根据硬件特点采用“自底向上的方法，逐步将l i n u x 内核移植到新的硬件平台上。而修改现有代码是指参考相近的硬件结构，根 据目标平台硬件特点修改原有内核代码，实现l i n u x 内核移植。 1 3 课题所使用到的硬件平台概述 本文采用a r m 9 系列处理器。a r m 9 系列处理器是基于哈佛体系结构来 设计实现的，既采用指令与数据分别来储存技术【3 5 娟】。a r m 9 系列存储器中 具有独立的指令和数据存储器接口，因此处理器具有较高并行处理读取指令 和读写数据的能力。另外a m 9 采用5 级流水、独立的存储器和写回流水线 等技术，分别来实现访问存储器和将结果写回寄存器功能。 论文中所使用的工控目标板可分为核心和底板两个部分，核心板上集成 了s a m s u n g s 3 c 2 4 1 0 a 处理器、s d ra m 内存、板载6 4 m b s d r a m 、3 2 b i t 数 据总线、f l a s h 存储器、板载6 4 m bn a n df l a s h 、板载2 m bn o rf l a s h 和关键的 芯片。底板上主要是外围接口电路。 核心板上的处理器是采用三星公司生产的$ 3 c 2 4 1 0 ，它是一款基于 a r m 9 2 0 t 核的精简指令处理器，其运行频率为2 0 3 m h z 。 $ 3 c 2 4 1 0 a 除了拥有a r m 9 2 0 t 核之外，其上还集成了两个协处理器分别 用调试控制、系统存储系统控制、测试控制。 6 哈尔滨丁程大学硕十学1 = 7 ：论文 1 4 论文主要工作和论文组织 ( 1 ) 论文工作 首先论文介绍了课题研究的背景与意义，分析了l i n u x 实时性的缺陷， 并对国内外实时l i n u x 改造现状及实时化改造成果进行分析总结。其后针对 l i n u x 2 6 2 2 内核的调度机制、调度策略、一些与调度相关度的数据结构进 行了研究。着重分析了l i n u x 2 6 内核中的经典调度算法( o ( 1 ) 算法) 和系统自 带的三种基本的调度策略，并给出了这三种调度策略在实时性方面的不足。 在以上工作基础之上，文章对实时调度理论中的两个经典算法一r m 调 度算法和l s f 调度算法进行研究和实现。首先对r m 算法的可调度性及实现 r m 算法的假设条件进行分析。之后，给出了r m 算法实现方法并依据该方 法对l i n u x 2 6 2 2 内核的调度器进行实时性改造。l s f 调度算法是基于动态优 先级的最小裕度调度算法。l s f 算法本身存在“颠簸 的缺陷。文章对传统 的l s f 算法的缺陷进行了改进，提出了基于跃变期的l s f 算法，并根据改进 后的算法针对l i n u x 2 6 2 2 内核调度器进行实现。对内核调度器修改后，本文 又对l i n u x 内核文件和启动过程进行分析，为内核配置文件系统，并完成内 核裁剪和移植工作。论文最后利用目前比较流行的内核测试工具l t t ( l i n u x t r a c et o o l l d 0 来实现修改后的l i n u x 内核的实时性参数测试。 ( 2 ) 论文的各章安排： 第一章绪论 介绍了课题的研究背景及意义。分析了l i n u x 实时性不高的原因，对国 内外实时l i n u x 研究情况进行分析总结。并介绍了课题涉及的硬件平台和论 文的主要工作。 第二章l i n u x 2 6 进程调度分析研究 分析了实现l i n u x 2 6 内核实时性改进的重要数据结构t a s ks t r c u t 、s t r e e t m n q u e q u e 和优先级数组p r i oa r r a y 。在此基础上研究了 内核的经t l i n u x 26 典o ( 1 ) 调度算法和系统默认的三种基本的调度策略，最后分析了这三种调度 策略的实时性的不足。 第三章实时调度器的设计与实现 7 哈尔滨工程大学硕士学位论文 分析了经典的r m 算法，研究了r m 算法的应用条件。并以r m 算法为 基础对l i n u x 2 6 内核进行修改，实现内核对周期任务的调度。 针对基于动态优先级的l s f 算法进行研究，对算法提出了改进，提出了 基于跃变期的l s f 算法，最后根据基于跃变期的l s f 算法对l i n u x 内核进行 改进，实现l i n u x 内核对动态优先级任务的支持。 第四章操作系统移植 分析u b o o t 工作原理和启动过程，实现u b o o t 的命令的裁剪，并将修 改后的u - b o o t 源代码编译为可执行文件，并将该文件写入到目标板上。在移 植u - b o o t 后，本文分析了l i n u x 内核的启动过程，完成了嵌入式文件系统的 配置，并对l i n u x 内核进行裁剪、编译，最终实现l i n u x 操作系统的移植。 第五章 在完成将修改后的l i n u x 内核加载到开发板之后，将对修改后的l i n u x 内核进行测试，来验证修改调度器后的内核在实时性和动态调度性。 8 哈尔滨工程大学硕十学位论文 第2 章l i n u x 2 6 进程调度分析与研究 l i n u x 是多任务多用户的分时操作系统，因此在l i n u x 系统中进程调度便 成为内核的主要责任之一【3 7 。3 8 1 。在内核中，进程的调度是由内核的进程调度 器来实现的。调度器主要负责合理的分配c p u 资源，确定进程调度的时机， 怎样选取一个合适的进程作为后备进程。本章针对l i n u x 2 6 2 2 内核的进程调 度进行研究，详细介绍实现l i n u x 2 6 内核进程调度的基本数据结构和o ( 1 ) 调 度程序的基本原理，最后进一步分析2 6 内核的三种调度策略和及其不足。 2 1 实现2 6 内核进程调度的基本数据结构 l i n u x 2 6 内核的调度方式在2 4 版本的基础之上发生了很大的变化。为 了实现这些变化，l i n u x 2 6 内核中修改了一些老版本中的数据结构并新增加 一些数据结构以支持高效调度算法。本节将对2 6 版本中进程调度所涉及到 的一些关键数据结构做详细的剖析。 2 1 1t a s ks t r u c t 结构 t a s ks t r u c t 是在文件k e r n e l i n c l u d e l i n u x s c h e d h 中定义的。t a s ks t r u c t 结构就是通常所说的“p c b ”进程控制块。它是用来标示进程和记录进 程的动态信息结构体。当有进程产生或者销毁时相应的便会产生或销毁一个 t a s ks t r u c t 结构体。t a s ks t r u c t 不但是l i n u x 操作系统标识，而且也是进程调 度和其他进程操作的基础。 随着2 6 版本调度方式的改进，t a s ks t r u c t 结构也有相应改变。在结构体 中不但新增了一些属性，而且一些已有的属性的含义也发生了改变，也有些 属性只是在2 6 中改了名字。以下为t a s ks t r u c t 中的一些和进程调度相关的 属性及其作用： l 、t h r e a di n f o ：当进程在创建时，每个进程都会得到两个连续的物理 块，顶部的物理块用来存放t a s ks t r u c t 中的t h r e a di n f o 结构体，而其余的信 息都存放在栈外。需要用到t a s ks t r u c t 结构体时，可以用t h r e a di n f o 中的t a s k 属性找到实际t a s ks t r u c t 结构。 2 、p r i o ：p r i