（计算机软件与理论专业论文）嵌入式linux操作系统实时机制的研究.pdf

摘要 随着数字信息技术与网络技术的高速发展，嵌入式系统产品迅 速增多。在这种环境下，在服务器市场站稳脚的l i n u x 在嵌入式领 域脱颖而出，并以其开放源代码和强大的功能等诸多优势很快发展 起来，成为近年来嵌入式领域研究和开发的热点。本文通过分析 l i n u x 内核主要模块的结构，研究了当前应用于嵌入式l i n u x 的主要 实时性方案，并分析了主流实时调度算法，提出提高嵌入式l i n u x 实时性的改造思路。 实时调度算法设计的优劣对于一个高性能的实时嵌入式系统来 说至关重要，而嵌入式操作系统的调度程序大多采用基于优先级的 调度算法。本文针对当前实时系统调度算法在任务高负载情况下存 在的不足，在基于两个参数的优先级表设计的实时调度算法的基础 上，提出了新的基于三个参数的优先级表设计的实时调度算法，并 进行了参数加权分析与验证，证明其有效地提高了实时任务处理能 力。 此外，本文在r e d l i n u x 的两级调度理论的基础上，提出了一 种面向多种应用的实时调度方案。该方案将进程调度方式改变为线 程调度方式，可以支持三种调度算法，能有效提高嵌入式l i n u x 系 统调度策略的可扩展性，理论分析和验证表明此方案在实时应用上 可有效地提高l i n u x 的实时响应能力。 关键词嵌入式l i n u x ，实时，调度算法，优先级表，线程 a b s t r a c t w i t l lt h e r a p i dd e v e l o p m e n t o fi n f o r m a t i o na n dn e t w o r k t e c h n o l o g i e s ，e m b e d d e ds y s t e m sh a v eo c c u p i e dm o r ec o m m e r c i a l m a r k e t s i n 廿1 i sc a s e l i n u xs y s t e mw h i c ha c h i e v e dg r e a ts u c c e s s e si n s e r v e ra p p l i c a t i o n sh a sg a i n e df u r t h e rd e v e l o p m e n ta n df o u n dw i d e a p p l i c a t i o n si nt h ee m b e d d e di n d u s t r y , f o ri t sa d v a n t a g e so f o p e ns o u r c e ， p o w e r f u lf u n c t i o n sa n ds oo n t h er e s e a r c ho ne m b e d d e dl i n u xs y s t e m s h a sr e c e n t l yr e c e i v e dm a n ya t t e n t i o n sa n db e c o m ev e r ya c t i v e i nt h i s p a p e r ，t h es t r u c t u r e sa n df i m c t i o n so f t h em a i nm o d u l e si nt h ek e m e la r e a n a l y z e d ，t h er e a l - t i m es o l u t i o n sf o re m b e d d e dl i n u xa r ei n v e s t i g a t e d , a sw e l la st h ec u r r e n tr e a l - t i m es c h e d u l i n ga l g o r i t h m sa r ed i s c u s s e da n d as o l u t i o nt oe n h a n c et 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 dl i n u xi s b r o u g h tf o r w a r d t h eh i g hp e r f o r m a n c eo fr e a l - t i m es c h e d u l i n ga l g o r i t h m si sv e r y c r u c i a lt oa l le x c e l l e n t r e a l - t i m ea n de m b e d d e ds y s t e m h o w e v e r , s c h e d u l i n ga l g o r i t h m sb a s e do np r i o r i t yh a v eb e e nw i d e l ya d o p t e di n e m b e d d e ds y s t e m s a i m i n ga tt h e s h o r t a g e o fc u r r e n tr 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 si n t h eo v e r l o a ds i t u a t i o na n db a s i n go nt h e r e a l - t i m es c h e d u l i n ga l g o r i t h mb a s e do nt h et w o - a t t r i b u t ep r i o r i t yt a b l e ， an e wr e a l t i m e s c h e d u l i n ga l g o r i t h mb a s e do nt h et h r e e - a t t r i b u t e p r i o r i t yt a b l ei sp u tf o r w a r da n dt h ep e r f o r m a n c ee v a l u a t i o ni sp r o v i d e d a tl a s t ，h a v i n gd r a w nl e s s o n sf r o mt h et w ot i e r ss c h e d u l i n gs c h e m a u s e di nr e d l i n u x w eb r i n gf o r t har e a l t i m es c h e d u l i n gs c h e m af o r m u l t i a p p l i c a t i o nd e f i n e d t h i ss o l u t i o nw i l ls u p p o r tt h r e et y p e s o f s c h e d u l i n ga l g o r i t h m s ，w h i c hp r o m o t e st h es c a l a b i l i t yo fe m b e d d e d l i n u xs c h e d u l i n ga l g o r i t h m s i na d d i t i o n ，i tc h a n g e sp r o c e s ss c h e d u l i n g m e t h o dt ot h r e a ds c h e d u l i n go n e d u et ot h r e a dm e t h o d sp r i o r i t yo n c o n t r o la n dr e s o u r c ed i s t r i b u t i o nt op r o c e s so n e ，t h i ss o l u t i o ng r e a t l y e n h a n c e st h er e a l - t i m er e s p o n s i v ec a p a b i l i t yo fl i n u xi nt h ea b s t r a c t k e y w o r d s e m b e d d e dl i n u x ，r 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 ，p r i o r i t y t a b l e ，t h r e a d u 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得中南大学或其他单位的学位或证书而使用过的材料。与我共 同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名：1 彩垄， 日期：至! ! 年乙一月2 三日 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定，即：学校有 权保留学位论文，允许学位论文被查阅和借阅；学校可以公布学位论 文的全部或部分内容，可以采用复印、缩印或其它手段保存学位论文； 学校可根据国家或湖南省有关部门规定送交学位论文。 作者签名：丝导师签名盐趔日期：坦l 年上月强日 硕士学位论文第一章绪论 1 1 研究背景 第一章绪论 所谓嵌入式l i n u x 操作系统【l ，2 1 ，就是根据实际情况的需要对发行版的 l i n u x 进行适当裁剪，得到一个小型系统，能够固化在容量只有几十万字节或 几十亿字节的存储器芯片或单片机中，应用于特定嵌入式场合的专用l i n u x 操 作系统。嵌入式l i n u x 的开发和研究是目前操作系统领域的一个热点。与其他 的嵌入式操作系统相比，l i n u x 具有一些独特的优势1 4 , 5 1 ： 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 6 l ，如交通、航空、工业控制等应用场 合。控制对象的动作具有严格的、机械的时序要求，系统时间上的错误，一般 会造成严重，甚至是灾难性的后果。在这样的应用环境中，非实时的普通操作 系统是无法胜任的。实时性的要求使得嵌入式操作系统的首要任务是调度一切 可利用的资源完成实时控制任务，重点是满足对时间的限制和要求。虽然事件 可能在无法预知的时刻到达，但是软件在事件发生时能在严格的时限内作出响 应( 系统响应时间) ，即使是在尖峰负荷下，也是如此。另外，嵌入式操作系统 要具有系统的可确定性，即系统能对运行情况的最好和最坏情况做出精确的估 计。 根据对实时性要求的不同，可以将实时分为软实时和硬实时两种类型【7 j 。 硬实时系统指系统要有确保的最坏情况下的服务时间，即对于事件的响应时间 的截止期限是无论如何都必须得到满足。比如航天中的宇宙飞船的控制等就是 现实中这样的系统。其他的所有有实时特性的系统都可以称之为软实时系统。 如果明确地来说，软实时系统就是那些从统计的角度来说，一个任务能够得到 有确保的处理时间，到达系统的事件也能够在截止期限到来之前得到处理，但 违反截止期限并不会带来致命的错误，像实时多媒体系统就是一种软实时系统。 但是l i n u x 在开发时就力争遵守p o s i x ( p o r t a b l eo p e r a t i n gs y s t e m 硕士学位论文第一章绪论 i n t e r f a c e ) 标、准【8 1 。p o s i x 是标准化类u n i x 操作系统必须具有的特征和接口的 规范。p o s i x 里面增加了对实时性的扩展，如p o s i x l b 或者i e e e1 0 0 3 1 b 已 经加入到p o s i x 标准中。在这些实时性扩展中已经定义了一些工具，如信号、 内存锁定、时钟和计数器、消息队列以及优先级抢先调度等等。不过p o s i x 里 的系统调用反映了u n i x 系统调用的复杂和笨重。l i n u x 虽然支持p o s i x1 0 0 3 1 3 标准( m u l t i p u r p o s er e a l t i m es y s t e mp r o f i l e ) 1 9 ，但是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 。 1 2 研究现状 国内外各大科研机构对嵌入式l i n u x 系统实时应用的研究与开发已经持续 了一段时间，并且取得了相当多的成果。目前，提高l i n u x 内核实时特性主要 有两种途径【l ”。 1 直接修改内核 为提高l i n u x 的实时性，此改进方案将内核中的进程调度、内存管理、中 断处理等部分模块按照p o s i x 标准进行改写，在源代码修改的基础上使l i n u x 变成一个真正的实时操作系统。这需要精心安排部分改动，一般要完全重新编 写一个由优先级驱动的实时调度器，替换原有内核中的进程调度器，根据进程 对实时性要求与否选择合适的调度器。对于实时进程，按照优先级驱动的原则 在时间片和资源分配上进行更高响应速度的调度，如抢占式调度。这样l i n u x 内核将完全变为一个实时内核。这种实现方法对开发人员要求高一要求精通 l i n u x 内核，而且开发难度大、周期比较长，往往适用于有前期研究经验积累 的开发团体，这种开放方法最大的优点在于系统执行效率高，可以获得更好的 性能。目前m o n t a v i s t al i n u x 及k u r t 是采用这一方案较为成功的商业实时 l i n u x 操作系统【1 2 1 。 虽然p o s i x 标准对实现一个实时l i n u x 做了相当多的支持，但是当前只有 软实时应用能用p o s i x 相关函数来实现。移植p o s i x 相关函数到l i n u x 上时 要面对的根本问题是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 i n u x 具有内核模块的动态可加载性，因此实时内核以可加载内核模 块的形式装入原有的内核。由于双内核机制保留了普通l i n u x 内核，以较小的 代价提供了强实时性，避免了大规模结构改造，新系统可以使用几乎所有普通 l i n u x 操作系统提供的功能，如图形环境( xw i n d o w ) 1 1 3 1 网络功能、丰富的 编程支持等功能。新墨西哥科技大学的r t - l i n u x t 弘1 2 】就是基于这种策略而开发 成功的。 r t a i l l 4 , 1 5 也采用双内核方法，不直接使用l i n u x 的任何功能，而是把需要 高度时间精度的工作写成一个驱动程序的形式，然后直接用p c 时序芯片所产 生的中断调用这个驱动程序。r t a i 与r t - l i n u x 的最大不同之处在于，它在l i n u x 上定义了一组实时硬件抽象层( r t h a l ) 。r t h a l 将r t a i 需要在l i n u x 中修改 的部分定义成一组程序界面，r t a l 只使用这组界面和l i n u x 沟通。这样做的好 处在于，用户可以将直接修改的l i n u x 核一t l , 程序代码减至最小，这有可能使得 将r t h a l 移植到新版l i n u x 的工作量减至最低。但是，r t a i 虽然满足了硬实 时性要求，却没有被裁减为足够小且适用于嵌入式系统。 而且这种方法要求运行在普通l i n u x 核心上的所有非实时任务必须是支持 可抢占式调度的。由于实时核心非常小，并不会增加整个系统的负载，所有这 些对开发实时性要求严格的实时软件提供了有力保障i l 6 ，”j 。 其他对l i n u x 内核实时性的改造技术还有设计细粒度的定时器，以及将普 通l i n u x 的调度算法改为基于优先级的调度算法等，这些方法的研究也都取得 了一定的进展，但是都只能应用于软实时应用场合i l “。 总之，当前大多数实时性改造方案都取得了一定的成果，但是仍然存在不 少问题和限制。从总体上说，这些方案都是基于具体的应用提出的，缺乏一整 套系统的理论体系，较多地停留在概念层次上。另外，大多数方法之间的联系 不是很紧密，可扩展性也比较差。因此，对嵌入式l i n u x 实时机制进行进一步 研究是完全必要的。 1 3 拟研究目标、研究问题及研究意义 硕士学位论文第一章绪论 嵌入式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 实时性方面作相关研究工作，不论从理论上还是从实践上都有其 重大的意义： 通过研究l i n u x 这个源代码开放的操作系统，可以对操作系统的核心技 术做深刻和透彻的学习和掌握，这对发展本国的操作系统，缩短与世界先进水 平的差距有重大意义。 该论文所涉及的相关理论和问题都是嵌入式操作系统研究的前沿问题， 通过对这些问题的研究与解决，甚至新的理论或技术突破，对赶超世界先进水 平有重大意义。 研究和开发出一种具有良好性能的嵌入式l i n u x 操作系统，在满足实时 应用基础上，做进一步的应用推广，其实际意义是显而易见的。 1 4 论文结构 第一章：介绍课题研究的相关背景，研究的现状及研究内容。 第二章：探讨实时性理论，对l i n u x 内核主要功能模块做重点分析。 第三章：简要分析了当前主流l i n u x 内核实时性改造方案，并且简要分析 4 硕士学位论文第一章绪论 了当前流行的实时调度算法，最后提出一种实时性改造方案。 第四章：详细分析和设计一种基于三个属性的优先级表的实时调度算法。 第五章：根据两级调度理论，给出一种支持多种任务类型及调度策略的面 向应用的调度模型，并将该模型与线程的调度方式结合，给出一种面向多种应 用的实时化方案。 第六章：对全文进行了总结，并提出了下一步的工作内容。 硕士学位论文第二章实时性理论研究及l i n u x 内核分析 第二章实时陛理论研究及l in u x 内核分析 2 1 实时性理论研究 一般的嵌入式系统都要满足实时性的要求，因此实时系统的大部分特点， 嵌入式系统都具备。本章分析实时系统理论，以说明嵌入式系统应该满足的实 时特性。 1 实时系统理论与方法 实时系统发展到现在已经成为计算机技术的一个重要分支，它主要研究的 是那些完成某种工作或提供某种服务具有时间性的系统，这种时间性不仅仅是 指时间响应上【1 9 l 。实时系统和操作系统有紧密联系，操作系统在管理任务时也 会有时间上或效率上的要求，但这种要求可能只是定性的，一般不做定量分析。 而实时系统在管理任务时主要是研究任务之间的时间满足关系和制约关系，所 以对时间特性有严格的定义。在绪论部分已经知道对时间特性的定义可以分为 硬实时和软实时。实时系统本身更具有理论性，它借鉴了许多数学方法和工具 来抽象模型研究实际的问题，如排队论等。所以从实时系统出发研究多种任务 的管理与调度对操作系统任务管理有很大的借鉴作用。 实时系统研究的是在有限的资源上如何按要求( 如时间要求等) 比较优地 完成任务。这样的问题求解，首先应该对问题有一个形式化的描述。描述方法 不只一种，不同的描述方法也导致不同的研究方法和研究工具。本文采用的是 一种最广泛使用的描述方法由j a n ew s l i u 教授所描述的实时系统参考模 型( r e f e r e n c em o d e lo fr e a l t i m es y s t e m ) ”。 根据这种参考模型，每一个实际的实时系统都可以由三种元素来描述： 一个描述系统任务工作负载的模型 一个描述系统任务可获得的资源的模型 描述系统如何来有效使用可获得资源完成系统任务的算法( 或策略) 集 合 通过这三个描述元素，可以准确地把一个实际问题抽象成一个理论模型， 在其上作理论研究工作。一个系统建立之后，其任务模型和资源模型一般是不 变的，所以工作的重点就在于研究系统的算法( 或策略) ，即如何使整个系统满 足时间上的要求，在满足要求的基础上是否还有最优解。这方面的工作一方面 是研究新的算法( 或策略) ，另一方面则是对应用系统选择和设计匹配的算法。 2 实时系统的主要时间参数 就绪时间：一个任务要运行所依赖的数据和控制条件都已满足，能够被 硕士学位论文第二章实时性理论研究及l i n u x 内核分析 调度并执行的那一刻时间，一般用符号r 来表示。 截止期限：一个任务要完成的那一刻时间，一般用符号d 来表示。 执行时间：一个任务要完成所占用的处理器的时间，一般用符号e 来表 示。 周期：一个任务各工作到来的间隔时间，一般用符号p 来表示。 3 实时系统任务类型 实时系统中为了便于系统性能分析，把任务分为三种类型：周期型任务、 非周期型任务、离散型任务。 周期型任务：某任务的各工作执行是在周期性的时间间隔内进行的，这 样的任务称为周期性任务。周期性任务一般用四元式t ( r ，p ，e ，d ) 来表示。 非周期型任务：非周期性任务一般是对随机事件的响应，其就绪时间不 具有周期性，并且任务的各工作只有软实时要求或没有时间要求。非周期性任 务一般用二元式a ( r ，e ) 来表示。 离散型任务：离散型任务同非周期性任务相似，也是对随机事件的响应， 其就绪时间是离散的，但与非周期性任务不同的是其任务的各工作有硬实时要 求。离散型任务一般用三元式s ( r ，e ，d ) 来表示。 4 实时系统参考模型 对实时系统进行研究时，必须有形式化的模型描述，以及在此模型基础上 的一套验证和性能检测方法，以对待研究的实时应用进行理论上的提炼和论证。 这个模型由三部分组成：任务负载模型、资源模型、算法策略集合。 ( 1 ) 任务负载模型 任务负载模型描述的是整个系统任务之间的关系，这种关系包括任务执行 的顺序关系和任务执行的数据依赖关系，以及每一个任务的性能特征( 时间特 性、功能特性等) 。便于对任务模型的理解，这里给出两个概念。 工作：参与处理器调度和处理的每一个任务单元称为该任务的一个工作， 工作是调度的最小单位。工作与操作系统中的线程概念相对应。 任务：用于完成某一特定功能的一系列相互关联的工作称为一个任务， 而这一系列工作就成为该任务的工作序列。任务与操作系统中的进程概念相对 应。 任务负载模型采用任务图来描述，任务图是一种扩展的前趋图。它是一个 有向图g = ( 3 - ， = 0 公式( 4 1 ) 表示该任务的截止期是当前可以达到的。于是只要在调度时，按公式( 4 1 ) 计算调度就绪任务的d ，若大于0 ，就进行调度，否则，就夭折它。 在这种算法里，系统时钟管理部分中的时钟滴答( t i c k ) 中断处理程序，必 须对运行任务的运行时间进行累计。空闲任务i d l e 的截止期应置为无限大，而 估算时间可为0 ，从而在进行任务调度时，可以保证就绪队列中至少有一个就 绪任务满足调度要求。这有效地解决了e d f 的上述缺点。但是e f d f 算法没有 考虑到任务的重要程度，会出现较为重要的任务却因为截止期晚而后执行，甚 至最后夭折的问题。 ( 4 ) 最小裕度算法( s l f ) 在上述算法中，优先级由截止期的早晚决定，可能使一些不可达截止期的 任务，因为来不及而夭折。另外一种算法1 3 9 , 4 伽是：计算任务的富裕时间，也就 是将任务的截止期减去当前时间和任务的剩余执行时间后得到的时间，称为裕 度( 1 a x i t y ) ( 有些地方称为空闲时间) ，裕度小的，优先级高，以弥补上述情况 的不足。在这种算法里，时钟的滴答中断，不但要累计运行任务的执行时间， 9 硕士学位论文 第三章l j n u x 内核实时性研究 还要对就绪队列上的任务的裕度进行累减。由于正在运行的任务，其裕度不变， 而就绪队列上的任务，其裕度随着时间的推移而减小，从而使得它们的优先级 动态的发生变化。 如果把任务控制块t c b 中的优先级字段p d o f i t y 改成为裕度字段l a x i t y ， 那么，这个字段可以用来存放任务的裕度。假设，任务t i 的实际裕度是l a x ， 称为绝对裕度值，令： l a x n = l a x n 公式( 4 2 ) 为正在运行的任务中裕度字段存放的绝对裕度值。就绪队列上的任务按裕 度递增的顺序排列。令队列上第i 个任务t i ( i = 0 ，n ) ，其裕度字段存放的值为： l a x l = l a x l - l a x n 公式( 4 3 ) l a x i = 慨一l a x l - l a x o( f 1 ) 公式( 4 4 ) 称为相对裕度值。其中，l a x 为就绪队列首元素的相对裕度。时钟滴答中 断只对l a x ，倒计数，就完成了就绪队列上所有任务裕度的累减，当l a x ，= o 时， 该任务的裕度与正在运行的任务的裕度相同，而当l a x = 1 时，该任务的裕度 就比正在运行的任务的裕度小，此时，就必须使任务发生切换。而任务切换时， 就绪队列首元素的裕度字段l a x 的值发生变化，因此，就绪队列上的裕度字段 的值必须进行整理，使其满足公式4 3 和公式4 - 4 。 最小裕度算法也有个缺点，即每一个时钟滴答都需要进行调度判断，当就 绪队列首元素任务的相对裕度为1 时，将处于调度的临界状态。这时，就绪队 列首元素任务和运行任务，每隔2 个时钟滴答，就得互相切换。频繁的调度判 断和任务切换，都将使系统性能变坏。 ( 5 ) 价值最高优先算法( h v f ) 在h v f 算法1 4 1 恒，每一个任务有一个价值函数，价值越大，优先级越高。 例如，构造如下的价值函数：v = c ( ( f - t 。) 一d + p - w 4 吐) 。其中， c 为任务的紧急度，t 为当前时间，。为任务的启动时间，d 为任务的截止期， p 为任务的已执行时间，d 。为执行该任务的裕度，为加权因子。这个算法将 价值作为衡量优先级大小的标准，保证了最关键的任务最先得到执行。但是该 算法会导致某些价值较大的任务长时间占有c p u 运行时间，使一些价值相对较 小，但是运行时间却很短的任务一直得不到运行而最终夭折。 ( 6 ) 价值比最大优先算法( v d ) 在v d 4 2 , 4 3 1 算法里，定义一个价值比函数： 胁：堕墨：盟 e - p 其中，v 为类似上面所定义的价值函数，t 为当前时间，e 为估算执行时间， 硕士学位论文第三章l i n u x 内核实时性研究 p 为已执行时间。这时，v d 值越大，优先级越高。该算法能够得到较好的性能， 但是价值函数的确定使得一些价值较大的任务反而晚于。 ( 7 ) 相对截止期与空闲时间优先算法 这是一种基于优先级表设计的调度算法【4 4 4 ”，优先级表设计时考虑了任务 的相对截止期和空闲时间两个特征参数，这种设计思想可以推广到对其他任意 两种特征参数进行的综合设计中。 任务的相对截止期是指任务到达时间和截止期之差，在抢占式动态调度过 程中，这种相对截止期可定义成任务的截止期与当前时刻之差，也是随时间变 化的。空闲时间的计算方法跟s l f 算法一样。这两个参数看起来好象相关，但 是空闲时间在任务刚进入任务队列时计算，在计算后就不受截止期这个参数约 束了。在综合考虑任务相对截止期和空闲时间两个特征参数时，需要考虑下面 两个方面的设计原则： ( 1 ) 截止期越早和空闲时间越短，任务的优先级就越高； ( 2 ) 对于任意两个任务，在它们的相对截止期和空闲时间两个参数中，只 要至少有一个参数不同，那么它们的优先级值也应该不同，即任务的优先级分 配是惟一的。 这种算法摈弃了上述两种算法将不同的量进行运算的缺点，保证了截止期 早的任务得到较早运行，但是其典型值的设置会影响到插值的效果，更会严重 影响该算法的应用范围。 上述这些算法均是基于优先级的调度算法，在实时系统中，尤其是在硬实 时系统中有着广泛的应用。在这些算法中，任务的优先级都是基于任务的某种 特征参数，如截止期、空闲时间或关键性( 即任务的重要程度或者价值) 等计 算而得。然而，如果优先级仅由某个特征参数来确定是不够的，这样会导致考 虑实时任务调度问题不是很全面，因而计算出的优先级也就不能完全反映任务 集中各个任务之间真实的先后关系。如e d f 策略是将最高优先级指派给具有 最早截止期的任务，l s f 策略是将最高优先级指派给具有最短空闲时间的任务， 尽管在正常的系统负载下这些算法表明了其最优性，但是在过载的情况下，系 统不可能保证所有的任务都能够满足截止期，而且此时e d f 或者l s f 算法的 性能通常会急剧下降，甚至导致“多米诺现象”【4 3 l 。再者，截止期或者空闲时 间短的任务不一定是最关键的，但是即使在过载的情况下系统也应该保证关键 任务的及时完成，从而支持系统性能优雅地降低，不致出现系统失效甚至崩溃。 而相对截止期与空闲时间优先算法采用了两个特征参数，从任务执行时间上区 分任务的关键性，但是并没有体现出任务的价值，在任务重负载情况下，有些 价值较高的任务并没有得到及时的调度执行。而且这种基于两个特征参数设计 硕士学位论文第三章l i n u x 内核实时性研究 的优先级表中，一个任务与其所确定的优先级值可能不是一一对应的，即不同 的任务可能有相同的优先级【4 5 】。并且，该算法要求必须事先明确特征参数的典 型值，并计算优先级表。而典型值的设置又会影响到插值的效果，进而会直接 影响到算法的性能。 从这些算法的分析中可以看出，当前基于优先级的实时调度算法的设计大 多考虑到三种特征参数：截止期( 或相对截止期) 、空闲时间和任务的关键性( 或 称为价值) 。因此在相对截止期与空闲时间优先算法的基础上，将价值也作为区 分任务关键性的一个特征参数，对于实现高价值率任务的优先调度执行是个有 益的尝试。本文将会在第四章中详细讨论基于三种特征参数计算任务优先级的 调度算法的设计和实现过程。 3 3 一种面向多种应用的实时化方案 近年来，虽然针对各种类型的实时任务模型和调度方案不断涌现，但是因 为实时系统应用的范围更加广泛，各种类型的实时任务共存于同一系统中的情 况越来越常见，而针对性强、应用范围比较专一的调度方案不能满足这种需求。 因此，对于系统层的调度方法，不仅支持某一种类型的实时任务的调度是必要 的，而且同时支持各种类型任务的调度也是需求之一。因此本文在借鉴 r e d l i n u x l 4 8 】提出的两级调度理论的基础上，给出一个面向多种应用的实时化 方案。 该方案总的设计思想是实时调度机制采用两级调度机制，第一级用来设置 调度参数，第二级根据调度参数选择相应的调度算法。并且将以进程创建和调 度的形式改为以线程创建和调度的形式，各相应的调度器都以线程的形式产生 和执行。为了进一步增强方案的实时性能，也借鉴了r t - l i n u x 的软中断模拟思 想。而普通l i n u x 的调度器也保留下来，作为一些非实时任务的调度器。 第二级的实时调度器根据实时任务的类型选择相应的调度算法。调度算法 支持面向硬实时应用的优先级驱动调度算法，面向软实时应用的基于共享的调 度算法和面向小型嵌入式应用的基于时间驱动的调度算法。其中，面向硬实时 应用的优先级驱动调度算法采用第四章给出的基于截止期、空闲时间和价值密 度等三个参数的硬实时调度算法。 根据这种思路设计的面向多种应用的实时性方案从理论上来说可以支持多 种调度算法，因而能够有效地扩展当前嵌入式l i n u x 操作系统的应用范围。并 且利用线程相对于进程在任务调度方面的优势，将线程做为任务调度和管理的 基本单位，这在一定程度上会提高l i n u x 的实时任务响应能力。而且p o s i x 相 关线程标准也为该方案提供了有力的支持。第五章将会详细讨论该方案的设计 过程。 硕士学位论文 第三章l i n u x 内核实时性研究 3 4 本章小结 本章主要分析了当前各种主流l i n u x 内核实时性改造方案的特点，并且讨 论了当前流行的实时调度算法的优缺点，从中可以看出这些改造方案和实时调 度算法都使得普通l i n u x 的实时性能得到不同程度的提高，并且各有其应用特 点。最后给出了一种面向多种应用的实时性方案的设计思路，并引入下文要进 行的工作。 硕士学位论文 第四章实时调度算法的研究与设计 第四章实时调度算法的研究与设计 实时任务的调度，就是当系统有多个就绪任务时，如何确定由哪一个任务 实际占用c p u 。它涉及到调度的策略和调度的机制问题。不同实时应用系统的 用户，可能希望用不同的策略来进行调度。因此，对于实时操作系统来说，最 好是把调度策略和调度机制分开l 。实时操作系统实现某些调度算法，并把调 度策略参数化，让用户在实时任务中，根据这些参数选择所需要的调度策略。 调度参数选择的恰当与否，会直接影响到所设计调度算法的性能，进而影 响到整个系统的实时任务处理能力。根据上一章对各种实时调度算法的分析， 本文选择了截止期( d e a d l i n e ) 、价值密度( v a l u ed e n s i t y ) 和空闲时间( s l a c k ) 等三 个特征参数。 4 1 算法的设计 此算法依然针对硬实时任务进行调度，基于优先级表的设计，采用三个不 同的特征参数：截止期、价值密度与空闲时间。其中，价值密度是指任务的价 值与其估计执行时间的比值。之所以采用价值密度这个参数，就是为了避免执 行时间较长的任务过早地占用c p u 执行时间，而使一些价值较小，但是执行时 间较短的任务长时间等待。而任务的空闲时间是指截止期减去当前时间和任务 的剩余执行时间后得到的时间，因此，空闲时间一般是动态变化的。 如果综合考虑三个参数的过程中，考虑顺序为截止期、价值密度、空闲时 间时，形成的算法为d v d s f 算法；如果考虑顺序为截止期、空闲时间、价值 密度时，形成的算法为d s v d f 算法。 d v d s f 算法基于这样的前提：算法对硬实时非周期任务集进行调度，不 考虑任务集中任务之间的关系，也不考虑单个任务占用其他除c p u 资源之外的 资源，使用单处理器按照优先级表来调度执行任务，属于单处理器调度算法。 1 任务描述 假设存在实时任务t i ，用9 元组表示为：t i = ( a i , c i ，c ，z ，d i ，v i ，v d , ，丑，z ) ， 其中： ( 1 ) 口表示任务的到达时刻，即任务被启动并准备执行的时间； ( 2 ) c i 表示任务的最坏情形执行时间段，即任务在最坏情况下无中断执行所 需的处理器时间； ( 3 ) f ，表示任务的剩余执行时间段； ( 4 ) z 表示任务的绝对截止期，即任务在这个时间应该完成执行并产生一个 有价值的结果( 如果没有特别说明，本文的截止期都是指任务的绝对截止期) ； 硕士学位论文第四章实时调度算法的研究与设计 ( 5 ) d i 表示任务的相对截止期，有d i = d 口。； ( 6 ) v i 表示任务的价值，即任务的关键性，该任务相对于任务集中其他任务 的重要程度： ( 7 ) v z 表示任务的价值密度，表示单位时间内任务的价值，有v d , = v i c i ； ( 8 ) s ，表示任务的空闲时间段，有= 4 ( t + c ，) ，其中t 表示当前时刻且 a t p d p f i o r ；定义指针，指向的尾结点 ( b ) i = p d 一 i + 1 ；初始化新任务在优先级表中的下标 ( c ) w h i l e ( ( p d ! = d h e a d ) a n d ( p n e w - d d ) ) ，确定新任务在中的位置 p d 一 i + + ；p d 2 p d 一 p d p f i o r ；i 一 ( d ) p n e w i _ i ；设置新任务在优先级表中的下标 ( e ) i n s e r t ( p d ，p n e w ) ；把p n e w 插入p d 之后 3 ) 把任务p n e w 插入q “ ( a ) p v d i = v d i h e a d 一 p v d i p r i o r ；定义指针，指向q “的尾结点 ( b ) j = p v d i 一 j + 1 ；初始化新任务在优先级表中的下标 ( c ) w h i l e ( ( p v d i ! - 一v d i h e a d ) a n d ( p n e w - v d i p v d i - v d i ) ) 确定新任务在q “ p v d i 一 j + + ；p v d i = p v d i 一 p v d i p r i o r ；j _ ) 中的位置 ( d ) p n e w 一 j = j ；设置新任务在优先级表中的下标 ( e ) i n s e r t ( p v d i ，p n e w ) ；h 把p n e w 插入p v d i 之后 4 ) 把任务p n e w 插入q 5 ( a ) p s = s h e a d - p s p r i o r ；定义指针，指向0 5 的尾结点 ( b ) k - p s 一 k + 1 ；初始化新任务在优先级表中的下标 ( c ) w h i l e ( ( p s ! = s h e a d ) a n d ( p n e w - s p s 一 s ) ) 确定新任务在q 5 中的位置 p s - k + + ；p s = p s 一 p s p r i o r ；k 一- ( d ) p n e w k = k ；设置新任务在优先级表中的下标 ( e ) i n s e r t ( p s ，p n e w ) ；把p n e w 插入p s 之后 5 ) 计算任务的优先级并判断是否需要抢占当前正在执行的任务 ( a ) 只，b ，弓； ，计算三个优先级等级 ( b ) p n e w 一 p = 0 ( 只) + o ( 足) + 0 ( 只) ； ，计算新任务的优先级 硕士学位论文第四章实时调度算法的研究与设计 ( c ) i f ( p n e w - p p a c t i v e 一 p ) ，新任务p n e w 抢占当前任务p a c t i v e p a c t i v e = p n e w ； ( 2 ) 任务完成夭折策略 当一个任务完成执行或者超过截止期而夭折时，系统需要调用任务完成 夭折策略，把完成执行或者天折的任务结点从优先级表中删除，并且相应地调 整后续任务的三个下标以重新计算任务的优先级，并且选择优先级最高的任务 去执行。 任务完成夭折策略的算法描述如下： 1 ) 从优先级表中删除当前完成的任务 ( a ) 从q 。链表中删除该任务结点 p d = p a c t i v e p d p r i o r - p d n e x t = p a c t