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

西南交通大学硕士研究生学位论文第1 页 摘要 作为类u n i x 操作系统，l i n u x 操作系统除了保持u n i x 稳定、高效 等优势之外，系统自身的功能更是不断发展，日益成熟。相对于其他操作 系统而言，l i n u x 可以按照需要修改源代码，并且具有支持多种硬件平台、 功能可剪裁等诸多优点，在实时领域内也有着广泛的潜在应用前景。 但是由于l i n u x 是一种通用操作系统，而不是一个真正的实时操作系 统，而只能称其为软实时操作系统，而不是一种强实时系统。其标准内核 不支持事件优先级和抢占实时特性，没提供很多嵌入式应用程序所需要的 可预测响应时间( p r e d i c t a b l er e s p o n s et i m e s ) 等。所以，在进行嵌入式l i n u x 系统动态扩展性研究开发时，首要的问题是扩展l i n u x 的实时性能。 由于l i n u x 主要在三个方面不利于实时性的增强：即过长的中断封锁 时间，非抢占式的内核，耗尽的、机会均等的调度策略，本文结合目前的 常用的改造内核的方法，提出新的修改方式，重点在l i n u x 以下几个方面 着手： 内核的不可抢占性：本文主要从抢占锁、互斥锁，中断处理与调度 函数四个方面提出修改方法。 中断线程化：对中断线程化进行研究，将其应用于2 6 内核中。 调度器设计：根据e d f 实时调度算法的相关思想，设计实现了一个 实时调度器，将其应用于l i n u x2 4 内核，并通过验证测试，证明改进后的 系统较好地解决了普通l i n u x 在实时性方面存在的不足，其能够在实时领 域有较好的应用。 关键字l i n u x ；实时；中断；抢占；内核；调度 西南交通大学硕士研究生学位论文第1 i 页 a b s t r ac t a sac a t e g o r yo fu n i xo p e r a t i n gs y s t e m ，l i n u xo b t a i n ss o m ef e a t u r e sl i k e s t a b i l i t ya n dh i g he f f i c i e n c yw h i c ha r ef e a t u r e so fu n i xo p e r a t i n gs y s t e m ； m e a n w h i l e ，t h ec a p a b i l i t i e so fl i n u xb e c o m em o r ep r o g r e s sa n dm a t u r e c o m p a r ew i t ho t h e ro p e r a t i n gs y s t e m s ，l i n u xc a nr e v i s ei t ss o u r c ec o d e s a c c o r d i n g t od i f f e r e n t d e m a n d s ，s u p p o r ts o m ea r c h i t e c t u r ep l a t f o r m sa n d c u s t o m i z es o m ef u n c t i o n s t h e s ef e a t u r e sm a k el i n u xh a v ea p o t e n t i a l p r o s p e c ti nr e a l t i m ea p p l i c a t i o n b u ta sag e n e r a lo p e r a t i o ns y s t e ma n dl i n u xi sn o tar e a l l yr e a lt i m e o p e r a t i o ns y s t e m ，s oi t i so n l yn a m e ds o f tr e a lt i m ea n di sn o th a r dr e a lt i m e o p e r a t i o ns y s t e m i t ss t a n d a r dk e r n e lh a sn o ts u p p o r t e de v e n tp r i o r i t ya n d p r e e m p t e dr e a lt i m e ，a tt h es a m et i m e ，i th a sn o tp r o v i d e dp r e d i c t a b l er e s p o n s e t i m ew h i c hh a sb e e nn e e d e df o rm o s to fe m b e d d e da p p l i c a t i o n s oi ti s i m p o r t a n tt oe x t e n di t sr e a lt i m ep e r f o r m a n c ed u r i n gd e v e l o p i n ge m b e d d e d l i n u xs y s t e m ： b u tt h e r eh a st h r e ea p p a r e n ts h o r t c o m i n g sa sag e n e r a lo p e r a t i o ns y s t e m ， i e 。，l o n gi n t e r r u p t e dl o c kt i m e ，u n p r e e m p t e dk e r n e l ，f a i rs c h e d u l ep o l i c y , s o t h i sp a p e rw i l ld i s c u s sn e x ts e v e r a lp a r t st oi m p r o v ei t sr e a lt i m ep e r f o r m a n c e i nf a v o ro fd e v e l o p i n gt h ee m b e d d e ds y s t e m ： u n p r e e m p t e dk e r n e l ：t h i sp a p e rp u t sf o r w a r dt h em o d i f y i n gi d e a sf r o m p r e e m p tl o c k ，m u t e xl o c k ，i n t e r r u p tp r o c e s sa n ds h e d u l ef u n c t i o n s c h e d u l e a l g o r i t h m ：i ts e tu pan e ws h e d u l em o d e la n dr a i s e san e ws h e d u l ea l g o r i t h m f r o mt h ec u r r e n ts h e d u l eb u g t h r e a d e di n t e r r u p t ：s t u d yt h r e a d e d i n t e r r u p t a n dt h r e a d e d i n t e r r u p t i s a p p l i e dt ot h e2 6k e r n e l s c h e d u l e rd e s i g n ：t h i sp a p e rd e s i g n sa n dr e a l i z e sar e a lt i m e s c h e d u l e r b a s e do ne d fi d e a a f t e rs o m et e s t s ，i tp r o v e st h a tt h en e wr e a lt i m es c h e d u l e r h a sb e t t e re f f e c ti nr e a lt i m ep e r f o r m a n c et h a nu n i m p r o v e dl i n u x ，a n dt h en e w o n ec a nb eu s e dw e l li nr e a lt i m ef i e l d k e y w o r d sl i n u x ：r e a lt i m e ：i n t e r r u p t ；p r e e m p t ：k e r n e l ：s h e d u l e 西南交通大学囱南父遗大罕 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规 定，同意学校保留并向国家有关部门或机构送交论文的复印件和 电子版，允许论文被查阅和借阅。本人授权西南交通大学可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采 用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 1 保密口，在5 年解密后适用本授权书； 2 不保密囹，适用本授权书。 学位论文作者签名：赤勾中良 e l 期：2 0 0 罗年歹月2 oe l 指导教师签名：新翻4 e 日期：l - 矿年岁月z ，日 西南交通大学学位论文创新性声明 本人郑重声明：所呈交的学位论文，是在导师指导下独立进行研究工 作所得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个 人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和 集体，均已在文中作了明确的说明。本人完全意识到本声明的法律结果由 本人承担。 西南交通大学硕士研究生学位论文第1 页 第1 章绪论 1 1 嵌入式系统的定义及分类 嵌入式系统被定义为：以应用为中心，以计算机技术为基础，软硬件 可裁剪，适用于应用系统对功能、可靠性、成本、体积、功耗有严格要求 的专用计算机系统【。根据不同的分类标准，嵌入式系统有不同的分类方 法。由于嵌入式系统由硬件和软件两大部分组成，所以其分类也可以从这 两方面划分。 1 1 1 嵌入式系统的硬件 从硬件方面来讲，各式各样的嵌入式处理器是嵌入式系统硬件中最核 心部分。目前，世界上具有嵌入式功能的特点的处理器已经超过1 0 0 0 种， 主要分为以下几类【z j ： 1 嵌入式微控制器( m i c r o c o n t r o l l e ru n i t , m c u ) 嵌入式微控制器的典型代表是单片机。从2 0 世纪7 0 年代出现到今天， 4 位、8 位、1 6 位的单片机在各个领域有着极其广泛的应用。由于m c u 低廉的价格、优良的性能、以及开发手段的简易性，m c u 拥有大量的品种， 并占有嵌入式系统约7 0 的市场份额。i n t e l 、m o t o r o l a 、p h i l i p s 等公司 的产品为其中的代表。 2 嵌入式d s p 处理器( d i g i t a ls i g n a lp r o c e s s ，d s p ) d s p 处理器是专门用于信号处理方面的处理器，其在系统结构和指令 算法方面进行了特殊设计，具有很高的编译效率和指令运行速度。在数字 滤波、f f t 、频谱分析等各种仪器上获得大规模的应用。自进入9 0 年代以 后，d s p 发展到了第5 代产品，集成度进一步增加，使用范围也更加广阔。 目前最流行的是t i 公司的t m s 3 2 0 c 2 0 0 0 c 5 0 0 0 系统。 3 嵌入式微处理器( m i c r o p r o c e s su n i t ，m p u ) 它是由通用计算机中的c p u 演化而来的，特征是具有3 2 位以上的处 理器，具有较高的性能，其价格也较高。目前主要的嵌入式处理器类型有 3 8 6 e x 、s c 4 0 0 、p o w e r p c 、6 8 k 、a r m s t r o n ga r m 系统等。 4 嵌入式片上系统( s y s t e mo nc h i p ，s o c ) 片上系统s o c 是追求产品系统最大包容的集成器件，是目前嵌入式应 用领域的热门话题之一。其最大的特点是成功实现了软硬件无缝连接。 西南交通大学硕士研究生学位论文第2 页 1 1 2 嵌入式系统的软件 目前嵌入式系统的软件主要有两大类：实时系统和分时系统。所谓实 时系统，是指计算的正确性不仅取决于程序的逻辑正确性，也取决于结果 产生的时间，如果系统的时间约束条件得不到满足，系统将会出错。 随着嵌入式系统的发展，在市场上占有较大份额的几种嵌入式操作系 统为：v x w o r k s 、r t - l i n u x 、u c l i n u x 、w i n c e 、0 n x 、p a l mo s 等。 1 2 嵌入式l in 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 ，从左到右依次 是：m o t o r o l ae 6 8 0 ip d a h a i e rn 6 0 ，e r i c s s o nc o r d l e s sw e b p a d p h o n e ，s h a r p 1 3 本课题的研究目的及意义 嵌入式工业的基础是以应用为中心的芯片设计和面向应用的软件开 发。中国将是世界上最大的r t o s 市场之一。就目前的技术而言，我国的 嵌入式l i n u x 的研究成果与市场的真正需求还有一段差距。因此，要开发 出真正成熟的嵌入式强实时l i n u x ，还需要我们不断的努力。 由于l i n u x 当初设计时是一种通用的操作系统，从而在实时性方面一 直差强人意，本文主要在以下几个方面进行研究和改进： 内核的不可抢占性：本文主要从抢占锁、互斥锁、中断处理与调度函 数四个方面提出自己的修改方法。 中断线程化：本文研究中断线程化技术的实现，将其应用于2 6 内核中。 调度器设计：根据e d f 实时调度算法的相关思想，设计实现了一个实 时调度器，并通过验证测试，证明改进后的系统较好地解决了普通l i n u x 西南交通大学硕士研究生学位论文第3 页 在实时性方面存在的不足，其能够在实时领域有较好的应用。 本课题将重点深入研究标准l i n u x 内核实时性的改进和完善，从而对 其标准内核进行部分改造，提出新的改进方法，以提高l i n u x 实时性，使 其内核更加完善以适应嵌入式系统。 1 4 本课题的内容及结构 本课题由六部分组成。从简单的嵌入式系统介绍入手，一层层剖析其 内容，其中包括了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 章对中断线程化技术进行研究，并把它应用到2 6 内核。 第5 章对e d f 进程调度算法进行了研究与分析，详细介绍了目前l i n u x 采用的调度策略、原理及常用的实时调度算法，最后设计调度器，把e d f 应用到2 4 内核中，使其更适应实时系统。 第6 章是结束语。对本文的工作进行总结。 西南交通大学硕士研究生学位论文第4 页 第2 章嵌入式操作系统及嵌入式l in 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 内核的实时性研究。 2 1 实时操作系统概述 2 1 1 实时系统与实时操作系统 实时系统可以这样定义：实时系统能在给定的时限( d e a d l i n e ) 勾对外部事 件作出正确的响应。进一步讲，实时系统不仅要求系统对外部事件的响应是 准确，而且要求系统响应的时间和时序也必须是严格保证的。按照这个定义 下的实时系统中，实时任务的性能在时限到达的时刻急剧下降，如图2 1 中 的系统a ，这就要求实时任务必须在时限时刻之前必须正确完成，否则会引 起整个系统性能的严重恶化，甚至会导致不可预料的灾难性后果。而图中的 系统b 和系统c 均不符合这种定义，在时限到来时刻，由于实时任务未能完 成，系统的性能虽然下降，系统仍然处于有效的状态，是非实时系统。 任 务 性 能 任 务 性 能 i i 任 务 性 能 - k 任务时限任务时限任务时限 d e a d l i n e sd e a d l i n e sd e a d l i n c s 系统a 实时系统 系统b 非实时系统系统c 非实时系统 。 图2 - 1 实时系统与非实时系统 运行于实时系统之上，符合系统实时性能要求的操作系统就是实时操作 系统，除了具备操作系统的一般特点之外，实时操作系统尤其强调对系统实 时任务实时运行的充分保证。 有趣的是，如果严格按照定义，任何我们已知的操作系统都符合该定义， 可以被认为是实时操作系统。假如我们将任务的时限定义的足够长，一个小 时、一天甚至是一年乃至更长，那么恐怕任何一个操作系统都符合这个定义 的要求。这个推论是有道理的，但没有任何的实际意义，只能说明我们事实 上无法给出实时操作系统的一个严格定义。 西南交通大学硕士研究生学位论文第5 页 实际上操作系统的实时应该被认为是一种设计思路，任何一个实时操作 系统都与一个具体的实时系统相关，针对这个特定的实时系统，依据系统的 需求，严格定义了需要实现的各种实时任务，包括任务的执行时序、任务时 限等，那么符合我们这种特定需求的操作系统，我们就认为它是实时操作系 统。 为了符合这种特定的需求，实时操作系统的设计所遵循的思路应该是： 在操作系统控制下的实时任务的运行必须有着严格的时序和完成时限；换一 句话说，实时操作系统的控制行为必须是可预测的、有严格的时间保证的， 系统能对运行的最好和最坏情况作出精确的估计。 2 1 2 软实时与硬实时 实时系统又可以分为“硬实时系统 和“软实时系统 。【3 】硬实时和软实 时的区别就在于对外界的事件做出反应的时间。硬实时系统必须及时的对事 件做出反应，绝对不能错过事件处理的时限( d e a d l i n e ) 情况，否则将导致重大 事故，例如，飞行器自动驾驶和导航系统、核工业控制系统等。软实时系统 是指，如果在系统负荷较重的时候，允许发生错过时限( d e a d l i n e ) 拘情况而且 不会造成太大的危害，例如，程控电话系统、大多数家用电子设备。 2 1 3 实时操作系统的主要构成 实时操作系统主要由以下几个模块构成m ： ( 1 ) 任务管理模块 对于实时操作系统，操作系统内核调度的基本单位是任务。从操作系统 的角度看来，任务和分时操作系统中的进程( 或者线程) 具有等同的地位， 在逻辑上看来它们是概念上等同的。所以任务同样由任务控制块、程序区、 数据区、堆栈区组成，对于多数实时操作系统而言，堆栈往往又分为系统堆 栈和用户堆栈。在实时操作系统中任务的驱动一般是基于消息或者事件的， 也即任务的设计按照依次处理可能收到的消息和事件，是一个反复循环的过 程。 实时任务在实时操作系统中有四个状态：运行( e x e c u t i n g ) ，就绪 ( r e a d y ) ，挂起( s u s p e n d e d ) 和睡眠( d o r m a n t ) 。任务的状态变迁如图2 2 所示。 西南交通大学硕士研究生学位论文第6 页 唤 等 图2 2 实时系统任务状态迁移 运行：获得对c p u 的控制权。 就绪：任务被唤醒进入等待队列等待被调度。 挂起：任务被阻塞或者被移出等待队列。 睡眠：任务完成，或者因运行错误被清除。 系统中只能有一个任务处于运行状态。系统中的所有任务按照级别分别 通过执行时间片的获取来取得对c p u 的访问控制权。 实时操作系统中的任务管理模块的功能就是多任务的管理和基于优先级 的任务调度。任务管理模块中的实时调度算法确定了不同任务的优先级别和 相应的执行次序。 ( 2 ) 任务间的同步和通信 与分时操作系统一样，实时操作系统支持多任务，拥有任务间的通信和 同步机制，包括：消息、事件、信号量，有的实时操作系统还提供了共享内 存的任务间通信机制。消息机制用于多任务协同时任务间共享信息的传递。 事件和信号量则是经典的任务间同步机制。实时操作系统和分时操作系统在 信号量同步机制上有一个明显的区别，实时操作系统解决了信号量机制中的 优先级倒置问题 4 1 。 ( 3 ) 内存管理 现在的绝大多数嵌入式处理器都具有内存管理单元( m m u ) ，所以实时 操作系统需要根据处理器的m m u 设计内存管理模块，一般包括实模式和 保护模式。此外在实时系统中，内存的管理需要更加高效和优化。 ( 4 ) 实时时钟模块 相对于一般操作系统而言，实时操作系统的实时时钟模块更为强大，是 实时调度的基础。灵活的、高精度的实时时钟服务是实时操作系统的一大特 点，包括定时唤醒、定时事件机制和定时消息机制。 西南交通大学硕士研究生学位论文第7 页 ( 5 ) o e 断管理模块 对于实时操作系统中断的操作和管理是一个基本和核心的功能，直接关 系到系统的实时响应性能。因此中断服务程序要求设计的更短小精悍，中断 禁止时间也要求更短。 2 1 4 实时操作系统的评价 实时操作系统由于对于事件响应的特殊要求，评判一个实时操作系统优 劣的标准有其特殊的地方，主要是其对外部实时事件实时响应特性和操作系 统自身行为的可预测性。 考核操作系统的实时性能可以从任务调度机制、调度算法、中断处理方 式和内存管理机制等几个主要影响实时性能的方面考虑。一般来讲，抢占式 调度优于非抢占式调度，调度必须是基于任务优先级的，任务调度算法必须 是实时调度算法，比如：单调速率算法和时限驱动算法；内存管理必须具有 内存锁定功能以减少任务换入换出内存带来的时延；中断处理机制必须保证 拥有很低的最大中断禁止时间。 最直观的评价方法就是通过测试环境和测试程序对实时操作系统进行系 统响应延迟时间的测量，韦伯斯特计算机词典中关于延迟的定义是“激励和 响应之间的间隔时间”。对于l i n u x 操作系统而言，其系统响应延迟时间就 是指系统输入( 激励) 到相应的任务处理( 响应) 所延迟的时间。在实时计 算的应用中，我们希望操作系统的延迟越低越好。 一2 1 5 衡量r t o s 实时性能的重要指标 通常，判断一个操作系统是否是一个实时操作系统，主要有以下几个指 标衡量： 1 确定性( d e t e r m i n i s t i c ) 在实时操作系统中，在一定的条件下，系统调用的运行时间可以预测。 这并不是指所有系统调用都总是执行一个固定长度的时间，而是指不论系统 负载如何，系统调用的最大执行时间可以确定。 2 可抢占( p r e e m p t i v e ) 一实时操作系统应该是可抢占的。抢占是指当系统处于核心态运行时，允 许任务的重新调度。换句话说就是指正在执行的任务可以被打断，让另一个 任务运行。抢占提高了应用对异步事件的响应性能力。操作系统内核可抢占 并不是说任务调度在任何时候都可以发生。例如当一个任务正在通过一个系 西南交通大学硕士研究生学位论文第8 页 统调用访问共享数据时，重新调度和中断都被禁止。可抢占内核如图2 - 3 所 示。 黝。l s r 阂h i g h p f i o r i t y t a s 。蕊沁心心阏t h eh i g h v r i o r i t vt a s kr e a d y7 湖 缓 m l 一一- l l i j d - - 3 上下文切换时f 司( c o n t e x ts w i t c h ) 。 多任务系统中，上下文切换是指c p u 的控制权由运行任务转移到另外一 个就绪任务时所发生的事件，当前运行任务转为就绪或者挂起、删除状态， 另一个被选定的就绪任务成为当前任务。上下文切换时间包括保存当前任务 的运行环境时间，恢复将要运行任务的运行环境时间。 4 中断延j 尽( i n t e r r u p tl a t e n c y ) 中断延迟是指从硬件中断发生到开始执行中断处理程序第一条指令之间 的这段时间。影响中断延迟的最大因素就是系统关中断的时间。 5 调度延迟( s c h e d u l i n gl a t e n c y ) 调度延迟是指当一个事件引起更高优先级的任务就绪到这个任务开始运 行之间的时间。即一个任务被触发后，由就绪到运行的时间。调度延迟由系 统的不可抢占时间和具体的调度算法决定。 其中，确定性和可抢占是r t o s 必须满足的条件；上下文切换时间和中 断延迟是衡量操作系统实时性的两个最重要时间指标；上下文切换时间又依 赖于中断延迟和调度延迟。 2 2 嵌入式l in u x 的实时性不足分析 标准l in u x 内核制约实时性的因素 标准l i n u x 有几个机制严重地影响了实时性： 1 内核不可抢占 西南交通大学硕士研究生学位论文第9 页 在l i n u x2 4 和以前的版本，内核是不可抢占的，也就是说，如果当前任 务运行在内核态，即使当前有更紧急的任务需要运行，当前任务也不能被抢 占。因此，那个紧急任务必须等到当前任务执行完内核态的操作返回用户态 后或当前任务因需要等待某些条件满足而主动让出c p u 才能被考虑执行，这 很明显严重影响抢占延迟。 在1 , i n u x2 6 中，由于内核已经可以被抢占，因而实时性得到了加强。但 是内核中仍有大量的不可抢占区域，如自旋锁( s p i n l o c k ) 保护的临界区，以及 一些使用p r e e m p t失效抢占的临界区。disable 2 中断关闭 l i n u x 在一些同步操作中使用了中断关闭指令，内核进程经常关闭中断 以尽快完成自己的任务。如果低优先级的进程关闭了中断，那么即使有高优 先级实时进程的中断发生系统也将无法响应。中断关闭将增大中断延迟，降 低系统的实时性。 3 自旋锁( s p i n l o c k ) 自旋锁是在可抢占内核和s m p 情况下共享资源的一种同步机制，一般地 一个任务对共享资源的访问是非常短暂的，如果两个任务竞争一个共享的资 源时，没有得到资源的任务将自旋等待另一个任务，直到该任务使用完共享 资源。这种锁机制是非常高效的，但是在保持自旋锁期间将失效抢占，这意 味着抢占延迟将增加。在2 6 内核中，自旋锁的使用非常普遍，有的甚至对 一个数组或链表的遍历过程都使用自旋锁。因此抢占延迟非常不确定。 4 大内核锁 由于历史原因，内核一直保留有几个大内核锁，大内核锁实质上也是一 种自旋锁，但是它与一般的自旋锁的区别是，它是用于同步整个内核的，而 且一般该锁的保持时间较长，即抢占失效时间长，因此它的使用将严重地影 响抢占延迟。 5 中断总是最高优先级的 在l i n u x 中，中断( 包括软中断) 是最高优先级的，不论在任何时刻， 只要产生中断事件，内核将立即执行相应的中断处理函数以及软中断，等到 所有挂起的中断和软中断处理完毕后才执行正常的任务。因此在标准的 l i n u x 系统上，实时任务根本不可能得到实时性保证。例如，假设在一个标 准l i n u x 系统上运行了一个实时任务( 即使用了s c h e df i f o 调度策略并且 设定了最高的实时优先级) ，但是该系统有非常繁重的网络负载和i o 负载， 那么系统可能一直处在中断处理状态而没有机会运行任何任务，这样实时任 西南交通大学硕士研究生学位论文第1 0 页 务将永远无法运行，抢占延迟将是无穷大。因此，如果这种机制不改，实时 l i n u x 将永远无法实现。 6 调度算法和调度点 在l i n u x2 4 和以前的版本，调度器的时间复杂度是o ( n ) 的，而且在s m p 的情况下性能低，因为所有的c p u 共享一个任务链表，任何时刻只能有一个 调度器运行。因此，抢占延迟很大程度上来于当前系统的任务数，具有非常 大的不确定性和不可预测性。在2 6 内核中引入的o ( 1 ) 调度器很好地解决了 这些问题。 7 时钟粒度粗糙。时钟管理是操作系统的脉搏，任务的执行和中止在很 多情况下都是由时钟直接或间接唤起的，它还是进程调度的重要依据。l i n u x 的周期模式定时器频率仅为1 0 0 h z ，远不能满足实时应用的要求。 此外，即使内核是可抢占的，也不是在任何地方都可以发生调度，例如 在中断上下文，一个中断处理函数可能唤醒了某一高优先级进程，但是该进 程并不能立即运行，因为在中断上下文不能发生调度，中断处理完了之后内 核还要执行挂起的软中断，等它们处理完之后才有机会调度刚才唤醒的进程。 在标准l i n u x 内核中，调度点( 有意安排的执行任务调度的点) 并不多，对 2 4 和2 6 内核测试的结果表明，缺乏调度点是影响l i n u x 实时性的一个因素。 2 3 常见的嵌入式实时操作系统分析 操作系统是计算机系统中的一个系统软件，它管理和控制计算机系统中 的硬件及软件资源，合理的组织计算机工作流程，以便有效地利用这些资源， 为用户和开发者提供一个功能强大、使用方便的工作环境。操作系统组织和 控制应用程序的执行，是应用程序和计算机硬件之间的接口。现代的操作系 统大多具备对多任务的支持能力。实时操作系统除了具备上述有关操作系统 的基本特点之外，对实时任务有力的支持是其最大的特点和最重要的评判依 据。 2 3 1r t - lid m x r t - l i n u x 是新墨西哥科技大学的研究成果。它的基本思想是为了在 l i n = 系统中提供对于硬实时的支持，它实现了一个微内核的小的实时操作 系统，而把普通l i n u x 系统作为一个该操作系统中的一个低优先级的任务来 运行。另外普通l i n u x 系统中的任务可以通过f i f o 和实时任务进行通信。 r t - l i n u x 的工作原理如图2 - 4 所示。 西南交通大学硕士研究生学位论文第1 1 页 非非非 实 实实f 1 f o 时时时 实实 实 任 任任 共享内存 时时时 务 务务 任任 任 务务务 lil l i n u x 内核 r t - l i n u x 实时内核 底层硬件 图2 - 4r t - l i n u x 工作原理图 r t - l i n u x 的关键技术是通过软件来模拟硬件的中断控制器。当l i n u x 系 统要封锁c p u 的中断时时，r t - l i n u x 中的实时子系统会截取到这个请求， 把它记录下来，并判断是否由实时子系统中的中断例程来处理还是传递给普 通的l i n u x 内核进行处理，实际上并不真正封锁硬件中断，这样就避免了由 于封中断所造成的系统在一段时间没有响应的情况，从而提高了实时性。另 外，普通l i n u x 系统中的最小定时精度由系统中的实时时钟的频率决定，一 般l i n u x 系统把该时钟设置为每秒来1 0 0 个时钟中断，所以l i n u x 系统中一 般的定时精度为1 0 m s ，即时钟周期是1 0 m s ，而r t l i n u x 通过把系统的实时 时钟设置为单次触发状态，可以提供十几个微秒级的调度粒度。r t - l i n u x 实时子系统中的任务调度可以采用r m 、e d f 等优先级驱动的算法，也可以 采用其他调度算法。 r t - l i n u x 对于那些在重负荷下工作的专有系统来说，确实是一个不错的 选择，但他仅仅提供了对于c p u 资源的调度，并且实时系统和普通l i n u x 系 统关系不是十分密切，这样的话，开发人员不能充分利用l i n u x 系统中已经 实现的功能，如协议栈等。所以r t - l i n u x 适合于工业控制等实时任务功能简 单，并且有硬实时要求的环境中，但如果要应用于多媒体处理中还需要做大 量的工作。 西南交通大学硕士研究生学位论文第1 2 页 2 3 2r e d - l i n u x r e d l i n u x 是加州大学i r v i n e 分校开发的实时l i m l x 系统，它把对实时 调度的支持和l i m l x 很好地实现在同一个操作系统内核中。它同时支持三种 类型的调度算法，即：t i m e d d v e n 、p d o r i t y - d i r v e n 、s h a r e - d r i v e n 。 为了提高系统的调度粒度，r e d l i n u x 从r t - l i n u x 那儿借鉴了软件模拟 中断管理器的机制，并且提高了时钟中断频率。当有硬件中断到来时， r e d l i n u x 的中断模拟程序仅仅是简单地把到来的中断放到一个队列中进行 排队，并不执行真正的中断处理程序。 另外为了解决l i n u x 进程在内核态不能被抢占的问题，r e d l i n u x 在 l i n u x 内核的很多函数中插入了抢占点原语，使得进程在内核态时，也可以 在一定程度上被抢占。通过这种方法提高了内核的实时特性。 r e d l i n u x 的设计目标就是提供一个可以支持各种调度算法的通用的调 度框架，该系统给每个任务增加了如下几项属性，并把它们作为进程调度的 依据： p d o r i t y ：作业的优先级；s t a r t - t i m e ：作业的开始时间； f 试s h t i m e ：作业的结束时间； b u d g e t ：作业在运行期间所要使用的资源的多少； 通过调整这些属性的取值及调度程序按照什么样的优先顺序来使用这些 属性值，几乎可以实现所有的调度算法。这样的话，可以把三种不同的调度 算法无缝、统一地结合到了一起。r e d l i n u x 调度程序的框架结构如图2 5 所示。 西南交通大学硕士研究生学位论文第1 3 页 图2 - 5r e d - l i n u x 调度框架 r e d l i n u x 的调度程序由两部分组成，其中s c h e d u l ea l l o c a t o r 初始化到 来的j o b 中的属性值；s c h e d u l ed i s p a t c h e r 根据j o b 的属性值选择一个j o b 进 行执行。 2 3 3qlin u x q l i n u x 是由a t & t 、德州大学分布式多媒体计算实验室和马萨诸塞大学 高级系统软件实验室联合开发出来的一种软实时( s o f t r e a l t i m e ) 核心。它能够 为实时多媒体应用提供q o s 支持。系统结构如图2 6 所示。 q l i n u x 实现了近年来操作系统领域内一些最新的研究成果，包括： h s f q 资源调度算法( h i e r a r c h i c a ls t a r t t i m ef a i rq u e u i n g ) ； 网络包的延迟处理技术( l a z y r e c e i v e rp r o c e s s i n g ：l r p ) ； c e l l o 磁盘调度算法； 西南交通大学硕士研究生学位论文第1 4 页 h s f q 资源调度算法由由德州大学的p a w a ng o y a l 等人提出，它采用了 一种分级调度的思想，先把资源在不同的应用类别之间进行按比例分配，并 在应用类别之间提供对于资源使用的隔离，同时在每一个应用类别中还可以 使用不同的资源调度算法。这样做的目的是为了在多媒体系统中提供q o s 支 持。 l r p 技术是一种新颖的设计o s 网络子系统的思想，它由r i c e 大学计算 机系的p e t e rd r u s c h e l 等人提出，其目的是为了解决普通u n i x 和类u n i x 系统 中网络包接收的问题。 传统的u n i x 系统没有对到来的网络包的协议处理的显式调度，它们一般 采用中断驱动的机制。当网卡有中断时，c p u 就立刻进行一系列由网卡中断 程序启动的包接收和协议处理操作，把最终的数据送给等待接收的进程，并 唤醒该进程。但这种处理方式会影响应用程序资源调度的性能，并在系统处 于过载状态时可能会引起一些应用层任务的饥饿，降低网络吞吐率，甚至会 让系统没有响应。为了解决这些问题，l r p 的核心思想就是每一个s o c k e t 有一个口包的队列，只有当上层应用程序请求数据时才进行协议处理，同时 对协议处理操作以请求数据的应用程序的优先级进行显式的调度。通过这种 途径增强了资源调度的公平性，能够提供一定程度的流量隔离，同时能够提 高系统过载状态时的吞吐量。 c e l l o 磁盘调度算法由德州大学p r a s h a n tj s h e n o y 等人提出。它能够支持 多种应用类别，比如，交互式尽力而为应用、大吞吐量尽力而为应用及软实 时应用等类别，并公平地给各个类别的应用分配磁盘访问带宽。 西南交通大学硕士研究生学位论文第1 5 页 在结构上c e l l o 磁盘调度采用的是一种两级式的调度方式，它由多个与 应用类别相关的调度器以及一个与应用类别无关的调度器组成，如图2 7 所 示。 7 自1 薛一一卜对列 类别相关 的调度器 图2 - 7c c 0 磁盘调度 c e l l o 调度算法中应用类别无关的调度器管理时间上粗粒度的磁盘的调 度，而应用相关的调度器控制着小粒度上磁盘调度。如上图中有n 个应用类 别，c e l l o 使用一个应用无关的调度器c 和n 个类别相关的调度器，系统中 有n + 1 个调度队列。类别无关的调度器c 决定任务请求何时以及多少磁盘请 求被从等待队列( p e n d i n gq u e u e ) 移到调度队列( s c h e d u l e d q u e u e ) ；类别相 关的调度器s i 对等待队列中的请求进行排序，并根据调度队列的状态来决定 磁盘请求被插入到调度队列的什么位置。 2 3 4 实时l ib u x 实现方案的总结 总结上述的各种实时l i n u x 的实现，它们针对不同的设计目标，从不同 的侧重点解决了通用l i n u x 操作系统对实时性支持的问题。 针对l i n u x 系统定时粒度过大的问题，一般的解决办法都是把实时时钟 - 编程为单次触发的状态，然后利用c p u 的时钟计数寄存器提供高达c p u 时 钟频率的定时精度。像r t - l i n i l x 采用的就是这种方法。 对于l i n u x 进程在进入内核态时不能被抢占的问题，r e d l i n u x 在内核 函数中插入抢占点的方法，实现了一种可抢占的内核。 西南交通大学硕士研究生学位论文第1 6 页 对于l i n u x 驱动程序中的封中断的方法，r t - l i n u x 所使用的软件模拟中 断控制器的方法可以有效地解决这个问题。 对于l i n u x 系统中缺乏实时调度机制和调度算法的问题，目前有很多新 颖的操作系统调度框架和调度算法都有l i n u x 实现，比如r e d l i n u x 所定义 的一个通用的实时调度框架；q l i n u x 所采用的分层式的c p u 调度框架，及 新颖的调度算法如h s f q ，以及c e l l o 磁盘调度算法等。 提供对于实时多媒体应用的支持，举措：引入新颖的调度算法( 网络包 调度，进程调度，磁盘调度) ，代表系统有q l i n u x ；引入新颖的调度框架 以及资源管理思想以更好地支持网络系统中的q o s 要求，比如o l i n u x 中的 分级调度的思想，以及r e d l i n u x 所提出来的一个通用的调度框架。 在实际的系统中，具体使用哪种实时l i n u x 技术，需要根据具体的系统 需求而定。如果目标系统是像机床控制或者导弹飞行姿态控制这样的硬实时 系统，那基于r t - l i n u x 是一个不错的方案；如果目标系统是一个像实时多媒 体系统这样的软实时应用，或者一个希望能够在高负载状态下提供更好的吞 吐率的服务器系统，那么q l i n u x 和r e d l i n u x 的思想提供了很好的参考。 西南交通大学硕士研究生学位论文第1 7 页 第3 章l in u x 可抢占内核结构分析与研究 内核是一个操作系统的核心，它负责管理系统的进程、内存、设备驱动 程序、文件和网络系统，决定着系统的性能和稳定性。 一般来讲，操作系统上运行的代码可以分成两部分：内核程序所在的地 址空间称作内核空间，较低的应用程序所在的地址空间称之为用户空间。 l i n u x 内核主要包括下列功能：资源抽象、资源分配、资源共享【8 1 。l i n u x 内 核包括进程管理、定时器、中断管理、系统调用、内存管理、模块管理、虚 拟文件系统接口、文件系统、设备驱动程序、进程间通信和网络管理等模块。 3 1lin u x 操作系统内核分析 l i n u x 操作系统是类u n i x 操作系统【9 1 ，所以l i n u x 操作系统的架构与u n i x 是一致的，可被看作是u n i x 的兼容操作系统。和u n i x 一样，l i n u x 操作系 统的架构有两大特点：用户空间内核空间结构、单一内核结构( 宏内核) 1 0 1 。 1 ) 用户空间内核空间的系统结构 l i n u x 采用用户空间内核空间的系统架构【1 1 1 ，用户程序以进程的方式运 行于用户空间，每个进程拥有相互独立的地址