（计算机应用技术专业论文）linux实时调度算法与测试平台的研究与实现.pdf

大连理工大学硕士学位论文 摘要 实时系统在过去几年里迅速成长，但能够提供实时功能的操作系统往往价格极为昂 贵。由于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 o m s ，过于粗糙。为了在不损失性能的情况下提高时钟精度，本文设计 并实现了用i n t e lp l i 系列以上c p u 内部的l o c a la p i c 定时器产生细粒度时钟中断，负 责调度实时进程的方案。没有改变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 实时调度算法测试平台的研究与实现 r e s e a r c ha n dr e a l i z a t i o no f l i n u xr 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 a n dt e s tb e n c h a b s t r a c t t h er e a l - t i m es y s t e mg r o w s u pv e r y f a s to v e rt h ep a s ts e v e r a ly e a r s ，b u tt h e p r i c eo f r e a l t i m e o p e r a t i n gs y s t e m t h a tc a no f f e rr e a l - t i m ef i m c t i o n si s u s u a l l ye x t r e m e l y e x p e n s i v e b e c a u s eo fo i ) 幽gs o u r e ec o d ea n de x c e l l e n tp e r f o r m a n c e ，l i n u xb e c o m e sn e w f a v o u r i t ei nt h er e a l - t i m es y s t e mf i e l d b u ta sag e n e r a lt i m e s h a r i n go p e r a t i n gs y s t e m ，l i n u x h a sal o to f s h o r t c o m i n g sa n dd e f i c i e n c i e sw h e n i ti su s e du n d e rt h ee m b e d d e da n dr e a l t i m e e n v i r o n m e n t ，s ot h ee x i s t i n gl i n u xs h o u l db et r a n s f o r m e d v a l u a b l er e s e a r c ho nt h er e a l i z a t i o nm e c h a n i s mo fe a c hp a r to fl i n u xo p e r a t i n gs y s t e m a c c o r d i n gt o t h ec h a r a c t e r i s t i c so fr e a l - t i m es y s t e mi sd e s c r i b e di nt h i st h e s i s a n ds e v e r a l a s p e c t su n s u i t b l ef o r r e a l - t i m ea p p l i c a t i o nh a v eb e e n i m p m v e d t oo p e r a t i n gs y s t e m ，p r e c i s et i m i n gi sv e r yi m p o r t a n tf o rt h ec o r r e c ts c h e d u l i n ga n d t i m e l yr e s p o n s eo f t a s k t h eg a i ns i z eo f p e r i o d i cc l o c ko fl i n u xi sl o m s ，a n dt o oc o a r s ef o r r e a l - t i m es y s t e m s i no r d e rt oi n c r e a s i n gt h ep r e c i s i o no ft h ec l o c ki nc a s eo fn o tl o s i n g p e r f o r m a n c e ，t h es c h e m e o fs c h e d u l i n gr e a l - t i m ep r o c e s si sd e s i g n e da n dr e a l i z e d 、i t hf i n e - g r a i nc l o c ki n t e r r u p tp r o d u c e db yl o c a la p i ct i m e ri nt h ec p u o fi n t e tpi is e r i e so ra b o v e ， a n d o f i 季n a ll i n u x c l o c k i n t e r r u p ti sn o tc h a n g e dy e t i nt h i sw a y , t h ep r e c i s i o no f t h ec l o c ki s i n c r e a s e d ，a n dp e r f o r m a n c ei sn o tl o s s e dt o o ，s op r o b l e mo fp r e c i s i o no ft h ec l o c ki sw e l l s o l v e d d e s i g no fl i n u xo p e r a t i n gs y s t e mi s u s e df o r t i m e - s h a r i n ga p p l i c a t i o n , i t sp r i o r i t y s c h e d u l i n gw a y d o e sn o tr e l a t e 、i l l lt i m e b u te a c ho f r e a l t i m et a s kh a v ed e m a n do f d e a d l i n e t h r e et i m e r sr e l a t e dw i t ht h et i m ec h a r a c t e r i s t i ca l eu s e df o rc h a n g e p r o c e s s sr u n n i n gs t a t e ，t h e n t h e p r o c e s s c a nb es c h e d u l e d a c c o r d i n g t ot i m e sd e m a n di nt h ef o l l o w i n g s c h e d u l i n gf u n c t i o n t h e s p e c i f i cr e a l t i m es c h e d u l i n ga l g o r i t h m i ss u i t a b l ef o rs p e c i f i ca p p l i c a t i o n i no r d e rt o e x a m i n et h ep e r f o r m a n c e ，g e n e r a ls c h e d u l i n gf r a m ei sa d o p t e da n dr e a l i z e di nt h i st h e s i s t h i s f i - a m ec a l lu s el o t so f r e a l - t i m e s c h e d u l i n ga l g o r i t n n t i n a e d r i v e i la l g o r i t h m i sr e a l i z e dt o o t h e e x p e r i m e n t r e s u l tp m v e st h a tt h ei m p r o v e m e n te n a b l e sl i n u xt os c h e d u l i n gt h er e a l t i m et a s ko f m i c r o s e c o n d g r a d e i nt h es i t u a t i o no fn o t i n c r e a s i n gs y s t e ml o a d k e y w o r d s ：r e a l - t i m es y s t e m ；r e a l t i m e o p e r a t i n gs y s t e m ；l i n u x ；s c h e d u l i n ga l g o r i t h m i 【一 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究 工作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得 大连理工大学或其他单位的学位或证书所使用过的材料。与我一同工作 的同志对本研究所做的贡献均已在论文中做了明确的说明并表示了谢 意。 作者签名：扬五日期：丝麴墨! 旦 大连理工大学硕士学位论文 引言 实时系统是指系统所产生的计算正确性不仅取决于程序的逻辑正确性，也取决于结 果产生的时间，如果系统的时间约束条件得不到满足，就会发生系统出错。在硬实时系 统中，不允许任务或早或晚的执行。在这样的系统中，如果不满足时限的要求，将有可 能造成灾难性的后果。而在软实时系统中，在时间上稍微晚一些进行响应则会比根本不 响应要好得多。 近年来，实时操作系统在多媒体通信、在线事务处理、生产过程控制、交通控制等 各个领域得到广泛的应用，因而越来越引起人们的重视。现有商业实时操作系统，有的 尽管提供了很小的核心和多任务开发环境，但性能并不理想，有的虽然各方面性能很 好，但是价格极为昂贵，使得开发实时应用的成本过高。 所以，人们把目光投向了通用操作系统，而l i n u x 作为嵌入式实时系统开发的解决 方案，在众多通用的操作系统中具有独一无二的优势。首先，l i n u x 遵循g p l 协议，开 放所有系统源代码，非常易于剪裁；其次，l i n u x 虽然最初也是作为通用操作系统而设 计开发的，但也提供了一些实时处理的支持。这包括大部分p o s i x 标准中的实时功能， 支持多任务、多线程，具有丰富的通信机制和网络功能等。l i n u x 还提供了符合p o s i x 标准的调度策略，包括调度实时进程的f i f o 、s c h e dr r 调度策略等，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 的实时缺陷对它进行实时化改造。 在实时操作系统中，实时调度算法是一个非常重要的研究领域。近些年来，新的实 时调度算法不断涌现，急需存在一个在常用的p c 机上就可以测试其性能的实时环境， 应上述要求，我们借鉴现有的各种基于l i n u x 的实时操作系统，在p c 机上实现一个可 以测试实时调度算法优劣的平台，充分利用l i n u x 开放源代码的优势，使其能够为我们 的科研和商业服务。 在本文中，主要工作有： 1 深入分析了实时系统的特征及目前常用的各种实时调度算法 2 系统地研究了l i n u x 操作系统的结构及各部分所使用的技术 3 通过对实时系统及l i n u x 操作系统的研究，提出了l i n u x 实时化急需解决的问题 及l i n u x 实时化的典型方法 l i n u x 实时调度算法测试平台的研究与实现 4 从三个方面对l i n u x 进行改造并建立了一个基于硬件细粒度时钟并提供了一个通 用的调度框架以测试实时调度算法的性能 5 实现了时钟驱动方式的实时调度算法 2 大连理工大学硕士学位论文 1 实时系统概述 操作系统的任务是控制和管理计算机系统内的各种硬件和软件资源，合理有效地组 织计算机系统的工作，为用户提供一个使用方便且易于扩展的工作环境。操作系统的分 类标准有很多种，而其中最基本的操作系统类型有三类，即多道批处理操作系统、分时 系统和实时系统。但一个实际的操作系统中有可能同时兼有三者或者两者的功能。 1 1 实时系统定义 实时系统是指产生系统输出的时间对系统是至关重要的系统。从输入到输出的滞后 时间必须足够小到一个可以接受的时限( d e a d l i n e ) 内。因此实时逻辑的正确性不仅依 赖于计算结果的正确性，还取决于输出结果的时间【1 。 这里的时限( d e a d l i n e ) ，指的是系统执行时间的限制，而系统功能的实现需要通过软 件的相互配合，因而这些组成系统的软硬件的执行时间也就有了相应的时间限制。 1 _ 2 实时要求 根据对时间操作的重要性，可以将操作系统分成以下几类。 ( 1 ) 批处理系统 许多计算机应用根本没有任何实时性要求。这样的一个例子就是编译器。在程序运 行前需要准备好它的输入，使其可用，然后在程序终止前，计算出输出。支持这种应用 的系统通常被称为批处理系统，因为数据是成批被处理的。而且，产生输出的时间并不 影响输出的正确性。然而，实际上，对于程序来说还是应该要求具有一定程度的效率 的。 ( 2 ) 交互式系统 现代计算机程序在处理数据的过程中总是和用户打交道的。用户向程序提交一个命 令，这个命令就执行希望的动作，并产生结果。然后，在接着提交一个新命令。我们把 这种系统叫做交互式系统。这种系统的一个例子是字处理器。为了交互式的进行工作， 执行命令所需要的时间必须很短。否则，如果延迟很长的话，用户就会认为系统很差， 很可能错误的终止操作的执行。例如，如果一个字处理器每次都需要几秒的时间将用户 按下的键更新到屏幕输出上，用户就可能认为字处理器没有处理某些字符，然后就会重 复按键的动作。这种结果显然不是我们想要的。 一3 l m x 实时调度算法测试平台的研究与实现 交互式系统通常具有一定的实时要求。接近半秒的响应时间通常被认为是合理的。 在大多数情况下，用户是不会注意到小于0 1 秒的延迟的。一个例外是那些处理仿真的 系统，为了获得平滑的运动效果，需要很短的响应时间。但是偶尔几次错过时限是不会 很严重的。在字处理器的例子中，用户可能会取消被错误插入的字符。在仿真的例子 中，错过一个时限可能会导致运动突然发生变化。如果这种情况很少发生，它也是可以 容忍的。 ( 3 1 软实时系统 当计算机控制着几种外设时，就需要加强实时要求。嵌入式计算机系统就属于这种 范畴。要求的响应时间比交互式系统还要短，通常是在1 0 到1 0 0 毫秒范围之间。要保 持对外设的控制以及使得它能够有效的执行任务，系统要能够满足它们的时限要求。然 丽在软实时系统中，也是偶尔发生这种错误的。 软实时系统的一个例子是电话交换系统。为了有效率的服务客户，系统必须很快的 响应呼叫者的动作。当呼叫者拿起听筒时，交互系统就必须产生拨号音，并且准备接收 拨叫的电话号码。如果交互系统不能做到这些，那么呼叫者就会认为在这一时刻系统不 能服务。但即使系统偶尔不能为一个呼叫者服务，作为系统的整体来说是不受影响的。 交互式系统与软实时系统之间有很多相似的地方。例如执行仿真的系统就可以被认 为是交互式系统，又可以认为是软实时系统。 “) 硬实时系统 一些实时系统必须处理一些具有严格时间要求的任务 2 】。错过这些任务的时限就会 导致系统的错误。自动控制系统就属于这种范畴。这些系统可以用来控制机器人运动， 发射飞船，和控制机器的操作等。 同时也注意到，在一些控制系统中，偶尔错过一些时限是不会导致系统错误的。这 样产生的结果只能是认为不够好。实际的实时系统通常是软实时与硬实时要求的结合 体。自动控制的硬实时系统会包括具有软实时时限的低优先级过程，和具有硬实时时限 的高优先级过程。低优先级过程可以用来与用户交互。 1 3 实时系统的特点 实时系统对时限和可靠性的要求都非常高，所具有的特点表现为： ( i ) 多路性。实时系统的多路性表现在对多个不同的现场信息进行采集以及对多个对象 和多个执行机构实行控制。 大连理工大学硕士学位论文 ( 2 ) 独立性。每个用户向实时系统提出服务请求，相互间是独立的。在实时控制系统中 对信息的采集和对象控制也是相互独立的。 ( 3 ) 及时性。实时系统所产生的结果在时间上有着严格的要求，只有符合时间约束的结 果才是正确的。在实时系统中，每个任务都有一个截止期，任务必须在这个截止期之内 完成，以此来保证系统所产生的结果在时间上的正确性。对于硬实时系统来说，如果所 产生的结果不符合时间约束，那么，由此带来的错误将是严重的和不可恢复的。而对于 软实时系统来说，虽然结果的产生不符合时间约束，但由此带来的错误还是可以接受 的、可以恢复的。 ( 4 ) 同时性。一般来说，一个实时系统常常有多个输入源，因此，这就要求系统具有并 行处理能力，以便能同时处理来自于不同输入源的输入。 ( 5 ) 可靠性。可靠性一方面是系统的正确性，即系统所产生的结果不仅在数值上是正确 的，而且在时间上也是正确的；另一方面是指系统健壮性，也就是说，虽然系统出现了 错误或外部环境与定义的不符合，但系统仍然可以处于可预测状态，它仍可以运行而不 会出现致命错误。 1 4 实时系统的可预测性 在实时系统中，特别是硬实时系统，一个重要的特性是可预测性。当我们说一个系 统是可预测的，就意味着存在最坏情况下的响应时间的上界，而且可以被计算出来。在 一个可预测的系统中是不能存在任意时间长度的延迟的。为了保证最大响应时间，系统 执行的每个操作都必须是可预测的。预测性可以保证所有的时限都可以得到满足。 ( 1 ) 平均情况执行效率和最坏情况执行效率 当衡量一个系统性能的时候，会研究它执行不同任务时所需要的时间。可以关注系 统在平均情况下或最坏情况下是怎样执行的。如果研究它的平均情况执行性能，就是说 通过测量或是对代码的理论分析，都可以决定执行时间。另一方面，可以通过最长的可 能执行时间的近似分析，得到最坏情况下的执行性能。 对批处理系统和交互式系统来说，为了获得一个可以接受的结果，我们仅仅关心平 均情况下的执行性能 对于实时系统，特别是具有硬实时需求的实时系统来说，必须保证系统不能错过任 何一个时限，至少是硬实时时限。在这样的系统中，可能会具有很好的平均情况执行性 能，但是更重要的是在最坏情况下也要满足每个时限。 5 一 l i n u x 实时调度算法测试平台的研究与实现 ( 2 ) 调度验证 在一个强调安全性的实时系统中，有两种方法可以用来验证系统是否满足所有的时 限。一个方法是运行软件并测量系统的性能。对于这种方法来说，有两个主要的缺点： 一个是非常难以保证测量的是最坏情况的执行性能：另一个是在实际应用环境中不可能 验证软件，因为错过时限会有非常严重的后果。没有验证，是不能相信软件运行的，但 是没有运行的话，又不能验证它。 第二个方法是在实际运行系统前，对软件做一个理论上的分析。这口q 做预先调度分 析。利用系统处理的知识，可分析出过程是在什么时间开始执行的。这种方法的缺点是 需要对硬件及软件的知识非常清楚。对于每个过程，都必须清楚它的执行模式和最坏情 况执行时间。而且，过程之间的通信和访问共事资源带来的阻塞也必须考虑在内。 从调度分析的观点来看，可以接受一个对最坏情况执行时间的保守估计。只要被估 计出来的不小于真实值，就可以信任调度分析。如果通过分析说明系统是可调度的，那 么实际上也将是可调度的。然而，如果我们使用非常保守的估计值，那么分析就会将实 际上可调度的系统判断为不可调度的系统。因此，我们希望估计的最坏情况执行时间应 该尽可能的与实际的相接近。 然而，对最坏情况执行时间的估计也是非常困难的问题。一种方法是研究编译器为 每个过程产生的代码，把每个单独指令的最大执行时间加在起。对批处理和循环的分 析比较困难，需要额外的信息，例如每个循环可能的最大循环次数。对管道和缓存的分 析也比较困难。可以通过人工计算或者通过一个模拟器运行代码来得到最坏情况执行时 间的估计值。另一个估计最坏情况执行时间的方法是给定一些输入，在目标硬件上实际 运行过程的代码，并测量执行时间，执行时间的最大值就可以认为是最坏情况执行时 间。当然，不能保证执行测量的时候，系统是处于最坏的可能情况中。为了在一定程度 上加以补偿，就需要将额外的时间加在测量的最坏情况时间上。即使通过这种方法不能 产生完全可信任的结果，在实际应用当中，它也是最常用的方法。 除了一些真正的高优先级进程之外，嵌入式控制系统中还包括很多具有低优先级的 进程。这些进程的工作可能是计算引用计数，代表控制进程的状态，获取操作者指令， 与其它计算机通信等。低优先级进程也必须满足一些实时要求，但是这些要求可能与交 互式系统或者软实时系统比较接近。而且，错过一个时限的结果也不如高优先级进程那 样严重。 ，6 ， 大连理工大学硕士学位论文 总的来说，嵌入式控制系统通常是使用些并发执行进程来实现的。系统的关键任 务只是一小部分，具有高优先级和严格的实时要求。必须要保证这些进程能够准时运 行，并且不受干扰。同时，系统也包括一些具有一般实时要求的低优先级进程。这些进 程的实时要求与交互式系统和软实时系统类似。 1 5 常用的实时调度方法 在实时系统研究中，实时调度是一个难点，也是被广泛研究的题目。调度的实质是 资源的分配，进一步地，实时调度强调的是为一系列任务决定何时得到何种资源运行。 合理的实时调度可以充分利用有限的系统硬件资源，从而确保实时任务的时间约束得到 满足。与分时系统中的调度所追求的公平性原则不同，实时调度根据各个任务的实时需 求的不同而区别对待它们【2 ，3 。 常用的实时系统调度方法有三种：时钟驱动调度、加权轮转调度和优先级驱动调 度。 ( 1 ) 时钟驱动调度方法 时钟驱动( 也称时间驱动) 调度【4 ，5 ，6 是指在系统开始执行之前，选择一些特定豹 时刻，在这些时刻决定哪一个作业在何时执行。在一个典型的使用时钟驱动调度方法的 系统里，所有强实时作业的参数都是固定的并且是已知的。作业的调度表脱机计算并被 保存，然后在运行时使用。依据该调度，调度程序在每一个调度决策时刻调度作业运 行。采用这种方法，运行时的调度开销可被最小化。 通常选择在有规律的空白时刻做出调度决策。一种方法是用硬件定时器来实现周期 性做出调度决策的调度程序。这样一来，不需要调度程序干预就可以把定时器设置成周 期性地到期。当系统初始化后，调度程序选择并调度作业执行，直到下一个调度决策时 刻为止，然后阻塞自己，等待定时器到期。当定时器到期时，调度程序被唤醒，并重复 以上的动作。 ( 2 ) 加权的轮转调度方法 轮转调度方法常常用于调度分时应用。每个基于轮转调度的作业，在准备运行时都 加入一个先进先出( f i f o ) 队列。位于队列头的作业将最多执行一个时间片。如果在时 问片结束时作业没有完成，该作业就被抢占并放到队列的尾部，等待下一轮调度。当队 列里有n 个就绪作业时，每个作业在每n 个时间片上都能获得一个时l 旬片，这就是一 轮。 7 l i n u x 实时调度算法测试平台的研究与实现 加权轮转调度算法是依据基本轮转调度方案建立的 5 。这个算法不是让所有的就绪 作业平等地共享处理器，而是绘不同的作业以个不同的权值。权值是指分配给作业的 处理器时间段。 ( 3 ) 优先级驱动方法 优先级驱动算法是指永远不会有意使资源处于空闲状态的一大类调度算法。即资源 只在需要该资源的作业没有就绪可执行时才能处于空闲状态 7 。在作业释放和完成等事 件发生时，才能做出调度决策。非实时系统中所用的大部分调度算法都是优先级驱动 的。 基于优先级的调度算法可以分为如下两种类型： 1 静态优先级调度算法： 这种调度算法给那些系统中得到运行的所有进程都静态地分配一个优先级。静态优 先级的分配可以根据应用的属性来进行，比如任务的周期，用户优先级，或者其它的预 先确定的策略。r m ( r a t e - m o n o t o n i c ) 调度算法 2 ，8 ，9 是一种典型的静态优先级调度 算法，它根据任务的执行周期的长短来决定调度优先级，那些具有小的执行周期的任务 具有较高的优先级。 2 动态优先级调度算法： 这种调度算法根据任务的资源需求来动态地分配任务的优先级，其目的就是在资源 分配和调度时有更大的灵活性。非实时系统中就有很多这种调度算法，比如短作业优先 的调度算法。在实时调度算法中，e d f 算法 2 ，8 ，1 0 】是使用最多的一种动态优先级调度 算法，该算法给就绪队列中的各个任务根据它们的时限来分配优先级，具有最近的截止 期限的任务具有最高的优先级。 1 6 实时操作系统与通用操作系统的比较 由于实时操作系统与通用操作系统的基本设计原则差别很大，因此在很多资源调度 策略的选择上阻及操作系统实现的方法上两者都具有较大的差异，这些差异主要体现在 以下几点： ( 1 ) 任务调度策略 通用操作系统中的任务调度策略一般采用基于优先缴的抢先式调度策略，对于优先 级相同的进程则采用时间片轮转调度方式，用户进程可以通过系统调用动态地调整自己 的优先级，操作系统可根据情况调整某些进程的优先级。 8 大连理工大学硕士学位论文 实时操作系统中的任务调度策略目前使用最广泛的主要可分为两种，一种是静态表 驱动方式，另一种是固定优先级抢先式调度方式。 ( 2 ) 内存管理 关于虚存管理机蛊4 在上面已经进行了一些分析。为解决虚存给系统带来的不可预测 性，实时操作系统一般采用如下两种方式： 1 在原有虚存管理机制的基础上增加页面锁功能，用户可将关键页面锁定在内存中， 从而不会被s w a p 程序将该页面交换出内存 1 1 。这种方式的优点是既得到了虚存管理机 制为软件开发带来的好处，又提高了系统的可预测性。缺点是由于t l b 等机制的也是 按照注重平均表现的原贝q 进行的，因此系统的可预测性并不能完全得到保障； 2 采用静态内存划分的方式，为每个实时任务划分固定的内存区域 1 2 。这种方式的 优点是系统具有较好的可预测性，缺点是灵活性不够好，任务对存储器的需求一旦有变 化就需要重新对内存进行划分，此外虚存管理机制所带来的好处也丧失了。 目前市场上的实时操作系统一般都采用第一种管理方式。 ( 3 1 中断处理 在通用操作系统中，大部分外部中断都是开启的，中断处理一般由设备驱动程序来 完成。由于通用操作系统中的用户进程一般都没有实时性要求，而中断处理程序直接跟 硬件设备交互，可能有实时性要求，因此中断处理程序的优先级被设定为高于任何用户 进程。 但对于实时操作系统采用上述的中断处理机制是不合适的。首先，外部中断是环境 向实时操作系统进行的输入，它的频度是与环境变化的速率相关的，而与实时操作系统 无关。如果外部中断产生的频度不可预测，则一个实时任务在运彳亍时被中断处理程序阻 塞的时间开销也是不可预测的，从而使任务的实时性得不到保证i 立口果外部中断产生的 频度中可预测的，一旦某外部中断产生的频度超出其预测值f 如硬件故障产生的虚假中 断信号或预测值本身有误) 就可能会破坏整个系统的可预测性。其次，实时控制系统中 的各用户进程一般都有实时f 生要求，因此中断处理程序优先级高于所有用户进程的优先 级分配方式是不合适的。 一种较适合实时操作系统的中断处理方式为：除时钟中断外，屏蔽所有其它中断， 中断处理程序变为周期性的轮询操作【j 3 。采用这种方式的主要好处是充分保证了系统 的可预测性，主要缺点是对环境变化的响应可能不如上述中断处理方式快。另外轮询操 作在一定程度上降低了c p u 的有效利用率。另一种可行的方式是：对于采用轮询方式 无法满足需求的外部事件，采用中断方式，其它时删仍然采用轮询方式。但此时中断处 9 l i n u x 实时调度算法测试平台的研究与实现 理程序与所以其它任务一样拥有优先级，调度器根据优先级对处于就绪态的任务和中断 处理程序统一进行处理器调度。这种方式使外部事件的响应速度加快避免了上述中断方 式带来第二个问题，但第一个问题依然存在。 此外为提高时钟中断响应时间的可预测性，实时操作系统应尽可能少地屏蔽中断。 ( 4 ) 共享资源的互斥访问 通用操作系统一般采用信号量机制来解决共享资源的互斥访问问题。 对于实时操作系统，如果任务调度采用静态表驱动方式，共享资源的互斥访问问题 在生成运行时间表时已经考虑到了，在运行时无需再考虑。如果任务调度采用基于优先 级的方式，则传统的信号量机制在系统运行时很容易造成优先级倒置问题，即当一个高 优先级任务通过信号量机制访问共享资源时，该信号量己被一低优先级任务占有，而这 个低优先级任务在访问共享资源时可能又被其它一些中等优先级的任务抢先，因此造成 高优先级任务被许多具有较低优先级的任务阻塞，实时性难以得到保证。因此在实时操 作系统中，往往对传统的信号量机制进行了一些扩展，引入了如优先级继承协议、优先 级顶置协议等机制，较好地解决了优先级倒置的问题。 ( 5 ) 系统调用以及系统内部操作的时间开销 进程通过系统调用得到操作系统提供的服务，操作系统通过内部操作( 加上下文切 换等) 来完成一些内部管理工作。为保证系统的可预测性，实时操作系统中的所有系统 调用以及系统内部操作的时间开销都应是有界的，并且该界限是一个具体的量化数值。 而在通用操作系统中对这些时间开销则未做如此限制。 ( 6 ) 系统的可重入性 在通用操作系统中，核心态系统调用往往是不可重入的，当一低优先级任务调用核 心态系统调用时，在该时间段内到达的高优先级任务必须等到低优先级的系统调用完成 才能获得c p u ，这就降低了系统的可预测性。因此，实时操作系统中的核心态系统调用 往往设计为可重入的。 ( 7 ) 辅助工具 实时操作系统额外提供了一些辅助工具，如实时任务在最坏情况下的执行时间估算 工具、系统的实时性验证工具等，可帮助工程师进行系统的实时性验证工作。 1 7 典型实时操作系统介绍 下面就几种典型非l i n u x 家族的嵌入式系统的特点作一下介绍 ( 【) v x w o r k s l o 大连理_ _ | 二大学硕士学位论文 v x w o r k s 操作系统是美国w i n d r i v e r 公司推出的一种嵌入式实时操作系统。在著名 的火星探测车上和爱国者导弹的导航系统中都用到了该系统，多家著名的公司如 c i s c o ，3 c o m ，h p ，l u c e n t 等都是v x w o r k s 的主要商业客户，它的特点有： 1 高性能实时微内核 2 p o s i x 兼容 3 自由配置能力 4 友好的开发调试环境 5 广泛的运行环境支持 u c o s 和u c ，o s i i u c o s - i i 是美国人j e a nj l a b r o s s e 开发的实时嵌入式操作系统，在各国的许多重要 系统上都采用了u c o s i i ，它的特点有： 1 多任务抢占式内核 2 良好的可移植性 3 内存分块管理 4 开放源代码 ( 3 ) w i n d o w sc e m i c r o s o f tw i n d o w s c e 是一个实时操作系统，用来建造下一代智能移动和占用内存 小的设备，可应用范围广泛。它的特点有： 1 开发环境全面 2 高度模块化 3 实时性能支持 4 多媒体及网络和通信的支持 5 提供高级应用程序服务 6 可定制的图形设备界面 ( 4 ) q n x q n x 实时操作系统是加拿大q n x 软件系统有限公司的产品，q n x 操作系统在初 始设计时就致力于提供优秀的实时控制性能，经过多年的不断发展与推广，已经应用于 自动化、控制、机器人科学、电信、数据通信、航空航天、军用控制系统等领域。它的 特点有： l i n u x 实时调度算法测试平台的研究与实现 使用范围广，可在各种配置的系统上使用 良好的实时性 支持多种网络 1 2 大连理工大学硕士学位论文 2 l i n u x 操作系统 2 1l i n u x 系统的特点 l i n u x 操作系统在短短几年之内就得到了非常迅猛的发展，这与l i n u x 具有的良好 特性是分不开的。l i n u x 包含了u n i x 的全部功能和特性。简单得说，l i n u x 具有以下主 要特性 1 4 1 ： ( 1 ) 开放性 开放性是指系统遵循世界标准规范，特别是遵循开放系统互联( o s d 国际标准。 凡遵循国际标准所开发的硬件和软件，都能彼此兼容，可方便地实现互联。l i n u x 遵循 i e e ep o s i x 标准。 f 2 ) 多用户 多用户是指系统资源可以被不同用户各自拥有使用，即每个用户对自己的资源有特 定的权限，互不影响。l i n u x 和u n i x 都其有多用户的特性。 ( 3 ) 多任务 多任务是现代计算机最主要的一个特点。它是计算机同时执行多个程序，而且各个 程序的运行互相独立。l i n u x 系统调度每一个进程平等地访问微处理器。由于c p u 的处 理速度非常快，其结果是，启动的应用程序看起来好像在并行运行。事实上，从处理器 执行一个应用程序的一组指令到l i n u x 调度微处理器再次运行这个程序之间只有很短 的时间延迟，用户是感觉不出来的。 ( 4 ) 良好的用户界面 l i n u x 向用户提供了两种界面：用户界面和系统调用。l i m t x 的传统用户界面是基 于文本的命令行界面，即s h e l l ，它既可以联机使用，又可存在文件上脱机使用。s h e l l 有很强的程序运行能力，用户可方便地用它编制程序，从而为用户扩充系统功能提供了 更高级的手段。可编程s h e l l 是指将多条命令组合在一起，形成一个s h e l l 程序，这个程 序可以单独运行，也可以与其它程序同时运行。 系统调用给用户提供编程时使用的界面。用户可以在编程时直接使用系统提供的系 统调用命令。系统通过这个界面为用户程序提供低级、高效率地服务。 l i n u x 还为用户提供了图形用户界面。它利用鼠标、菜单、窗口、滚动条等功能， 给用户呈现一个直观、易操作、交互性强的图形化界面。 ( 5 ) 设备独立性 1 3 l i n u x 实时调度算法测试平台的研究与实现 设备独立性是指操作系统把所有外部设备统一当作文件看待，只要安装它们的驱动 程序，任何用户都可以像使用文件一样，操纵、使用这些设备，而不必知道它们的具体 存在形式。 具有设备独立性的操作系统，通过把每一个外围设备看作一个独立性的文件来简化 增加新设备的工作。当需要增加新设备时，系统管理员就在内核中增加必要的连接。这 种连接保证每次调用设备提供服务时，内核以相同的方式来处理它们。当新的及更好的 外设被开发并交付给用户时，操作允许在这些设各连接到内核后，就能不受限制地立即 访问它们。设备独立性的关键在于内核地适应能力。其它操作系统只允许一定数量或一 定种类的外部设备连接，而具有设备独立性的操作系统能够容纳任意种类及任意数量的 设备，因为每一个设备都是通过其与内核地专用连接独立进行访问的。 l i n u x 是具有设备独立性的操作系统，它的内核具有高度适应能力，随着更多程序 员加入l i n u x 编程，会有跟多硬件设备加入进来，另外，由于用户可以免费得到l i n u x 的源代码，因此，用户可以修改内核源代码，以便适应性增加的外部设备。 ( 6 ) 丰富的网络功能 完善的内置网络是l i n u x 在通信和网络功能方面优于其它操作系统。其它操作系统 不包含如此紧密地与内核结合在一起的连接网络的能力，也没有内置这些联网特性的灵 活性，而l i n u x 为用户提供了完善的、强大的网络功能。 支持i n t e m e t 是其网络功能之一。l i n u x 免费提供了大量支持i n t e m e t 的软件。 i n t e r n e t 是在u n i x 领域中建立并繁荣起来的，在这方面使用l i n u x 是相当方便的，用户 利用l i u u x 可以与世界上的任何人通过i n t e m e t 网络进行通信。 文件传输是其网络功能之二。用户能通过一些l i n u x 命令完成信息或文件的传输。 远程访问是其网络功能之三。l i n u x 不仅允许进行文件和程序的传输，它还为系统 管理员和技术人员提供了访问其它系统的窗口。利用这种远程访问的功能，一位技术人 员能够有效地为多个系统服务，即使那些系统位于相距很远的地方。 f 7 ) 可靠的系统安全 l i n u x 采取了许多安全技术措施，包括对读写进行权限控制带保护的子系统、 审计跟踪、核心授权等，这为网络多用户环境中的用户提供了必要的安全保障。 ( 8 ) 良好的可移植性 可移植性是指将操作系统从一个平台转移到另一个平台使它仍然能按其自身的方式 运行的能力。l i n u x 是一种可移橱陛的操作系统，能够在从微型计算机到大型计算机得 1 4 大连理： 大学硕士学位论文 任伺环境中和任何平台上运行。可移植性为运行l i n u x 的不同计算机平台与其它任何机 器进行准确而有效的通信提供了手段，不需要另外增加特殊的、昂贵的通信接口。 目前l i n u x 已经可以在数十种3 2 位和6 4 位芯片中运行。 2 。2l i n u x 内核结构 内核是l i n u x 操作系统的内部核心程序，它向外部提供了对计算机设备的核心管理 调用。操作系统的代码可以分成两部分。内核所在的地址空间称做内核空间。外部的琶： 理程序与用户进程所占据的地址空间称为外部空间。通常一个程序会跨越两个空间。当 执行到内核空间的代码时称程序处于内核态，当执行到外部空间代码时称处于用户态。 l i n u x 内核采用单一内核结构，如图2 1 所示 用户蔓耀 土 。l 用户空间 系统调用 k ， 1r 内梭l 猎i内梭g 掰2 内 内核膝务3 l r 硬燃 图2 1l i n u x 单一体系内核结构 f i g u r e 2 1s i n g l es y s t e mk e r n e l a r c h i t e c t u r ei nl i n u x 1 5 核空问 l m l 实时调度算法测试平台的研究与实现 在l i n u x 中，可以动态装入和卸载内核中的部分代码。l i m l = x 中将这样的代码段落 称为模块( m o d u l e ) 。并对模块给予强有力的支持。在l i n u x 中，可以在需要时自动装 入和卸载模块。 l i n u x 内核包括进程管理、定时器、中断管理、系统调用、内存管理、模块管理、 虚拟文件系统接口、文件系统、设各驱动程序、进程间通信、网络管理、系统初始化等 程序。 2 2 1 进程调度 l i n u x 进程调度是基于优先级的。进程调度由s c h e d u l e ( ) 函数从进程就绪队列中选 出一个进程投入运行。为了适应各种不同应用的需要，内核在此基础上实现了三种不 同的策略：s c h e d 、以及 。每个进程都有自己适用_ f i f o s c h e dr r s c h e d o t h e r 的调度策略，并且，进程还可以通过系统调用s c h e ds e t s c h e d u l e r 0 。设定自己适用的调 度策略。其中s c h e df 口o 适合于时间性要求比较强、但每次运行所需的时间比较短 的进程，实时的应用大都具有这样的特点。s c h e dr r 中的“r r ”表示“r o u n d r o b i n ”，是轮流的意思，这种策略适合比较大、也就是每次运行需时较长的进程。而 除此之外的s c h e do t h e r ，则为传统的调度策略，比较适合于交互式的分时应用。 这几种调度策略是通过各个进程的优先级高低区分的。 ( 1 ) 非实时优先级 每个l i n u x 进程都有一个优先级，这是从l 到4 0 的一个整数，其值存储在s t r u c t t a s k s t r u c t 结构的p r i o r i t y 成员中。它的范围使用p r i oi v l i n 和p r i o _