（计算机系统结构专业论文）基于rtos的dsp硬实时开发平台的设计.pdf

摘要 摘要 由于缺乏优化的c 编译器和嵌入式r t o s 的支持，目前，基于d s p 的嵌入式 硬实时系统的软件开发与调试仍是采用汇编语言面向裸机的开发模式，这种开发 模式的根本问题就是开发效率低下，已经越来越不适应该系统向更加复杂、更加 智能化的方向发展的要求。 针对缺乏优化的c 编译器支持这一问题，本文分析了影响b f 5 3 xc 编译器编 译效率的瓶颈不支持硬件循环，在此基础上，改进了g e e 对硬件循环的支持， 并在g e ef o rb f 5 3 x 上完整实现了对b f 5 3 x 两层硬件循环的支持。 针对缺乏嵌入式r t o s 的支持这一问题，本文首先提出了基于静态优先级调 度的双任务模型，并据此在b f 5 3 x 上实现了一个深嵌入式r t o s 。该嵌入式r t o s 仅具备简单的任务管理与调度功能，并且具有极小的额外开销( u s 级) ，非常适 合于对实时性有苛刻要求的嵌入式硬实时系统。为了克服深嵌入式r t o s 存在的 可扩展性差等局限，本文进一步提出了基于有限的共享资源模型实现嵌入式硬实 时l i n u x 的新思路，并据此在b f 5 3 x 上实现了一个高端嵌入式r t o s 。该嵌入式 r t o s 是一个标准的g n u l i n u x 开发环境，具有良好的可移植性和可扩展性，可 以有效提高应用的开发效率。同时，该嵌入式r t o s 具有百璐级的额外开销，对 于大多数嵌入式硬实时系统是可以接受的。 最后，本文基于以上的两个嵌入式r t o s 构建了全新概念的目标识别与跟踪 系统，解决了实现中的关键问题，在保证系统执行效率的前提下有效的提高了系 统开发效率，达到了预期的目的。 关键词：嵌入式，实时操作系统，硬实时，l i n u x ，目标识别与跟踪系统 a b s t r a c t b e c a u s et h el a c ko f u s a b l eo p t i m i z e dcc o m p i l e ra n de m b e d d e dr t o s t h es o f t w a r e d e v e l o p i n ga n dd e b u g g i n go ft h ed s p - b a s e de m b e d d e dh a r d - r e a l t i m es y s t e m sn o w s t i l la d o p t st h ed e v e l o p m e n tm o d eo f u s i n ga s s e m b l yl a n g u a g eo l ln a k e dm a c h i n e 1 1 1 e r e a lp r o b l e mo f t h i sm o d ei st h a ti th a sv e r yl o wd e v e l o p m e n te f f i c i e n c y , w h i c hm e a l l s i tw o n tm e e tt h ed e v d o p i n gr e q u i r e m e n t so fm o r ec o m p l i c a t e d ，m o r ei n t e l l i g e n t s y s t e m s i nr e s p e c tt ot h el a c ko f u s a b l eo p t i m i z e dc c o m p i l e r , t h i sd i s s e r t a t i o nf i r s ta n a l y z e d t h eb o t t l e n e c ko ft h ec o m p i l i n ge f f i c i e n c yo fb f 5 3 xce e m p i l e t ：n o ts u p p o r t i n g h a r d w a r e1 0 0 p t h e n , i m p r o v e dt h es u p p o r tf o rh a r d w a r el o o pi ng e e , a n dc o m p l e t e l y i m p l e m e n t e dt h es u p p o r tf o rb f 5 3 x st w o n e s t e dh a r d w a r el o o p si ng e ef o rb f 5 3 x i nr e s p e c tt ot h el a e ko fu s a b l ee m b e d d e dr t o s ，t h i sd i s s e r t a t i o nf i r s tb r o u g h t f o r w a r dt h ed u a lt a s k sm o d e lb a s e d0 1 1s t a t i cp r i o r i t ys c h e d u l i n gp o l i c y , a n d i m p l e m e n t e dad e e p l ye m b e d d e dr t o so nb f 5 3 xb yu s i n gt h i sm o d e l t h i se m b e d d e d r t o so n l yh a ss i m p l et a s km a n a g e m e n ta n ds c h e d u l i n gf u n c t i o na n dh a sv e r yl o w e x t r ao v e r h e a d ( u s1 e v e l ) ，s oi t sv e r ya p p r o p r i a t ef o rt h ee m b e d d e dh a r d - r e a l - t i m e s y s t e m sw h i c hh a v er i g o r o u sr e a lt i m er e q u i r e m e n t s t oo v e r c o m et h el i m i to fd e e p l y e m b e d d e dr t o s ，l i k es c a l a b i l i t y , t h i sd i s s e r t a t i o nt h e nb r o u g h tf o r w a r dan e wt h o u g h t ： i m p l e m e n t i n gt h ee m b e d d e dh a r d - r e a l - t i m e l i n u xb a s e do nt h el i m i t e ds h a r i n g r 鹤眦e sm o d e l a n di m p l e m e n t e dah i g h - e n de m b e d d e dr t o s n l i se m b e d d e d r t o si sas t a n d a r dg n u l i n u xd e v e l o p i n ge n v i r o n m e n t ，s oi th a sg o o dp o r t a b i l i t ya n d s c a l a b i l i t ya n dc a ne f f e c t i v e l yi m p r o v et h ed e v e l o p m e n te f f i c i e n c yo fa p p l i c a t i o n s a t t h es a m et i m e ，i th a sh u n d r e d - m i c r o s e c o n d sl e v e le x t r ao v e r h e a d ，w h i c hi sa c c e p t a b l e b ym o s te m b e d d e d h a r d r e a l t i m es y s t e m s a tl a s t , t h i sd i s s e r t a t i o nc o n s t r u c t e df u l l yn e w c o n c e p ts y s t e m so f t a r g e ti d e n t i f y i n g a n dt r a c k i n gb a s e d0 1 1t h e s et w oe m b e d d e dr t o s ，s o l v e dt h ek e yp r o b l e m sr e l a t e d w i t hi m p l e m e n t a t i o n s t h e s ew o r ke f f e c t i v e l yi m p r o v e dt h ed e v e l o p m e n te f f i c i e n c y w h i l ea s s u r i n gt h ee x e c u t i o ne f f i c i e n c y , w h i c hm e tt h ee x p e c t e dt a r g e t s k e y w o r d s ：e m b e d d e d , r e a lt i m eo p e r a t i n gs y s t e m ，h a r dr e a lt i m e , l i n u x ，s y s t e mo f t a r g e ti d e n t i f y i n ga n dt r a c k i n g 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特另u ；h n 以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明 确的说明并表示谢意。 签名：篓! ! ! 咝日期：2 ，。7 年石月铲日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) ， 签名：歪：墨竺璺导师签名： 日期：如7 年多月甲日 第一章绪论 1 1 论文的研究背景 第一章绪论 嵌入式系统经历了从早期用4 位或8 位微处理器实现的简单控制系统，到基 于8 位或1 6 位微处理器的超循环系统、再到现在的基于1 6 位或3 2 位微处理器的 面向多任务的实时系统这样三个发展阶段。对应的，软件开发语言也从只能采用 汇编语言发展到主要采用c c + + 、j a v a 等高级语言的阶段。同时，实时操作系统 ( r t o s ) a p i 的标准化、软件调试工具和测试工具的完善，这些都扶根本上改交 了嵌入式系统开发效率低下的关键问题。 基于d s p 的嵌入式系统同样经历了一般嵌入式系统的三个发展阶段，目前是 以准3 2 位( 3 2 位内部总线，1 6 位外部总线) 和3 2 位的d s p 为主流。但是相对 于基于微处理器的一般嵌入式系统来讲，d s p 的软件开发工具一直处于滞后状态， 使得基于d s p 的嵌入式系统的软件开发仍是采用汇编语言面向裸机的开发模式， 这种开发模式的根本问题就是开发效率低下，已经越来越不适应系统向更加复杂、 更加智能化的方向发展的要求。一个典型的例子就是用于成像跟踪领域的目标识 别与跟踪系统。该系统的传统特点在于其是面向实时图像处理领域，需进行密集 的矩阵运算，因此传统上该系统采用面向密集运算的数字信号处理器( d s p ) ，是 一个典型的基于d s p 的嵌入式硬实时系统。随着该系统中软件变得越来越复杂、 越来越智能化，软件规模变得越来越大，如何有效的提高该系统上的软件开发效 率已经成为一个亟待解决的问题。 本论文正是以此为出发点，在国家8 6 3 计划高新技术预研课题资助之下完成 的。本论文同时得到2 0 0 5 年四川省青年软件创新工程资助。 1 2 论文的研究目的及内容 针对目前基于d s p 的嵌入式系统开发效率低下的问题，本论文的研究目的就 在于设计与实现高效率、高稳定性的d s p 软件开发平台，从根本上提高d s p 软 件开发效率。该平台应满足如下三点基本要求：采用高级语言( 如c ) 进行开发； 面向嵌入式r t o s 迸行开发；d s p 软件具有高的执行效率。前两点可以保证高的 电子科技大学硕士学位论文 开发效率，与第三点在一定程度上是存在矛盾的，因此，在本论文的研究过程中， 一个贯穿始终的关键问题是，如何在开发效率与执行效率之间找到一个最佳的平 衡点。 值得强调的是，本论文的研究遵循从个别到一般、从具体到抽象的认识过程， 即以目标识别与跟踪系统这一个别、具体的应用为出发点考虑问题，避免泛泛而 谈，在此基础之上，适时地将问题上升到一般和抽象的层次，使得研究的成果具 有一般性和通用性。对于体系结构、c 编译器的讨论，本论文也是既重视一般性 的讨论，也重视对特定体系结构( a d s pb f 5 3 x ) 的深入分析。 本论文的研究内容包括： ( 1 ) b f 5 3 xc 编译器效率评估； ( 2 ) g e e 支持硬件循环的分析和改进； ( 3 ) g e ef o rb f 5 3 x 支持硬件循环的实现； ( 4 ) 额外开销为几u 8 的双任务系统( i m 0 5 3 x 平台) 的设计与实现； ( 5 ) 额外开销为百u 8 的标准多任务系统( h r t - l i n u x ) 的设计与实现； ( 6 ) 典型的硬实时系统( 目标识别与跟踪系统) 的设计与实现； 1 3 国内外现状和发展趋势 目前，传统的两大d s p 供应商1 r i 与a d i 对其主流的d s p 均提供w i n d o w s 平台下的集成的开发环境( m e ) ，该开发环境具有模拟和在线仿真两大功能，支 持汇编语言、c c + + 语言。但是，这些d s p 供应商提供的i d e 存在的共同问题是： 第一，不支持特定d s p 的某些特殊体系结构特征，c 编译器效率不够理想；第二， 不支持面向操作系统的标准a p i ( 如p o s i x 标准或其子集) 的开发方式；第三， 在线仿真方式不支持对应用的实时调试。这些问题使得基于d s p 的嵌入式系统的 软件开发仍必须采用汇编语言面向裸机的开发模式。以a d i 公司的v i s u a ld s p 斗斗 为例，首先，其c 编译器不支持b f 5 3 x 系列d s p 的硬件循环指令，对代码的优 化程度也远逊色于g c c ；其次，该i d e 集成的v i s u a l d s p + + k e r n e l ( v d k ) 虽号称 是一个r t o s 内核，但由于其并不支持标准的a p i ( 如p o s i x 标准或其子集) ， 故基本上不可用；最后，该i d e 基于j t a g 的在线仿真方式不支持对应用的实时 调试。 从以后的发展趋势来看，d s p 供应商有可能逐渐使其c 编译器支持d s p 的 某些特殊体系结构特征，并且提高其c 编译器的代码优化能力。然而更可能的两 2 第一章绪论 种方式是，其一，d s p 供应商利用开源资源( 如g n u l i n u x ) 来实现对其d s p 更好的支持；其二，d s p 供应商与第三方的系统软件供应商进行合作，对其d s p 进行更好的支持。前一种方式已被包括1 r i 与a d i 在内的多数d s p 供应商采用， 这与嵌入式l i n u x 的风靡有着直接的关系。以a d i 公司为例，该公司通过充分利 用g e e 、u b o o t 、u c l i n u x 这些开源软件资源实现了对b f 5 3 x 系列d s p 更好的支 持，这包括：g e e 的c 编译器具有更为理想的编译效率；标准的l i n u x 开发环境， 可以有效提高应用的开发效率，同时易于实现对应用的实时调试。这些使得采用 b f 5 3 x 系列d s p 可以高效率的开发基于嵌入式l i n u x 的软实时应用。 1 4 论文的组织结构 本论文主要涉及两方面的研究内容，一是嵌入式系统中的实时性需求，二是 体系结构与系统软件( 包括编译器与操作系统) 。这两者在本论文中是相互依存、 相互渗透的关系。基于此，为了叙述的方便，本论文以体系结构、编译器、操作 系统为主线，从底层到高层进行论述，将实时性需求融入到这一论述过程中。各 章的大致内容如下： 第一章，绪论：阐明了本论文的研究背景、目的、内容等。 第二章，嵌入式系统中的实时概念：一般往的探讨了嵌入式系统中涉及的实 时性的基本概念，明确了衡量硬实时性能的两个重要指标。 第三章，实时系统的基石体系结构与编译器：体系结构与编译器构成实 时系统的基石，其重要性不言而喻。本章深入探讨了b f 5 3 x 体系结构，对b f 5 3 x 的两种c 编译器的效率进行了评估和对比；重点分析和改进了g e e 对硬件循环的 支持，实现了g e ef o rb f 5 3 x 对硬件循环的支持。 第四章，实时系统的核心嵌入式r t o s ：这一章深入探讨了实时系统的核 心一r t o s ，设计和实现了两个嵌入式r t o s ：基于静态优先级调度的双任务模 型在u - b o o t 上设计和实现了额外开销为几瑚的双任务系统；基于有限的共享资 源模型在嵌入式l i n u x 上设计和实现了额外开销为百l l s 的标准多任务系统。 第五章，典型的硬实时系统目标识别与跟踪系统：对目标识别与跟踪系 统中的实时需求进行了深入分析；基于双任务系统和标准多任务系统分别构建了 目标识别与跟踪系统。 第六章，结论与展望：主要是总结了论文的工作，谈及了它的创新，它的不 足以及以后的工作方向。 3 电子科技大学硕士学位论文 第二章嵌入式系统中的实时概念 嵌入式系统是以应用为中心，以计算机技术为基础，其软硬件可裁剪，适用 于应用系统对功能、可靠性、成本、体积、功耗有严格要求的专用计算机系纠“。 在很多的应用中，嵌入式系统也必须是一个实时系统，即系统的正确性不仅仅依 赖于计算的逻辑结果，而且依赖于结果产生的时间 2 1 。鉴于此，本论文中对“嵌 入式系统”和“实时系统”这两个概念并不加以严格区分，往往将两者联系在一 起；同样的，对“嵌入式r t o s ”与“r t o s ”这两个概念也不加以严格区分， 往往将嵌入式r t o s 简称为r t o s 。本章将就嵌入式系统中涉及的实时概念作一 个概要性的介绍和分析，为后续章节的嵌入式实时系统设计打下一个坚实的基础。 2 1 软实时与硬实时 根据确定性的强弱，可将嵌入式系统分为硬实时、软实时系统： 软实时：系统对响应时间有要求，但是如果系统响应时间不能满足，不会导致 系统出现致命的错误或崩溃。大多数的消费电子产品就是典型的软实时系统。 硬实时：系统对响应时间有严格的要求，如果系统响应时间不能满足，就要引 起系统崩溃或致命的错误。换个说法，硬实时意味着，无论系统负载有多重，硬 实时任务( h a r d - r e a l - t i m et a s k ，以下简称h r y r ) 必须在给定的时间( 称为p d l t ， 见2 7 中的定义) 之内得到响应，并在给定的时闻( 称为截止时间或死线) 之前完 成。用于实时控制领域的很多嵌入式系统就是典型的硬实时系统，比如本论文中 重点探讨的目标识别与跟踪系统。 2 2 外部中断驱动与定时器驱动 r t o s 必须能在一个事先定义好的时间限制内对内部或外部的事件进行响应 和处理。在r t o s 中，外部中断产生的事件可以认为是r t o s 的外部事件，定时 器( 包括系统定时器) 到期产生的事件可以认为是r t o s 的内部事件。r t o $ 对 这两类事件的实时性要求是一致的。用于实时控制领域的嵌入式硬实时系统往往 是外部中断驱动的，而消费电子产品领域的嵌入式软实时系统往往是定时器驱动 4 第二章嵌入式系统中的实时概念 的。有时，为了方便调试外部中断驱动的嵌入式硬实时系统，我们可以在定时器 驱动的嵌入式软实时系统上对其进行模拟调试。 2 3 周期任务与非周期任务 按照到达情况的可预测性，任务可以划分为周期任务( p e r i o d i ct a s k ) 和非周 期任务( n o n p c r i o d i ct a s k ) 两种类型。 周期任务每隔一个固定的时间间隔就会执行一次口1 ，比如标准帧频的目标识 别与跟踪系统的处理任务就是每隔2 0 m s 执行一次。与此相反，非周期任务执行的 间隔时间则为不确定的，如移动通信设备中的通信任务。 2 4 关键任务与非关键任务 按照任务的重要程度，任务又可以分为关键任务( c r i t i c a lt a s k ) 和非关键任 务( n o n c r i t i c a lt a s k ) 两种类型。 关键任务为需要得到及时执行的任务，否则将出现灾难性的后果，如目标识 别与跟踪系统的处理任务；相对来说，非关键任务如果没有得到及时执行，则不 会产生严重后果。 在硬实时系统中，h r t t ( h a r d - r e a l t i m et a s k ) 即为关键任务，非h r t t 即 为非关键任务。本论文中，由于目标系统是硬实时系统，因此直接采用h r t t 与 非h r t t 这一术语。 2 5 共享资源 在嵌入式系统中，被各种并发执行的任务共享的资源称为共享资源【4 】。这些 共享资源可以分类为可剥夺的( p r e e m p t i b l e ) 和不可剥夺的( n o n - p r e e m p t i b l e ) 。 不可剥夺的共享资源必须被各种并发执行的任务互斥地访问，否则，将产生无法 预测的结果。本文中所指的共享资源特指不可剥夺的共享资源。 2 6 基于优先级的可抢占调度的系统的特有问题：优先级反转问题 在基于优先级的可抢占调度的系统中，理想情况下，当高优先级任务处于就 电子科技大学硕士学位论文 绪状态后，高优先级任务就能够立即抢占低优先级任务而得到执行。但在多个任 务需要使用共享资源的情况下，可能会出现高优先级任务被低优先级任务阻塞， 并等待低优先级任务执行的现象。高优先级任务需要等待低优先级任务释放资源， 而低优先级任务又正在等待中等优先级任务的现象，就被称为优先级反转( p r i 耐t y i n v e r s i o n ) 。如图2 1 所示。在该图中，高优先级任务由于与低优先级任务竞争共 享资源而被后者阻赛( t 1 t 3 ) ，之后低优先级任务被中优先级任务剥夺( t 4 t 5 ) ， 而后者的执行时间将是不确定的，由此高优先级任务何时得到调度执行将是不确 定的，也就是说，优先级反转问题将导致不确定的内核剥夺延迟。 i 不确定7 i i l 一 广 f i 广勘 一t a k el 一 昀o i v e 一 一 l 朋ll j i jl 一一一l l = 囝；l t l口t 3饵岱惦口惦 时间 图2 1 优先级反转导致不确定的内核剥夺延迟 解决优先级反转问题的常用协议包括：优先级继承协议( p r i o r i t yi n h e r i t a n c o p r o t o c 0 1 ) 、优先级天花板协议( p r i o r i t yc e i l i n gp r o t o c 0 1 ) 。 优先级继承协议的基本思想是：当一个任务阻塞了一个或多个高优先级任务 时，该任务将不使用其原来的优先级，而使用该任务所阻塞的所有任务的最高优 先级作为其执行l 临界区的优先级。当任务退出该临界区时，又恢复到其最初的优 先级。 在优先级天花板协议中，如果任务获得信号量，则在任务执行临界区的过程 中，任务的优先级将被抬升到所获得信号量的优先级天花板( 即所有使用该信号 量的任务的最高优先级) 。使用优先级天花板协议的目的在于解决优先级继承协议 中存在的死锁和阻塞链问题。 两者都能解决优先级反转问题，但在处理效率和对程序运行流程的影响程度 上有所不同。优先级继承协议可能多次改变占有某临界资源的任务的优先级，而 优先级天花板协议只需改变一次，显然后者效率更高；优先级天花板协议的特点 6 第二章嵌入式系统中的实时概念 是一旦任务获得某临界资源，其优先级将被抬升到可能的最高程度，而不管此后 在它使用资源的时间内是否真的有高优先级任务申请该资源，这样就有可能影响 某些中间优先级任务的完成时间。但在优先级继承协议中，只有当高优先级任务 申请已被低优先级任务占有的临界资源这一事实发生时，才抬升低优先级任务的 优先级，因此优先级继承协议对任务执行流程的影响相对要较小。 2 7 硬实时性能衡量指标一：p d l t 2 1 中提到的p d l t ( p r o c e s sd i s p a t c hl a t e n c yt i m e ) 定义如下阎：从h r t t 中断产生到h r t t 被调度并开始执行第一条指令这段延迟时间详见图2 2 。 图22p d l t 包含多个筵遮 可见，p d l t 主要包括四个延迟：中断响应延迟( 琢t ) ；中断处理延迟( i s r l a t e n c y ) , 内核剥夺延迟( p r e e m p t i o nd e l a y ) , 调度延迟( s c h e d u l i n gl a t e n c y ) 。 p d l t 完整的反映了系统的硬实时响应性能，可以作为评估系统硬实时性能的指 标之一。 另外，p d l t 的定义基于如下假设： ( 1 ) h r t t 由中断驱动，也就是说，h r t t 中断产生将使得h r t t 被唤醒而 处于就绪态； ( 2 ) h r t t 具有实时优先级，将被调度程序优先调度。 7 电子科技大学硕士学位论文 2 8 硬实时性能衡量指标二：可调度性分析 可调度性分析决定实时系统中是否所有的任务可以调度运行，并且满足它们 使用调度算法建立的死线( d e a d - l i n e ) ，同时仍要获得优化的处理器效率。注意， 可调度性分析只观察系统如何满足时序要求，而不是满足功能要求。 2 8 1 静态调度算法之一：人为安排优先级 在静态调度算法中，任务的优先级需要在系统运行前进行确定，一旦确定后 不再发生改变。 人为安排优先级是嵌入式实时软件开发中使用得非常多的一种方法。该方法 以系统分析、设计人员对系统需求的理解为基础，确定出系统中各个任务之间的 相对优先情况，并据此确定出各个任务的优先级。 2 8 ，2 静态调度算法之二：速率单调调度算法r m s 1 9 7 3 年，l i u 和l a y l a n d 在a c m 上发表了题为“s c h e x t u l i n ga l g o r i t h m sf o r m u l t i p r o g r a m m i n gi nah a r dr e a l - t i m ee n v 缸o n m e n t ”的论文，该论文奠定了实时 系统所有现代调度算法的理论基础。速率单调调度算法r m s ( r a t e - m o n o t o n i c s c h e d u l i n ga l g o r i t h m ) 即在该论文中被提出来。r m s 是在基于以下假设的基础上 进行分析的： ( 1 ) 所有任务都是周期任务； ( 2 ) 任务的相对截止时间等于任务的周期： ( 3 ) 任务在每个周期内的计算时间都相等，保持为一个常量； ( 4 ) 任务之间不进行通信，也不需要同步； ( 5 ) 任务可以在计算的任何位置被抢占，不存在临界区。 r m s 是一个静态的固定优先级的调度算法，任务的优先级与任务的周期表现 为单调函数的关系，任务周期越短，任务的优先级越高；任务周期越长，任务的 优先级越低。r m s 是静态调度中的最优调度算法，即如果一组任务能够被任何静 态调度算法所调度，则这些任务在r m s 下也是可调度的。 任务的可调度性可以通过计算任务的c p u 使用率，然后把得到的c p u 使用 率同一个可调度的c p u 使用率上限进行比较来获得。这个可调度的c p u 使用率 上限被称为可调度上限( s c h e d u l i n gb o u n d ) 。可调度上限表示给定的一组任务在 第二章嵌入式系统中的实时概念 特定调度算法下能够满足截止时间要求的最坏情况下的最大c p u 使用率。可调度 上限的最大值为1 0 0 ，与调度算法密切相关。对于一组任务，如果任务的c p u 使用率小于或等于可调度上限，则这组任务是可被调度的；如果任务的c p u 使用 率大于可调度上限，就不能保证这组任务是可被调度的，任务的可调度性需要进 一步分析。 在r m s 中，c p u 使用率的可调度范围为 一 1 等烈( 2 ”一1 ) 公式( 2 1 ) 7 r 二芷al z 1j i = l 罩i 这里： c i = 周期任务i 的最长执行时间 t i = 周期任务i 的周期 n - 周期任务个数 上述条件是一个充分条件，但不是一个必要条件。如果任务的c p u 使用率满 足该条件，则任务是可调度的；但如果不满足该条件，也有可能被r m s 所调度。 在任务比较多的情况下( 即n 为无穷时) ，由公式( 2 1 ) 易知，r m s 的可调 度上限为l n 2 或0 6 9 3 。如此低的c p u 使用率对于大多数的系统来说都是不可接 受的。对于r m s 来说，既使c p u 的使用率小于1 0 0 ，但如果大于了算法给定 的可调度范围，仍有可能不能满足截止时间的要求。 另外，r m s 的不足之处还在于它假定任务是相互独立的、周期性的，且任务 能够在任何计算点被抢占。但是，在实时系统中，任务之间通常都需要进行通信 和同步。r a j k u m a r 在博士论文“s y n c h r o n i z a t i o ni nr e a l t i m es y s t e m s ：ap n o f i w i n h e r i t a n c e a p p r o a c h ”中，基于r m s 提出了可以处理任务同步的调度算法。该算 法解决了单处理器上任务之间的同步问题。r a j k u m a r 还解决了任务之间存在互斥 执行的问题，允许任务存在临界区；在执行临界区时，任务不能被其他任务所抢 占。为了支持非周期任务的处理，比较简单的方法是以先用后台方式执行非周期 任务，或是把就绪的非周期任务组织成一个队列，然后用周期性的查询该队列是 否有非周期任务的方式来执行。后台执行非周期任务的方式效率比较低，非周期 任务只有在所有周期任务都没有执行的情况下才会得到调度。周期性的查询方式 相对来说性能要好一点，但有可能出现刚查询完成，就有非周期任务就绪的情况， 导致该任务等待一个轮询周期才能得到调度执行的现象。 9 电子科技大学硕士学位论文 2 8 3 动态调度算法之一：截止时间优先调度算法e d f 不同于静态调度，在动态调度中，任务的优先级可根据需要进行改变，也可 能随着时间按照一定的策略自动发生变化。 由2 8 2 节的讨论可知，r m s 调度算法的c p u 使用率比较低，在任务比较多 的情况下，可调度上限为6 9 。针对此问题，l i u 和l a y l a n d 又提出了一种采用动 态调度的、具有更高c p u 使用率的调度算法截止时间优先调度算法e d f ( e a r l i e s td e a d l i n ef i r s t ) 。在e d f 中，任务的优先级根据任务的截止时间来确定。 任务的截止时间越近，任务的优先级越高；任务的截止时间越远，任务的优先级 越低。当有新的任务处于就绪状态时，任务的优先级就有可能需要进行调整。同 r m s 一样，l i u 和l a y l a n d 对e d f 算法的分析也是在一系列假设的基础上进行的。 在l i u 和l a y l a n d 的分析中，e d f 不要求为周期任务，其他假设条件与r m s 相同。 e d f 调度算法是最优的单处理器动态调度算法，其可调度上限为1 0 0 。在 e d f 调度算法下，对于给定的一组任务，任务可调度的充分必要条件为 对于给定的一组任务，如果e d f 不能满足其调度性要求，则没有其他调度算 法能够满足这组任务的调度性要求。 同基于固定优先级的静态调度相比，采用基于动态优先级调度的e d f 算法的 显著优点在于e d f 的可调度上限为1 0 0 ，使c p u 的计算能力能够被充分利用起 来。e d f 的不足之处是，在实时系统中不容易实现，并且，同r m s 相比，e d f 具有更大的调度开销，需要在系统运行的过程中动态的计算确定任务的优先级。 另外，在系统出现l 临时过载的情况下，e d f 不能确定哪个任务的截止时间会得不 到满足，而且很难区别系统是在满负荷运行还是将要错过截止时间。 为此，l i u 和l a y l a n d 进一步提出了一种混合的调度算法，即大多数任务都采 用r m s 进行调度，只有少量任务采用e d f 调度算法。尽管混合的调度算法不能 达到1 0 0 的c p u 使用率，但确实综合了e d f 和r m s 调度算法的优点，使整个 调度比较容易实现。 1 0 垒誓 。m 第三章实时系统的基石体系结构与编译器 第三章实时系统的基石体系结构与编译器 计算机体系结构定义了计算机的硬件软件接口，高级语言编译器则是通过编 译、汇编的过程将高级语言程序映射到这一接口上。高效、简洁的体系结构与优 化的编译器是构成实时系统的基石，因此我们将首先对其进行深入探讨，在此基 础上进行编译器的改进工作。本章所进行的b f 5 3 x 体系结构的深入分析也是第四 章进行嵌入式r t o s 设计与实现的基础。 3 1 体系结构的一般讨论 本节将就计算机体系结构涉及的一些重要概念和技术作一个一般性的讨论， 由于是一般性的讨论，因此并不限定是d s p 还是一般的微处理器。 3 1 1 冯诺伊曼机 1 9 4 4 年，冯诺伊曼( j o h nv o nn c u l n a n n ) 加入到e n i a c 项目中，与该项目 组成员一起提出了存储程序计算机( s t o r e d - p r o g r a mc o m p u t e r ) 的概念 6 1 ，这就是 现在广为人知的冯诺伊曼机( v o n n e u m a n n c o m p u t e r ) 。尽管计算机在硬件实现上 已经历了真空管、晶体管、集成电路、l s i 与v l s i 四代的发展，但这些计算机从 体系结构上讲都是冯诺伊曼机。 冯诺伊曼机的核心就是存储程序概念，即指令与数据一样保存在存储器中。 经典的冯诺伊曼机中，指令与数据通过同一组数据、地址总线从同一个存储器中 进行加载，这就是所谓的冯诺伊曼结构，如图3 1 所示。 电子科技大学硕士学位论文 图3 1 冯诺伊曼结柯 3 1 2 哈佛结构与改进的哈佛结构 最早，h o w a r d a i k e n 开发的真空管计算机m a r k - i l l 和m a r k i v 采用了分离的 指令存储器和数据存储器，人们就用哈佛结构( h a r v a r da r c h i t e c t u r e ) 这个术语来 描述这种具有分离存储器的计算机。d s p 从诞生之初都毫无例外的采用了这种结 构，将指令和数据的存储器空间分开，各有自己的地址和数据总线。这种结构便 于对指令和数据的并行处理，从而可以大大的提高运算的速度。 现在人们通常用这个术语来描述具有单个大的主存储器但具有分离的指令和 数据c a c h e 的计算机。如图3 2 所示。现代的绝大多数处理器都无一例外的采用 了这种结构。现代的d s p 也基本融入到这种结构中，片内区分指令存储器与数据 存储器，两者的部分可分别被指定为指令和数据c a c h e ，片外可以挂接大容量的 s d r a m 作为主存储器。 在d s p 领域，为了进一步提高信号处理的效率，在哈佛结构的基础上，又加 以改进，使得指令和数据存储空间之间可以进行数据的传送，这就是所谓的改进 的哈佛结构( m o d i f i e dh a r v a r da r c h i t e c t u r e ) 。这样做的好处是显然的。例如，在 作数字滤波处理时，将滤波器的参数存放在指令存储空间里，而将待处理的样本 存放在数据空间里，这样，处理器就可以同时提取滤波器参数和待处理的样本， 进行乘和累加【7 1 。a d i 公司的s h a r c 系列d s p 采用了改进的哈佛结构，它允许 指令存储器包含数据和指令，这使得不仅可以将附加数据挤压到片内指令存储器， 而且有时可以允许并行的从两个存储器中取出数据。 第三章实时系统的基石体系结构与编译器 3 1 3c i s c 与r i s c 2 0 世纪6 0 年代末7 0 年代初，限于硬件的能力，大多数程序都是用汇编语言 编写的，为了提高汇编程序的编写效率，计算机体系结构逐渐倾向于增加功能强 大的指令，使得指令集越来越复杂，单个指令的执行时间( c p i ) 越来越长，形 成所谓的复杂指令集计算机( c i s c ) 。与此同时，高级语言计算机系统结构( h u c a ) 被提了出来，目标是消除计算机硬件与高级语言之间的间隙，这在某种程度 上加速了c i s c 的形成【”。 到了2 0 世纪8 0 年代初，随着硬件能力的快速增长，更高效的编程语言和编 译器的出现，人们不再依赖于手工编写汇编代码，计算机系统结构也开始从为语 言提供高级硬件支持的方向转移出来。d i t z e l 和p a t t e r s o n 分析了高级语言系统结 构所遇到的问题，认为解决之道在于比较简单的系统结构，并第一次讨论了精简 指令集计算机( r i s c ) 的思想。r i s c 有以下几个特点，这些特点明显简化了r i s c 的硬件实现，并且便于高级语言编译器生成高效的代码： ( 1 ) 所有运算使用的数据都来自寄存器，运算结果也都写入寄存器，每个寄 存器的典型长度是3 2 位或6 4 位，存在足够多的通用的这些寄存器。 ( 2 ) 能够访问内存的操作只有两条指令：从内存中读取数据到寄存器的l 0 a d 指令和向内存中写数据的s t o r e 指令。l o a d 指令和s t o r e 指令可以对一个寄存器的 一部分进行操作( 例如：一个字节、1 6 位或者3 2 位) 。 ( 3 ) 指令的数量比较少，所有指令的长度均相同。 迄今为止，只有一种c i s c 指令集在r i s c c i s c 的激烈争论中坚持了下来， 那就是可以兼容p c 机软件的机器。这是由于p c 芯片生产的数量非常大，其利润 完全可以支付额外的设计；而且摩尔定律( m o o r e sl a w ) 也为制造那些在内部实 现c i s c 到r i s c 转化芯片所需要的资源提供了保证。 嵌入式处理器市场竞争的重点在于价格和功耗，不可能提供额外的硬件转换， 所以基本上无一例外的使用r i s c 系统结构和编译器。 d s p 市场也不例外，新一代的d s p 处理器，如a d i 的b f 5 3 x 系列就是r i s c 类的处理器。 3 1 4 指令级并行方法 1 9 8 5 年以来，包括嵌入式处理器在内的所有处理器，都使用流水线方式 ( p i p e l i n i n g ) 使指令的执行可以重叠进行以提高效率。这种指令问可能存在的重 电子科技大学硕士学位论文 叠被称为指令级并行( i n s t r u c t i o n - l e v e lp a r a l l e l i s m ，i l p ) ，因为这样指令可以并行 处理。 提高指令级并行度有两种不同的方法，一种是动态的、依赖硬件的技术，另 一种是静态的、更依赖于软件的技术。前一种技术的典型例子是超标量技术，后 一种的典型例子是v l i w ( v e r yl o n gi n s t r u c t i o nw o r d ) 。以硬件为主的动态技术 被广泛用在桌面电脑和服务器处理器中，而以软件为主的静态相关技术则被更多 的用在嵌入式处理器中。对于d s p ，出于对确定性和实时性的严格要求，往往采 用以软件为主的静态相关技术。 3 1 5 存储器层次结构 计算机的先驱们正确的预见到了：第一，编程者希望拥有无限大容量的快速 存储器；第二，解决这个问题的一个较经济的方法就是采用存储器层次结构，该 结构中每一层都比其上一层具有更大的容量和更慢的访问速度。其后，基于程序 访问的局部性原理以及硬件规模越小、其速度越快的指导思想，产生了基于不同 速度和容量存储器的层次结构。这种组织结构的目标是提供一个存储器系统，使 其价格几乎相当于最便宜的一层存储器的价格，但是访问速度却与最快一层的接 近。层次结构中各层之间通常是子集关系，某一层中的所有数据总能在其下一层 中找到，而下一层中的所有数据也能在再下一层中找到，如此直到层次结构的最 底层。 图3 3 是一个典型的台式机和服务器的多级存储器层次结构。在该图中，c a c h e 的管理( c a c h e 到存储器的映射) 和存储器的管理( 包含存储器保护和存储器到 磁盘存储的映射) 构成现代处理器的两个重要功能模块。后者即是所谓