（计算机应用技术专业论文）基于可分布线程的实时corba调度模型研究.pdfVIP

中国科学技术大学硕士论文 摘要 摘要 c o r b a ( c o m m o no b j e c tr e q u e s tb r o k e ra r c h i t e c t u r e ) 是当前最具有影响力 的分布对象计算( d i s t r i b u t e do b j e c tc o m p u t i n g ) 技术，l 【j 于它本身的跨平台性、 语言无关性以及实用性，c o r b a 技术在许多领域的应用系统中已经得到了广泛 的应用，并已经成为事实上的工业标准。但在军事、航空、电信、制造等领域中， 一些应用系统需要c o r b a 系统支持实时处理的能力，为此o m g ( o b j e c t m a n a g e m e n tg r o u p ) 组织对通i t jc o r b a 规范进行了扩展，并相继制订了实时 c o r b a 规范10 、ll 、20 等版本。 如何合理分配系统资源，以保证实时任务的时间特性要求，是实时c o r b a 系统要解决的基本问题；而相应的系统调度模型以及算法和实现则是实时 c o r b a 系统的核心问题。本文围绕着以上的问题，以实时c o r b a 20 规范为参 照开展了如下的研究工作： ( 1 ) 研究了华盛顿大学开发的实时c o r b a 系统一t a o 系统，t a o 调度 服务的调度策略和调度框架； ( 2 ) 对实时c o r b a 2 0 规范所提出的可分布线程概念以及基于可分布线程 的节点独立调度模型进行详细分析，指出了节点独立调度模型的存在的不足； ( 3 ) 针对节点独立调度模型的不足，提出了基于可分布线程的二层调度模 型，该模型在节点调度器上面引进了元调度器；并对该模型的可调度性、负载平 衡性、全局优化性等方面的改进进行分析； ( 4 ) 根据所建立模型，结合t a o 系统的调度策略和调度框架，给出了二层 调度模型的实现接口描述以及可调度分析算法。 关键闻： 弱d 节点调度 实时c o r b a 元调度 可分布线程 全局优化性 中国科学技术大学硕士论文a b s t r a c t a b s t r a c t c o r b a ( c o m m o no b j e c tr e q u e s tb r o k e ra r c h i t e c t u r e ) t e c h n i q u ei st h em o s t i n f l u e n c i n gd i s t r i b u t e d o b j e c t c o m p u t i n gt e c h n i q u ea tp r e s e n tw i t ha d v a n t a g e ss u c h a sc r o s s p l a t f o r m ，l a n g u a g e i n d e p e n d e n c y , a n dp r a c t i c a b i l i t y , c o r b at e c h n i q u eh a s b e e nw i d e l yu t i l i z e di nm a n yd o m a i n sa p p l i c a t i o ns y s t e m s ，a n dm a k i n gi tt h ed ef a c t o i n d u s t r i a ls t a n d a r d b u ti nm i l i t a r y , t e l e c o m m u n i c a t i o n ，a v i a t i o na n dm a n u f a c t u r i n g d o m a i n ，t h e r ea r es o m ea p p l i c a t i o n st h a th a v er e a l t i m er e q u i r e m e n t o m g b j e c t m a n a g e m e n tg r o u p ) h a v ee x t e n d e dt h eg e n e r a lc o r b as p e c i f i c a t i o nt h e r e f o r e ，a n d w o r ko u tt h er e a l t i m ec o r b a s p e c i f i c a t i o nw i t hv e r s i o n10 ，1 1 ，2 0o n ea f t e rt h e o t h e r i nr e a l t i m ec o r b a s y s t e m ，t h ee s s e n t i a lp r o b l e mi sh o wt oa l l o c a t es y s t e m r e s o u r c e st or e a lt i m et a s k ss o a s t om e e tt h et i m ed e m a n do fe v e r yt a s k t h er e l e v a n t s y s t e ms c h e d u l i n gm o d e l ，a l g o r i t h m sa n dr e a l i z a t i o na r et h ec o r ep r o b l e mo fr e a l - t i m e c o r b a s y s t e mt h i sd i s s e r t a t i o ni sb a s e do no m gr e a lt i m ec o r b as p e c i f i c a t i o n 2 0a n df o c u s e do nt h ei s s u e sm e n t i o n e da b o v e ，d e v e l o p st h ef o l l o w i n gr e s e a r c h ： ( 1 ) t h ed i s s e r t a t i o na n a l y s e st h es c h e d u l i n gs t r a t e g ya n ds c h e d u l i n gf r a m e w o r k o f t a o ，ar e a l t i m ec o r b as y s t e m ，w h i c hd e v e l o p e db yw a s h i n g t o nu n i v e r s i t y ( 2 ) a n a l y s e st h ed i s t r i b u t a b l et h r e a d sn o t i o no f r e a l t i m ec o r b as p e c i f i c a t i o n 2 0 ，a n dt h en o d ei n d e p e n d e n ts c h e d u l i n gb a s e do ni t ，p o i n t so u tt h es h o r t a g eo fn o d e i n d e p e n d e n ts c h e d u l i n gm o d e l ( 3 ) a i m sa tt h es h o r t a g eo fn o d ei n d e p e n d e n ts c h e d u l i n gm o d e l ，at w o l e v e l s c h e d u l i n gc o r b a m o d e li s p r o p o s e d t h et w o l e v e ls c h e d u l i n gm o d e lf e t c h e si n m e t a s c h e d u l e ro nt h et o po fn o d e - s c h e d u l e r t h es c h e d u l a b i l i t y , w o r k l o a db a l a n c e a n d g l o b a lo p t i m i z a t i o ne t co f t h ep r o p o s e dm o d e la r ea n a l y z e d ( 4 ) r e f e r st ot h es c h e d u l i n gs t r a t e g ya n ds c h e d u l i n gf r a m e w o r ko ft a os y s t e m , t h ed i s s e r t a t i o n p r o p o s e s t h ei n t e r f a c ea n ds c h e d u l a b l ea l g o r i t h mo ft w o - l e v e l s c h e d u l i n gm o d e l k e yw o r b s ： t a or e a l t i m ec o r b ad i s t r i b u t a b l et h r e a d s n o d es c h e d u l i n gm e t as c h e d u l i n g g l o b a lo p t i m i z a t i o n n p 国科学技术大学硕士论文第1 章绪论 第1 章绪论 本章摘要：分布式应用系统的开发经历了s o c k e t 、r p c 以及分布式对象计算 等多个阶段，c o r b a 是目前最为流行的分布式对象计算技术之一，它具有跨平台、 语言无关性和面向对象思想等优点，实时c o r b a 是对通用c o r b a 的拓展，在军事、 电信、航空、制造等领域都有着非常广阔的应用前景。 1 1 分布式对象计算技术 起初，分布式应用系统是基于网络编程接口套接字( s o c k e t ) 或者t l i ( t r a n s p o r t l a y e r i n t e r f a c e ) i i 】进行开发的。在基于网络编程接口的开发方式中， 网络所提供的服务仅仅是用户数据的传输，并不涉及用户数据的定义，而用户在 开发过程中需要自己设计、实现应用之间的交互原语以及数据的编解码工作，这 些工作是相当复杂的，对开发人员的网络背景知识要求相当高，因此，基于这种 开发方式开发的主要是一些和网络密切相关的应用，例如文件传输、远程登录， 电子邮件等等。 随着分布应用需求的增加和c s 开发模式的流行，分布应用不再局限于网 络，而是丽向各个行业，用户需要层次更高的、屏蔽网络运输层细节的分布式应 用开发环境。由于当时程序的开发方式主要足以面向过程为主，对于普通开发人 员来说，需要能够像调用本地过程一样去调用远地的过程，因此以远程过程调用 ( r p c ) 2 1 为代表的分布式应用系统开发、运行环境便应运而生。但是随着新应 用、新技术和新需求的出现，它们开始变得有些不适应，存在的明显不足之处主 要包括以下两个方面t 3 】【4 】： ( i ) 虽然远程过程调用是按照c s 模式的模式构建系统。但是客户程序和 服务器程序之间的调用关系却是静态的也就是说，一旦程序发生了变化( 尤其 是服务方程序) ，那么整个系统就必须重新编译生成，原有的系统就会被抛弃。 ( 2 ) 从理论上说，客户程序和服务器程序必须使用r p c 的实现语言来编 制，这样就大大限制了用户的可选语言范围这些缺点限制了r p c 的进一步发 展。 中国科学技术大学硕士论文第1 章绪论 与此同时，在实际应用中。面向对象的分析、设计和开发方法的应用越来越 普遍。而且，由于传统上对象和访问对象的程序只能存在于同一进程之中，外部 进程无法了解和访问这些对象。传统的面向对象的开发工具也正在面临着支持分 布式处理的需求。凶此，分布式处理技术就逐步与面向对象技术相结合，并产生 了分布对蒙计算技术。 经过发展，：b l l 已经形成了) l o j , 主流的分布式汁算模型。其中包括o m o 组 织的c o r b a ( c o m m o no b j e c tr e q u e s tb r o k e ra r c h i t e c t u r e ，通用对象请求代理体 系结构) 标准、m i c r o s o f t 公司的c o m d c o m ( c o m p o n e n to b j e c tm o d e l i ) i s t r i b u t e d c o m ，组件对象模型分布组件对象模型) 标准、s u n 公司的j a v ar m i ( j a v ar e m o t e m e t h o di n v o c a t i o n ，j a v a 远程方法调用) 标准和o s f 的o o d c e ( o b j e c t - - o r i e n t e d d i s t r i b u t e dc o m p u t i n ge n v i r o n m e n t ，面向对象的分布式计算环境) 等。就目前的 应用范围、产品成熟度和市场占有量出发进行比较，c o r b a 、c o m d c o m 和 j a v a r m i 的应用是最为广泛的。 1 2c o r b a 技术 对象管理组织( o m g ) 成立于1 9 8 9 年，目前已经有8 0 0 余家著名的计算机公 司与机构加盟。o m g 组织一直致力于采纳和吸收基于面向对象的、异构分布环 境下应用的开发和支撑技术，积极制订相关标准，并于1 9 9 1 年开始推出了分布 式对象汁算的开放性标准- - c o r b a 规范。c o r b a 规范已经成为最有影响力的 分布式对象计算技术。根据不断发展的用户需求，o m g 组织已经发布了c o r b a 规范1 0 、2 0 、2 1 、2 2 、23 和3 0 t 5 】版本。随着c o r b a 技术以及c o r b a 产品 的推广和成熟，c o r b a 技术已经在制造、电信、金融、电子商务、军事、航空、 航天、教育和交通运输等应用领域的软件系统中得到了广泛的应用。 c o r b a 技术之所以能够如此广泛地应用，主要和它具备如下的特点【1 l l 有 关： ( i ) c o r b a 技术具有操作平台无关性。这可以使基于c o r b a 技术开发 的应用工作于不同的操作系统和网络环境一b - ( 事实上，目前各种c o r b a 产品所 支持的操作系统已经覆盖所有主流的操作系统) ；而且，客户与服务器可以位于 不同平台之上。 ( 2 ) c o r b a 技术具有编程语言无关性；这可以方便开发者采用多种编程 语言( 面向对缘月 面向对象) 编写应用系统( 目前最新版本的c o r b a 规范总 2 中图科学技术大学硬i ：论义第l 章绪论 哭支持六种编辆! 语占，即c + + 、c 、j a v a 、s m a l l t a l k 、a d a 和c o b o l ) ：而且， 客户和服务器可以使用不同的编程语言开发。 ( 3 ) c o r b a 技术基于面向对象思想；这样c o r b a 技术就秉承了面向对 象技术的所有特点，使基于c o r b a 技术的应用系统具有封装性和继承性。因此， 在统一接口描述语言o m gi d l 的支持下，c o r b a 麻用系统的客户端和服务器 端可以独立开发，而且系统的扩展和升级是相对方便和简单的。 1 3 实时c o r b a 系统 在c o r b a 技术不断拓展应用范围，向垂直领域发展的过程中，制造、军事、 电信以及航天航空等领域的某些应用( 例如过程控制、敏捷制造、核反应堆控制、 航空控制和c 3 i 或c 4 i 等) ，需要c o r b a 系统支持c s 交互的严格时间限制需 求。这样的应用系统一般称作分布式实时系统【”。然而，大量的研究和时间表明， 通用的c o r b a 规范以及响应的c o r b a 产品并不适用于支持分布式实时系统的 开发和运行。因此，c o r b a 技术本身需要进行拓展或者改进以支持实时应用的 需求。这在某种程度上可以被看作为c o r b a 技术向水平领域的发展f 6 1 0 实际上，实时处理和实时处理的研究工作已经具有相当长的历史。传统的实 时处理概念和技术主要集中在嵌入式控制系统领域，由于嵌入环境的特殊要求， 实时系统所能够利用的计算机硬件和软件系统的能力相当有限，从而传统实时系 统一般而言具有规模较小，结构简单，任务静态和处理集中的特点。实时处理和 实时系统的研究在当时，很大程度上隶属在嵌入系统的研究和开发范围之内【”。 但是，随着实时应用需求逐步向大型化，动态化以及分布化的方向发展，实时处 理和系统已经渗透到社会生活的各个领域并发挥着重要的作用。而实时任务调度 理论、实时操作系统、实时通信协议的研究也不断地得到发展，形成了大量有用 地结论、算法、工具。这些成果为c o r b a 技术向实时领域地发掌奠定了坚实的 基础。 把时间因素引入c o r b a 技术后，町以充分发挥c o r b a 技术在分布式软件 系统开发和集成方面的独特优势，提高分如式实时软件系统的质量，降低开发成 本和周期，并使得异构分布环境下实时软件系统具有可重用、可移植和可操作等 特性【3 5 i 。 中国科学技术大学硕士论文 第1 章绪论 1 3 1 实时系统概念 实时系统这个概念没有严格和统一的定义。一个比较常用的定义是【8 】：所谓 实时系统，是指这样的一类系统，它们的正确性不仅仅取决于其计算结果逻辑上 的正确性，同时也取决于获得计算结果的时间的正确性。 实时系统通常具备一下几个重要特征【9 l ： 及时性( t i m e l i n e s s ) ：实时系统所产生的结果在时间上有严格的要求，只有 符合时间约束条件的结果才是正确的。在实时系统中，每个任务都有一个截止期， 任务必须在这个截止期之内完成，以此来保证系统所产生的结果在时间上的正确 | 兰e 。 同时性( s i m u l t a n e i t y ) ：一般来说，一个实时系统通常有多个输入源，因此， 这就要求系统具有并行处理的能力，以便能同时处理多个实时任务。 可预测性( p r e d i c t a b i l i t y ) ：实时系统的实际行为必须在一定的限度内，而这 个限度可以从系统的定义获得。这意味着系统得处理必须全部是可预测的，即使 在最坏的条件下，系统也要严格遵守时间约束，实时系统性能得评价尺度是系统 行为在时间上得可预测性强弱，而非实时系统性能的主要评价尺度是系统行为的 平均时间。 根据实时系统的及时性特征，实时系统可以分为强实时系统和弱实时系统 i s l 。对于强实时系统而言，如果所产生的结果不符合时间约束，那么，由此带来 的错误将是严重的和不可恢复的，也就是说，强实时系统中的每一个任务完成时 间都不允许超过该任务的截止期。而对于弱实时系统来说，如果产生的结果不符 合时间约束，但由此带来的错误还是可以接受的、可以恢复的。这就是说，弱实 时系统中的某些任务的完成时间可以超过该任务的截止期。 根据实时系统调度策略的不同，实时系统可以分为静态系统和动态系统。所 谓静态系统，是指实时系统中的所有任务及其特性都预先己知并且不再变动，在 系统运行过程中，不会增加新的实时任务，也不会停止现有实时任务或者改变现 有实时任务的特性。而对于动态系统而言，在系统运行过程中，可以增加新的实 时任务，也可以停止现有实时任务或者改变现有实时任务的特性，也就是说系统 的任务是动态变化的。 从实时系统所调度的实时任务的特性来看，则可以把实时系统的任务划分为 周期性任务( 又称为基于速率的任务) 、非周期性任务( 又称为基于事件的任务) 。 4 中国科学技术大学硕士论文第1 章绪论 每个实时任务包含一组作业。个实时作业足它所对应的实时任务的具体实例， 它在特定的时刻被释放并进入就绪队列，等待调度器的调度。由于实时作业被释 放时就处于就绪状态，因此，后面的章节中，除非特别说明作业释放和作业就 绪可以互换使用。对于周期性任务，可以使用一个四元组来表示 ，t i = ( s i ed i ，p i ) ， 其中s i 表示任务的起始时间，e i 表示任务( 最坏) 执行时间，d i 表示( 相对) 截 止期。p ；则表示任务的周期。因此周期性任务的第k 个作业被释放( 即就绪) 的时间为t = s i + k p 。对于非周期性任务，可既使用一个三元组来表示t i = ( e i d 。p i ) ，其中e i 和d ，的含义于周期性任务的相同，而p i 则表示任务t i 的作业之 间的o 最小时间间隔，也就是说，非周期性任务的任意两个相邻作业j k 和j k l 被释放的时间满足一f 面的公式：j k t = p 。 1 3 2 实时c o r b a 应用需求 实时c o r b a 系统主要在一下的领域有应刚需求： ( 1 ) 军事领域。随着现代军事理论、战术和战备的不断发展，c 3 1 ( c o m m a n d ， c o n t r o l ，c o m m u n i c a t i o na n di n t e l l i g e n c e ) 以及c 4 i ( c o m m a n d ，c o n t r o l ， c o m m u n i c a t i o n ，c o m p u t e ra n di n t e l l i g e n c e ) 系统逐步得到了各国军事力量的重视。 这些现代军事系统强烈地依赖于快速、安全和实时的信息供应链；实时地从各类 传感设备( 包括卫星、空中、水面咀及水下的侦察设备) 采集数据，实时地传输 到分析机构进行分析和决策，再实时地传递到军事单元( 部队和武器系统) 。随 着这些系统的大量部署和实施可扩展的、安全的、实时分布支持环境成为了一 个至关紧要的环节，而实时分布对象中间件( 目前主要是c o r b a ) 就是其中一 个重要的组成部分。 ( 2 ) 电信领域：随着消费者对各种类型媒体信息需求的不断增加，电信公 司不得不在其有线和无线的网络环境下，部署更大带宽和实时的传输服务以支持 像视频点播这样的应删。此外，在网络管理系统中，为l 及时反映网络使用的状 况和性能以及即使处理f 嘲络的故障，需要实施舱控机制的支持。以上的服务和应 用都可以依托于实时c o r b a 系统实现，从而能够快速实施，方便扩展。 ( 3 ) 航空领域：目前的空中交通越来越繁忙，航空线路的拥塞和竞争也日 趋严重。现代航空管制系统因而就需要处理更高的交通流量，并提供更有效的线 路确定机制。这样，实时的现代航空管制系统将及时确定危险情况，灵活地寻找 合适的线路以缓解交通拥塞，防止航天器碰撞，从而增加安全性并提高交通效率。 中国科学技术大学硕士论文第1 章绪论 由于其应用环境的分锕性和异构性的特点，实时的现代航空管制系统也可以依托 于实时c o r b a 系统开发和实现。 ( 4 ) 制造领域：c o r b a 技术和系统应，h 一直足制造领域的热点。而许多 制造企业的车间的生产线都具有一定的实时需求。在生产一件产品的时候，机械 手或机器人需要根据定的工序，以一定的频率进行动作，对产品进行装配或者 混合。而且机械手或者机器人发生一定故障的时候，需要能够实时地通知控制系 统，以便及时干预，从错误中恢复到正常的生产过程。由此可见，在制造领域的 生产环境中，4 i 仅需要实时c o r b a 系统支持相关应用系统的开发和运行，而且 还需要实时c o r b a 系统具有一定的容错性。 在不周应用领域，( 分布式) 实时系统在其系统特性、实时任务集特性和调 度策略等方面存在着显著的差异。 实时c o r b a 系统作为一个面向对象的实时分布中间件，首要的需求是支持 具有不通特性的实时应用系统f 10 1 。而且，根据o m g 组织向其会员征询有关实时 c o r b a 系统功能和体系结构的需求意见的结果来看，除了需要支持具有上面所 列举的系统特性、调度策略和实时任务特性的实时系统的开发和运行之外，实时 c o r b a 系统还应该具有较高的性能和有效控制资源( 计算资源、通信资源和存 储资源等) 的机制。只有消除c o r b a 系统本身多余的开销，进行适度的性能优 化，才能够在系统资源有限的前提下，支持尽可能多的实时任务的并发运行。而 实时c o r b a 系统的实现也取决于系统对端系统资源( 主要是c p u 处理资源和 内存资源) 以及网络资源的管理、控制的能力和程度。 o m g 组织为了促进实时c o r b a 技术的发展，加快实时c o r b a 规范的制 订，也相应成立了实时特别兴趣工作组( r t s i g ) ，改工作组的目的就是制定实 时c o r b a 规范，并最终使得所制订的实时c o r b a 规范成为c o r b a 3 0 标准族 的一个组成部分【l 。r t s i g 认为实时c o r b a 规范应该达到以下的一系列目标： 定义实时c o r b a 系统的o m g i d l 接口并对其应用语义作出具体解释； 保证实时c o r b a 系统能够在不同的垂直领域进行互操作，这些应用领域包 括命令，控制系统、电信系统、医疗系统以及金融系统等等， 实时c o r b a 规范与c o r b a 规范已经相关的c o r b a 公共对缘服务兼容。 实时c o r b a 规范尽可能利厢舀静实时处理领域已有的国际标准、事实标准 或工业标准， 目前，在r t s i g 的努力下，0 m g 组织已经发布了“实时c o r b a l 0 规范”、 6 中国科学技术大学硕士论文 第1 章绪论 “实u 寸c o r b a i1 规范”、“实时c o r b a 20 规范”。本论文对实时c o r b a 系统 调度模型以及实现的研究就是基于实时c o r b a 20 规范1 的。 1 4 论文梗概 本文主要分析了t a o 的基于策略的调度模型和框架，并结合o m g 组织的 实时c o r b a 规范2 0 ，研究了实时o r b a 系统的调度模型，提出了一个二层调 度模型，这是在节点独立调度模型的基础上的改进，最后给出了二层调度模型的 接口描述和可调度分析算法，文章下面的章节是这样组织的： 第二章：实时c o r b a 技术的研究工作很大程度上依赖于已有的大量实时处 理领域( 尤其是实时任务调度理论，实时操作系统以及实施通信网络) 的研究成 果，因此在介绍实时c o r b a 技术和系统的具体研究和实验之前，有必要先对实 时处理技术的研究理论与实践进行简要的介绍。本章首先介绍了实时任务的时钟 驱动方法和优先级驱动方法两大类调度方法，着重介绍了优先级驱动方法中一些 著名的算法和资源访问控制的协议；并详细分析了华盛顿大学开发的实时 c o r b a 系统t a o 的基于策略的调度方法。 第三章：介绍了实时c o r b a 规范2 0 中可分布线程的概念，并分析了基于 可分布线程的节点独立调度的特点，节点独立调度能够使得各个节点上的可分布 线程有序执行具有灵活性较高，比较简单等特点；但是节点独立调度由于各个 节点“各自为政”，缺乏全局观点，在系统的结点负载平衡、可调度性和全局优 化性方面存在着可以改进之处，并在此基础上挺出了二层调度模型，着力于解决 负载平衡、可调度性以及调度的全局优化性等问题。 第四章：介绍了t a o 调度模型和框架下的实现接口，并参照实时c o r b a 规范2 0 ，给出了基于可分布线程的二层调度模型i d l 接口描述；最后分析了二 层调度模型可调度性算法。 第五章：对全文的研究内容、研究方法和贡献进行了总结，最后提出了进一 步的研究工作。 中国科学技术大学硕士论文第2 章实时c o r b a 系统相关工作 第2 章实时c o r b a 系统相关工作 本章摘要：本章首先介绍了实时任务的时钟驱动方法和优先级驱动方法两大 类调度方法，着重介绍了优先级驱动方法中一些著名的算法和资源访问控制的协 议：并详细分析了华盛顿大学开发的实时c o r b a 系统t a 0 的基于策略的调度方法 2 1 前言 实时c o r b a 技术的研究工作很大程度上依赖于已有的大量实时处理领域 ( 尤其是实时任务调度理论，实时操作系统以及实施通信网络) 的研究成果，因 此在介绍实时c o r b a 技术和系统的具体研究和实验之前，有必要先对实时处理 技术的研究理论与实践进行简要的介绍。 2 2 实对任务调度方法 任何实时系统的目标都是为了在有限的资源限制下调度一组任务以达到一 定的目标( 例如，满足所有的任务截止期，使截止期延时最小等等) ，所以，实 时调度理论是实时处理技术的核心与关键。 实时任务调度方法一般可以分为砖大类1 2 】：基于时钟的调度方法( 时钟驱 动方法) 和基于优先级的调度方法( 也叫事件驱动方法) 。 2 2 1 时钟驱动方法 在时钟驱动的调度方 去中，通常对系统模型做如下假设： 系统包含n 个周期性任务。只要系统处于运行状态，你就是固定的： 所有周期性任务的参数都预先可知。特别地，任意周期性任务地作业被释放 的时刻之间的偏差可以忽略不计。也就是说，任务t i 的每个作业都在其前一个 作业被释放的p i 单位时间后被释放并且就绪； 每个作业h 在其就绪时刻r 吐之后就立即准备执行。 根据时钟驱动的调度方法。调度器在某个预先设定的特定时刻，确定在处理 8 中国科学技术大学硕士论文第2 章实时c o r b a 系统相关工作 器上执行哪个实时作业。通常，对于一个采用时钟驱动的调度方法的系统而言， 系统中所有实时作业的相关参数都是预先可知的，而且这些参数在系统执行过程 中，足固定不变的。这样，系统中的作、i k 调度序列就能够在离线状态下被计算出 来， ：且存储在系统r 1 1 。神：系统的运行过程小，调度器根据浚调度序列在调度时 刻对实时作业进行调度。 时钟驱动的调度器通常是周期性地进行工作。周期性地调度决策时刻就把时 间轴划分成为一个个地“时间帧”( f r a m e ) 。每个时间帧具有特定地长度，称之 为时间帧长度f a 因为调度器的调度决策仅仅在每个时间帧的起始时刻才会进行，所以在各个 时间帧内部是不会抢占地。调度器不仅需要在调度决策时刻选择下一个执行地作 业，而且也需要对每个时间帧内所需调度的各个作业是否都已经就绪以及系统是 否处于过载状态等情况进行监控和处理。 时间帧的选择对于时钟驱动的调度方法而言是最为关键的因素。选择时间帧 可以有许多考虑的准则，而且这些准则之间有时是互相矛盾的。例如，如果时间 帧足够长，则各个作业能够在一个时间帧内完成，从而避免作业之间的抢占；而 如果时间帧足够短，就能够使得调度器的循环执行时间间隔长度足够小，并因此 减少各任务的平均等待时间。因此，调度器时间帧必须根据具体的应用系统以及 系统中所有实时任务的参数进行仔细的选择。当确定了时间帧之后，某些作业可 能需要根据时间帧的长度被划分多个具有较小执行时间的片断。 这样，时间驱动的调度方法可以分为两个步骤：在第一个步骤中，所有工作 都是离线的状态下进行的。首先，选择适当的时间帧长度；其次将某些作业划分 多个片段；最后将这些作业以及作业的片断分配到不同的时间帧中，l ( k ) 列出了 在第k 个时间帧调度器所调度执行的作业和作业片断；而f 则表示在一个调度器 主执行循环( 主执行循环的长度为所有周期性实时任务的周期的最小公倍数) 中 所包含的时间帧数目。 第二步，调度器就基于第一步中生成的序列，按照以下的调度算法进行调度。 该算法在每个时间帧开始时刻进行执行。而且该算法还能够调度非周期性作业， 使之能够使用周期性任务的作业使用剩余的时间。 时钟驱动的调度方法有许多优点i “1 。最重要的一点就是它的简单性。时钟 驱动的调度方法相对而言，比较容易验证和测试。 但是时钟驱动调度方法也有许多缺点。最明显的一个缺陷【2 9 j 就是时钟驱动 中周科学技术大学硕士论文第2 章实时c o r b a 系统相关工作 的调度方法很脆弱。因为时钟驱动的调度方法需要系统中所有周期性任务的参数 预先可知且固定不变，所以，时钏驱动的调度方法是静态的，难以应用到动态系 统。 2 2 2 优先级驱动疗法 优先级驱动方法调度决策时刻是在作业被释放和完成的时刻，这一点上和时 钟驱动的调度方法是不同的，时间驱动方法也称优先级调度方法，是实时调度方 法和理论当中最为重要的类方法。 目前大多数优先级驱动的调度算法都是针对单处理器设计的，它们基本上都 将周期性任务作为调度对象，丽且大多数也采用了抢占式的系统模型( 高优先级 的任务可以抢占低优先级的任务进行执行) 。优先级调度方法调度周期性任务的 算法可以分为两类： 固定优先级算法( f i x e d ，p r i o r i t y ) ：对个任务中所有作业都分配相同的优先 级。 动态优先级算法( d y n a m i c p r i o r i t y ) ：对一个任务中的每个作业可能分配不 同的优先级。每个作业的优先级是当它被释放进入就绪队列时分配的。旦分配 了优先级，作业的优先级就不再改变。 实际上，可以把优先级驱动的实施调度算法分为三类：固定优先级算法、任 务级动态优先级( 作业级固定优先级) 算法，和作业包括任务级动态优先级算法。 在一般实时调度方法研究文献中，所谓动态调度算法，指的是任务级动态优先级 ( 作业级固定优先级) 算法。 动态优先级算法 最早截止期优先算法1 1 3 l ( e a d i e s td e a d l i n ef i r s t 简称e d f ) 是一种基于操 作的截止期对操作的分发进行排序的动态优先级调度算法。该算法通过给截止期 较近的操作赋予较高的优先级来保证截止期最近的操作在截止期较远的操作之 前被分发。e d f 允许动态地( 运行时) 改变操作地周期和频率。只要有操作地 调度请求，e d f 调度策略就被调用。新分发的操作可能会也可能不会优先占有 当前执行的操作，这要看优先级部件如何映射到线程优先级的。 e d f 最主要的局限是不管余留下的时间够不够在截止期之前完成此次执行， 距离截止期最近的操作都会被分发。因此，若一个操作在截止期之前不能够完成， 那么截止期过去之前是检测不出来的。若一个在截止期之前不能够完成的操作被 o _ l 国科学技术大学硕士论文第2 章实叶c o r b a 系统相关工作 分发了，本可以分配给其它操作的c p u 时间就被浪费了。 最小松弛度优先算法1 1 4 j ( m i n i m u ml a x i t yf i r s t ，简称m l f ) 的产生就是为 了改善e d f 的缺陷。松弛度是此刻到截止期的时间减去操作的剩余执行时间。 m l f 通过综合考虑操作的剩余执行时间和截止期来改善e d f 算法，当一个作业 被释放时，调度器就检查所有就绪作业的松弛度，并根据它们的松弛时间进行排 序：松弛时间越小，优先级就越高。使用m l f 可以检测山到最终期限之前不能 完成的搡作，若发生这种情况，在分配余下的c p u 时间时。调度会管理这些操 作。例如，一利，策略就是简单的摘除那些松弛度4 i 够的操作，这种策略会减小后 面的操作错过截止期的概率，当系统暂时过载时效果更为明显。 最大化增值效用( m a x i m i z ea c c r u e du t i l i t y ，简称m a l t ) 最大化增值效用算 法使用一个效用函数和每个线程相关联来建立线程调度。每个函数提供了线程的 完成时间到一个效用值的映射。例如，完成时间非常接近于截止期限但是先于截 止期限将是非常有用的，然而完成时间大大提前于截止期限的用处将会很小，完 成时间滞后于截止期限将毫无用处甚至有负面作用。传统的截止期限是效用函数 的一种特殊情况。m a u 原则寻找导致最大化增值效用的调度。m a u 主要用于 动态系统。 除此之外，还有先进先出算法( f i r s ti nf i r s to u t ，简称f 正o ) 和后进先出 算法( l a s ti nf i r s to u t ，简称l i f o ) ，也都是动态优先级算法。 当作业之间允许抢占，且作业之间不存在共享资源时，e d f ( m l f ) 算法能 对运行于单处理器上的实时作业j ( 各个作业具有任意的作业就绪时间和截止 期) ，找到一个可行的调度，当且今当实时作业集j 存在可行的调度。这样e d f 和m l f 算法就是最优的( o p t i m a l ) 。“屉优”的调度算法意味着，如果一组作业 存在可行的调度满足各个作业的截止期需求，那么，e d f ( m l f ) 算法必然能够 找到一个这样的调度序列：而对一组作业e d f ( m l f ) 算法找不到可行的调度， 那么任何其它算法都无法找到可行的调度策略。 动态优先级调度算法的调度决策时刻足在作业就绪或者完成的时刻。也就是 说。每当某个任务的作业被释放并就绪，或者该任务完成其执行，调度器就需要 为所有就绪的作业重新设定新的优先级并根据新的优先级从就绪作、队列里选 择作业进行执行。 固定优先级算法 速率单调( r a t em o n o t o n i c ) 算法是一个十分著名的固定优先级调度算法。 中国科学技术大学硕士论义第2 章实时c o r b a 系统相关工作 该算法根据任务的周期分配它们的优先级：周期越短，优先级越高。个任务的 速率( r a t e ) 也就是该任务的作业释放速率，即就是该任务周期的倒数。 另一个著名的固定优先级的调度算法是“截止期单调”( d e a d l i n em o n o t o n i c ) 算法。该算法根据任务的相对截止期分配优先级：相对截止期越小，优先级越高。 当每个任务的相对截止期和其周期成固定比例时，r m 算法和d m 算法是相 同的。f i 当各个任务的相对截止期与其周期不成固定比例时，d m 算法比r m 算 法更优。也就是说，有时r m 算法尢法得到可行的调度时，r m 算法总是无法得 到可行调度。 此外，固定优先级调度算法和动态优先级调度算法e d f 和m l f 的一个重要 不同在于【3 4 1 ；一般而言，固定优先级算法不是最优的。也就是说，固定优先级 调度算法在调度某些具有可行调度系统时，按照所分配的优先级，可能会导致失 败( 某些任务无法满足截止期的要求) 。 资源访问控制 许多关于优先级驱动的调度算法的结论在各任务( 的作业) 之间存在资源共 享的情况下都无法直接适用。一般地，除了处理器之外，系统还可能包含多种可 以串行使用地共享资源，而每种资源义包含了多个不同地单元。这些共享资源一 般是按照不可抢占和互斥地方法进行分配地。换句话说，当一个单位地资源被分 配给一个作业时，该单位不能被其它作业所使用，除非使用该资源地作业释放了 该资源【1 9 1 。 任务( 的作业) 之问存在资源共享的情况下，常用的同步方式主要是锁( l o c k ) 和信号灯( s e m a p h o r e ) 。但是，仅仅使用锁或者信号灯同步对共享资源的访问， 则可能引起死锁或者优先级逆置问题1 6 】。优先级逆置问题是指由于资源共享，造 成实时系统中高优先级任务长时间被低优先级任务阻塞的现象。任务间资源的进 竞争可能导致优先级逆置，主要是因为资源是以不可抢占的方式分配给作业的。 这样，在作业间因为资源冲突时，即使作业是可抢占的，一个高优先级的作业也 可能被低优先级的作业所阻塞。当发生优先级逆置时，时间特性的异常现象就相 伴而生了。更为严重的是，如果没有好的资源访问控制，优先级倒置的持续时间 是不可预期和不可限定的。 通过规定加锁顺序可以避免死锁问题，却无法解决优先级逆置，从而无法保 证实时任务在时间上的可预测性。因此，必须设计相应的资源访问控制协议 ( r e s o u r c ea c c e s s c o n t r o lp r o t o c 0 1 ) ，简称访问控制协议( a c c e s s c o n t r o l 中国科学技术大学硕士论文第2 章实时c c r b a 系统相关工作 p r o t o c 0 1 ) ，是一组控制下述行为的规则：( 1 ) 何时以及在什么条件下一个资源请 求才能够进行资源分配；( 2 ) 请求资源的作业是如何进行调度的。资源访问控制 协议的设计目标主要就是控制优先级逆置，即使得每次优先级逆置的持续时间 ( 高优先级的任务阻塞时间) 是有确定上界的。 目前主要的资源访问控制协议包括：n p c s 协议1 5 l 、优先级继承协议【“l ( p i p ) 和优先级升限协议( p c p ) 。目前使用最广泛的资源访问控制协议是优先级升限 协议，它实际上是为了解决优先级继承协议可能引起的死锁问题产生的。优先级 升限协议包括基奉p c p 洳议f 1 7 j l ”i 、升限优先级卧议( c p p ) 和基于堆栈的p c p 协议1 1 9 1 。 优先级升限协议定义了一个概念【”l ：优先级升限。优先级升限分为资源优 先级升限和系统优先级升限。资源优先级升限记录了所有使用该共享资源的作业 的最高的优先级；而系统优先级升限则记录了当前时刻，系统中所使用的资源优 先级升限的最大值。由此可见，优先级升限协议的运用必须预先知道系统中的各 个作业对系统共享资源的使用情况以及各个作业的优先级。 在调度器调度各个作业时，按照作业的当前优先级( 此时，当前优先级等与 其分配优先级) 进行调度的。在需要使用共享资源时，如果资源正在被使用，那 么请求该资源的作业就被阻塞。如果该资源并没有被使用，那么就判断该作业的 优先级是否大于当前的系统优先级升限，如果当前的系统优先级升限，就把该共 享资源分配给该作业。如果该作业的优先级并不大于当前的系统优先级升限，而 正在使用的资源中，所有资