（计算机应用技术专业论文）可重构系统中实时任务调度算法研究.pdf

f 1 h 产 r e s e a r c ho nr e a l t i m et a s ks c h e d u l i n g a l g o r i t h mo fr e c o n 行g u r a b l es y s t e m c a n d i d a t e ：y i nj i n y o n g s u p e r v i s o r ： a c a d e m i cd e g r e ea p p l i e df o r ： s p e c i a l i t y ： d a t eo fs u b m i s s i o n ： d a t eo f0 r a le x a m i n a t i o n ： u n i v e r s i t y ： p r o f g ug u o c h a n g d o c t o ro f e n g i n e e r i n g c o m p u t e ra p p l i e dt e c h n o l o g y a p r i l ，2 0 1 0 j u n e ，2 0 1 0 h a r b i ne n g i n e e r i n gu n i v e r s i t y 。 e 气 哈尔滨工程大学 学位论文原创性声明 本人郑：藿声明：本论文的所有工作，是在导师的指导下， 由作者本人独立完成的。有关观点、方法、数据和文献的引用 己在文中指出，并与参考文献相对应。除文中已注明引用的内 容外，本论文不包含任何其他个人或集体已经公开发表的作品 成果。对本文的研究做出重要贡献的个人和集体，均已在文中 以明确方式标明。本人完全意识到本声明的法律结果由本人承 担。 作者( 签字) ：孱业寥 日期：勘6 年6 月h - - m 哈尔滨工程大学 学位论文授权使用声明 本人完全了解学校保护知识产权的有关规定，即研究生在校 攻读学位期问论文j l j 作的知识产权属于哈尔滨工程大学。哈尔滨 工程大学有权保留并向困家有关部i 、j 或机构送交论文的复印件。 本人允许哈尔滨 ：程大学将论文的部分或全部内容编入有关数据 库进行检索，町采用影印、缩印或扫描等复制i = - 段保存和汇编本 学位论文，可以公布论文的全部内容。同时本人保证毕业后结合 学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈 尔滨工程人学。，涉密学位论文待解密后适用本声明。 本论文啦授予学位后即可口在授予学位12 个月后 口 解密后) 由哈尔滨工程大学送交有关部门进行保存、汇编等。 作者( 签字) ：声船鸢 导愀签痞乏回 日期：删6 年6 月陟日洲6 年6 月p 日 0 f 谚季、 ， 气 ， ， ，- 可弧构系统巾变时任务凋度算法研究 摘要 可重构计算兼有软件的灵活性和硬件的高效性，在嵌入式系统、高性能 计算和实时系统等领域有广阔的应用自订景，已成为计算机领域中的一个研究 热点。典型的可重构系统由一个( 或多个) 处理器和一片( 或多片) f p g a 组成， 为发挥可重构计算的灵活性和高性能，一个实时任务可把计算密集部分划分 成硬件任务( 逻辑电路) 在f p g a 上加速执行，而其余部分以软件任务( 指令集) 方式在处理器上执行。这样在可重构系统上执行的实时任务就包括仅在处理 器上执行独立软件任务、优先约束软件任务和在处理器f p g a 上执行的软 硬件混合任务，本文针对这3 类实时任务的调度问题进行了深入研究，主要 研究内容如下： 1 在实时系统中，周期任务和非周期任务并存，而现有的独立周期非周 期混合实时任务调度算法是针对单处理器系统提出的，适用范围窄，故此提 出了适用于多处理器系统的独立周期非周期混合实时任务调度算法。该算法 在d s 服务器 ：调度非周期仟务，混合调度d s 服务器和周期任务，能够满足 所有周期仟务和系统接收的非周期f t 务的截止期限。 2 在多处理器系统中，有些实时任务包含多个具有优先约束火系的子任 务，而现有的优先约束实时任务调度算法多为静态调度算法，计算复杂度高 且不能调度1 e 刷期任务，故此提出了优先约束周期- - 1 1 ：周期混合实时任务的动 态调度算法。该算法在系统运行前判定周期任务的可调度性，降低了系统的 在线调度：销，在多个d s 服务器上调度随机到达的非周期任务。 3 在可晕构系统中，有些实时任务不仅包含在处理器上执行的软件予任 务，还包含在f p g a 上执行的硬件子任务，而现有的实时调度算法只能调度 软件任务或硬件任务，故此提出了软硬件混合实时任务调度算法。该算法把 每个实时任务的硬件子任务分成若干组，每组子任务配置到同一个窄闲槽内， 提高了可重构资源利用率j 该算法分析了实时任务的可调度性，能够保证所 有实时任务满足截止期限。 4 在可重构系统中，硬件电路的配置信息存储在静态r a m 中，容易受 哈尔滨i ：程人学博十学位论文 n ) z j 【i | i l - q ：境的l 二扰，使硬件l u 路出现故障，故此提出了种实时任务容错凋 度算法，以提高系统的可靠性。该算法把每个软件子任务调度到两个处理器 上同时执行，如果处理器出现故障则回卷到上一个检测点处执行，保证了软 件子任务的萨确性；把每个硬件子任务划分到3 个组中，调度到3 个空闲槽 内执行，屏蔽了错误结果。在硬件资源丌销不大的情况下，该算法能够容忍 多个硬件故障，保证实时任务的截止期限。 关键词：实时调度算法：多处理器；可重构系统；d s 服务器；优先约束任 务；软硬件混合任务 ， r 1 b e c a u s ep e r i o d i ca n da p e r i o d i ct a s k sc o - e x i s ti nr e a l - t i m es y s t e ma n dt h e p r o p o s e dr e a l t i m es c h e d u l i n ga l g o r i t h m sf o rp e r i o d i c a p e r i o d i ch y b r i dt a s k so n l y a p p l i e dt ou n i p r o c e s s o rs y s t e m ，ah y b r i dr e a l t i m es c h e d u l i n ga l g o r i t h mi s p r o p o s e dt oa p p l yt om u l t i p r o c e s s o rs y s t e m t h ea l g o r i t h ms c h e d u l e sa p e r i o d i c t a s k so nd ss e r v e r sa n ds c h e d u l e sd ss e r v e r sa n dp e r i o d i ct a s k sj o i n t l y t h e a l g o r i t h mc a l lm e e ta l lp e r i o d i ct a s k s d e a d l i n e sa n dt h ea c c e p t e da p e r i o d i ct a s k s d e a d l i n e s 2 i nm u l t i p r o c e s s o rs y s t e m ，s o m er e a l t i m et a s k sa r ec o m p o s e do fs e v e r a l s u b t a s k su n d e rp r e c e d e n c ec o n s t r a i n t s t h ep r o p o s e da l g o r i t h m sf o rt a s k su n d e r p r e c e n d e n c e c o n s t r a n t sa r e m o s t l y s t a t i c s c h e d u l i n ga l g o r i t h m sa n d t h e i r c o m p u t i n gc o m p l e x i t i e sa r eh i g ha n dc a n ts c h e d u l ea p e r i o d i ct a s k s ，s oad y n a m i c s c h e d u l a b i l i t yb e f o r es y s t e ms t a r t i n g ，i t so n l i n es c h e d u l i n go v e r h e a dd e c r e a s e d g r e a t l y t h ea l g o r i t h ma l s oc a l ls c h e d u l ea p e r i o d i ct a s k so nd ss e r v e r s 3 i nr e c o n f i g u r a b l es y s t e m ，s o m er e a l - t i m et a s k sn o to n l yh a v es o f t w a r e s u b t a s k se x e c u t i n go np r o c e s s o rb u ta l s oh a v eh a r d w a r es u b t a s k se x e c u t i n go n f p g ad i r e c t l y t h ep r o p o s e da l g o r i t h m sc a no n l ys c h e d u l es o f t w a r er e a l t i m e t a s k so rh a r d w a r er e a l t i m et a s k s ，s oas c h e d u l i n g a l g o r i t h mi sp r o p o s e df o r s o f t w a r e h a r d w a r eh y b r i dr e a l t i m et a s k s t h ea l g o r i t h mp a r t i t i o n se a c hr e a l t i m e t a s k sh a r d w a r es u b t a s k si n t os e v e r a lg r o u p sa n dc o n f i g u r e ss u b t a s k si nt h es a m e g r o u pi n t oo n es l o t ，t h e r e f o r et h er e c o n f i g u r a b l er e s o u r c eu t i l i z a t i o n i n c r e a s e s t h ea l g o r i t h mh a sa n a l y z e dr e a l - t i m et a s k s s c h e d u l a b i l i t ya n dc a nm e e ta l lt a s k s d e a d l i n e s 4 i nr e c o n f i g u r a b l es y s t e m ，c i r c u i tc o n f i g u r ei n f o r m a t i o ni ss t o r e di ns t a t i c r a ma n di ss u s c e p t i b l et oe l e c t r o m a g n e t i ci n t e r f e r e n c ew h i c hc a nc a u s ec i r c u i t f a u l t s oaf a u l t t o l e r a n ts c h e d u l i n ga l g o r i t h mi sp r o p o s e dt oi m p r o v es y s t e m r e l i a b i l i t y t h ea l g o r i t h ms c h e d u l e se a c h s o f t w a r es u b t a s kt o e x e c u t eo nt w o p r o c e s s o r sa t t h es a m et i m e ，a n di faf a u l to c c u r s ，t h es o f t w a r es u b t a s k sw i l l r o l l b a c kt ot h el a s tc h e c k p o i n tw h i c hg u a r a n t e e ss o f t w a r es u b t a s k s ? c o r r e c t n e s s e a c hh a r d w a r es u b t a s ki si n c l u d e di nt h r e eg r o u p sa n de x e c u t e si nt h r e es l o t s s i m u l t a n e o u s l ya n dt h ee r r o rr e s u l t i sm a s k e do f f t h ea l g o r i t h mc a nt o l e r a t e s e v e r a lf a u l t sa n dg u a r a n t e ea l lt a s k s d e a d l i n ew i t hl i t t l eh a r d w a r eo v e r h e a d k e y w o r d s ：r e a l t i m es c h e d u l i n ga l g o r i t h m ；m u l t i p r o c e s s o r ；r e c o n f i g u r a b l e s y s t e m ；d ss e r v e r ；t a s ku n d e rp r e c e d e n c ec o n s t r a i n t s ；s hh y b r i dt a s k r ，t 可呕构系统巾实时仟务凋腹茆法研究 目录 第l 章绪论1 1 1 课题研究背景一1 1 2 可重构计算概述一2 1 2 1f p g a 可重构模式2 1 2 2 可重构系统结构3 1 3 实时系统概述一4 1 3 1 实时任务属性及分类4 1 3 2 实时系统特点6 1 4 实时调度技术的研究现状7 1 4 1 软件任务调度9 1 4 2 硬件任务调度j 1 4 1 5 论文研究内容l5 1 6 论文组织结构1 7 第2 章独立软件实时任务调度2 0 2 1 引言一2 0 2 2 任务模型2 1 2 3 非周期任务调度2 l 2 3 1d s 算法2 1 2 3 2r b 算法2 3 2 3 3s u 算法2 4 2 3 4d s e d f 算法2 4 2 4 混合任务调度2 8 2 4 1g s h t 调度算法2 8 2 4 2p s h t 调度算法3 7 2 5 实验结果及分析3 9 3 5g s h t p c 调度算法5 4 3 5 1 混合可调度性分析5 4 3 5 2 算法描述5 5 3 6 实验结果及分析5 7 3 6 1 相关算法比较5 7 3 6 2 周期任务调度结果：5 9 3 6 3 非周期任务和混合任务调度结果6 2 3 7 本章小结6 3 第4 章软硬件混合实时任务调度6 5 4 1 引言6 5 4 2 任务和资源模型6 5 4 2 1 任务模型6 5 4 2 2 可重构资源模型6 7 4 3 硬件子任务分组6 8 4 3 1 分组算法描述6 8 4 3 2 分组算法实验结果7 1 4 4s s h t n b 调度算法7 2 4 4 1 可调度性分析7 2 4 4 2 算法描述7 3 4 4 3 实验结果与分析7 5 j 可m 构系统中实h 寸任务凋度锋法研究 4 5s s h t w b 渊度算法7 8 4 5 1 可调度性分析一7 8 4 5 2 算法描述81 4 5 3 实验结果与分析8 3 4 6 相关算法比较8 7 4 7 本章小结8 7 第5 章软硬件混合实时任务容错调度8 9 5 1 引言一8 9 5 2 容错技术9 0 5 。2 1 硬件冗余容错9 0 5 2 2 软件冗余容错9l 5 2 3 时间冗余容错9 2 5 3f t - s s h t n b 调度算法9 3 5 3 1 处理器和软件子任务故障检测9 4 5 3 2 硬件子任务容错9 8 5 3 3 实时任务容错可凋度性判定9 9 5 3 4 算法描述l0 0 5 4 实时性分析1 0 l 5 5 实验结果j 分析1 0 2 5 6 本章小结1 0 4 结论1 0 5 参考文献10 7 攻读博士学位期间发表的论文1 l8 致谢11 9 第1 章绪论 第1 章绪论 ， 1 1 课题研究背景 f 当我们实现一个应用时，软件设计者会使用某种编程语言设计一个应用 程序，然后在处理器上执行它，而硬件设计者则会利用原理图或者硬件描述 语言进行设计，然后以a s i c ( a p p l i c a t i o ns p e c i f i ci n t e g r a t e dc i r c u i t ) 的方式实 现，处理器和a s i c 已经成为传统的两大主流计算模式。a s i c 实现快速、高 效，但硬件设计完成后便难以修改；软件实现灵活，却牺牲了性能。 可重构计算( r e c o n f i g u r a b l ec o m p u t i n g ) ，有些文献把它称之为自适应计 算( a d a p t i v ec o m p u t i n g ) ，也有的文献把它称之为f p g a 计算的本质足利用 f p g a 可多次重新配置逻辑单元的功能和互连的特性，使系统兼具灵活性、 高性能、高叮谨、低能耗、低成本、易于升级等多种优良特性。可重构计算 填补了软、硬件之间的鸿沟，它不仅保持了硬件的高性能，同时还具有接近 于软件的灵活性。 由于以上优点，可蓬构计算已成为当自，j - 研究的热点，并应用到航空航天， 高性能计算等领域1 2 l 。空| 日j 太阳望远镜( s p a c es o l a rt e l e s c o p e ，s s t ) 是一个太 刚观测科学卫星，其主要作用是在外层空i 、日j 直接采集数据并传回地球进行分 和处理。s s t 上带有多个观测装置，以便从不同角度司时对太阳进行观测， 每天产生大量数掘，由于s s t 和地球之l 日j 有效通信时问短、传输速率低，因 此在卫星上使用f p g a 芯片进行高速数据预处理和压缩，再传回地球。当 f f p g a 内部电路出现故障时，对故障电路在预留资源t 进行重构，提高了系 统的叮靠性。美幽s t a r b r i d g e 公司的设计h c 3 6 和h c 6 2 高性能计算机完全 使用f p g a 芯片作为计算器件，把处理器系统嵌入到f p g a 中，实现了混合 计算。并通过v i v a 软件将应用程序划分成由处理器执行的软件和由f p g a 直 接执行的逻辑电路两部分，根据需要动态重构硬件电路，降低了功耗，提高 哈尔滨l ：稗人! 学博十学何论文 了计算性能。 1 2 可重构计算概述 可重构概念最早由美国加利福尼亚大学的g e r a i de s t r i n 在2 0 世纪6 0 年 代术提出。由于当时实现技术尚不完善，e s t r i n 研制的可重构系统只是理论 设计的粗略近似。直到1 9 8 6 年x i l i n x 公司第一款基于s r a m 的f p g a 的 问世，才标志着现代可重构计算的丌始。f p g a 技术的发展，推动了可重构 技术的发展，而可重构技术的进展和需求，也促进了f p g a 技术的进步。 1 2 1f p g a 可重构模式 嗣 配矗义f ，i 二= j 配置史f ，f 嗣 配山义 圃固1 、鸯磐 配五 i i f 虬n j b 多上卜文 削“h 眦r l j u c 部分可重构 图1 1f p g a 的3 种可重构模式 f i g 1 it h e r er e c o n f i g u r a b l em o d e l sf o rf p g a 1 单上下文：单上下文f p g a 使用配置比特流顺序的进行编程，如图 1 1 ( a ) 所示。因为这种类型的f p g a 只支持顺序访问，所以任何一处配置的改 变都需要重新对整片f p g a 重构。为了在单上下文f p g a 上实现动态可重构， 需要将各个配置分组到各个上下文中去。 2 多上下文：多上下文f p g a 为每个可编程位准备了多个存储位置，如 图1 1 ( b ) 所示。其中某个平台的配置信息可在给定的时刻变为激活状态，器 件能在很短的时间内进行平台问切换。实际上，多上下文f p g a 可视为多个 2 玉 零为易漱雷 r 产 ，l 笫1 事绪论 单上f 文器件的集合，时j ：每个配置位的修改样需要埘整片f p g a 进 j ：重 构，它允许在一个上下文处于激活状念时，装载另一个上下文将要用到的配 置信息。 3 部分可重构：在很多情况下，配置信息并不足以占掘整个可重构硬件， 或者重构时只需对部分配置进行修改。这时采用单、多上下文的器件就显 得效率很低，因此有学者提出了部分可重构技术。在部分可重构f p g a 中， 底层的编程位类似于r a m ，它用地址表示配置数据的目标位置，允许有选择 的对特定位置重构，如图1 1 ( c ) 所示。部分可重构的f p g a 允许计算与重构 同时进行，即f p g a 芯片可在运行时动态改变某一部分的配置，又允许其未 更改部分仍按原有方式正常工作。 1 2 2 可重构系统结构 c 协处理器 l 删 i 傩 c 洲扩 - - ri吖，： 图1 25 类可重构系统 f i g 1 - 2f i v ec l a s s e so fr e c o n 行g u r a b i es y s t e m s 根据f p g a 与c p u 的耦合的方式，可重构系统通常可分为以下5 种类型 i t 】，如图1 2 所示。 第1 类系统是最松散的耦合方式( 图卜2 a ) ，f p g a 作为外部独立的处理单 r；：”，i元1。，“一，单一，；巍 ，止 辎。，l 批 毕搿 一 a u 哈尔滨i ：样人学博十学位论文 元，处理器和f p g a 通过i o 接u 进行通信，凶此这类系统适合于f p g a 与 处理器通信不频繁的应用。 第2 类和第3 类是两种折中方烈1 2 。1 ( 图1 2 b 和图1 2 c ) 。在第2 类系统 中，f p g a 作为处理器的附加处理单元【1 6 17 1 ，它的功能类似于多处理器系统 中的一个处理器。因为处理器的数掘缓存对f p g a 是不可见的，所以处理器 和f p g a 的通信延时较大；在第3 类系统，f p g a 是处理器的协处理器。这 两类系统的通信代价小于第l 类系统。 如图1 2 d 所示，第4 类系统是处理器和可重构组织最紧密的耦合方式， 处理器内部包含一个可重构功能单元( f u ) ，文献【1 8 2 1 】对此类结构均有介绍。 图1 2 e 所示的是第5 类系统，在这种系统中，处理器嵌入到f p g a 内部， 处理器既可以是硬核，也可以是软核f 2 2 之训。 1 3 实时系统概述 性： 实时系统一直没有一个标准的定义，比较来说，以下两种描述较有代表 在实时系统中，计算任务的正确性不仅仅依赖于计算结果逻辑上的i f 确性，而且还依赖于计算结果产生的时问。如果系统的时| h j 约束没有 被满足，将会产生系统故障。因此，保证系统的时| 【i j 约束被满足是对 一个实时系统最基本的要求，这就需要系统具有可预测性。在时间约 束被保证的基础上，取得较高的系统利用率也是对系统的一个要求。 p o s i x 标准1 0 0 3 1 把操作系统的“实时”定义为：操作系统在有限 反应时间内提供所要求的服务水平的能力。 1 3 1 实时任务属性及分类 定义1 1 任务( t a s k ) ：任务是指完成某一特定功能的程序，包括一个或 多个子任务( s u b t a s k ) ，子任务是实时调度中的一个基本单位。任务在其生命 4 一 | i 第1 覃绪论 期中的某一次执行称为该任务的一个作业( j o b ) ；具有时限约束的任务称为实 时任务( r e a l t i m et a s k ) ，反之则称为非实时任务( n o n r e a l t i n et a s k ) t 1 1 6 1 i 。 一个实时任务的属性，通常用以下参数来捕述： 定义1 2 到达时问( a r r i v et i m e ) ：任务被激活的时问称为到达时间。任 务到达以后才可分配它所需要的所有资源。 定义1 3 释放时间( r e l e a s et i m e ) ：当任务分配到除处理器以外的所有必 要资源的时候，它能够被系统调度执行，此时的状态称为就绪念。一个作业 由其他状态转变为就绪态的那个时刻称为它的释放时间。 定义1 4 响应时间( r e s p o n s et i m e ) ：作业从它的到达时间起，到它被完 成时刻止的时间段长度称为它的响应时间。若作业的响应时间有一个最大值 限制，那么这个最大值被称为它的相对截止期i 艰：( r e l a t i v ed e a d l i n eo 若一个 作业被要求在某个时刻之前完成，那么那个时刻称为它的绝对截止期限 f a b s o l u t ed e a d l i n e ) ! 1 1 7 _ 1 1 8 】。 对于实时任务，一个常见的实时性能需求是：它的所有作业都被要求在 各自的绝对戗止期限之前完成。为叙述方便，本文以卜用术语“截止期限” 表示绝埘截止期限。 定义1 5 最坏执行时i 日j ( w o r s t c a s ee x e c u t i o nt i m e ，w c e t ) ：任务在其生 命期巾的每个作业的执行时| 1 i j 的最大可能值引。 以下任务的执行时m 指的是最坏执i j ：时l 日j 。 定义1 6 周期( p e r i o d ) ：任务被周期性地执行的f j 仃后两个作、i 匕之间的时| 日j 问隔。 根据不同的分类标准，任务可以有多种分类方法。 1 按照任务包含的子任务个数可分为2 种类型： 独立任务( i n d e p e n d e n tt a s k ) ：任务只包含一个子任务。 优先约束任务( t a s kw i t hp r e c e d e n c e ) ：任务包含多个子任务，子任务问存 在某种偏序或者控制依赖关系，必须按照某种次序执行。 2 按照任务的执行方式可分为3 种类型： 软件任务( s o f t w a r et a s k ) ：软件任务是一种传统的任务类型，在处理器上 哈尔滨i ：程人学博十学侮论文 执行。 硬件任务( h a r d w a r et a s k ) ：硬件任务是指在f p g a 上执行的逻辑电路， 由于硬件任务之间通信的复杂性，硬件任务一般只有一个节点，通过软件任 务与其他硬件任务通信。 软硬件混合任务( s o f t w a r e h a r d w a r eh y b r i dt a s k ) ：这是可重构系统中特 有的任务类型，任务包含软件任务和硬件任务两部分并有一定的约束关系。 3 按照任务到达时间的规律性可分为3 种类型： 周期任务( p e r i o d i ct a s k ) ：周期任务是指按照一定频率到达的任务，任务 的剧期即为到达频率的倒数。 偶发任务( s p o r a d i ct a s k ) ：在偶发任务中，虽然其作业的到达时刻不是严 格周期的，但相邻作业到达时刻的时间间隔有个最小值。在实际应用中， 如果把相邻作业最小的时间问隔看作任务的周期，那么偶发任务也可作为周 期任务处理。 非周期任务( a p e r i o d i ct a s k ) ：非周期任务是指随机到达系统的任务。 4 按照任务是否具有截止期限以及错失截止期限对系统产生的影n 向可分为3 种类型： 硬实时任务( h a r dr e a l t i m et a s k ) ：硬实时任务必须在规定的时问内完成， 不允y ：错失截止期限。如果有硬实时任务错失截止期限，则会对系统造成f i 可估显的损失。 软实时任务( s o f tr e a l t i m et a s k ) ：通常允许软实时任务错失截止期限， 错失截止期限后的计算结果仍然有一定的意义，但其意义随着超时时间的增 加而下降。 非实时任务( n o n r e a l t i m et a s k ) ：非实时任务没有截止期限，但其响应时 间越短越好。 1 3 2 实时系统特点 和一般的计算机系统相比，实时系统具有如下的特点： 6 气 筇1 审绪论 1 时i 、日j 约束性 时l 、日j 约束性指各任务不仅要满足相互之f h j 的时序约束，还要遵从各自的 绝对时间约束和相对时间约束。任务具有时问约束是实时系统最重要的特征。 在实时计算中，时间是最为重要的因素，也是实时系统需要管理和控制的首 要资源。实时计算要求在有限的时间内完成任务的分配、调度和执行。逻辑 正确性和时序j 下确性对实时计算的j f 确性同样重要。 2 可预测性 可预测性是指系统能对实时任务的执行时m 进行判断和分析，确定能否 及如何满足任务的时限要求。由于实时系统对时间约束要求的严格性，使得 可预测性成为实时系统的一项荤要性能需求。除了要求硬件延迟的可预测性 外，还要求软件系统的可预测性，包括应用程序的响应时f h j 是可预测的，即 在有限的时问内完成必须的工作，以及操作系统的可预测性，即调度函数、 通信原语、中断处理等运行丌销应是有界的，以保证应用程序执行时间的有 界性。 3 可靠性 可靠性对大多数实时系统足至关晕要的。在一些重要的实时应用中，任 何不可靠凶素和系统的一个微小故障，或某些特定硬实时任务超过时限，都 可能引起经济或人身安全的灾难。陀的后果。为此，一些系统需要采用静态分 析和保帮资源的方法以及冗余配置，使得系统在最坏情况下都能i e 常工作或 避免损失。可靠性己成为衡量实时系统性能的小可或缺的重要指标。 1 4 实时调度技术的研究现状 实时调度一直都是实时系统研究中的热点问题，而实时调度的核心是实 时任务可调度性判定问题。因为实时任务具有时限要求，需要保证每个硬实 时任务都能够在其截止期限内完成。 定义1 7 可行调度( f e a s i b l es c h e d u l a b i l i t y ) ：如果每个实时任务在某种调 度方式下都能满足截止期限，则称该调度时可行调度。 定义1 - 8 可调度性判定( s c h e d u l a b i l i t yt e s t ) ：判定给定的胛个实时任务 哈尔滨l ：程人学博十学位论文 在渊度算法a 调度下能台，_ 生一个可j j ：的渊度。如果，? 个实时任务在在调度 算法a 调度下能产生一个可行的调度，则称这刀个实时任务可被算法a 调度。 表l - 1 实时任务调度分类 t a b 1 1c a t e g o r i e so fr e a l t i m et a s k ss c h e d u l i n g 分类依据分类 根据任务执行序列生成的时问静态凋皮干动态调度 根据实时任务是否可被抢- 叶抢。o i 式凋度和一作抢l l i 式凋度 根据系统中处理器的数量单处理机调度和多处理机调度 根据任务类刑软什任务调度和硬什任务调度 软件任务调度算法的分类可有多种方法。常用分类方法如表1 1 所示。 1 静态调度和动态调度7 1 静念调度是在任务集执行之前就产生一个静念的调度表，在运行时总是 按照调度表决定从就绪任务队列中选择哪个任务来执行。这类调度算法假设 系统中实时任务的特性( 执行时间，截止期限，执行次序等) 是全部已知的， 适合于问题需求确定，并且运行中不会有较大变化的情况，如简单的工业过 程控制。静态凋度算法的优点是运行丌销小，可预测性强。但是它的灵活性 较差，不适合动态变化的，或不可预测环境下的调度。 动态调度算法是在运行期问才决定选择哪个就绪任务来运行。它所根据 的是目 j ，j 就绪任务的相关属性，以此来决定当自仃的调度序列。这类算法能够 对变化的环境做出反应，因此，这类调度算法比较灵活，适合于任务不断生 成，并且在任务生成之前，其特性并不清楚的动态实时系统，如自行机器人 控制系统。但是，动念调度算法的运行丌销一般较日订者大【7 1 2 0 1 。 2 抢占式调度和非抢占式调度1 1 1 6 1 在抢占式调度中，目前f 在运行的任务可以被别的更紧迫和更重要的任 务中断。同时，被抢占的任务在未来可以恢复运行，且不会影响到任务的整 体时限约束。这种抢占式的调度常见于工业制造中。它的优点是比较灵活， 对资源的利用率高；但由于经常出现的上下文切换使得其丌销较大【l2 1 j 。 如果在调度中不允许正在运行的任务被别的任务中断，任务一旦占有了 处理器便会一直运行直至完成，这样的调度则是非抢占式的，它比较适合于 入 第1 苹绪论 任务运行时l 日j 都比较短的系统。其优点是省去了进行上卜义切换的，l ：销，同 时，具有更好的可预测性，更易于测试，在保证对共享资源的一匾斥访问上也 有较强的继承能力。非抢占式调度没有抢占式调度那样灵活，对资源的利用 率也相对较低。 3 单处理器调度和多处理器调度【陇1 如果实时系统运行在一个单独的处理器上，则为实时单处理器系统。在 这种系统中对实时任务进行调度时，仅需要考虑任务在这个处理器上的运行 情况。如果实时系统运行在一个多处理器的环境下，则为实时多处理器系统， 此时在进行实时调度时，不仅要考虑任务在单个处理器上的运行情况，还要 考虑任务被分配到哪一个处理器上运行，即任务分配问题。 4 软件任务调度和硬件任务调度 实时任务分为软件任务和硬件任务，软件任务是指令集，在处理器上执 行而硬件任务是逻辑电路，直接在f p g a 上执行。如果一个调度算法仅能调 度软件任务或硬件任务，则称该算法为软件任务调度算法或硬件任务调度算 法。 可重构系统中包括在处理器上执行的软件任务和在f p g a 上直接执行的 硬件任务，本节从软件任务和硬件任务两个方面阐述了实时调度技术的研究 进展。 1 4 1 软件任务调度 1 4 1 1 单处理器调度 首先介绍了周期任务调度，接下末介绍了在保证周期任务可调度的情况 下非周期任务的调度。 1 9 7 3 年，l i u 和l a y l a n d 提出了一种适用于可抢占的硬实时周期性任务 调度的静态优先级调度算法r m ( r a t em o n o t o n i c ) 调度算法1 2 5 j ，r m 算法 赋予周期最短的任务以最高优先级，高优先级任务可抢占低优先级任务执行。 l i u 和l a y l a n d 从处理器利用率角度给出了周期任务集可调度的充分条件，并 9 哈尔滨i ：科人学博十学位论文 证明r m 算法足最优的，【! j 对j ：在任t , qc 他静态优先级算法卜u j 调度的任务 集合，在r m 算法下也是可调度的。d m ( d e a d l i n em o n o t o n i c ) i g 度算法1 2 6 j 是 r m 算法的一个变种，任务的截止期限越小，其优先级越高，当相对截止期 限等于任务周期时，r m 算法与d m 算法是等价的。b u r c h a r d 等人给出了更 高的周期任务集可调度性判定的处理器利用率最小上界1 3 引，l e h o c z k y 等人对 固定优先级算法的特征进行了更为精确的研究，在文献【3 3 】中给出了r m 算 法可调度性判定的充要条件。 在实时系统中不仅存在周期任务，还存在随机到达的非周期任务。处理 软实时非周期任务的最简单方法是后台处t 里( b a c k g r o u n dp r o c e s s i n g ) 算法1 3 4 j 。 后台处理算法是在处理器空闲时以先来先服务( f i r s tc o m ef i r s ts e r v e d ， f c f s ) 次序执行这些任务。如果周期任务的负载很高，则用于处理非周期任 务的时间就相当少，因此非周期任务的响应时间是不可预测的。 为了提高非周期任务的调度性能，人们提出了许多非周期任务调度算法， 这些算法可以分为两类：基于服务器( s e r v e rb a s e d ) 的算法与基于空闲时间 ( s l a c kb a s e d ) 的算法【”j 。基于服务器的算法，又称为带宽预留( b a n dw i d t h p r e s e r v i n g ) 算法，其主要思想是，在保证满足周期任务截止期的前提下，引 入一个或者几个额外的周期任务使用指定的处理器带宽作为服务器来处理非 周期任务。基于空闲时间的算法主要包括空闲时间偷取算法( s l a c ks t e a l i n g a l g o r i t h m ) 、时j 日j 片移位算法( s l o ts h i f t i n ga l g o r i t h m ) 与双重优先级算法 ( d u a lp r i o r i t ya l g o r i t h m ) ，这些算法都是通过离线或在线分析从周期任务调度 的空隙获得尽可能多的处理时间来处理非周期任务。 l e h o c z k y 掣3 4 j 提出了d s ( d e f e r r a b l es e r v e r ) 与p e ( p r i o r i t ye x c h a n g e ) 方 法，p e 与d s 算法的区别在于保持这些分配的高优先级执行时问的方式。 之后，s p r u n t 等给出了一种更好的s s ( s p o r a d i cs e