（计算机应用技术专业论文）硬实时调度抢占开销的在线优化策略及仿真实现.pdf

l 户 l - at h e s i sf o rt h e d e g l l e eo fm a s t e ri nc o m p u t e ra p p h c a t i o nt e c h n o l o 野 m 一 。l 。n eo n l i n eo d t l m l z a t l o ns t r a t eg va n ds l m u l a t l o no 士d r e e m p t l o n o v e r h e a di nh a r dr e a l 一t i m es c h e d u l i n g b yz h a o z h e ny u s u p e r v i s o r ：p r o f e s s o rz h a 0h a i n o r t h e a s t e mu n i v e r s i t y d e c e m b e r2 0 0 7 046 jjjji4咖8i_y j 1 独创性声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文中取得的 研究成果除加以标注和致谢的地方外，不包含其他人已经发表或撰写过的 研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示诚挚 的谢意。 学位论文储签名：缓于 签字日 强：弘晤l2 ，f 钐 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论 文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部 或部分内容编入有关数据库进行检索、交流。 ( 如作者和导师同意网上交流，请在下方签名：否则视为不同意) 学位论文作者签名：乏乡邑萝导师签名：巡沟 签字 日期 ：舢铲2 口签字日期：7 沉谬。2 矽 东北大学硕士学位论文摘要 硬实时调度抢占开销的在线优化策略及仿真实现 摘要 嵌入式系统已广泛地应用到人们的生产生活领域。在硬实时嵌入式系统中，任务间 的抢占不仅导致操作系统上下文切换的时间开销，而且还会造成存储设备、网络设备、 外界环境等资源带宽的降低以及能源消耗的浪费。如何在保证系统实时性的同时，对硬 实时任务调度中的抢占开销进行优化，提高系统性能是本文研究的主要问题。 本文在实时系统通用的周期性任务模型基础上分析了固定优先级以及动态优先级 实时调度的时序关系及任务间的抢占关系。分别对r m 调度和e d f 调度抢占行为的可 推迟时间进行了量化分析，推导出受低优先级任务阻塞而造成的受阻任务集，以及在任 意抢占时刻，推迟高优先级硬实时任务的执行来避免抢占发生的判定条件。提出了一种 硬实时任务调度抢占开销的在线优化策略。通过在m a t l a b 中的t o r s c 脏工具箱搭建 仿真测试环境，对该优化策略进行了仿真实验。并与标准r m ，e d f 调度模型以及抢占阈 值静态模型的仿真实验数据进行了对比。 仿真实验数据结果表明，本文提出的硬实时任务调度中抢占开销在线优化策略可以 有效地减少系统运行中的抢占次数。能够在保证任务的可调度性的同时，有效减少不同 调度算法下任务抢占发生的次数，降低抢占开销。 关键词：嵌入式系统；硬实时；抢占优化；抢占阈值模型；阻塞任务集 一i l 东北大学硕士学位论文 a b s t r a c t t h eo i d i n eo p t i m i z a t i o ns t r a t e g ya n ds i m u l a t i o no f p r e e m p t i o n o v e r h e a di nh a r dr e a l t i m es c h e d u l i n g a b s t r a c t t h ee m b c d d e ds y s t e mh 弱b e 钮w i d e l y a p p l i c dt 0p e o p l e sl i v 嚣觚dp r o d u c t i 册a r e 孤h t h eh a r d 他a l - t i m ee m b e d d e ds y s t e m s ，t h cp r e c m p t i 仰s0 ft a s l 【sn o t 0 n l yl e a d t 0t h e c 0 n t c x t - s w i t c h i l l gt i m cs p e n d i n g0 ft h e 叩e m t i n gs y s t e m ，孤do t h e r 他s o 姗c c st 0 他d u c c b 狮d w i d t h 锄dw 弱t c e 略y n 蛐m p t i h o wt 0g u a 砌t e et h c 他a 1 t i m cc h a r a c l 叮0 f s y s t 啪，o p t i m i z et h ep f c e m p t i o n0 v e r h e a d0 fh a r dr c a l - t i i i l et 弱ks c h e d u l i n g 柚di m p r o v ct l l e s y s t 锄p c 哟锄柚c cm t h em a i ni s s u ei nt h i sp a p c r ht h i sp a p l c r ，岫d e rt h e 岫i v e r s a lp c r i o d i ct a s km o d e lo f 陀a 1 t i m es y s t e m s ，t h ea u n l o r 锄a l l ) ，z e st h et i m i n gr e l a t i 咖s h i po f 钕e d 埘硎t y 锄dd y n 锄i c 埘硎t ys c h e d u h n g 粕dt h e p r c e m p t i r e l 撕0 n s h i p 锄0 n gt a s l 【s w h n cf e s p e c t i v e l yd o i n gt h cq u 锄t i t a t i v c 锄a l y s i st 0m e s u s p e n d i n g 劬eo ft l 地r m 锄de d fs c h e d u l i n gp r c e m p t i o na d i o n 懿p c nt h eb 1 0 c k c dt 弱k s e t0 b s t n l c t c db y1 0 w 研谢t yt a s l 【s 卸dt h ed c t e m i n 锄tc o n d j t i t 0a y o i dt h cp r c e m p t i 伽i n t h e 砷i t r a r ) rp r e e m p t i o nm o m e n tb yp o s t p o n i n gh i g h - p r i o r i t yt a s l 【si nh a f df e a l t i n l e s y s t e m t h i sp a p c rp r c s e n t sa no n l i n eo p t i m i z a t i o ns 缸a t e g y0 fh 棚他a l t i m et 砸汰s c h e d u l i n g p f c 锄p t i o ns p e n d i n 昏b yt h et o r s c h et 0 0 l b o xo fm a t l a b ，t h e 孤t h o rb u i l das i m u l a t i o n t c s tc n v i 姗m 锄t 柚dc o n d u c tt h es i m u l a t i 蚰t e s tt 0t h eo p t i m i z a t i s 缸砒e 西鼯a n dt h ed a t a c o m p 砌w i t hm es i m u l a t i o nd a t ao ft h cs t 锄d a r dr m ，e d fs c h e d u l i n gm o d e l 卸dt h c p r e e m p t i o nt h r c s h o l dm o d e l t h es i m u l a t i o n 懿p e r i m e n t a lr c s u l t ss h o wt h a t ，t h eh 缸dr e a l - t i m et a s k h e d u l i n g i z i n g t h eo n l i n co p t i m i z a t i o ns t r a t e g yp r c s e n t e db yt h i sp a p e fc a n e f ! f e c t i v e l yr e d u c ct h en u m b e r0 f p r e e m p t i o n si nt h es y s t e mo p e n t i w 1 l i l et 0e n s u r et h et 雒ks c h e d u l i n 岛e f ! 陋c t i v e l yf e d u t l l en 啪b c ro ft 弱kp r e e m p t i o n si nt h ed i 仃e r c n ts c h e d u l i n ga 1 9 0 r i t h m s 卸dt h ep r c e m p t i o v e r h e a d k 对w o r d s ： e m b e d d e d s y s t e m ；h a r dr e a l t i l e ；o p t i m i z a t i o np r c e m p t i ；p r e e m p t i t h r c s h o l d ；o b s t m c t i v et a s ks e t n i 东北大学硕士学位论文 目录 目录 独创性声明。i 摘要1 l a b s t ra c t 。i i i 第一章绪论。l 1 1 嵌入式系统的特点与实时性。1 1 2 嵌入式实时系统与实时调度1 1 2 1 嵌入式实时系统1 1 2 2 实时任务调度2 1 3 在线调度与离线调度2 1 4 抢占优化的意义3 1 5 论文的结构安排。3 第二章实时系统参考模型5 2 1 实时系统工作负荷的时间参数5 2 1 1 释放时间与时限5 2 1 2 任务的执行时间5 2 2 任务模型6 2 2 1 周期性任务模型6 2 2 2 非周期和偶发任务7 2 3 实时调度算法7 2 3 1 固定优先级调度算法。8 2 3 2 动态优先级调度算法8 2 4 抢占阈值模型9 2 4 1 临界时刻( c r i t i c a li n s t 觚t k 1 0 2 4 2 i 级忙周期( 1 c v e l - i b u s yp e r i o d ) 1 0 2 4 3 任务模型。1 0 2 4 4 运行机制模型1 1 2 4 5 可调度性分析1 1 2 4 6 预定义优先级的抢占阈值分配。1 3 2 5 本章小结。1 5 第三章实时调度抢占开销的在线优化1 7 3 1 固定优先级调度抢占开销的在线优化1 7 一v 一 东北大学硕士学位论文目录 3 1 1 启发性的例子1 8 3 1 2 符号与假设。1 9 3 1 3 固定优先级调度算法的可调度性条件2 0 3 1 4 有效时限2 1 3 1 5 抢占作业可被阻塞时间上限计算2 2 3 1 6 阻塞任务集的确定2 4 3 1 7 固定优先级系统中的静态空闲计算2 5 3 1 8 减少抢占的在线判定2 6 3 1 9 算法描述2 6 3 2 动态优先级调度抢占开销的在线优化2 7 3 2 1 符号与假设2 7 3 2 2e d f 算法的可调度性条件2 8 3 2 3 抢占作业可被阻塞的时间上限。2 9 3 2 4 确定受阻作业集3 0 3 2 5 减少抢占的在线判定3 1 3 2 6 算法描述3 3 第四章抢占开销优化策略的仿真3 5 4 1 仿真平台环境。3 5 4 2 仿真程序工作原理3 5 4 2 1 随机任务集的产生3 5 4 2 2 任务调度仿真3 5 4 3 任务抢占判定仿真3 9 4 3 1 固定优先级任务抢占判定3 9 4 3 2 动态优先级任务抢占判定4 0 4 4 抢占阈值模型的仿真实现4 2 第五章仿真实验结果及数据分析4 3 5 1r m 调度抢占优化结果统计分析。4 3 5 1 1r m 调度抢占优化实验数据4 3 5 1 2r m 抢占开销优化实验结果4 4 5 1 3r m 抢占优化仿真实验数据分析4 5 5 2e d f 调度的优化效果及统计分析4 6 5 2 1e d f 抢占优化实验结果4 7 5 2 2e d f 抢占优化仿真实验数据分析。4 9 5 3 本章小结5 0 第六章总结与展望5 1 一v 卜一 东北大学硕士学位论文目录 6 1 本文的贡献5 1 6 2 未来工作展望5 l 参考文献5 3 致 谢5 7 一v i i 东北大学硕士学位论文第一章绪论 第一章绪论 1 1 嵌入式系统的特点与实时性 嵌入式系统( e m b e d d e ds y s t e m ) 【1 捌多指深藏于通信设备、工业系统、机电仪表、消 费电子类产品内部，完成某种特定功能的计算机系统【3 1 。它是以应用为中心，软硬件可 裁减的，适应应用系统对功能、可靠性、成本、体积、功耗等综合性严格要求的专用计 算机系统。 嵌入式系统现已广泛应用到生产，生活中的电器设备，如汽车电子系统、工业控制 设备、移动计算设备、汽车、电梯、工业自动化仪表与医疗仪器等。但是由于体积，能 耗，价格等各方面的约束，其处理器速度往往比较慢，存储容量有限。由于嵌入式系统资 源的有限性，因此如何高效利用受限的资源是嵌入式系统设计的关键问题。大多数的嵌 入式系统需要跟踪外界动态的连续物理过程或离散事件，并在一定的时间约束内作出计 算响应达到预期控制效果，因此实时性也是嵌入式应用系统的重要特性之一。 1 2 嵌入式实时系统与实时调度 1 2 1 嵌入式实时系统 实时系统是指系统在接收到数据的同时，能够在规定的时间内予以响应，以足够快 的速度处理，及时将处理结果送往目的地的一种处理系统。这种系统的正确性不仅依赖 于计算的逻辑结果，而且还与计算结果产生的时间有关h 1 。对于什么是实时，p o s 1 0 0 3 1 b 标准作了这样的定义：操作系统在限定的时间内提供所需服务水平的能力。如 果任务没有在规定的时间内完成，计算结果不仅毫无意义，而且有时还会引起严重的后 果。因为实时性是嵌入式系统与生俱来的属性，也是外界应用环境对嵌入式系统的根本 要求，因此，平日所说的嵌入式系统通常就是特指嵌入式实时系统。 在嵌入式实时系统中任务一般都对截止时间有要求，按照对时间要求的强与弱，嵌 入式实时系统一般可以分为嵌入式硬实时系统和嵌入式软实时系统。硬实时和软实时的 定义【5 纠筇3 8 l 一般基于任务( 系统的工作负荷) 功能的关键程度、迟到结果的可用性和时 限约束的确定性以及概率特性。通常使用的定义是如果不能满足定时约束或时限就被认 为是致命的错误，那么该定时约束就是硬实时约束。一个硬实时约束的任务错过截止期 所产生的结果将会导致灾难性的后果。而软实时约束不能被满足并不会造成严重的伤 害，但随着实时任务延迟完成数量的增多，系统的整体性能会表现为严重下降。具有硬 实时约束的任务就是硬实时任务。含有硬实时任务的嵌入式系统称为嵌入式硬实时系 一1 一 东北大学硕士学位论文第一章绪论 统。很多嵌入式系统都是嵌入式硬实时系统。 1 2 2 实时任务调度 调度的实质是资源分配，而实时任务的调度强调的是任务的时间约束【7 1 。在实时系 统中，实时应用功能互不相同的各种任务构成一个并发活动的有机整体，并且任务之间 存在着各种复杂的逻辑关系。如何统一安排各个任务的执行，以确保所有任务在其截止 期内完成是实时系统的一个关键问题，通常称为实时任务调度。 实时系统最本质的特征是任务的实时性和可预测性。因此，实时系统的首要目标是 满足系统内实时任务的时间约束，合理地调度并执行它们，使它们能在各自的任务时限 ( d e a d l i n e ) 之前完成操作。这就使实时任务的调度成为实时系统的核心问题之一，它是 计算机科学领域研究的热点之一嘲。 由于实时系统的侧重点不同，实时调度亦有多种分类方式【9 1 0 托3 7 1 。根据任务是在一 个或多个处理器上运行，分为单处理器实时调度和多处理器实时调度，多处理器实时调 度又可分为集中式调度和分布式调度；根据调度算法和可调度分析是在任务运行之前还 是运行期间进行的，分为静态调度、动态调度和混合调度；根据被调度的任务是否可以 互相抢占，分为抢占式调度和非抢占式调度；根据任务请求到达的情况不同，分为周期 性任务调度和非周期性任务调度，不同调度方式具有各自的优缺点，适用于不同类型的 实时系统。 1 3 在线调度与离线调度 调度程序通常使用事先计算好的实时作业的调度表，如果该调度表的计算基于全部 时间内所有作业的释放时间和处理器时间资源需求。当系统的操作模式发生改变时，也 要为了使用而事先计算和保存新的调度表，以指定每个作业在新的操作模式下何时执 行。这种情况下，称这种调度为离线调度。如果调度程序在每次做出调度决策的时候， 还不知道将要释放的作业的任何信息，就称这种调度程序是在线的或者说使用了在线算 法；直到作业被释放之后，在线调度程序才知道每个作业的参数。 离线调度的一个明显缺点是它的不灵活性。只有当系统是确定的时候，该方法才能 适用。系统的确定性是指系统提供一组固定的功能，所有作业的释放时间和处理器时间 资源需求都是已知的，它们不会发生变化或者只变化很小。对于确定性的系统，离线调 度具有一些优点，其中一个是系统具有确定的定时行为。 当系统中将来的工作负荷上具有不可预测性的时候，在线调度是系统惟一的选择方 式。在线调度程序能够适应用户序需求和资源可用性方面的动态变化。但在线调度的灵 活性和适应性降低了调度程序充分利用系统资源的能力。 一2 一 东北大学硕士学位论文第一章绪论 1 4 抢占优化的意义。 当前许多调度算法都试图充分利用任务集合的某一些特性，但没有一种算法能适合 所有类型的任务集合。l i u 和l a v l 锄d 的开创性工作奠定了实时调度分析的基础，其首 先提出的固定优先级调度算法( 如r m 、d m 调度算法) 和动态优先级调度算法( 如e i ) f 调度算法) 都是非常简单有效的实时调度算法。由于到目前为止建立的这些理想化的调 度理论基本上都忽略了在非理想资源上调度一个任务集所导致的实现开销，因此实时调 度理论与其在特定硬件平台上实时操作系统内核中的实现存在着很大的差距。 抢占是指在一个任务的执行过程中，当有高优先级任务就绪时，调度程序中断当前 低优先级任务的执行，优先执行高优先级任务，待高优先级任务执行完毕后再返回执行 这个被中断的低优先级任务。 当使用抢占式调度算法时，每个任务会使用一个栈空间，消耗较多的内存资源，产 生一定的系统开销，其中包括任务切换过程中操作系统保存当前任务的堆栈指针、程序 计数器和通用寄存器以及恢复低优先级任务上下文的时间和空间开销；对于带有c a c h c 的高端处理器，抢占会导致被抢占任务的数据及指令重复多次在c a c h e 中释放后又重新崎一 装载，造成一定的时间延迟和能源消耗。 另一方面，对于操作系统调度的实时应用来说，抢占会产生不同程度的负面影响。止， 以磁盘调度为例，如果磁盘文件的读和写操作都是可抢占的，那么每次这些操作被抢占 时，重新恢复被抢占的文件读、写操作都需要额外的寻道时间，此时多余的抢占会损失 很大的带宽。根据应用的不同，受到抢占行为的影响也各不相同，这种影响可以统称为 抢占导致的应用开销。 由此可知，实时系统的抢占开销包括操作系统开销和外部应用开销。而在多数的实 时应用中，系统的工作负荷是由很多频率快，执行时间短的任务组成，任务的抢占开销 相对于整体系统是不可忽略的，传统实时调度算法单纯追求实时性的抢占行为往往造成 处理器以及其它资源平均利用率的降低。因此对于一个基于某种调度算法进行调度的实 时系统来说，研究实时调度的抢占行为并通过某种优化策略来减少或控制其抢占开销具 有现实的应用价值。如何在保证系统任务实时性的同时，对实时调度的抢占开销进行优 化具有重要意义。 1 5 论文的结构安排 在保证硬实时任务可调度的情况下，如何对硬实时任务调度抢占开销进行优化是本 文的主要研究内容。 在第二章中主要介绍了实时系统的基本概念以及调度优化的基本模型，这部分是对 嵌入式实时系统最基本定时需求的抽象。在第二章周期性任务模型的基础上，第三章提 一3 东北大学硕士学位论文第一章绪论 出了硬实时调度抢占开销优化策略。针对固定优先级调度和动态优先级调度分别提出了 抢占行为的在线优化算法。第四章针对调度抢占行为开销优化策略在m a t l a b 下进行了 仿真实验。第五章对调度抢占开销优化的仿真实验数据进行了分析，并将实验数据与标 准的r m ，e d f 以及抢占阈值静态模型实验数据进行比较，分析优化策略的可行性。第六 章对全文进行了总结，并对未来的工作加以展望。 一4 一 东北大学硕士学位论文第二章实时系统参考模型 第二章实时系统参考模型 随着计算机技术的飞速发展与普及，实时系统已经成为人们生活和生产中的重要组 成部分。实时系统具有及时响应、高可靠性、专用性、人工干预少等特征，被广泛应用 于工业控制、信息通讯、网络传输、媒体处理、军事等领域。因此实时系统目前已受到 广泛的关注。实时系统的一个显著特点是试图同时实现计算在逻辑和时间上的正确性。 实时调度算法是保障实时系统两个必备特性时限性和高可靠性的重要手段之一。 当需要考虑在处理器和其它资源组成的嵌入式系统中如何调度一个实时应用以及 如何确定最后的系统是否满足所有的定时需求时，使用抽象的系统模型进行研究可以去 掉很多与调度无关的应用细节。本章所描述的实时系统参考模型是本文后续章节的研究 基础，原因在于该模型是对实时系统最基本的定时需求及其调度算法的抽象。 2 1 实时系统工作负荷的时间参数 在实时系统中，每个作业通常由其时间参数、功能参数、资源参数和互连参数来表 征。时间参数说明了作业的定时约束和行为。互连参数描述了作业如何依赖于其他作业 以及其他作业如何依赖于它。功能参数则说明了作业的内在属性。资源参数说明其资源 需求1 5 l 。 2 1 1 释放时间与时限 作业的释放时间( r e l e 弱et i m e ) 是一个时刻，在这一时刻上，作业能够执行。从释放 时间开始到此后的任一时间，只要作业的数据和控制依赖条件得到满足，它就可以被调 度和执行。 作业的时限( d e a d l i n e ) 是对作业完成的一个限制时刻，在此时刻之前完成它的执行。 响应时间( r c s p o 螨et i n l e ) 是从作业的释放时问到其完成时间的时间长度。 作业的相对时限( r c l a t i v ed e a d l i n e ) 就是作业的最大允许响应时间。本文中用协表示 任务f f 的相对时限，即在f 时间释放的“中的作业必须在f 之后的协个时间单元内完成。 作业的时限也称为绝对时限( a b s o l u t ed e a d l i n e ) ，它等于作业的释放时间加上其相对时限。 2 1 2 任务的执行时间 任务中作业的执行时间是在其所需要的资源都具备的情况下，独自完成执行所需要 的时间。因此，任务的执行时间主要取决于任务的复杂度和用于执行此任务的处理器速 度，同任务如何被调度并没有关系。 有很多原因会使任务中的作业完成执行所需要的实际时间发生变化。举例来说，计 一5 东北大学硕士学位论文第二章实时系统参考模型 算可能包括条件分支，不同的条件分支所需要的完成时间不同，计算作业执行时采用那 个分支取决于输入数据。如果支撑系统有性能增强特性，那么，即使没有条件分支，每 次执行时完成计算所花费的时间也会不同，在这种情况下只能通过分析和测量事先确定 完成每个任务所需要的最大和最小时间量，即确定任务f f 的执行时间在范围【，g d 之内，g 嘲和g 呶分别是“的最小执行时间和最大执行时间。不过，为了确定每个任务 中的作业是否都能按时完成，通常只要知道每个任务的最大执行时间就足够了。 2 2 任务模型 一般说来，根据实时系统中任务请求到达的情况不同，将实时系统中的任务分为周 期性的( p e r i o d i c ) 任务和非周期性的( a p e r i o d i c ) 任务两类。在通常情况下，这两类实时任 务可能会共同存在于同一个实时系统中【5 1 。其中，周期性任务是系统要处理的主要任务， 占用处理机的时间较多；而非周期性任务则是系统为了处理一些意外情况或紧急事件所 需要执行的任务，占用处理机时间较少而且数目也较少。实时系统的任务调度就是对这 两类任务的调度，使它们满足各自的任务时限，且任务调度处理过程一般是先调度周期 任务，在保证周期任务的时间约束条件的基础上，再考虑如何调度非周期任务。当整个 任务集通过调度执行都满足它们的任务时限时，则称此任务集是可调度的。 2 2 1 周期性任务模型 周期性任务模型是著名的确定性实时工作负荷模型。在周期性任务模型中，通过各 种扩展，可以精确表征很多强实时应用的特征，比如数字控制，实时监视、常量比特率 音频视频传输。基于该模型的很多经典调度算法具有很好的性能和容易理解的行为，而 且对于此模型，可以精确的表征实时系统。目前已有很多方法和工具来支持系统的设计、 分析与验证。 如果每个计算或者数据传输按照规则的或者近似规则的时间间隔，反复不断地执 行，以便为系统提供某个功能，就将它建模为周期性任务o 面0 dt 弱k ) 。每个周期性任务 是由一系列作业所组成。在一个周期性任务模型中称能够被系统调度和执行的工作单元 为作业a o b ) ；共同提供某种系统功能的一组相关作业为任务( t a s k ) ，这里用“表示，当有 必要引用任务“的单个作业时，就将它们称为，： ，1 ，五，2 等，这里五 代表任务“的第七个 作业。当希望讨论各个作业的属性，而且不考虑这些作业属于哪个任务时，称这些作业 为 ，以等。 每个任务“的第一个作业 l 的释放时间n ，l 称为f f 的相位，用，f 来表示，即厂f - r j ，1 。 说某些任务同相是指它们具有相同的相位，但是一般来说，不同的任务具有不同的相位， 如果任务模型中不含有厂，这一参数，则任务具有任意相位。 一6 一 东北大学硕士学位论文第二章实时系统参考模型 周期任务f f 的周期不是f f 中相连的作业的释放时间间隔之中的最小长度。其执行时 间g 是“中所有作业的最大执行时间。在所有情况下，系统中所有周期任务的周期和执 行时间都是已知的。 用日表示乃的最小公倍数，f = 1 ，2 ，行，即舴l c m ( 死，死，瓦) 。长度为 日的时间间隔称为周期任务的超周期。每个超周期中作业的最大个数为日z 。 称比率“产甜乃为任务“的利用率。l l f 等于周期为乃，执行时间为g 的完全周期性 任务保持处理器忙的时间比率。系统中所有任务的总利用率u 是其中各个任务的利用率 之和，即u - 争。 2 2 2 非周期和偶发任务 几乎所有的实时系统都要响应随时发生的外部事件。当这样的事件发生时，系统会 执行一组作业去进行响应外部事件。但有些作业的释放时间在触发之前是并不知道的。 称这些作业称为偶发作业( s p o r a d i cj o b ) 或者非周期作业( a p e r i o d i cj o b ) 。它们是在随机时 刻释放的。如果任务中的作业是弱时限或者没有时限，则称此任务为非周期任务。如果 一个任务包含的作业其释放时间是随机的但此作业又是硬时限约束的，则此任务为偶发 任务。 在周期性任务模型中，每个非周期或偶发任务分别是一个非周期性任务或偶发任务 作业流。在这样任务中相连作业之间的时间间隔可能会变化得很大也可能会很小，并在 不断变化。通常情况下，每个任务中的作业模仿的是系统为了响应同一类事件所做的工 作。特别要指出的是，每个非周期任务中的作业在某种程度上是类似的，比如它们都有 相同的统计行为和相同的定时需求。它们的到达时间间隔是同样的随机分布变量，都遵 从某个概率分布彳。同样地，每个非周期任务中作业的执行时间也是同样的随机分布 变量，它们遵从概率分布b 0 ) 而分布。这些假定意味着，系统及其环境的统计行为并不 随时间而改变，也就是说系统是稳定的。当时间间隔的长度与日相似，尤其是在周期性 任务的任一超周期内，且在超周期中没有添加或者删除周期任务时，系统是稳定的，这 种情况是正确的。 2 3 实时调度算法 通常在单处理器上调度周期性任务的优先级驱动算法可以分为两类：固定优先级调 度算法和动态优先级调度算法。两类调度算法在如何给作业分配优先级上是各不相同 的。 一7 一 东北大学硕士学位论文第二章实时系统参考模型 2 3 1 固定优先级调度算法 固定优先级调度算法为每个任务中的所有作业分配相同的优先级，也就是说每个周 期性任务的优先级相对于其它任务来说是固定不变的。具有代表性的经典固定优先级调 度算法有r m ( r a t em o n o t o n i c ) 和d m ( d e a d l i n em o n o t o n i c ) 算法。 2 3 1 1 速率单调( r a t e m o n o t o n i c ，r m ) 算法 1 9 7 3 年，u 和l a y l 锄d 在基于一系列假设的基础上提出了一种适用于可抢占的实时 周期性任务模型的固定优先级调度算法速率单调( r a t em 0 n o t o n i c ，简称r m ) 调度算 法，并对其可调度分析问题进行了研究1 1 1 ，1 2 1 。 r m 调度模型的基本假设如下： ( 1 ) 所有的任务请求都是周期性的，具有硬时限要求，即必须在截止期内完成； ( 2 ) 任务的时限要求仅限于任务必须在该任务的下一个请求发生之前完成； ( 3 ) 任务之间都是独立的，每个任务的请求不依赖于其他任务请求的开始或完成； ( 4 ) 每个任务的运行时间是不变的，这里任务的运行时间是指处理器在无中断情况 下用于处理该任务的时间； ( 5 ) 调度和任务切换的时间忽略不计； ( 6 ) 任务之间是可抢占的； ( 7 ) 所有任务的分配都在单处理器上进行。 r m 算法是一种常用的固定优先级算法。该算法基于任务周期分配任务优先级：周 期越短，优先级越高。任务的( 作业释放) 速率t e ) 与其周期成反比。因此速率越高，优 先级越高。u u 和l a y l 锄d 证明了r m 调度算法是最优的，即对于在任何其他固定优先 级算法下可调度的任务集合，在r m 调度算法下也是可调度的。r m 调度算法的最优性 保证了其能够广泛地应用于各种固定优先级调度的情况，这是r m 调度算法受到重视的 重要原因。 2 3 1 2 时限单调( d e a d i n e m o n o t o n i c ，d m ) 算法 时限单调算法【1 3 ，1 4 1 是另一种常用的固定优先级算法。该算法按照任务的相对时限来 分配优先级：相对时限越短，优先级越高。 如果每个任务的相对时限与它的周期成正比，那么r m 算法与d m 算法是一致的。 当相对时限是任意的时候，d m 算法表现较好。 2 3 2 动态优先级调度算法 和固定优先级调度算法不同，动态优先级算法为每个周期性任务的单个作业分配不 同的优先级。当作业释放并完成时，任务的优先级相对于其他任务的优先级要发生变化。 一8 一 东北大学硕士学位论文第二章实时系统参考模型 这也是称该类算法为“动态”的原因。最早时限优先( e a r l i s t d e a d l i n e f i r s t ，e d f ) 算法 和最小空闲时间优先( k a s t s l a c k 砸m e f i r s t ，l s d 算法是使用最为广泛的经典动态优先 级调度算法。 2 3 2 1 最早时限优先( e d f ) 调度算法 在系统调度的过程中按照作业的时限为它们分配优先级，作业的时限越早，优先级 就越高，基于这种优先级分配方案的优先级驱动调度算法称为最早时限优先 ( 】巳a r e s t d e a d l i n cf i r s t ，e d f ) 算法【1 5 1 们。在允许抢占并且作业不竞争资源的情况下，这 个算法在调度一个处理器上的可抢占作业时是最优的。 对于具有任意释放时间和时限的任务集f ，当作业j ；i 允许抢占，但作业并不竞争 资源时，当且仅当上，存在可行的调度时。e d f 算法才能够在单处理器上产生一个可行 的调度。如果系统满足条件：如果系统中具有独立的、可抢占的任务，并且每个任务的 相对时限都等于各自的周期。则该系统在单处理器上能够可行地调度当且仅当它的总利 用率小于或者等于1 。 2 3 2 2 最小空闲时间优先( l s n 调度算法 ? l s t 调度算法【5 】按作业的空闲时间来分配优先级：空闲时间越小，优先级越高。在 时刻f ，剩余执行时间( 作业剩余的执行时间部分) 为工，时限为d 的作业的空闲时间等于 小纵。每次在新作业释放时，调度程序检查所有就绪作业的空闲时间，并按照空闲时间 将新作业和现有作业重新排序。 2 4 抢占阈值模型 按照任务集中的作业在执行过程中是否可以被抢占，调度算法可以分为抢占式调度 算法和不可抢占式调度算法。在静态优先级的调度中，通常认为抢占式调度程序较非抢 占式调度程序能够提供更好的可调度性。但是，研究发现抢占式调度程序并没有取代非 抢占式调度程序而占领支配地位。也就是说，在非抢占式调度环境中可调度的一个任务 集并不意味着这个任务集在抢占式调度环境中也可调度，同样，在抢占式调度环境中可 调度的一个任务集并不意味着这个任务集在非抢占式调度环境中也可调度。 w 抽g 和s a k s 钮a 基于e x p r c s sb g i c 公司提出的抢占阈值概念1 1 7 1 ，提出了一个一般 化的静态优先级调度模型，它包含了抢占式和非抢占式调度机制。在这个模型中，每个 任务除了它的优先级外，还有具另外一个属性- 抢占阈值。即内核中存在一个整数用 来表示当前抢占优先级的水平( 这个整数的值可能高于当前执行任务的优先级) 。抢占阈 值可以阻止其它任务抢占当前正在执行的任务，除非任务的优先级高于当前的抢占阈 值。 实际上，抢占阈值导致了一个双优先级的系统，其中每个任务具有一个普通的优先 一9 一 东北大学硕士学位论文第二章 实时系统参考模型 级用于抢占其它任务，一个抢占阈值作为任务执行期间( 或者一个任务完成要作出调度 决策时) 的有效优先级。抢占阈值可以通过在任务开始执行时将普通优先级改成抢占阈 值，在执行结束再恢复成原来的值的方式模拟。对于重复到达的任务，如周期性任务， 每个实例都必须进行上述过程。 因此，不难看出抢占式和非抢占式调度都是抢占阈值调度的特例。每个任务的抢占 阈值与它的优先级相等，就是抢占式调度。如果每个任务的抢占阈值等于系统中任务的 最高优先级，那么这个调度就是非抢占式调度。所以，抢占阈值调度具有抢占式和非抢 占式两种调度的优点，从而可以使得一个在抢占式或者非抢占式调度中不可调度的任务 集变得可以调度。 w 抽g 和s a l 【s 锄a 针对抢占阈值分配这个问题提出了用于最坏情况响应时间分析的 任务模型和运行机制模型并给出了问题的形式化描述，概要地介绍了问题的解决方法。 2 4 1i 临界时亥0 ( c r i t i c a li n s t a n t ) 任务“的临界时刻( c r i t i c a li n s t 锄t ) 是： ( 1 ) 如果“的每个作业的响应时间都等于或小于“的相对时限觑，那么在该临界时 刻释放的“中所有作业的最大的响应时间。 。 ( 2 ) 如果“中有些作业的响应时间超过“的相对时限d f ，那么在该临界时刻释放的 作业的响应时间大于d f 。 2 4 2i 级忙周期( 1 e v e l i b u s yp e r i o d ) l c h o c z k y 提出了i 级忙周期的概念( 1 e v e l i b u s yp 面o d ) ，用于支持任意最终截至期的 静态优先级调度算法，在分配优先级后分析任务集合的可调度性。 一个i 级忙周期是一个时间间隔【a ，b 】，在这一间隔里，执行了具有优先级i 或者更 高优先级的任务实例，但在时间间隔【a e ，a 】或者【b ，b + e 】内，没有优先级为i 或者更高 优先级的任务实例被处理。其中e 是大于o 的极小值。需要注意的是，在一个i 级忙周 期内，没有优先级低于i 的任务实例能够执行。在时刻b 所有优先级高于或者等于i 的 任务实例必须结束执行。而且，在时刻b 不应该有优先级高于或者等于i 的任务实例就 绪。对于从第一个临界时刻开始的i 级忙周期【0 ，b 】必须满足两个条件： ( 1 ) 在【0 ，b 】内，不能有低于i 优先级的任务执行； ( 2 ) 在时刻b 所有优先级等于和高于i 优先级的任务必须结束执行。 2 4 3 任务模型 w 抽g 和s a l 【s e n a 所考虑的任务集包含以个独立的周期性任务或突发任务，即f j ，”， “。每个任务“用一个三元组 表示，其中g 是任务“的计算时间，正是任务n 一】0 一 东北大学硕士学位论文第二章实时系统参考模型 的周期( 或者最小到达间隔) ，皿是任务