（计算机软件与理论专业论文）嵌入式工业监控系统中实时调度策略的研究.pdf

东北大学硕士学位论又 摘要 嵌入式工业监控系统中 实时调度策略的研究 摘要 随着嵌入式工业的不断成熟与发展，在线监测与故障诊断智能化仪器的开发已 经成为了 嵌入式工业的一个重要的应用领域。实时嵌入式工业监控系统作为嵌入式系统的一个分支， 除了具 有所有嵌入式系统普遍存在的资源受限等特点外，其自 身还对系统的可靠性和实时性 有着更高的 要求。为满足实时嵌入式工 业监控系统中任务的时限要求，需要在操作系统这一 软件层次上， 提供面向实际系统的，具有高可预测性的任务调度算法。 本文首先提出了一个实时嵌入式工业监控系统的结构模型，分析了这一模型中主要功能 模块的实时特性与需求。 在此基础之上， 从嵌入式系统特点和工业监控系统的应用 特点两个 方面提出了这个系统的整体实时需求。 根据对实际系统的分析结论， 我们从实时调 度算法的 功能角度提出了为实时嵌入式工业监控系统选择和设计调度算法需要遵循的主要原则，并在 此原则指导下， 选择了 时限单调算法作为本系统的主调度算法并陈述了 选择的理由。 理想的时限单调算法具有很多不符合系统客观特性的假设，例如任务间无资 源共享， 任 务间 无逻辑依 赖关系， 系 统开销为零等。 这些假设的 存 在使得在实际系 统中，理想 算法可调 度判定的 准确性大大降 低口 本文利用l u i s h a 等人提出的优先级置顶协议对理想时限单调算法进行了扩展，扩展后 的算法能够解决资源共享所带来的问题。在此荃础上，本文提出了一个实时系统的进程状态 转换模型， 分析了 状态转换过程中可能引发调度的事件， 基于 k a t c h e r 等人提出的集成中断 事件驱动调度机制， 详细分析了调度过程中的 开销情况，并对前面步骤得到的可调度判定进 一步扩展， 使得新的判定能 够处理调度与切换开销对可调度性的影响。 本文还提出了 一种任务分割策略， 该策略可以 把一个任务根据需要分割成若干个子任务。 对于系统中 部分任务会长时间占用共享资源的 情况， 采用这种分割策略可以 有效的改善高 优 先级任务通过可调度侧试的可能性。同 时任务分割策略还可以处理任务实际重要性与算法分 配的优先级不对应的问题。 利用上述技术扩展后的时限单调算法在保持了 原算法的 特性的同时。 也能够处理诸如资 源共享 和调 度切换开 销等实际问 题。得到的扩展判 定摆脱了 理 想算法的 部分 假设，能 够为 复 杂的任务系统提供实时可调度保证。 关键字:嵌入式， 工业监 控系统，实时调度， r m算法， d m算法，资源共享，调 度开销， 任务切换开销，p c p 协议，任务分割策略 东 北大学硕士学 位论又 ab s 汀a c t s t u d y o n t h e r e a l - t i me s c h e d u l i n g p o l i c y i n e mb e d d e d i n d u s t r i a l mo n i t o r a n d c o n t r o l s y s t e ms ab s t r a c t wi t h t h e d e v e l o p m e n t a n d m a tu r it y o f e m b e d d e d i n d u s t ry , i n t e l l i g e n t o n l i n e m o n i t o r a n d e r r o r d i a g n o s t i c s y s t e m s h a v e b e c o m e o n e o f t h e m a j o r f i e l d s . a s a b r a n c h o f e m b e d d e d s y s t e m s , re a l - t i m e e m b e d d e d in d u s t r i a l m o n i t o r a n d c o n t r o l s y s t e m h a s n o t o n l y r e s o u r c e c o n s t r a i n t s t h a t a r e c o m m o n t o e m b e d d e d s y s t e m s , b u t a l s o s p e c i fi c r e q u i r e m e n t s o n h i g h r e l i a b i l i ty a n d r e a l - t i m e p e r f o r m a n c e . t o s a t i s f y t h e t i m i n g r e q u i r e m e n t s o f s u c h c o n t r o l s y s t e m s , r e a l s y s t e m o r i e n t e d p r e d i c t a b l e s c h e d u l i n g a l g o r i t h m s a r e n e e d e d in t h e o p e r a t in g s y s t e m s o ft w a r e l a y e r . a n a b s t r a c t e d m o d e l o f a t y p i c a l r e a l - t i m e e m b e d d e d i n d u s t r i a l m o n i t o r a n d c o n t r o l s y s t e m i s p r e s e n t e d i n t h i s p a p e r a n d t h e re a l - t i m e c h a r a c t e r is t i c s o f e v e ry m o d u l e a r e a n a l y z e d . o v e r a l l s y s t e m re a l - t i m e r e q u i r e m e n t s a r e g iv e n fr o m t h e v i e w o f b o t h e m b e d d e d s y s t e m s a n d in d u s t r i a l m o n i t o r a n d c o n tr o l a p p l i c a t i o n s . o n t h e b a s i s o f t h e a b o v e a n a l y s i s , w e p r e s e n t s o m e c r i t i c a l p r i n c i p l e s o n s e le c t i n g s c h e d u l i n g a l g o r i t h m s f o r s u c h s y s t e m s a c c o r d i n g t o f u n c t i o n a l i t i e s o f t h e a l g o r i t h m s . t h e r e a s o n s w h y d e a d l i n e m o n o t o n i c a l g o r i t h m i s s e l e c t e d a r e a l s o g i v e n . i d e a l d e a d l i n e m o n o t o n i c a l g o r i t h m h a s m a n y a s s u m p t i o n s , s u c h a s n o r e s o u r c e s h a r i n g , n o l o g i c a l d e p e n d e n c i e s a m o n g t a s k s , n o c o n t e x t s w i t c h i n g o v e r h e a d a n d s o o n . t h e s e a s s u m p t i o n s m a y c o m p r o m i s e t h e p r e c i s i o n o f t h e s c h e d u l a b i l i ty t e s t i n a re a l s y s t e m i n t h i s p a p e r , p r i o r i ty c e i l in g p r o t o c o l , w h i c h i s f a s t p r e s e n t e d 勿l u i s h a a n d h i s c o l l e a g u e s , i s b o r r o w e d t o e x t e n d t h e b a s i c d e a d l i n e m o n o t o n i c a l g o r i t h m w i t h t h e a b il i ty t o h a n d l e r e s o u r c e s h a r i n g p r o b l e m s . t h e n a p ro c e s s tr a n s i t i o n m o d e l i s p r e s e n t e d a n d h o w t h e s c h e d u l e r c a n b e a c t i v a t e d i s a n a l y z e d . b a s e d o n k a t c h e r s i n t e g r a t e d i n t e r r u p t e v e n t - d r i v e n s c h e d u l in g p o l i c y , a d e e p a n a l y s i s i n t o s c h e d u l i n g o v e r h e a d a n d c o n t e x t s w i t c h i n g o v e r h e a d i s m a d e , a n d t h e s c h e d u l a b i l i ty t e s t i s f u r th e r e x t e n d e d t o i n c o r p o r a t e t h e s e o v e r h e a d s . a t a s k p a r t i t i o n in g s t r a t e g y i s p re s e n t e d i n t h i s p a p e r , w h i c h c a n p a rt i t i o n a t a s k in t o s e v e r a l s u b - t a s k s . i f t h e r e a r e t a s k s th a t m a y s t a y i n a c r i t i c a l s e c t i o n f o r a l o n g p e r i o d in a s y s t e m , t h e t a s k p a rt it io n in g s t r a t e g y m a y im p r o v rq t h e p ro b a b i li ty o f a h i g h e r p r io r i ty t a s k p a s s in g t h e s c h e d u l a b i l i ty t e s t . t h i s s t r a t e g y c a n a l s o re s o l v e t h e i n c o n s i s t e n c y i n t h e m a p p i n g o f r e a l i m p o r t a n c e o f a t a s k t o i t s a s s i g n e d p r i o r i t y . wi t h t h e s e r e v i s e s , t h e e x t e n d e d d e a d l i n e mo n o t o n i c s c h e d u l a b i l i t y t e s t c a n h a n d l e r e s o u r c e s h a r in g a n d s y s t e m o v e r h e a d a n d s t i l l m a i n t a i n s t h e c h a r a c t e r i s t i c s o f t h e b a s i c a l g o ri t h m . i t s a p p a r e n t t h a t t h e e x t e n d e d s c h e d u l a b i l i ty t e s t h a s r e l e a s e d s o m e a s s u m p t i o n s m a d e i n t h e b a s i c a l g o r i t h m , a n d i t c a n g u a r a n t e e t h e r e a l - ti m e r e q u i r e m e n t s o f c o m p l e x s y s t e m s . k e y w o r d s e m b e d d e d , i n d u s tr i a l m o n i t o r a n d c o n t r o l s y s t e m , re a l - t i m e s c h e d u l i n g , r m a l g o r i t h m , d m a l g o r i t h m , r e s o u r c e s h a r in g , s c h e d u l i n g o v e r h e a d , t a s k c o n t e x t s w i t c h in g o v e r h e a d . p c p p r o t o c o l , t a s k p a r t i t i o n i n g s t r a t e g y 独创性声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文中取 得的研究成果除加以 标注和致谢的地方外，不包含其他人已 经发表或 撰写过的研究成果，也不包括本人为获得其他学位而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均己 在论文中作了明的 说明并表示谢意。 学 位 论 文 作 者 签 名 : 务呜松 日期: 0 1 0 0 了_ / , 0 . 学位论文版权使用授权书 本学位论文作者和指导教师完全了 解东北大学有关保留、使用学 位论文的规定:即学校有权保留并向国家有关部门 或机构送交论文的 复印 件和磁盘，允许论文被查阅和借阅。 本人授权东北大学可以将学 位论文的全部或部分内容编入有关数据库进行检索、交流。 ( 如作者和导师同意网上交流，请在下方签名;否则视为不同意。 ) 学 位 论 文 作 者 签 名 : 夯鸟村 签 字日 期:a o5. 4 . / l 导 师 签 名 : 舟戈 签字日 期: 奋 的 上 、1 ， 及 东北大学硕士学位论文第一幸 引言 竿 一 音日i 誉 ， 洲 7月 声.j . 刁 当今计算机行业的发展已经进入了后 p c时代，嵌入式设备与系统己经渗透到了工 业控 制、 网 络通信、家 用电 器、 汽车电 子、 移动电话与 手持设备、 信息安全等重要领域。田 子 具 有体积小 能耗低、可移动以及实时性好等优势，嵌入式系统发挥着其他计算机系统所不能 替代的作用。工业实时监控就是嵌入式系统最大的应用领域之一， 它对于高可靠性和高实时 性的要求要明显高于其他类型的嵌入式系统。 一个嵌入式工业监控系统的设计既要 求满足嵌 入式系统自 身的需 求，同时也要有很好的实时性保证。保证一个嵌入式系统实时性的主要环 节就是在嵌入式操作系统这一软件层次上，提供适合 应用 特点的实时调度算法，这方面的工 作也成为了嵌入式系统和实时系统的重要研究领域。 1 . 1 嵌入式系统背景 “ 嵌入式” 这一概念是在2 0 世纪8 0 年代中期被i n t e l 公司首先提出的， 但是它的历史 却 可以 追溯到上个世纪7 0 年代单片机的产生和发展。 单片机的产生是应用需求驱动的结果， 它 的发展历经了s c m, m c u , s o c 三个 阶段， 而嵌 入式系统 就是由s o c 逐渐演化而来的。 嵌入式系统通常被定义为“ 嵌入到对象体系中的 专用计算 机系统” 。 在网络文献中还常被 定义为 “ 以应用为中心、以 计算机技术为基础、软件 硬件可裁剪、 适应应用系统对功能、 可 靠性、 成本、 体积、 功耗严格要求的专用计算机系统” 。 从另外一个角度， 嵌入式系统又叫做 “ 资源受限” 系统， 这是因为在一个嵌入式系统中， c p u计算能力、 存储容量、 供电能力等 方面都相对匾乏。 虽然当 前硬件的发展使得嵌入式系统的c p u速度大幅增加， 存储容量也不 再是瓶颈， 但是对嵌入式设备体积的 要求和电 池技术的 滞后发展仍旧使得其设计必须仔细考 虑资源消耗的问 题。 由于嵌入式技术的出 现， 原有的根据计算机规模对计算机系统进行划分的 方法已 经不科 学了。 现代计算机技术发 展根据应用需求， 将计算机划分为两大分支: “ 通用计算机” 和“ 嵌 入式计算机系 统” 。 通用计算机系统的设计使得用户可以 通过软件配备实现各种功能， 其发展 方向 是追求总线速 度的 无限 提升和存储容量的 无限 扩大。 然而 诸如工 业控制，数据 采集，自 动监测，智能家电， 无线通信等应用则要求将微型计算机系统嵌入到一个对象体系中，实现 对该 对象体系的 智能 控制， 这类具有 特殊应用的系 统通常是嵌入式系 统 嵌入式系统自 身的应用环境和设计成本等因素决定了 在硬件和软件的设计方面有着和通 用计 算机系统完全不同的要求。 例如通用计算机系统中c p u的设计一股不考虑功耗问题， 其 设计思路是追求更高的主频和更大的 吞吐量，而嵌入式系统的c p u则 必须考虑芯片的体积、 功耗以 及指令系统等，以 适应特殊应用的需求。而在操作系统方面， 通用系统主要是为使用 者提供更丰富的功能，更友好的用户界面，以及为程序设计人员 提供更加易用的编程接口; 嵌入式系统则要求操作系统必须是微内核设计以满足设计人员对系统可裁减性的要求，同时 苛刻的应用环境要求嵌入式操作系统要比通用操作系统具有更高的可靠性 在进程调度方面， 通用操作系统一般采用分时轮转的调度策略，目的是尽可能 提高系统的吞吐率并满足调度的 公平性; 而在嵌入式系统中，进程调度必须满足任务的实时性要求，不仅要保证任务执行结 东北大学硕士学位论文第一幸 引言 竿 一 音日i 誉 ， 洲 7月 声.j . 刁 当今计算机行业的发展已经进入了后 p c时代，嵌入式设备与系统己经渗透到了工 业控 制、 网 络通信、家 用电 器、 汽车电 子、 移动电话与 手持设备、 信息安全等重要领域。田 子 具 有体积小 能耗低、可移动以及实时性好等优势，嵌入式系统发挥着其他计算机系统所不能 替代的作用。工业实时监控就是嵌入式系统最大的应用领域之一， 它对于高可靠性和高实时 性的要求要明显高于其他类型的嵌入式系统。 一个嵌入式工业监控系统的设计既要 求满足嵌 入式系统自 身的需 求，同时也要有很好的实时性保证。保证一个嵌入式系统实时性的主要环 节就是在嵌入式操作系统这一软件层次上，提供适合 应用 特点的实时调度算法，这方面的工 作也成为了嵌入式系统和实时系统的重要研究领域。 1 . 1 嵌入式系统背景 “ 嵌入式” 这一概念是在2 0 世纪8 0 年代中期被i n t e l 公司首先提出的， 但是它的历史 却 可以 追溯到上个世纪7 0 年代单片机的产生和发展。 单片机的产生是应用需求驱动的结果， 它 的发展历经了s c m, m c u , s o c 三个 阶段， 而嵌 入式系统 就是由s o c 逐渐演化而来的。 嵌入式系统通常被定义为“ 嵌入到对象体系中的 专用计算 机系统” 。 在网络文献中还常被 定义为 “ 以应用为中心、以 计算机技术为基础、软件 硬件可裁剪、 适应应用系统对功能、 可 靠性、 成本、 体积、 功耗严格要求的专用计算机系统” 。 从另外一个角度， 嵌入式系统又叫做 “ 资源受限” 系统， 这是因为在一个嵌入式系统中， c p u计算能力、 存储容量、 供电能力等 方面都相对匾乏。 虽然当 前硬件的发展使得嵌入式系统的c p u速度大幅增加， 存储容量也不 再是瓶颈， 但是对嵌入式设备体积的 要求和电 池技术的 滞后发展仍旧使得其设计必须仔细考 虑资源消耗的问 题。 由于嵌入式技术的出 现， 原有的根据计算机规模对计算机系统进行划分的 方法已 经不科 学了。 现代计算机技术发 展根据应用需求， 将计算机划分为两大分支: “ 通用计算机” 和“ 嵌 入式计算机系 统” 。 通用计算机系统的设计使得用户可以 通过软件配备实现各种功能， 其发展 方向 是追求总线速 度的 无限 提升和存储容量的 无限 扩大。 然而 诸如工 业控制，数据 采集，自 动监测，智能家电， 无线通信等应用则要求将微型计算机系统嵌入到一个对象体系中，实现 对该 对象体系的 智能 控制， 这类具有 特殊应用的系 统通常是嵌入式系 统 嵌入式系统自 身的应用环境和设计成本等因素决定了 在硬件和软件的设计方面有着和通 用计 算机系统完全不同的要求。 例如通用计算机系统中c p u的设计一股不考虑功耗问题， 其 设计思路是追求更高的主频和更大的 吞吐量，而嵌入式系统的c p u则 必须考虑芯片的体积、 功耗以 及指令系统等，以 适应特殊应用的需求。而在操作系统方面， 通用系统主要是为使用 者提供更丰富的功能，更友好的用户界面，以及为程序设计人员 提供更加易用的编程接口; 嵌入式系统则要求操作系统必须是微内核设计以满足设计人员对系统可裁减性的要求，同时 苛刻的应用环境要求嵌入式操作系统要比通用操作系统具有更高的可靠性 在进程调度方面， 通用操作系统一般采用分时轮转的调度策略，目的是尽可能 提高系统的吞吐率并满足调度的 公平性; 而在嵌入式系统中，进程调度必须满足任务的实时性要求，不仅要保证任务执行结 东 北大学 硕士学 位论文 第一章 引言 果的逻辑正 确性， 还要保证 任务在规定的时间内完成，否则可能造成灾难行后果. 1 . 2 工业监控系统产业背景 大型电 机、水泵等机电系统属于典型的旋转机械设备，主要应用于电力、石化、冶金、 矿山等行业，在国民 经济工业生产中处于极为主要的关键地位。 几十年来对这类机械的监slj 与诊断一直 受到人们的重视。 这些设备的安全运行是保证生产系统的重要前提。 随着嵌 入式技术的不断成熟与发展，面向大中型机电设备的在线状态监测与故障诊断类 仪器的开发已经形成了 一个很大的 产业。该类智能 仪器的出现，已 经在大型机电设备维修和 故 障诊断方 面带来了 一 场革命， 这就是 用科学的“ 状态维修” 。 逐渐代替非 科学的周期性维修。 采用在线维修的方法，一是可以提前发现故障，避免重大事故和经济损失:二是使维修变得 经济可靠， 在大型机电 设备上 应用智能 化状态监 测和故障诊断 仪器之后， 使企业可以 有依据 的只对有问 题的设备进行维修， 而其他设备可以照常运行， 产生效益。我国当前普遍采用的 维修方法是周期性维修，即到一定周期， 不管设备有没有问 题， 全部停机大 拆。这种维修方 法没有可靠性依据， 长时间的大修期给企业造成的损失巨大， 仅以电厂的一个机组为例，一 次大修需要3 个月， 给电 厂造成的 损失可 达千 万。 而在两个维修 期之间的 这段时间，设 备出 现故障却不 能被提前发 现， 仍然不 可进免的出 现一 些大型事故。 面向 大 型设备 状态监测与故障 诊断智能仪 器的 开发， 在发 达国 家已 经非 常成熟， 美国的 c s i 、 本特立、 思秦克、西屋等公司 的产品在世界各地的各 大工 矿企业都有成功的应用， 产 生了巨 大的 社会效益。国内许多企业逐渐认识到设备在线故障监测的重要性. 但是到目 前为 止，基于嵌 入式技术的该 类设备 在我国 仍属空白， 没 有成熟的 产品 应用。 这一 现状的 根本原 因 就是 我国 在开发这 类产品时， 没有统一的开发标 准和 共用的开发 平台， 而且没有可靠的 功 能和性能侧试标准，各个企业的开发技术力t分散，极大的影响了该类产品 开发的效率和可 靠性。 而制 造出 来的产品同国 外同 类产品 相比， 功能相差太大， 没有竟争力， 因此市场墓本 上被国外公 司所占 领。 开发一个该类嵌入式开发系统己 经是势在必行。 先进的 监控系统在如下的一些方面有着很高的要求。首先就是要有一个实时嵌 入式操作 系统作为所 有软件开发的 基础。 这 样的 操作系 统必须提供可 抢占 式的 任务调 度策略， 支持实 时时 钟服务 与中断 服务， 具有可 预测的 任务同步 机制和通信机制， 为 上层程序提供尽可能高 的稳定性与 可预测性。 其次，这类系统都有一个实时数据库系统作为整个系统数据处理、 数 据组织和管理的 核心。嵌入式实时数据库系统需要结合实时数据处理技术和数据库技术，与 传统的数据库不同， 嵌入式实时数据库必须同时满足访问实时性和数据一致性的要求。 另外 在操作系统 层次 之上， 还需要有一个中间 件层， 这一层包括 支持实时性， 可 靠性， 安全性等 功能的 过程 库函数， 提供在实时操作系统， 实时数据库，实时通信系统基 础上的扩展功能。 因此嵌入式 监控系统和消费 类等嵌入式系统相比有着不同的系统需求 1 . 3 实时调度研究背景 实时调 度是一个实时 嵌入式系统中实时性得到 保证的关键部分， 它属于 操作系 统 进程调 度的 范畴。 实时调 度算法的 研究从2 0 世纪7 0 年代就己 经开始了， 有大 it的 研究人员 进入该 领域， 也出 现了很多适用于不同 应用需求的调度算法， 例如适用于高可靠性系统的调度算法， 适用多媒体 流a r 务的 调度算法等。 文献 r a s 9 4 和 s u r g o 中 都分析了几 类主 流的 调度算 法。 这 些算法可以 从调度机制本身分成以下的几个大类。 东 北大学 硕士学 位论文 第一章 引言 果的逻辑正 确性， 还要保证 任务在规定的时间内完成，否则可能造成灾难行后果. 1 . 2 工业监控系统产业背景 大型电 机、水泵等机电系统属于典型的旋转机械设备，主要应用于电力、石化、冶金、 矿山等行业，在国民 经济工业生产中处于极为主要的关键地位。 几十年来对这类机械的监slj 与诊断一直 受到人们的重视。 这些设备的安全运行是保证生产系统的重要前提。 随着嵌 入式技术的不断成熟与发展，面向大中型机电设备的在线状态监测与故障诊断类 仪器的开发已经形成了 一个很大的 产业。该类智能 仪器的出现，已 经在大型机电设备维修和 故 障诊断方 面带来了 一 场革命， 这就是 用科学的“ 状态维修” 。 逐渐代替非 科学的周期性维修。 采用在线维修的方法，一是可以提前发现故障，避免重大事故和经济损失:二是使维修变得 经济可靠， 在大型机电 设备上 应用智能 化状态监 测和故障诊断 仪器之后， 使企业可以 有依据 的只对有问 题的设备进行维修， 而其他设备可以照常运行， 产生效益。我国当前普遍采用的 维修方法是周期性维修，即到一定周期， 不管设备有没有问 题， 全部停机大 拆。这种维修方 法没有可靠性依据， 长时间的大修期给企业造成的损失巨大， 仅以电厂的一个机组为例，一 次大修需要3 个月， 给电 厂造成的 损失可 达千 万。 而在两个维修 期之间的 这段时间，设 备出 现故障却不 能被提前发 现， 仍然不 可进免的出 现一 些大型事故。 面向 大 型设备 状态监测与故障 诊断智能仪 器的 开发， 在发 达国 家已 经非 常成熟， 美国的 c s i 、 本特立、 思秦克、西屋等公司 的产品在世界各地的各 大工 矿企业都有成功的应用， 产 生了巨 大的 社会效益。国内许多企业逐渐认识到设备在线故障监测的重要性. 但是到目 前为 止，基于嵌 入式技术的该 类设备 在我国 仍属空白， 没 有成熟的 产品 应用。 这一 现状的 根本原 因 就是 我国 在开发这 类产品时， 没有统一的开发标 准和 共用的开发 平台， 而且没有可靠的 功 能和性能侧试标准，各个企业的开发技术力t分散，极大的影响了该类产品 开发的效率和可 靠性。 而制 造出 来的产品同国 外同 类产品 相比， 功能相差太大， 没有竟争力， 因此市场墓本 上被国外公 司所占 领。 开发一个该类嵌入式开发系统己 经是势在必行。 先进的 监控系统在如下的一些方面有着很高的要求。首先就是要有一个实时嵌 入式操作 系统作为所 有软件开发的 基础。 这 样的 操作系 统必须提供可 抢占 式的 任务调 度策略， 支持实 时时 钟服务 与中断 服务， 具有可 预测的 任务同步 机制和通信机制， 为 上层程序提供尽可能高 的稳定性与 可预测性。 其次，这类系统都有一个实时数据库系统作为整个系统数据处理、 数 据组织和管理的 核心。嵌入式实时数据库系统需要结合实时数据处理技术和数据库技术，与 传统的数据库不同， 嵌入式实时数据库必须同时满足访问实时性和数据一致性的要求。 另外 在操作系统 层次 之上， 还需要有一个中间 件层， 这一层包括 支持实时性， 可 靠性， 安全性等 功能的 过程 库函数， 提供在实时操作系统， 实时数据库，实时通信系统基 础上的扩展功能。 因此嵌入式 监控系统和消费 类等嵌入式系统相比有着不同的系统需求 1 . 3 实时调度研究背景 实时调 度是一个实时 嵌入式系统中实时性得到 保证的关键部分， 它属于 操作系 统 进程调 度的 范畴。 实时调 度算法的 研究从2 0 世纪7 0 年代就己 经开始了， 有大 it的 研究人员 进入该 领域， 也出 现了很多适用于不同 应用需求的调度算法， 例如适用于高可靠性系统的调度算法， 适用多媒体 流a r 务的 调度算法等。 文献 r a s 9 4 和 s u r g o 中 都分析了几 类主 流的 调度算 法。 这 些算法可以 从调度机制本身分成以下的几个大类。 东 北大学 硕士学 位论文 第一章 引言 果的逻辑正 确性， 还要保证 任务在规定的时间内完成，否则可能造成灾难行后果. 1 . 2 工业监控系统产业背景 大型电 机、水泵等机电系统属于典型的旋转机械设备，主要应用于电力、石化、冶金、 矿山等行业，在国民 经济工业生产中处于极为主要的关键地位。 几十年来对这类机械的监slj 与诊断一直 受到人们的重视。 这些设备的安全运行是保证生产系统的重要前提。 随着嵌 入式技术的不断成熟与发展，面向大中型机电设备的在线状态监测与故障诊断类 仪器的开发已经形成了 一个很大的 产业。该类智能 仪器的出现，已 经在大型机电设备维修和 故 障诊断方 面带来了 一 场革命， 这就是 用科学的“ 状态维修” 。 逐渐代替非 科学的周期性维修。 采用在线维修的方法，一是可以提前发现故障，避免重大事故和经济损失:二是使维修变得 经济可靠， 在大型机电 设备上 应用智能 化状态监 测和故障诊断 仪器之后， 使企业可以 有依据 的只对有问 题的设备进行维修， 而其他设备可以照常运行， 产生效益。我国当前普遍采用的 维修方法是周期性维修，即到一定周期， 不管设备有没有问 题， 全部停机大 拆。这种维修方 法没有可靠性依据， 长时间的大修期给企业造成的损失巨大， 仅以电厂的一个机组为例，一 次大修需要3 个月， 给电 厂造成的 损失可 达千 万。 而在两个维修 期之间的 这段时间，设 备出 现故障却不 能被提前发 现， 仍然不 可进免的出 现一 些大型事故。 面向 大 型设备 状态监测与故障 诊断智能仪 器的 开发， 在发 达国 家已 经非 常成熟， 美国的 c s i 、 本特立、 思秦克、西屋等公司 的产品在世界各地的各 大工 矿企业都有成功的应用， 产 生了巨 大的 社会效益。国内许多企业逐渐认识到设备在线故障监测的重要性. 但是到目 前为 止，基于嵌 入式技术的该 类设备 在我国 仍属空白， 没 有成熟的 产品 应用。 这一 现状的 根本原 因 就是 我国 在开发这 类产品时， 没有统一的开发标 准和 共用的开发 平台， 而且没有可靠的 功 能和性能侧试标准，各个企业的开发技术力t分散，极大的影响了该类产品 开发的效率和可 靠性。 而制 造出 来的产品同国 外同 类产品 相比， 功能相差太大， 没有竟争力， 因此市场墓本 上被国外公 司所占 领。 开发一个该类嵌入式开发系统己 经是势在必行。 先进的 监控系统在如下的一些方面有着很高的要求。首先就是要有一个实时嵌 入式操作 系统作为所 有软件开发的 基础。 这 样的 操作系 统必须提供可 抢占 式的 任务调 度策略， 支持实 时时 钟服务 与中断 服务， 具有可 预测的 任务同步 机制和通信机制， 为 上层程序提供尽可能高 的稳定性与 可预测性。 其次，这类系统都有一个实时数据库系统作为整个系统数据处理、 数 据组织和管理的 核心。嵌入式实时数据库系统需要结合实时数据处理技术和数据库技术，与 传统的数据库不同， 嵌入式实时数据库必须同时满足访问实时性和数据一致性的要求。 另外 在操作系统 层次 之上， 还需要有一个中间 件层， 这一层包括 支持实时性， 可 靠性， 安全性等 功能的 过程 库函数， 提供在实时操作系统， 实时数据库，实时通信系统基 础上的扩展功能。 因此嵌入式 监控系统和消费 类等嵌入式系统相比有着不同的系统需求 1 . 3 实时调度研究背景 实时调 度是一个实时 嵌入式系统中实时性得到 保证的关键部分， 它属于 操作系 统 进程调 度的 范畴。 实时调 度算法的 研究从2 0 世纪7 0 年代就己 经开始了， 有大 it的 研究人员 进入该 领域， 也出 现了很多适用于不同 应用需求的调度算法， 例如适用于高可靠性系统的调度算法， 适用多媒体 流a r 务的 调度算法等。 文献 r a s 9 4 和 s u r g o 中 都分析了几 类主 流的 调度算 法。 这 些算法可以 从调度机制本身分成以下的几个大类。 东 北大学 硕士学位论文 第一章 引言 最早的一类实时调度算 法是基于静态表的调度算法。在系统开始执行之前，调度器要生 成一个调度表， 表中 包含了 每个任务的开始时间 和结束时间，所有任务按照表中规定的顺序 执行。 这种调 度算 法的 最大 优点是可以 提供最高 程度的可 预测性， 但是 其可 伸缩性是最差的， 任务的增删或修改都将导致静态表的重新生成。 在其之后出 现的 实时调 度算法主要是 优先级驱动的可 抢占 式算法， 这种 算法是实时调 度 领域的主流算法，由于其易于实现，并能提供较好的可预测性，在众多实际系统中得到了广 泛的应用。 这类算法又可以 根据任务优先级在系统执行过程中是否可变，分为静态优先级调 度算法和动态优先级调度算法。 速率单调算法 ( r m) 和时限单调算法 ( d m) 是静态优先级调度中的两种主要算法。以 r m算法为 例， 它主 要用来处理周期性任务， 对于一 组周期性 任务， 周期越小的 任务其优先 级越高， 这就是r m算 法的 根本思想。 该算法的优点 是运行时调 度开销小， 可预测性高，而 且在过载情况下具有稳定的表现。 而d m算法能够处理周期和时限不相等的这类任务， 具体 的原理将在后面的章节阐述，该算法也是本论文要进行优化修改的基础算法。 在动态优先级这类算法中， e d f , l l f 和m u f 是具有代表性的几种。 其中e d f 是 “ 最 早时限 优先”的 意思。 每个 任务 都会提交其时限 给系 统， 调 度器 根据当 前任务的绝 对时限 选 择最近的一 个执行， 任务的 优先级会根据当前一次执行的绝对时限 和其他任务绝对时限的关 系而动态变化。 l l f 是“ 最短松弛时间优先” 算法， m u f 是 “ 最高紧急性任务优先” 算法。 后两个算法的基本思路是和e d f 相通的。这类算法的优点是具有更高的c p u使用率，可以 处理非 周期 任务， 但是由 于任务的 优先级是动态改变的， 并且调 度器要随时计算系 统中 各任 务的绝对时限， 因此运行时 调度开销 要比 静态优先级调 度算法大得多。 此类算法在 系统 过载 时的可预测性大大降 低， 调 度性能甚至低于一 些随机调 度算法。 上述可抢占 优先级驱动的主流算法虽然都有其缺陷， 但是在通常情况下对于硬实时任务 能够很好的保证其可调度性。尤其是睁态优先级算法，在给定任务的参数后，在运行前就可 以分析出这一组任务的时限是否可以都被满足。而对于动态优先级算法，虽然过载时性能下 降，但是非过载情况下对于 硬实时任务能够很好的 满足实时性需求。 除 上 述两 类算 法 外 还 有 第三 类基于 带宽 预留( b a n d w i d th p re s e r v in g ) 的 优先 级驱 动算 法。 这 类算 法 包括文 献 s s i .8 7 中 提出 的p o ll i n g s e r v e r 算法 和p r io r it y e x c h a n g e 算 法， 文 献 s l s 9 5 提出 的d e f e r r a b l e s e r v e r 算 法， 文 献 s p b 9 6 提出 的t o t a l b a n d w id t h s e r v e r 算 法 和文献 s s l 8 9 与 【 s p r 9 0 提出 的s p o r a d i c s e r v e r 算法。 这类算法会为任务 预留 处理机时间， 所以叫 做带宽 预 留算法。 虽然e d f 等动态优先级算法也能够处理非周期 任务， 但是实践中多 用来处理周期任 务。而 带宽预留算法的设计目 标就是处理非周期性任务。 而带宽预留的里和补充时 机的差异 导 致了 不同的 算法， 而不同 的 算法对非周期任务的响 应性是不同 的， 文献 g o m 9 9 对这类算 法进行了 详细的性能比 较。 除了以上的几类算法外，还有一类叫做 “ 动态尽最大努力”的调度算法。这类算法适用 于一些特定的 应用，比如在多媒体系统中，对于帧的传输并不需要 1 0 0 % 不丢帧， 只要保证 一定百分比的帧能正确达到 就可以忍受。这种应用就和需要 1 0 0 % 保证实时性的硬实时系统 有着本质的区 别。 在另 外一 些系统中， 任务的 到达频率很高， 系统容易出 现过载的 情况。 动 态尽最大努力算法的 优点 就是能 够在 过载的 情况下 仍有比 较好的 表现。当 然这类算 法的 缺点 也是很明 显的， 首 先一种 启发算法很 难是最 优的， 其次该 类算法不能保 证硬实时 任务的时限 要求。 东 北大学硕士学 位论文 贾一章 引 万 1 . 4任务来源 本课题隶属于己 经申 报国家8 6 3 课题并于2 0 0 2 年启动的嵌入式项目 面向 大型机电设 备状态监测与故障诊断的智能仪器嵌入式软件平台的开发。 该项目 的主要目 的是:针对大型 机电设备状态监测与故障诊断类嵌入式智能仪器开发的 嵌 入式技术的巨大 和迫切应用需求， 开发面向 该 行业的嵌入式系统开发平台，开发可视化的 开发 工具和功能 和性能 测试工具。 应用该开发 平台能 够为 该类仪器的开发人员 提 供一 个高 性 能、高可靠性和高健壮性的开发环境，同时由于该平台提供了大量共用 模块的开发， 可大大 提高针对该类智能化产品开发的效率。 该项目 的意义是:通过本项目 的实施，开发一个面向 行业应用的嵌入式开发平台，促进 我国在大型 机电 设备状态监测与故障诊断类嵌入式智能仪器的 产业发展，抵挡和取代国外产 品 在该行业的垄断地位，取得良 好的经济和社会效益. 1 . 5需要解决的问题 该嵌入式项目面临许多需要解决的问题，包括了从硬件到软件的诸多方面。如具有自主 知识产权的电路板的开发设计， c p u与外设接口 的高速数据传输， 基于 蓝牙技术的 无线通信， 基于嵌入式i n t e m e t 的通信技术以 及实时调 度技术与实时事务处理等。 嵌入式系统中的调度策略不仅要满足任务结果的逻辑正确性，同时还要满足任务的时限 要求。本文所面向的系统中的调度策略的设计，就是要在嵌入式应用环境下，满足大型旋转 机电设备特殊的实时需求。 常见的实时调 度算法主要是静态优先级调度和动态优先级调度两大类。这些算法中， 有 些算法调度开 销很大， 适用于大型 机系统或分布式系统， 而有些算法的 理想 假设 过多， 从而 不适用于实际系统。 本课题分析了 现有的主流实时调度算法， 选择了d m算法作为本系统的 基础调度策略。 基于d m算法和己有的实时调度领域的 成果， 对d m算法进行了 进一步的 分 析和扩展， 扩展后的可调度性判定更加接近实际系统的情况。 优化后的d m算法与其他实时 调度算法相比，要满足嵌入式系统中低调度开销要求，适合数据采集与处理这类特殊应用的 需求，过载时算法的稳定性以及算法易于实现和分析 1 . 6 后续章节的安排 本章主要介绍了和研究方向相关的背景知识，并提出了需要解决的问题。后面的章节安 排如下:第二 章介绍了 实时调 度中的 基本 概念和相关算法: 第三章 提出了 项目 的 抽象模型并 阐述了 该项目 的实时性需求:第四章分析了为本文所面向的系统选择实时调度算法的依据: 第五章从资源共享和系统开销两个方面对d m算法进行了 扩展，并提出了一种任务分割策略 用来