（计算机应用技术专业论文）嵌入式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 的任务调度算法具有重要的理论意义和现实意义。本文以国家 8 6 3 b 类项目“基于嵌入式l i n t l x 的p d a 开发平台”为契机，对l ir l u x 的实时化 改造、引入容错调度算法等进行深入研究。 首先，分析了嵌入式l i n u x 的主要特点，指出其优点与不足，分析了提高 l i l l x 实时性能的方法：一种是修改核的方法，另一种是双核机制；重点介绍了 典型的嵌入式实时操作系统r t l i n u x ，分析了其体系结构，以及r t - l i f l u x 为满 足硬实时应用而在中断管理、时钟粒度、实时调度等方面做的改动，为以后在 r t l i n u x 中实现实时容错调度算法做了铺垫。 其次，详细分析了系统可靠性的基本概念，在此基础上系统、深入地研究了 容错实时调度的基本技术以及多种容错实时调度算法；提出了两种多处理机调度 算法：p p b m f t e d f 算法和a p b m f t e d f 算法。两种算法在单处理器上都采用e d f 调度，前者采用被动备份容错技术，后者采用主动备份容错技术。文章给出了两 种算法的可调度条件证明以及模拟结果。结果表明主动备份容错调度算法优于被 动备份容错调度算法。 第三，在r t l i n u x 基础上实现了玎一e d f 调度算法，文章对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 ，容错，调度算法 皇三型垫盔兰堡主兰垡笙苎! 壁垒茎! ! ! 竺茎堕窒壁塑塞苎茔塑堡生量塞翌 a b s t r a c t a p p l i c a t i o n s i ne m b e d d e dl i n u xo p e r a t i o n s y s t e m i s ah o tr e s e a r c h s u b j e c t n o w a d a y s h o wt oc h a n g et h el i n u xf r o mn o r m a lo s t oe m b e d d e dr e a l t i m eo si sa v e r yi m p o r t a n tr e s e a r c hi s s u e h o wt oi m p r o v er e a l - t i m ea b i l i t ya n dr e l i a b i l i t yo ft h e e m b e d d e dl i n u xo p e r a t i o ns y s t e mi sai s s u et h a ti sf u l lo fc h a l l e n g e b e c a u s et a s k s c h e d u l i n gd i r e c t l yi m p a c t s t h es y s t e mp e r f o r m a n c e ，t os t u d yt a s ks c h e d u l i n gs c h e m ei n e m b e d d e dl i n u xo p e r a t i o ns y s t e mi so fg r e a ts i g n i f i c a n c e w i t ht h es u p p o r to ft h e n a t i o n a l8 6 3p r o j e c t ，w h i c ha i m st oc o n s t n j c tap l a t f o r mf o re m b e d d e ds o t t w a r e ，t h i s d i s s e r t a t i o nh a sd e e p l ys t u d i e df a u l t t o l e r a n t s c h e d u l i n gt h e o r y i nl i n u x o p e r a t i o n s y s t e m f i r s t l y , t h e d i s s e r t a t i o n a n a l y z e s t h ec h a r a c t e r so fe m b e d d e dl i n u xo s ，t h e a d v a n t a g e a n dd i s a d v a n t a g ea r ep o i n t e do u ta c c o r d i n g l y a n a l y z e st h em e t h o do f i m p r o v i n g t h er e a l t i m e a b i l i t y , i n t r o d u c e s a t y p i c a l e m b e d d e dr e a l - t i m el i n u x o s - - r t - l i n u x a n a l y z e si t ss y s t e mc o n s t r u c t i o n m o d i f i c a t i o n t l l a ta r m st oh a r d r e a l - t i m ep e r f o r m a n c e ，a n di t ss c h e d u l i n g a l g o r i t h m s e c o n d l y , t h ed i s s e r t a t i o nd i s c u s s e st h ef a c t o r st h a ti n f l u e n c et h es y s t e mr e l i a b i l i t y , t h ec a u s e so ft h o s ef a c t o r s ，a n dt h eb a s i cc o n c e p t so fs y s t e mr e l i a b i l i t ys y s t e m a t i c a l l y ， i n t r o d u c e sr e a l - t i m e s c h e d u l i n gi n d e t a i l a n dt h e np r e s e n t st w od i f f e r e n tr e a l - t i m e m u l t i - p r o c e s s o r f a u l t - t o l e r a n t s c h e d u l i n ga l g o r i t h m s ： p p b m f t - e d fa n d a p b m f t - e d f t h ef i r s to n ei sp a s s i v eb a c k u p ，w h i l el a s to n ei sa c t i v eb a c k u p t h e c e r t i f i c a t i o nf o rt a s ks c h e d u l a b l ei sg i v e na n ds o m ei m p o r t a n tc h a r a c t e ra b o u tt h et w o a l g o r i t h m si sp r e s e n t t h ec e r t i f i c a t i o n a n ds i m u l a t i o nr e s u l t sh a v e p r o v e dt h a t t h e p e r f o r m a n c eo f a f 。b m f t - e d fa l g o r i t h mi sb e t t e rt h a np p b m f t - e d f - t h i r d l y , w ea c h i e v et h ef t - e d fa l g o r i t h mb a s e d0 1 1r t - l i n u x t h i sd i s s e r t a t i o n a n a l y z e st h es c h e d u l i n gm o d u l e o f r t - l i n u xi nd e t a i l ，a n dp r e s e n t st h em o d i f i c a t i o nt o t h es c h e d u l i n gm o d u l et h a tm a k e sf t e d fa l g o r i t h mu s a b l e s o m et e s tb a s eo nt h e m o d i f i e da l g o r i t h mh a sb e e nc a r r i e do u t n er e s u l t ss h o wt h a tt h et i m ea n d p e r f o r m a n c e c o s to f f a u l t - t o l e r a n c es c h e d u l i n gc a n s a t i s f yr e q u i r e m e n t so f r e a l t i m es y s t e m k e y w o r d s ：e m b e d d e dl i n u x ，r t - l i n u x ，f a u l t t o l e r a n c e ，s h e d u l ea l g o r t h m i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名： 吐国殛日期：胁f 年，月土日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：吐! 旦整导师签名：匈叠) 日期：2 蜘r 年多月日 第一章绪论 1 1 嵌入式操作系统概述 第一章绪论 嵌入式系统的出现至今已经有3 0 多年的历史了，嵌入式技术也历经了几个发 展阶段。进入9 0 年代后，以计算机和软件为核心的数字化技术取得了迅猛发展， 不仅广泛渗透到社会经济、军事、交通、通信等相关行业，而且深入到家电、娱乐、 艺术、社会文化等各个领域，掀起了一场数字化技术革命。多媒体技术与i n t e m e t 的应用迅速普及，消费电子( c o n s u m p t i v ee l e c t r o n ) ，计算机( c o m p u t e r ) ，通信 ( c o m m u n i c a t i o n ) ，3 c 一体化趋势日趋明显，嵌入式技术再度成为一个研究热点。 嵌入式系统( e m b e d d e ds y s t e m ) 是指：以应用为中心，以计算机技术为基础， 软硬件可剪裁，适应应用系统对功能、可靠性、成本、体积、功耗严格要求的专用 计算机系统。与通用计算机操作系统不同，嵌入式操作系统是针对具体应用的专 用系统，它的硬件软件都必须高效率、高可靠性的设计。 1 1 1 国际上相关产品的现状及技术发展趋势 从八十年代起，国际上就开始进行一姥商用嵌入式系统和专有操作系统的开 发，下面介绍几个比较著名的嵌入式系统。 ( 1 ) w i n d o w s c e m i c r o s o f t 公司生产的w i n d o w s c e 是一个简洁、高效的多平台操作系统，它不 是w i n d o w s 9 5 的缩减版，而是从整体上为有限资源平台设计的多线程、完整优先 权、多任务的操作系统。它的模块化设计允许它对于从掌上电脑到专用的工业控制 器的用户电子设备进行定制。操作系统的基本内核需要至少2 0 0 k 的r o m 。从s e g a 的d r e a m c a t 游戏机到现在的大多高价掌上电脑，都使用了w i n d o w s c e 操作系 统，但是高昂的价格使得整个产品的成本急剧提高。 ( 2 ) v x w o r k s w i n d r i v e r 公司生产的v x w o r k s 是目前应用最为广泛、市场占有率最高的商用 实时操作系统。它支持多种处理器，如x 8 6 、i 9 6 0 、s t m s p a r c 、m o t o r o l a m c 6 8 x x x 、 m i p s r x o o o 、p o w e r p c 等等。使用与u n i x 不兼容的环境，具有专有的v x w o r k s a p i 。 采用g n u 的编译和调试器。 ( 3 ) p s o s p s o s 现在是属于w i n d r i v e r 公司的产品，它是一个模块化、高性能的实时操 作系统，专为嵌入式微处理器设计，提供一个完全的多任务环境，在定制的或是商 电子科技大学硕士学位论文：嵌八式l i n u x 实时容错调度算法的设计与实现 业化的硬件上提供高性能和高可靠性。开发者可以利用它来实现从简单的单处理器 到复杂的、网络化的多处理器系统。 ( 4 ) q n x q n x 是一个实时的、可扩充的操作系统，它遵循p o s i x1 ( 程序接口) 和p o s i x 2 ( s h e l l 和工具) ，部分遵循p o s i xl b ( 实时扩展) 。它提供了个很小的微内核 以及一些可选的配合过程。其内核仅仅提供4 种服务：进程调度、进程间通信、底 层网络通信和中断处理，进程在独立的地址空间内运行。所有其他的o s 服务，都 作为协作的用户进程，因此q n x 内核非常小巧( q n x 4 x 大约为1 2 k b ) 。这个灵活 的结构可以使用户根据实际需求将系统配置成微小的嵌入式操作系统或是包括几 百个处理器的超级虚拟操作系统。 ( 5 ) p a l m o s 3 c o m 公司生产的p a l m o s 在掌上电脑市场上占有很大的市场份额，它提供开 放的操作系统应用编程接口( a p i ) ，开发商可以根据需要自行开发所需的应用程序。 目前已经有总共3 5 0 0 多个应用程序可以运行在p a l m p i l o t 上，这些应用程序包括计 算器、游戏、电子宠物和地理信息等等。在开发环境方恧，可以在w i n d o w s 9 5 9 8 、 w i n d o w s n t 以及m a c i n t o c h 下安装p a l m p i l o td c s k t o p ，p a l m p i l o t 可以与p c 平台上 的应用程序如w o r d 、e x c e l 等进行数据交换。 ( 6 ) o s 一9 m i c r o w a v e 的o s - 9 是为处理微处理器的关键性实时任务而设计的操作系统， 广泛应用于高科技产品中，包括消费电子产品、工业自动化、无线通讯产品、医疗 仪器，数字电视多媒体设备中。它提供了很好的安全性和容错性。与其他的嵌入 式系统相比，它的灵活性和可升级性非常突出。 ( 7 ) l y n x 0 s l y n xr e a l t i m e s y s t e m s 公司生产的l y n x 0 s 是一个分布式、嵌入式、可规模扩 展的实时操作系统，它遵循p o s i xl a 、p o s i xl b 和p o s i xl c 标准。l y n x 0 s 只是 多线程，提供2 5 6 个全局用户线程优先级；提供一些非实时系统的服务特征；提供 与工业标准兼容的网络系统及应用开发工具。 ( 8 ) l i n u x l i n u x 是一套以u n i x 为基础发展而成的操作系统。自1 9 9 1 年诞生至今，在 很多方面已经赶上甚至超过了很多商用的系统。它充分利用了的任务切换机制，实 现了真正的多任务、多用户环境。对硬件配置的要求相当低，能够在4 m 内存的 3 8 6 机器上很好的运行，支持多种处理器芯片。更为重要的是，众多程序员愿意在 上开发程序，开发人员随时对的开放内核进行升级和修补，很多b u g 可以很快地得 到检测和修复。 第章绪论 在嵌入式应用方面，l i n u x 核心小到可以在张软盘上运行，符合嵌入式系统 对体积的要求，另外l i n u x 的开放式开发原则使得l i n u x 下的驱动程序升级速度非 常快捷。 1 1 2 国内相关产品的现状及技术发展趋势 国内的嵌入式系统开发也取得了一定的成绩，代表产品有中科院的e e o s ，凯 思昊鹏的h o p e no s 等等。但是国内产品大多为外国公司产品的附属或者扩充， 技术含量较低。 ( 1 ) e e o s e e o s 是中科院计算所组织开发的开放源码的嵌入式操作系统。该嵌入式操作 系统重点支持p - j a v a ，要求一方面小型化，一方面能利用l i n u x 的驱动和其它模块。 e e o s 采用先进的内核仿真调试技术，能够使c 程序员快速熟悉实时系统的结 构和开发过程，大幅度降低学习、研究、开发实时系统的时间代价。e e o s 专为嵌 入式系统设计，代码尺寸小，同时e e o s 考虑了实时需求，具有很高的实时响应速 度，因而能够在各种环境下工作，具有良好的可伸缩性。 ( 2 ) h o p e n o s h o p e n o s 是凯思集团自主研制开发的嵌入式操作系统，由一个体积很小的内 核及一些可以根据需要进行定制的系统模块组成。其内核h o p e nk e r n e l 一般为 1 0 k b 左右大小，具有实时、多任务、多线程的系统特征。使用者可以很容易地对 这一操作系统进行定制或作适当开发，该系统不仅可以广泛应用于：移动计算平台 ( 如p d a ) 、家庭信息环境( 3 n 机顶盒，数字电视) 、通讯计算平台( 如媒体手机) 、车 载计算平台( 如导航器) 、工业、商业控制( 智能如工控设备、p o s a t m 机) 、电子商 务平台( 3 0 智能卡应用、安全管理) 等信息家电上，还可应用于与i n t e r n e t 相联接的 一切接入设备，是未来信息家电的核心。 该系统目前已能在x 8 6 、p a r i s c 、p o w e rp c 、a r m 、s t r o n ga r m 、m i p s 、 m o t o r o l a6 8 x x x 等多种芯片上运行。 1 2 实时操作系统 二十世纪七十年代以来，实时计算机操作系统被越来越广泛地用来监视和控制 与人类生活相关的一些物理过程。这些实时操作系统监视其外部物理过程的变化， 并根据变化产生控制指令，引导物理过程按照正确的方式运转。典型的应用包括飞 行器和航天器的控制系统、汽车电子系统、工业过程控制系统、电站控制系统、危 重病人的生命维持系统、通信系统以及目前正在大规模兴起的消费类电子产品。实 电子科技大学硕士学位论文：嵌入式l i n u x 实时容错调度算法的设计与实现 时系统的正确性依赖于运行结果的逻辑正确性和运行结果产生的时间正确性，即实 时系统必须在规定的时间范围内正确地响应外部物理过程的变化。 1 2 1 什么是实时操作系统 实时系统的行为正确性不仅取决于结算结果的正确性，还取决于得到这个结果 所花费的时间。在牛津计算技术字典中有如下定义0 1 ： 实时系统指系统输出的产生时间具有决定性意义的系统。这是因为系统的输 入来自于物理世界的某个动作，而输出是对该动作的响应。输入和输出同的延迟 必须小于某个确定的时间间隔。 实时系统的基本特性是任务响应时间的确定性和系统处理任务的高吞吐量。1 。 实时系统的应用领域十分广泛，不同的应用对时间确定性的要求也不同。为此，可 以将实时系统分为硬实时系统和软实时系统两种。硬实时系统用以描述对响应时间 要求极其严格的实时系统。在硬实时系统中，若输出由于不能满足响应时间确定性 的要求而被放弃，系统的正确性将受到严重影响。相反，在软实时系统中，只要响 应时间超出确定的时间范围的频率低于某一阈值，则不影响系统的正确性。 除了必须具备响应时间确定性以外，实时系统其它的重要特性包括并发性、可 预测性和可靠性。并发性是指实时系统必须能够在规定时段内处理多个外部输入。 可预测性实质上是对响应时间确定性的保证。外部输入的本质是并发和随机分布， 每一个输入触发实时系统产生相应的动作，而这些动作的流程、所需的处理器时间 是可预知的。只有在这种情况下才能保证响应时间的确定性。 实时调度算法是实时系统解决并发和保证可预测性的基本手段。实时调度算法 根据调度策略为并发的外部输入确定处理顺序，并按照该顺序为每一个处理操作分 配系统资源。实时调度算法的另一个主要功能是根据可调度条件确定系统现有资源 是否满足处理操作的时间确定性。与通用调度算法不同，实时调度算法首先保证所 有就绪处理操作均能在规定时限前结束，其次才是尽可能多地处理外部事件以提高 系统的资源利用率。如何在保证时间确定性的前提下提高系统资源利用率是实时调 度算法研究的热点问题。 1 2 2 容错在实时系统中的重要性 相对于其它计算机系统而言，实时系统对可靠性要求十分严格。例如，当桌面 应用程序在求解某一数学问题时失败，放弃该程序的执行所损失的只是失败前所消 耗的系统资源。然而，在实时系统中，这种简单的放弃往往是不可接受的。例如， 在高炉炼钢的过程中，当错误出现时，实时系统必须能够提供降级服务，以保证能 够将钢水排出高炉，因为放弃对高炉的控制将造成巨大的经济损失。又如，飞行控 7 第一章绪论 制系统若因系统某一组成部分出错而放弃对飞机的控制必将导致灾难性的后果。因 此，飞行控制系统必须具有出错导向安全的特性，既在出错时通过降级或其他措施 保证飞行员能够使飞机安全着陆。 容错技术主要用于保证系统在出错情况下仍然能够继续运行。a v i 2 i e n i s 给容 错给出了如下定义m ： 容错的功能是在系统内部出现错误的情况下，仍然能够提供外部环境所需的 服务。在提供正确的服务的同时，系统检测并且纠正错误，定位永久性缺陷，并 将其与系统的其他部分隔离。这一目的的实现需要错误检测算法、缺陷诊断、恢 复算法和空闲资源的支持。 容错的关键是冗余，而冗余的关键是冗余管理。所有的容错技术均要为系统引 入空闲资源。所谓空闲，是指这些资源在系统正常运行时并不重要，甚至得不到使 用，但却是系统出错时维持其正常工作的决定性因素。冗余包括硬件冗余、软件冗 余和时间冗余。上述三种冗余技术的结合被称为保护性冗余。通常，硬件冗余用于 处理永久性缺陷，而软件冗余和时间冗余用于处理暂时性或间歇性错误。容错技术 研究的主要目的是，在保证系统可靠性的前提下，尽可能减少系统的冗余度。 1 3 本文课题来源与研究内容 论文课题以国家8 6 3 b 类项目“基于嵌入式l i n u x 的p d a 开发平台”为契机， 对l i n u x 实时化改造、可靠性机制等进行深入研究。本文研究的方向是底层操作系 统级的实时、容错性能扩展。 1 ，4 本文的组织 本文由七个章节组成： 第一章：绪论。介绍了国内外嵌入式实时系统的现状；说明了实时系统的重要 概念；指出了容错性能在嵌入式实时系统中的重要性；并对本文的研究背景及所做 工作加以阐述。 第二章：嵌入式实时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 。 第三章：容错与实时操作系统。详细介绍了容错与实时操作系统的基本概念、 实现技术以及其相互关系。 第四章：实时容错调度算法研究与设计。给出实时调度、容错实时调度算法的 基本概念；分类描述了多种单处理器实时调度算法、单处理器容错实时调度算法、 电子科技大学硕士学位论文：嵌入式l j n u x 实时容错调度算法的设计与实现 多处理器实时调度算法、多处理器实时容错调度算法以及分布式实时容错调度算 法。 第五章：两种多处理机容错调度算法的设计与分析。在研究了多处理机调度算 法的基础上，针对现有多处理机实时容错调度算法的不足，提出了两种多机实时容 错调度算法，给出了可调度性的证明以及模拟结果。 第六章：容错调度算法在r t l i n u x 下的设计与实现。给出了f t - e d f 调度算法 在r t - l i n u x 下实现的详细方法；给出了、狈i 试环境及测试结果，结果显示了调度算 法的有效性。 第七章：结论。对全文的工作进行了总结，并提出了进一步的研究方向。 舞二章嵌入式实时l i n u x 现状 第二章嵌入式实时l i n u x 现状 2 1 嵌入式l i n u x 概述 l i n u x 是1 9 9 1 年由l i n u st o r v a l d s 所创建的类u n i x 操作系统，在众多计算机 程序员的共同努力下，借助于i n t e r a c t ，l i n u x 历经众多版本的改进，目前已经发展 成为一个完整的遵循p o s i x 规范的操作系统，与s y s t e m v 以及b s du n i x 实现了 源码级兼容。它是一个真正的多任务、多用户、多平台系统，支持多处理器，安全 可靠，性能卓越。 嵌入式l i n u x ( e m b e d e dl i n u x ) 是指对l i n u x 经过小型化裁剪后，能够固化在容 量只有几十万字节或几十亿字节的存储器芯片或单片机中，应用于特定嵌入式场合 的专用l i n u x 操作系统。 2 2 嵌入式l i n u x 的优点及其不足 嵌入式l i n u x 是按照嵌入式操作系统的要求而设计的一种小型操作系统。由一 个k e m e i ( 内核) 及一些根据需要进行定制的系统模块组成。其k e m e i 很小，一般只 有几百k b 左右，加上其它必须的模块和应用程序，所需的存储空间也很小。它具 有多任务、多进程的系统特征，有些还具有实时性。一个小型的嵌入式l i n u x 系 统只需要引导程序、l i n u x 徼内核、初始化进程这3 个基本元素。运行嵌入式l i n u x 的c p u 可以是x 8 6 、a l p h a 、s p a r c 、m i p s 、p p c 等。嵌入式l i n u x 通常使用r o m 、 c o m p a c t f l a s h 、m s y s t e m 的d i s k o n c h i p 、s o n y 的m e m o r y s t i 、i b m 的m i c r o d r i v e 等体积小( 与主板上的b i o s 大小相近) 、存储容量不太大的存储器。它的内存可以 使用普通的内存，也可以使用专用的r a m 。 2 21 选择l i n u x 作为嵌入式操作系统的优势 l i n u x 自身的许多优点，使其非常适合成为嵌入式操作系统，主要表现为以下 几个方面； 1 、开发成本低 大多数商业操作系统，如w i nc e 、v x w o r k s 等对每套操作系统均收取高额的 许可证使用费用。l i n u x 是个免费的操作系统，公开源代码，且内核支持模块结 构。不同领域和不同层次的用户可以根据自己的应用需要很容易地对内核进行裁 减，在低成本的前提下，设计和开发出真正满足自己需要的嵌入式系统。 电子科技大学硕士学位论文：嵌入式l i n u x 实时容错调度算法的设计与实现 2 、稳定性高 与目前流行的桌面操作系统相比，l i n u x 稳定可靠，并且由于内核的稳定性使 得l i n u ) 【在移植至b 特定平台后与通用平台具有一样的高稳定性，虽然新平台下的外 围设备可能完全不同。 3 、可移植性好 l i n u x 是一个多平台的操作系统，可以运行子x 8 6 、p o w e r p c 、m i p s 等多种 处理器之上，在嵌入式应用方面这一优点尤为重要。据统计，一个设计优良的嵌入 式系统移植到另一平台只需改动其中的4 代码。同时由于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 提供c 、c + + 、j a v a 等很多种开发平台。更重要的是，在l i n u x 中容易 自行建立嵌入式系统的开发环境和交叉运行环境，并且可以跨越嵌入式系统开发中 仿真工具的障碍。l i n u x 基于g n u 的工具包提供了完整的与无缝交叉平台开发工 具，从编辑器到底层调试，并充分考虑支持各种不同的微处理器结构和调试环境。 l i n u x 所具有的上述独特优势，使得它在嵌入式应用领域的发展极为迅速。 2 2 2l i n u x 在实时性方面的不足 l i n u x 作为一种类u n i x 操作系统，继承了u n i x 的很多不适合实时应用的特点， 使得l i n u x 支持硬实时性有以下技术障碍： 1 、内核不可抢占 l i n u x 下有用户态和核心态两种模式，当进程运行在用户态时，很容易被优先 级更高的进程抢占，但当它进入核心态时( 比如通过系统调用f o r k 进入核心态) ，则 即使其他的用户态的进程优先级再高( 比如实时进程) ，也不能抢占处于核心态的低 优先级的普通进程，因为l i n u x 内核是不可抢占的。当进程调用系统调用而进入核 心态运行时，即使出现了一个具有更高优先级的进程，该进程也只有等待系统调用 返回后方能抢占低优先级的进程。这种方式与硬实时应用中优先级高的就绪任务可 以抢占低优先级任务相矛盾。 2 、进程调度 l i n u x 作为一个分时系统，它的调度目标是提供一种公平的调度机制，平衡系 第二章嵌入式实时1 i n u j 琚状 统响应时间和吞吐量，保证系统中运行的所有进程都能获得一段运行时间。因此， l i n u x 采用多级反馈轮转调度算法，系统中每个进程都拥有可变的优先级，当进程 没有在规定时间片中结束，该进程将放弃c p u ，其优先级降低一级，并被挂到当 前所在优先级进程等待队列的尾部。但分时调度通常与实时应用中要求的低延迟和 高度的可预测性相矛盾。实时操作系统必须保证目前运行任务的优先级是可运行任 务中最高的，除非更高优先级的就绪任务出现、该任务运行结束或主动放弃控制权， 其他任务无法获得c p u 。 3 、时间粒度 时间粒度是指操作系统所能提供的晟小时间间隔。l i n u x 的两次系统时钟中断 间的时间间隔就是系统的时间粒度。时间粒度越小，系统开销越大；时间粒度越大， 进程的响应延迟越大。l i n u x 的时钟中断的周期设为1 0 毫秒，时间粒度处于百毫 秒级，这足以满足l i n u x 进程对于时间粒度的要求，系统开销也较为合理。但对于 一个要求在1 0 0 坤后被唤醒的实时任务而言，则时间粒度过大。 4 、内存管理 为了提高内存的利用率，l i n u x 采用了虚拟内存管理技术。进程对内存的访问 必须通过地址映射将逻辑地址转换成物理地址。当内存不足时，操作系统将选择一 部分己分配内存，将其中的数据写入交换分区，然后对这段内存进行再分配。这一 方法仅对没有时间要求的l i n u x 进程有效。然而，实时任务首先要满足时间的确定 性。如果一个实时任务被换出内存，当再次调度它运行时，必须首先经过一个时间 不确定的换入过程。这将极大地影响系统的响应时间。 5 、屏蔽中断 为了互斥地访问临界区，l i n u x 在进行临界区操作时，采用屏蔽相应的可屏蔽 中断。该方法的效率往往高于使用信号量实现互斥。但屏蔽中断也抑制了系统及时 响应外部时间的能力。多数实时任务的运行是为了响应外部事件。因此，l i n u x 对 中断的屏蔽极大地影响系统对于时间确定性的保证。 2 2 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 的实时性，该案将内核中的进程调度、内存管理、中断处理等部 分遵循p o s i x 标准进行改写，在源码级修改的基础上使l i n u x 变成一个真正的实 2 电子科技大学硕士学位论文：嵌 式l i n u x 实时容错调度算法的设计与实现 时操作系统。这需要精心选择改动部分，一般要重新编写一个优先级驱动的实时调 度器( r e 8 d t i m es c h e d u l e r ) ，替换原有内核中的进程调度器。对于不同的进程，实 时调度器根据进程是否有实时性需求区别对待。对于实时性进程，按照优先级驱动 的原则在时间片和资源分配上进行调度。这样，l i n u x 内核将完全变成一个实时内 核。这种实现方法对开发人员要求高( 精通l i n u x 内核) ，而且开发难度大、周期长， 往往适用于有前期研究积累的开发团体。优点在于系统执行效率高，可以获得更好 的性能。m o n t a v i s t a 公司发布的h a r d h a tl i n u x ，k a n s a s 大学开发的k u r t l i n u x 以 及加州大学i r v i n e 分校开发的r e d l i n u x 等采用了这一方法吼 虽然p o s i ) ( 路线对实现一个实时l i n u x 提供了保证，但目前只有软实时的应 用能用p o s i xl b 函数来实现。移植p o s i xl b 函数到l i n u x 上时要面对的根本问题 是l i n u x 的内核是不可抢占的。因此，要想实现l i n u x 硬实时内核，必须对l i n u x 内核进行彻底的改动。 2 、采用双核机制，在原内核基础上增加一个实时内核 这种方法在同一硬件平台上采用了两个相互配合，共同工作的系统内核。一个 内核提供精确的实时多任务管理，另一个内核提供复杂的非实时通用功能，是通过 在l i n u x 操作系统的最底层增加一层实时核心层来实现。实时内核的功能包括底层 任务创建、底层任务通信队列、中断服务例程( i s r ) 等，负责硬件管理并提供实时 任务管理。它接管来自硬件的所有中断，并依据是否是实时任务决定是直接响应， 或是转给非实时内核处理。实时内核用软件“模拟”常规l i n u x 内核对底层硬件的 使用禁止中断，而不是真正的操作中断控制寄存器。l i n u x 内核被看做实时内核中 优先级最低的任务来调度，只有当没有可运行的实时任务时l i n u x 核心才被调度。 由于l i n u x 的内核模块可以动态加载，因此实时内核以可加载内核模块 ( l o a d a b l ek e r n e lm o d u l e ) 的形式装入原有的内核。由于双内核机制保留了常规 l i n t t x 内核，以较小的代价提供了强实时性，避免了大规模结构改造，新系统可以 使用几乎所有常规l i n u x 操作系统提供的功能，如中文图形环境( xw i n d o w ) 、 t c p i p 协议栈、丰富的编程资源等功能。 这种方法要求在常规l i n u x 核心上的所有非实时任务必须支持可抢占式调度。 这样才能对实时核心提供实时保证。由于实时核心非常小，不会增加整个系统的负 载，所有这些对开发实时性要求严格的实时软件都提供了有力保障。新墨西哥科技 大学开发的r t - l i n u x 是双核机制实时l i n u x 的代表作f 6 】o 2 3r t - k i n u x 介绍 r t - l i n u x 美国新墨硒哥大学计算机系m b a r a b a n o v 和v y o d a i k e n 等人通过对 第二章嵌入式实时l i n t u t 现状 l i n u x 操作系统进行改造而实现的一个硬实时l i n u x 。作者认为任何实时任务都可 以分解成两部分：逻辑简单但要求快速响应的实时操作；用户界面等没有实时要求 的操作【7 】。它的基本思想是：为了在l i n u x 系统中提供对硬实时的支持，实现一个 微内核的小的实时操作系统( 也称为r t - l i n u x 的实时子系统) ，而将普通l i n u x 系统 做为该系统中一个优先级最低的任务来运行。普通l i n u x 系统中的任务可以通过 f i f o 和实时任务进行通信。下面详细介绍r t - l i n u x 在l i n u x 实时化改造的做法。 2 3 1r 。r - l i n u 结构 r t - l i n u x 在l i n u x 内核基础上实现了一个微小的实时内核。这个内核需要完成 底层任务创建、中断服务程序，并为底层任务、i s r 和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 来完成。因为简单并且完全抢占l i n u x 内 核任务，r t - l i n u x 的相应速度非常快。r t - l i n u x 的详细结构如图2 1 所示： 直福瑾 件冉越 l i n u x 系统 i 。话，；一- - 2 3 2 中断模拟 图2 - lr 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 内核工作环境做了一些变化，如图 2 2 所示； l 中断控制硬件 t t 中断控制硬件 工 i 中断控制硬件 中断控制硬件 0 r t - l i n u x 内核 00 l i n u x 内核实 ：声时胁卜 时 任 务 l i n u x 进程 图2 - 2r 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 中，当l i n u x 通知硬 件( 指c p u ) 关闭中断时，r t - l i n u x 内核截获这个请求，并将它记录下来，然后返回 到l i n u x 继续运行( 注意：并未真的将中断关闭，c p u 标志寄存器的中断标志位i f 仍为“l ”) ，这样，l i n u x 永远不能禁止中断，无论l i n u x 处在什么状态，它都不 会对实时系统的中断响应时间增加任何延迟。当一个中断到来时，r t - l i n u x 内核截 获到这个中断，并决定如何处理。如果这个中断的实时处理函数存在，则唤醒；如 果不存在，或者这个实时处理函数表明要同l i n u x 共同处理这个中断，则对之做“待 处理”( p e n d i n g ) 标记，并送入一个队列排队等侯。接下来，若l i n u x 已经开放( e n a b l e l 中断( 如上所述，实时内核会对l i n u x 的所有相关中断的操作做记录) ，那么所有这 些待处理的中断就被当成硬件中断信号。r t - l i n u x 内核唤醒l i n u x 一侧的中断处理 函数，同时，将硬件中断重新开放( 每当c p u 响应一个中断时会自动关中断，i f = o ) ， 以允许实时中断进入。这样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 用宏“c l i ”和“s t i ”来实现关中断和开中断。在标准的l i n u x 内核中， 这些宏只是简单地执行相应的x 8 6 指令。r t - l i n u x 对这些宏作了修改。当l i n u x 用 “c l i ”关闭中断时，它并不是真的屏蔽所有中断，而是转去执行一些r t - l i n u x 代 码。无论