（计算机应用技术专业论文）嵌入式linux实时性分析与改造研究.pdf

华中科技大学硕士学位论文 摘要 f 随着以计算机技术、通讯技术为主的信息技术的快速发展和互联网的 广泛应用，计算机的发展已显示出微型化和专业化的趋势，嵌入式系统将 在这一时期大显身手，而利用l i n u x 搭建嵌入式操作系统则是近年来出现 的最令人振奋的方案。y 7 f 实时性是嵌入式操作系统的基本要求。l i n u x 作为一种通用的操作系 统，。在某些方面还不适合作为嵌入式操作系统的需要。在详细分析l i n u x 内核源代码的基础上，对其采用的进程调度机制进行了研究，指出该调度 机制在实时处理上存在一定的缺陷，主要表现为：在调度算法中，采用了 对可运行队列进行线性搜索的方法来选择下一调度进程，造成了调度时间 上的不确定性：在调度方式上，不允许在内核空间中对进程进行抢占式调 度，造成了一定的调度延迟。 针对这些不足馒出并实现了一种基于优先级的抢占式调度机制。首 先，该机制采用了一种基于优先级排序的进程调度器p o s c h e d u l e r ，该调 度器在保持了l i n u x 现有调度器一切优良特性的基础之上，还具有以下一 些优点：使用了复杂度为o ( 1 ) 的调度算法，保证了调度时间的确定性：强 调了紧迫任务对响应时间的要求，使系统具有更好的响应能力；使用了更 合理的数据结构，在实现上更加简洁。其次，该调度机制采用了抢占式的 调度方式，利用在内核中插入可抢占点的方法，将m n u x 改造成内核可抢 占的；并对s m p 版本中的s p i n l o c k 机制进行改进，从而方便地对可抢占点 进行设置。新的调度方式允许系统在内核状态下对进程进行抢占调度，从 而减少了调度延迟的产生。通过上述这种调度机制，使得l i n u x 具有一定 程度的软实时特性，从而满足其作为嵌入式操作系统的需要。 基于优先级的抢占式调度机制已成功应用于同深圳泛友科技有限公司 合作开发的j i n u x 嵌入式操作系统之中，该系统已通过国家有关部门鉴定， 具有良好的市场前景。 关键词：l i n u x ：嵌入式操作系统：实时性：进程调度 华中科技大学硕士学位论文 a b s t r a c t w i t ht h ed e v e l o p m e n to ft h ec o m p u t e r & c o m m u n i c a t i o nt e c h n o l o g y ，a l s o t h eb r o a du s eo fi n t e r n e t ，c o m p u t e rt e n d st om i e r o m a t i o na n ds p e c i a l i z a t i o n t h ee m b e d d e ds y s t e mw i l ls t r u ti t ss t u f ft h i sp e r i o d ，a n du s i n gl i n u x t ob u i l d ! e m b e d d e d o p e r a t i n gs y s t e mi st h em o s ti n s p i r i n gt h i n g ， r e a l t i m e c a p a b i l i t i e s i st h eb a s er e q u i r e m e n to fa ne m b e d d e do s ，b u t 。 l i n u xh a ss o m es h o r t c o m i n g si nb e i n ga ne m b e d d e do p e r a t i n gs y s t e ma s a g e n e r a lp u r p o s e o s a f t e ra n a l y z i n gt h o r o u g h l yt h ek e r n e l s o u r c ec o d e ， e s p e c i a l l y t h e p r o c e s ss c h e d u l i n gm e c h a n i s m ，t h ep a p e rp o i n t s o u tt h i s m e c h a n i s mh a ss o m ed e f i c i e n c yw h e nh a n d l i n gr e a l - t i m et a s k s ：o n ei s i t a d o p t s al i n e a r s e a r c h i n ga l g o r i t h m w h e ns c h e d u l i n g ，w h i c hw i l lm a k e s c h e d u l i n gt i m eu n p r e d i c t a b l e ；t h e o t h e ri si td o e sn o tp e r m i tp r e e m p t i v e s c h e d u l i n gi nk e r n e lm o d e ，w h i c h w i l lr e s u l ti ns c h e d u l i n gl a t e n c y a i m i n g a tt h e s e p r o b l e m s ，t h ep a p e rb r i n g s f o r w a r da p r e e m p t i v e s c h e d u l i n gm e c h a n i s mb a s e do np r i o r i t y f i r s t l y ，i t u s e sap r i o r i t yo r d e r e d s c h e d u l e rp o - s c h e d u l e r t h i ss c h e d u l e r k e e p s a l lt h e g o o dt h i n g s o ft h e c u r r e n ts c h e d u l i n gm e c h a n i s m a n da l s oh a ss o m ee x t r ac h a r a c t e r i s t i c s ：u s i n g a no ( 1 ) c o m p l e x i t ya l g o r i t h mt os c h e d u l et a s k sw h i c hk e e p st h es c h e d u l i n g t i m e c o n s t a n t ；e m p h a s i z i n g t h et i m e r e q u i r e m e n t o f u r g e n t t a s k sw h i c h p r o v i d e ss y s t e m ab e t t e r r e s p o n s ec a p a b i l i t y ；m a k i n g u s eo fab e t t e rd a t a s t r u c t u r ew h i c hl e a d st oac o n c i s e r e a l i z a t i o n s e c o n d l y ，i ta d o p t s a p r e e m p t i v es c h e d u l i n gm a n n e r ，w h i c hm a k e sl i n u xk e r n e lp r e e m p t i v eb yt h e w a y o f i n s e r t i n gp r e e m p t i v ep o i n t i ta l s om o d i f i e st h es p i n l o c km e c h a n i s m o f s m pv e r s i o nt o s e t u pt h ep r e e m p t i v ep o i n t sc o n v e n i e n t l y ，t h u sr e d u c e st h e o c c u r r e n c eo fs c h e d u l i n g l a t e n c y b ya d o p t i n g t h e s c h e d u l i n gm e c h a n i s m m e n t i o n e da b o v e ，l i n u xc a nh a v eas o f tr e a l t i m e c a p a b i l i t y a n dm e e tt h e d e m a n d so fb e i n ga ne m b e d d e d o p e r a t i n gs y s t e m t h en e ws c h e d u l i n gm e c h a n i s mh a sb e e ns u c c e s s f u l l yu s e di nt h ej i n u x s y s t e mw h i c hi sd e v e l o p e db yt h e s h e n z h e nf a n y o ut e c h n o l o g yc o l t d j i n u xh a sp a s s e dt h ea u t h e n t i c a t i o na n dh a san i c e rm a r k e tf o r e g r o u n d k e yw o r d s ：l i n u x ； e m b e d d e do s ；r e a l t i m e ；p r o c e s ss c h e d u l i n g i i 华中科技大学硕士学位论文 1 绪论 1 1l i n u x 概述 1 1 1l i f l u x 的历史 出于教学的需要，荷兰教授a n d r e ws t a n e n b 搬编写了个小型的类u n i x 操 作系统m i n i x 1 - 3 j ，它可以在p c 机上运行，但是缺乏实用价值。看到m i n i x 的这种 缺点，芬兰大学生l i n u st o r v a l d s 决定在自己的p c 机上，以m i n i x 为起点，按照 u n i x 的设计，开发出一个真正可以实用的u n i x 内核，并将其命名为l i n u x t 2 - 4 。l i n u s t o r v a l d s 的一个最重要的决定就是将其基本完成的第一个l i n u x 内核版本放在了互 联网上，一来把自己写的代码公诸于众，二来邀请有兴趣的人参与。他的这种做法 很快就引起了热烈的反应，并且与美国“自由软件基金会”f s f 3 主张的开放源代 码不谋而合。l i n u x 的出现使得由l i n u st o r v a i d s 主持的l i n u x 内核开发、改进和维 护成为了f s f 的主要项目之一。另外，f s f 的其它项目，如g n u 的c 编译器g c c 、 程序调试工具g d b 、还有各种s h e l l 和应用程序，乃至w e b 服务器a p a c h e 、浏览器 m o z i l l a ( 实际上就是n e t s c a p e ) 等等，则正好与之配套成龙。正是在这种开发模式 和开发环境下，l i n u x 逐渐发展和壮大起来，已经成为了i t 市场的主要动力。 1 1 2 l i n u x 的特点 l i n u x 的特点主要有以下几点 i - 4 ： ( 1 ) 良好的开放性。l i n u x 是一个免费的、开放源码的操作系统，用户可以按自 己的要求修改源码，并进行发布，只要遵守g p l 中的规定即可。 ( 2 ) 多平台支持。l i n u x 最初是在i n t e l8 0 3 8 6 平台上实现的，但是已经被移植到 各种主要的c p u 系列上，包括a l p h a 、m 6 8 k 、m i p s 、s p a r c 、p o w e rp c 等等。同时，在同一个系列的c p u 上，l i n u x 内核既支持常规的单c p u 结 构，也支持多c p u 结构。 ( 3 ) 符合国际通用标准。l i n u x 是符合p o s i x l 0 0 3 1 标准的操作系统。 p o s 1 0 0 3 1 标准定义了一个最小的u n i x 操作系统接口，因此许多u n i x 应用程序不需要修改就可以直接运行在l i n u x 上。 ( 4 ) 拥有先进的网络特性。l i n u x 对网络的支持比大部分操作系统都更出色，它 几乎支持目前所有的网络协议，而且其使用性能已经经历了实际应用的考 验。 华中科技大学硕士学位论文 r 5 ) 拥有真正的多用户、多任务能力。l i n u x 是一个多用户操作系统，允许多个 用户同时访问系统而不会造成用户之间的相互干扰。同时l i n u x 还具有多任 务的能力，同一个用户可以通过创建多个任务来并行处理多个工作。 f 6 ) 动态链接能力。l i n u x 操作系统并非采用静态的链接方式，而是如同 w i n d o w s 中的“动态链接库”方法来实现应用程序和标准库的使用，从而 使系统的运行具有高效性。 1 2 嵌入式l i f l u x 操作系统 1 2 1 嵌入式操作系统 嵌入式系统被定义为【5 7 l ：以应用为中心、以计算机技术为基础、软件硬件可裁 剪、适应应用系统对功能、可靠性、成本、体积、功耗严格要求的专用计算机系统。 作为嵌入式系统灵魂的嵌入式操作系统是随着嵌入式系统的发展而出现的，它 的出现大大提高了嵌入式系统开发的效率，增强了嵌入式应用软件的可移植性，使 嵌入式系统的开发更具科学性。与通用操作操作系统相比，嵌入式操作系统具有如 下一些特征睁8 】： ( 1 ) 小巧。嵌入式系统所能够提供的资源有限，所以嵌入式操作系统必须做到 小巧以满足嵌入式系统硬件的限制。 ( 2 ) 实时性。大多数嵌入式系统工作在实时性要求很高的环境中，这就要求嵌 入式操作系统必须将实时性作为一个重要的方面来考虑。 ( 3 ) 可装卸。由于嵌入式系统需要根据应用的要求进行卸装，因此嵌入式操组 系统应该能够根据要求简化相应的模块。 ( 4 ) 固化代码。在嵌入式系统中，嵌入式操作系统和应用软件被固化在嵌入式 系统计算机的r o m 中。 ( 5 ) 高稳定性。嵌入式系统一旦开始运行就不需要过多的人工干预。在这种条 件下，要求负责系统管理的嵌入式操作系统具有较高的稳定性。 ( 6 ) 统一的接口。随着各种各样的嵌入式操作系统的出现，有必要为嵌入式系 统提供统一的接口，从而为嵌入式应用软件的运行提供平台的无关性。 目前比较成熟的嵌入式操作系统有v x w o r k s 、p s o s 、n e c u l e u s 和w i n d o w s c e ， 随着l i n u x 的日益普及，嵌入式l i n u x 已崭露头角，并对上述操作系统构成了不小 的威胁。 华中科技大学硕士学位论文 1 2 2 嵌入式l j n u x 的特点 嵌入式l i n u x 是按照嵌入式操作系统的要求而设计的一种小型操作系统，由一 个k e r n e l ( 内核) 及一些根据需要进行定制的系统模块组成。其k e r n e l 很小，一般 只有几百k b 左右。即使加上其它必须的模块和应用程序，所需的存储空间也很小。 它有多任务、多进程的系统特征，有些还具有实时性【9 _ 1 1 】。 一个小型的嵌入式l i n u x 系统仅需要三个基本元素： f 1 ) 引导工具。 ( 2 ) l i n u x 微内核，由内存管理、进程管理和定时服务构成。 f 3 ) 初始化进程。 要实现最低限度的工作能力，还需要添加： f 4 ) 硬件驱动程序。 ( 5 ) 提供所需功能的一个或多个应用进程。 随着要求的增加，可能还需要： ( 6 ) 一个文件系统( 可能是在r o m 或者是r a m 里) 。 ( 7 ) t c p i p 网络协议栈。 ( 8 ) 储存半瞬态资料和提供交换空间的磁盘。 运行嵌入式l i n u x 的c p u 可以是x 8 6 、a l p h a 、s p a r e 、m i p s 、p p c 等。与这些 芯片搭配的主板都很小，与一张p c i 卡大小相当，有的甚至更小。嵌入式l i n u x 所 需的内存不是软盘、硬盘、z i p 盘、c d r o m 、d v d 这些众所周知的常规内存，它 使用r o m 、c o m p a c t f l a s h 、m s y s t e m s 的d i s k o n c h i p 、s o n y 的m e m o r y s t i e k 、m m 的m i c r o d r i v e 等体积极小与主板上的b i o s 大小相近，存储容量不太大的内存。 它的内存可以使用普通的内存，也可以使用专用的r a m 。 1 2 3 嵌入式l i n u x 面临的挑战 l 血u 】( 的良好特性使得嵌入式l m u x 的开发和研究成为目前操作系统领域的一个 热点。但就目前的技术而言，嵌入式l m u x 的研究成果与市场的真正需求还有一段 差距，其中一个最主要的因素就是l i n u x 的实时性能存在先天性的不足。 实时性是嵌入式操作系统的基本要求【l 叫2 1 。由于l i n u x 是一种通用操作系统， 而不是一个真正的实时操作系统，内核不支持事件优先级和抢占实时等特性。所以， 在开发嵌入式l i a u x 的过程中，首要问题是扩展l m u x 的实时性能。一般来说，对 l l a u x 实时性的扩展可以从两方面进行：向外扩展和向上扩展。向外扩展是从范围 上扩展，让实时系统支持的范围更广，支持的设备更多。目前的开发所面向的设备 华中科技大学硕士学位论文 一般仅限于较简单的有实时要求的串并口数据采集、浮点数据计算等，而像实时网 络这样实时系统的高级应用还需进一步的发展。向上扩展是扩充l i n u x 内核，从功 能上扩充l i n u x 的实时处理和控制系统。 1 3 l i n u x 实时性分析 1 3 1 实时操作系统 所谓“实时”，对于计算机系统而言不但要求逻辑结果正确，而且还有时间的要 求，即这个结果必须产生在截止时限( d e 砌i n e ) 之蒯”4 ”。对于实时而言，时间期限 的要求是必须得到满足的，但是对于具体应用场合，这种要求的严格程度又有所不 同。如果这种要求是绝对的，任何一次不满足就能造成实难性后果，就被称为强实 时或硬实时( h a r dr e a l t i m e ) ：若偶尔的不满足并不足以造成严重后果，是可以接受的， 则被称为弱实时或软实时( s o f tr e a l t i m e ) 【l 酬引。相应的，具有这两种特性的操作系统 就分别被称为硬实时操作系统和软实时操作系统。以核能电厂和看v c d 为例，用 在核能电厂的操作系统如果出了差错可能会导致严重的损害，然而v c dp l a y e r 出 了些差错不过是让使用者认为观看效果不够好而已，并不会产生巨大的灾害。所以 前者是硬实时，后者是软实时。 实时操作系统( r e a l t i m eo s ) 是相对于分时操作系统( t u n e s h a r i n go s ) 的一个 概念。在一个分时操作系统中，系统资源会被平均的分配给系统内所有的任务，每 个任务都有机会得到运行，其追求的是系统资源的最大利用率。而在一个实时操作 系统中，有多少个任务在运行并不是它关心的，它关心的是不仅要按要求正确完成， 还要按给定的时限完成每一个任务，其追求的是实时性、可确定性和可靠性【i ”。 由此可以看出两种操作系统的不同之处在于：分时操作系统侧重于“公平”，实时 操作系统侧重于“时限”。 1 3 2 实时操作系统的基本特征 i e e e 实时u n i x 分委员会认为实时操作系统应该具备以下几种特征 2 2 - 2 4 1 ： ( 1 ) 异步的事件响应。实时操作系统能在系统要求的时间内响应异步的外部事 件，要求有异步i o 和中断处理能力。 ( 2 ) 确定的任务切换时间和中断延迟时间。 ( 3 ) 优先级中断和调度。必须允许用户定义中断优先级和被调度的任务优先级 并指定如何进行中断服务。 华中科技大学硕士学位论文 ( 4 ) 抢占式调度。为保证相应时间，实时操作系统必须允许高优先级任务一旦 准备好运行，就能马上抢占低优先级任务的执行。 ( 5 ) 内存锁定。必须具有将程序或部分程序锁定在内存的能力，从而保证了快 速的响应时间。 ( 6 1 连续文件。应提供存取盘上资料的优化方法，使得存取资料时查找时间最 少。通常要求把资料存储在连续文件上。 ( 7 ) 同步。提供同步和协调共享资料使用和时间执行的手段。 总的来说，实时操作系统是事件驱动的( e v e n t d r i v e n ) ，能对来自外界的作用和信 号在限定的时间内作出响应。它强调的是实时性、可靠性和灵活性，与实时应用软 件相结合成为有机的整体，起着核心作用。由它来管理和协调各项工作，为应用软 件提供良好的运行软件环境及开发环境。 1 3 3l i f l u x 在实时性方面的缺陷 尽管现有的l i n u x 在某些方面已经具备了一些实时操作系统的特性，但它由 u n i x 发展而来，仍是一个典型的分时系统。要使l i n u x 成为一个实时系统的重大障 碍有以下几点： ( 1 ) l i n u x 的核心是不可切换的 2 5 , 2 6 1 。当一个进程运行于核心态，例如执行系统 调用的时候，它将不被换出。直到退出核心态，即从系统调用返回，或因 某种原因而阻塞，如等待i o 设备完成动作。就是说，这段时间之内是不能 进行进程切换的，这样实时事件的实时响应自然也就无从谈起了。一个真 正的抢占式操作系统允许正在系统状态下的当前进程被打断，然后进程切 换回来时还能继续从刚才的执行点继续下去。 ( 2 ) 对外部中断响应的延迟【2 7 ，2 8 】。l i n u x 内核中为了保证核心资料的完整性，在 进入对关键核心数据结构进行修改的所谓“l | 缶界区”时惯常采用“关中断” 的办法。此时系统无法对中断做出响应，所以频繁的关中断导致实时任务 不能被及时调度执行1 2 9 j 。 ( 3 ) l i n u x 的进程调度器并不是一个真正的实时进程调度器r 3 0 m l 。对于一个实时 性能强的操作系统来说，系统必须规定不同进程的优先级，并把优先级作 为唯一的进程选择标准。l i n u x 中有两种类型的进程：一般进程和实时进程。 实时进程比所有一般进程的优先级高，因此实时进程总会被认为是最值得 运行的进程。但是，l i n u x 核心的设计主要集中在应用程序的吞吐量上。追 求吞吐量的必然结果就是l i n u x 调度器采用一种“公平共享”的策略保证所 华中科技大学硕士学位论文 有的进程得到平均的c p u 资源 3 2 - 3 5 1 。而且，l i n u x 的进程调度器只是简单 的将标有实时标志的进程权重加1 0 0 0 ，对于实时进程间的轻重缓急没有周 密的完整设计。另外，l i n u x 调度器采用的调度算法也造成了响应时间的不 确定性。每当调度发生时，调度器按照一定的算法从一个可运行进程队列 中选择一个最值得运行的进程。这种线性的搜索算法其复杂度 3 6 - 3 9 随着可 运行进程数量的增多面增加，因此影响了系统的响应时间。 l i n u x 在实时性能上的不足并不表示它不适合作为嵌入式操作系统，这是因为随 着专用的嵌入式处理器性能的不断提高，已经可以在一定程度上从硬件弥补l i n u x 的一些实时性能缺陷；而且l i n u x 良好的内核体系和开发源代码的特性也保证了可 以对其进行改造，增强它的实时性。 1 3 4 提高l ir t l i x 实时性能的一些措施 要将l i n u x 用作实时嵌入式系统，必须使之具有更好的实时性，一般采用的改 进措施大致有以下几种 4 0 4 2 l ： ( 1 ) 采用双内核结构。在原来的l i n u x 内核上增加一个实时内核，该实时内核只 完成少量的底层任务，如所有的线程和低级进程管理、f i f o 、进程通信和 中断处理等。改进后的系统运行于两种模式下：实时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 模式进行抢占。 ( 2 ) 提高时钟精度。在以x 8 6 为处理器的p c 上，系统时钟可以提供的最高频 率超过了1 m h z 。l i n u x 通过对它的编程，将时钟频率设定为1 0 0 h z ，即时 钟中断间隔为1 0 m s 。对于实时操作系统而言，这种时钟粒度太粗，无法满 足实时响应的需求。通过改变时钟中断的固定频率模式，并重新设定以使 时钟能以u s 为单位在任何需要的时候产生中断。从而既保证了响应时间， 又避免了不必要的开销。 ( 3 ) 在内核中插入抢占点。在内核的关键代码段中加入抢占点标志位，当进入 该段代码时，将标志位置为否，离开时则恢复原状。这样当进行调度时， 若标志位为否就禁止任务切换；否则就进行任务切换，从而实现内核的抢 占式调度。 ( 4 ) 修改调度器。采用基于优先级的抢占式调度机制，允许在内核状态下对进 程进行抢占，并按照优先级大小对进程进行调度，从而避免了现有l i n u x 调度机制产生的响应时间上的不确定性问题。 6 华中科技大学硕士学位论文 1 3 5 一个基于l i n u x 的实时操作系统实例：r t l i f l u x 目前国内外有很多公司和大学对如何增强l i n u x 的实时性能进行了积极有效地 研究，也取得了不小的进展。已经有不少成熟的产品问世，如新墨西哥理工学院( n e w m e x i c ot e c h n o l o g y ) 的r t l i n u x t 4 z l 、加州大学i r v i n e 分校的r e d l i n u x 、t u n es y s 的l i n u x r t 以及l i n e o 的e m b e d i xr e a l t i m e 等，这些系统都是基于l i n u x 的，但具 体的实现方法却有所不同。下面对r t - l i n u x 操作系统进行分析，从而了解该操作系 统在增强l i n u x 实时性方面采用的一些方法。 r t - l i n u x 是由新墨西哥理工学院开发出来的。这一套系统可以说是所有 r e a l - t i m el i n u x 的鼻祖。它目前已经发展到3 0 版。该系统是由v i c t o ry o d a l k e n 和 他的学生m i c h a e lb a r a b a n o v 所完成。这个系统的概念是“架空”l i n u x 内核，使得 它的实时进程得以尽快的被执行。图1 1 说明了r t - l i n u x 和其它类似产品的系统架 构。 由图可知，r t - l i n u x 采用的是双内核结构：构造一个简单的强实时内核，而应 l 中断控制硬件 工， il i l i l l 】【内核 ： ll i i l u x 进程 图1 1r t - l i n u x 系统构架 用的实时部分作为实时进程直接运行在这个强实时内核之上；原有的常规l i n u x 核 心作为一个优先级最低的任务被这个实时内核所调度，而应用的非实时部分则作为 非实时进程运行l i n u x 核心之上，从而可以获得l i n u x 核心所提供的一切服务。为 了做到这一点r t - l i n u x 采用了如下手段： ( 1 ) 对l i n u x 核心进行改动，将其与中断控制器隔离，不再允许它任意关中断。 核心中所有的中断操作指令都被替换为相应的宏，可以简单地理解为这时 关中断、开中断的指令实际上仅仅变更一个中断状态标志的值，而不真正 改变中断状态此时，中断控制器由实时核心来控制所有的中断首先被 华中科技大学硕士学位论文 实时核心所截获，实时核心首先进行相关的中断处理，然后才把中断传给 l i n u x 核心。这样l i n u x 核心的一切活动都无法导致中断被关闭，也就无从 影响实时核心的任务调度，从而保证了核心的强实时性，同时这种方法依 然维持了l i n u x 核心中数据结构的完整性。 ( 2 ) 改变时钟中断机制。r t - l i n u x 改变了时钟中断的固定频率模式，通过重新 设定使得时钟能以l l s 为单位在任何需要的时候产生中断。从而产生粒度更 细的时钟，提高了系统的响应能力。 f 3 ) 提供实时调度。r t - l i n u x 在这方面采用了非常灵活的做法，它把调度模块 的编写任务交给了系统的使用者。使用者编制的模块可以很容易地加入到 系统之中。这样，使用者可根据自己的不同需求，采用适宜的调度算法。 另外r t - 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 获得了良好的实时性能，但r t - l i n u x 其实只 是一个实时驱动程序的架构，算不上是真正的r e a l t i m el 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 的后续版本的发布己成为一个广受关注 的问题。 1 4 本课题的研究内容及意义 嵌入式系统将成为i t 界的又一个焦点，从目前国内r r 市场来看，嵌入式系统 及其产品在由家电产品和i n t e m e t 衍生出来的新型市场中占有主导地位和独特份额。 因此，嵌入式系统的市场争夺战，是未来后p c 时代r r 市场的关键之战。 研制自主版权的嵌入式操作系统意义重大，它可以摆脱p c 时代我们被外国牵 着鼻子走的局势，使中国的i t 行业真正走向成熟和自立。一方面，嵌入式系统的 硬件技术已经成熟，只要引进先进技术，根据专业性的特征，加以吸引和同化，就 可以形成自己的嵌入系统硬件生产体系。另一方面，随着l i n u x 的日益成熟和发展， 华中科技大学硕士学位论文 我们可以在以开放源码的l i n u x 作为自主版权的操作系统核心的基础上，按照特定 的环境和需求定制嵌入式o s 的各种发布版本。除了对o s 核心部分的改进需要公 开源码外，其它自行开发的部分可以拥有知识产权。 嵌入式l i n u x 目前面i 临的一个很大的挑战就是如何增强自身的实时性能，而这 也是本课题的主要研究内容。本论文将致力于改进l i n u x 内核中的进程调度子系统 这一部分来达到增强l i n u x 实时性能的目的。论文在第二章对l i n u x 进程调度内核 源代码进行了分析，并指出了该调度机制在实时性上存在的不足之处；针对这些不 足，提出了一种基于优先级的抢占式调度机制，并分别在第三章和第四章中从两方 面加以介绍。其中第三章描述了基于优先级排序的进程调度器p o s c h e d u l e r ，该调 度器消除了现有调度算法中产生的“调度时间上的不确定性”的因素，并保持了原 有调度器的其它优良特性；第四章介绍如何利用现有的s m p 体系结构中的同步互 斥机制s p i n i o c k ，将内核改造成为可抢占式的，从而减少原有调度器产生的“调度 延迟”。使系统具有更好的响应能力。在第五章，对原有的系统和改进后的系统在 性能上进行了测试，并给出了试验结果。 - _ _ _ _ _ _ l _ _ _ - _ - - _ - _ _ _ _ _ - - - _ _ _ _ _ _ - - - _ _ _ _ ，_ _ _ 一。 9 华中科技大学硕士学位论文 2l in u x 进程调度源代码分析 在深入分析了约十五万行l i n u x 内核源代码的基础上，本章将对l i n u x 的进程 调度机制进行介绍。首先介绍了进程的一些基本概念：然后分析了l i n u x 采用的进 程调度机制；最后对该调度机制的实时性能进行了分析。对l i n u x 内核的分析主要 是基于版本号为2 4 、基于i 3 8 6 平台的单个c p u 版本的l i n u x 源代码。 2 1 进程 2 1 1l i n u x 进程四要素 一般来说，l i n u x 系统中的进程都具备下列诸要素： ( 1 ) 有一段程序供其执行，这段程序不一定是进程所专有，可以与其它进程公 用。 ( 2 ) 有起码的“私有财产”，即进程专用的系统堆栈空间。 ( 3 ) 在内核中有一个t a s ks t r u c t 数据结构，即通常说的“进程控制块”。有了这 个数据结构，进程才能成为内核调度的一个基本单位接受调度。同时该结 构还记录着进程所占用的各种资源。 ( 4 ) 有独立的存储空间，即拥有专用的用户空间。也就是说不仅拥有前述的系 统堆栈空间。还拥有用户堆栈空间。 这四条都是必要条件，缺了其中任何一条就不成其为“进程”。如果只具备前三 条而缺的四条，那就称为“线程”。特别的，如果完全没有用户空间，就成为“内 核线程”( k e r n e lt h r e a d ) ；如果共享用户空间就成为“用户线程”。这里的“线程” 与某些系统中在用户空间的同一进程内实现的“线程”是不同的，后者显然不拥有 独立、专用的系统堆栈，也不作为一个调度单位直接受内核调度。而且l i n u x 内核 既然提供了对线程的支持，也没有必要再在进城内部，即用户空间中自行实现线程。 另外，进程与线程的区分也不是很严格，需要根据上下文理解其含义。事实上， 在l i n u x 系统中，许多进程在“诞生”之初都与父进程公用一个存储空间，所以严 格来说还是线程：但是子进程可以建立其自己的存储空间，即所谓的“写时复制技 术”( c o p y o nw r i t e ) ，并与父进程分道扬镳，成为真正意义上的进程。 2 1 2 进程控制块t a s k s t r u c t 由于进程是操作系统的最小调度单位元，进程控制块( p c b ) 需表达方方面面 的信息，因此l i n u x 的p c b ，即t a s ks t r u c t 是系统中最重要的数据结构之一。该结 i o 华中科技大学硕士学位论文 构在源文件s c h e d h 中定义，仅将与本文相关的主要部分解释如下： ( 1 ) 进程状态 进程执行时会根据具体情况改变状态，进程状态是调度和切换的依据。在l i n u x 中，进程状态主要有：就绪状态( t a s kr u n n i n g ) ，既正在运行或在就绪队列中 准备运行的进程，实际参与进程调度：阻塞状态( t a s k 唧r r u p t i b l e t a s ku n i n t e r r i 咖l e ) ，由于等待资源而处于等待队列中；僵死状态 ( t a s kz o m b i e ) ，表示进程已经结束运行且释放大部分资源，但尚未释放p c b ； 暂停状态( 1 a s ks t o p p e d ) ，通过其它进程的信号才能唤醒。主要用于调试目的。 ( 2 ) 进程调度信息 调度程序利用这部分信息决定系统中哪个进程最值得运行，并结合进程的状态 信息保证系统运行的高效和公平。主要是：时间配额( c o u n t e r ) ，代表进程当前还 可运行多久；静态优先级( n i c e ) ，用于对c o u n t e r 重新赋值；实时进程的优先级 ( f t _ p r i o r i t y ) ，用于对实时进程的调度；进程调度策略( p o l i c y ) ，有s c h e d _ o t h e r 、 s c h e df i f o 、s c h e dr r 三种；进程调度标志( n e e dr e s c h e d ) ，1 表示需要进行 调度：0 表示不需要。 ( 3 ) 进程组织 每一个进程都不是孤立地存在于系统中，而总是根据不同的目的、关系和需要 与其它的进程相联系。主要有三种方式：将所有进程组成一个双向链表；将所有进 程按照“家庭与社会关系”组织起来形成“家谱”；通过h a s h 表将进程组织起来。 数据结构t a s ks t r u c t 是很复杂的，其中不仅包含了上述几方面的信息，还包含 了大量的其它信息，如文件系统信息、虚拟内存信息、时间和定时器信息等等，由 于这些都不是要讨论的重点，在此并没有对它们进行介绍，具体可参考s c h e d h 中 的定义。 2 1 3 进程的分配 l i n u x 是一个具有分页功能( 每页大小4 k 字节) ，可运行多个任务的操作系统， 同时，l i n u x 还使用了两级保护机制：o 级供操作系统内核使用，3 级供应用程序使 用。l i n u x 是一个3 2 位的操作系统，这意味着在i 3 8 6 平台上，l i n u x 拥有线性地址 从0 g b 到4 g b 的虚拟空间。l i n u x 内核将这4 g 字节的空间分成两部分，最高的l g 字节用于内核本身，称为“内核空间”，也叫“系统空间”：较低的3 g 字节用作各 个进程的“用户空间”。每个进程有各自的私有代码和资料，存储在用户空间，因 而对系统中的其它进程不可见。l i n u x 内核由所有进程共享，存储在内核空间。 华中科技大学硕士学位论文 如前所述，每个进程都有一个t a s ks t r u e t 数据结构和一片用作系统空间堆栈的 存储空间。这两者缺一不可，又有紧密的联系，所以在物理存储空间上也连在一起。 内核在为每个进程分配一个t a s ks t r u c t 结构时，实际上分配两个连续的物理页面。 这两个页面的底部用作进程的t a s ks t r u c t 结构，而在结构的上面就用作进程的系统 空间堆栈，如图2 1 所示。显然，这两个物理页面对应于内核空间，且系统空间堆 栈的大小是静态确定了的，不能像用户空间堆栈那样可以在运行时动态的扩展。 两个连续的 物理页面 ( 8 k b ) 图2 i 进程分配的物理位置 系统空间堆栈 ( 大约7 k b ) t a s ks t t u n ( 大约i k b ) 当进程在系统空间运行时，常常需要访问当前进程自身的t a s ks t r u c t 结构，而 鉴于进程t a s k _ s t r u c t 结构和系统空间堆栈的这种特殊安排，内核中定义了一个宏操 作c u r r e n t ，提供指向当前进程的t a s ks t r u c t 结构的指针。该宏通过将当前堆栈指针 寄存器e s p 的内容与8 1 9 1 u l 相“与”而得到当前进程t a s ks t r u c t 结构的起始地址， 代码如下： s t a t i ci n l i n es l r u c tt a s k _ _ s t r u c t g e t c u r r e n t ( v o 栅 ， s t r u c tt a s k _ s t r u c t * c u r r e n t ： o s m ( a n d l 涨e s p o ：”：”- r “( c u r r e n t ) ：”伊( 8 1 9 l u l ) ) ： r e t l l n lc u r r e n t ； ， # d e f i n ec u r r e n t g e t _ _ c u r r e n t 0 在这段代码中，一条a n d 指令的执行只需4 个c p u 时钟周期，而一条从寄存 器到寄存器的m o v 指令也才2 个c p u 时钟周期，这要比访问内存所需的时间小的 多，是性能上的巨大改善，也再一次显示好的工程并不只限于大公司。 1 2 、ill厂fl，厂iij，弋1ll 华中科技大学硕士学位论文 2 2 进程的调度 2 2 1 进程调度 在多进程的操作系统中，进程调度是一个全局性的、关键性的问题，它对系统 的总体设计、系统的实现、功能设置以及各方面的性能都有决定性的影响。根据调 度结果所做的进程切换的速度，也是衡量一个操作系统性能的重要指针。一个好的 系统的进程调度机制，要兼顾三种不同应用的需要： f 1 ) 交互式应用。在这种应用中，着重于系统的响应速度，使共享一个系统的 各个用户都能够感觉到自己是在独占地使用一个系统。特别当系统中有大 量进程共存时，仍能保证每个用户都有可以接受的响应速度而且并不感到 明显的延迟。 r 2 ) 批处理应用。该应用往往是作为“后台作业”运行的，考虑的是“平均速 度”，即完成个作业所需的时间，对响应速度并无要求。 ( 3 ) 实时应用。这是时间性最强的应用，不但要考虑进程执行的平均速度，还 要考虑“实时速度”；不但要考虑响应速度，还要考虑有关程序能否在规定 的时间内完成。在实时应用中，注重的是对程序执行的“可预测性”。 在设计一个进程调度机制时，要考虑的具体问题主要有：