（计算机应用技术专业论文）实时操作系统任务调度算法的改进及网络协议栈的实现.pdf

华 中 科 技 大 学 硕 士 学 位 论 文 摘要 随着嵌入式系统和网 络的日 益结合， 在嵌入式实时操作系统中引 入 t c p i i p协议 栈，以 支持嵌入式设备接入网 络， 成为嵌入式领域重要的 研究方向。 在网 络服务环境 下，实时嵌入式操作系统可能既要处理实时任务，又要提供一定的i n t e rn e t 服务。 对 于实时任务，需要按照优先级不同顺序完成; 对于非实时的服务进程， 则希望它们轮 流执行。因 此，指定相应的调度策略显得尤为重要。 u c c 3 s - i i 是一个源代码公开的 抢占 式内 核实时嵌入式操作系统， 只包含了 任务调 度、 任务管理、 时间管理、内 存管理和任务间的通信与同步等基本功能。 没有提供输 入输出管理、 文件系统、网络之类的额外服务。由子u c o s - i i 的可移植性和开源性， 用户可以自己 添加所需的各种服务。 为更好地满足实时嵌入式系统网络服务的特点，以u c / o s - i i 为基础， 根据其内核 优先权分配的特点， 对其任务调度算法函数进行改进。 在操作系统方面， 对内核进程 调度函数以及内存缓存 n b u f 分配和释放函数进行改进，实现了局部进程之间的时何 片轮转， 而在整体上， 继续保持 着优先权的 调度模式。 在用于分配存储器缓存的函数 中，通过加入一定的信号量控制，实现对全局统一的n b u f 资源进行统一调配。 在t c p / i p协议栈方面， 针对u c o s - i i 操作系统的特点，考虑到嵌入式系 统占 用 的内存大小， 主要对源代码进行了一定的裁剪和改写， 并列出了主要的数据结构和数 据报处理流程，以及相关的主要系统函数，以实现基本的i n t e rne t 协议功能。 关键词:嵌入式， 操作系统， 任务 调度算法，网络协议 华 中 科 技 大 学 硕 士 学 位 论 文 ab s t r a c t w i t h t h e i n c r e a s i n g c o m b i n a t i o n o f e m b e d d e d s y s t e m a n d t h e n e t w o 氏 i n t r o d u c i n g t c p / i p p r o t o c o l s t a c k t o s u p p o rt t h e c o n n e c t io n o f e m b e d d e d d e v i c e t o t h e n e tw o r k h a s b e c o m e a n i m p o rt a n t r e s e a r c h t o p i c i n e m b e d d e d fi e l d . u n d e r t h e c i r c u m s t a n c e o f n e t w o r k s e r v i c e , r e a l - t i m e e m b e d d e d o p e r a t i o n s y s t e m m a y h a v e t o p r o c e s s r e a l- t i m e t a s k s , a n d p r o v id e c e r t a i n i n t e r n e t s e r v ic e . f o r r e a l - t i m e t a s k s , t h e y s h o u l d b e d o n e a c c o r d i n g t o t h e s e q u e n c e o f p r i o r i t y ; f o r n o n - r e a l - t i m e t a s k s , t h e y a r e e x p e c t e d t o b e d o n e i n t u rn . t h e r e f o r e , t h e a p p o i n t m e n t o f p r o p e r s c h e d u l in g s t r a t e g y i s e s p e c i a l l y i m p o rt a n t . u c / o s - i i i s a p r e e m p t i v e k e rn e l e m b e d d e d o p e r a t i o n s y s t e m w h o s e s o u r c e c o d e is o p e n e d . i t i n c l u d e s o n l y b a s i c f u n c t i o n s , s u c h a s t a s k s s c h e d u l in g , t a s k s m a n a g e m e n t , t im e m a n a g e m e n t , m e m o ry m a n a g e m e n t a n d t h e c o m m u n i c a t i o n a n d s y n c h r o n i z a t i o n b e t w e e n t a s k s . i t d o e s n t p ro v id e t h o s e e x t r a s e r v i c e l ik e i / o m a n a g e m e n t , fi l e s y s t e m a n d n e t w o r k . b e c a u s e o f t h e t r a n s l a t a b il it y a n d o p e n n e s s o f u c / o s - 1 1 , u s e r s c a n a d d t h e r e q u i r e d s e r v i c e s b y t h e m s e l v e s . i n o r d e r t o s a t i s f y t h e r e q u ir e m e n t o f t h e n e t w o r k s e r v i c e i n t h e r e a l - t i m e e m b e d d e d s y s t e m , o n t h e b a s i s o f u c / o s - l i , t h e i m p r o v e m e n t o f it s t a s k s c h e d u l i n g a l g o r it h m f u n c t i o n h a s b e e n m a d e a c c o r d i n g t o t h e c h a r a c t e r i s t i c o f k e rn e l p r io r it y d i s t r ib u t i o n . o n t h e a s p e c t o f t h e o p e r a t i o n s y s t e m , i m p r o v e m e n t h a s b e e n d o n e o n k e r n e l p r o c e s s s c h e d u l i n g a n d n b u f a l l o c a t i o n t o r e a l i z e t h e r o u n d - r o b i n b e t w e e n p r o c e s s e s . b u t a s a w h o l e , t h e p r i o r i t y s c h e d u l i n g m o d e i s p r e s e r v e d . i n t h e f u n c t i o n f o r d i s t r i b u t in g m e m o r y b u f f e r , t h e a l l o c a t i o n o f n b u f r e s o u r c e s h a s b e e n d o n e 妙t h e a d d i ti o n o f c e rt a i n s i g n a l . o n t h e a s p e c t o f t c p / i p p r o t o c o l s t a c k , a c c o r d i n g t o t h e c h a r a c t e r i s t i c o f u c / o s - i i o p e r a t i o n s y s t e m , i n t e r n e t s t a c k m o d e l a r e p r o p o s e d c o n s i d e r i n g t h e m e m o r y s i z e o c c u p i e d b y e m b e d d e d s y s t e m . t h e m a i n w o r k h a s b e e n d o n e o n t h e e d i t a n d r e w r it i n g o f t h e r e s o u r c e c o d e t o r e a l i z e t h e b a s i c f u n c t i o n o f t c p / i p p r o t o c o l . t h e m a in d a t a s t r u c t u r e , a n d d a t a fl o w p roc e s s , a n d r e l a t i v e s y s t e m f u n c t i o n a r e l i s t e d i n o r d e r t o r e a l iz e t h e b a s ic p r o t o c o l f u n c t i o n o f i n t e rn e t , k e y w o r d s : e m b e d d e d , o p e r a t io n s y s t e m , s c h e d u li n g a l g o r i t h m , n e t w o r k p r o t o c o l 皿 独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的 研究成果。尽我所知，除文中己经标明引用的内容外，本论文不包含任何其他个 人或集体己经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体， 均己在文中以明确方式标明。本人完全意识到本声明的法律结果由 本人承担。 学 位 论 文 作 者 签 名 : o 日 期 :户啤年了月/ 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即:学校有 权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和 借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、 保密口， 本论文属于 不保 密 团 。 缩印或扫描等复制手段保存和汇编本学位论文。 在一 一 一 一年解密后适用本授权书。 ( 请在以上方框内打 “d ) 学 位 论 文 作 者 签 名 : ? it- ft 日 期 : 户 作 歹月/ a 日 指导教师签名: 日 期: a 0 0 刁 年 华 中 科 技 大 学 硕 士 学 位 论 文 1 绪论 1 . 1 课题背景 随着电 子技术得迅速发展， 特别是随着大规模集成电 路产生而出 现的 微型计算机 给人类生活带来了 根本性的改变。 如果说微型机的出 现使 现代科学研究得到了 质的飞 跃， 那么可以毫不夸张的说， 嵌入式微控制器技术的出现则是给现代工业控制领域带 来了一次新的技术革命。在微型计算机中微处理器是现代信息技术的 “ 心脏” ，微处 理 器主要分为通用式和嵌入式两大 类1 1 由 嵌入式微控制器组成的系统， 最明显的优势就是可以嵌入到任何微型或小型仪 器、设备中。 嵌入式系统则被定义为:以应用为中心，以 计算机技术为基础， 软件硬 件可裁剪，适应应用系统，对功能、可靠性、 成本、 体积、功耗严格要求的专用计算 机系统12 ,3 1嵌入式系统是将先进的计算机技术、 半导体技术、 电 子技术和各个行业的 具 体 应 用 相结 合 后的 产物 【4 ,5 1 嵌入式系统是面向用户、 面向产品、 面向 应用的， 如果独立于应用自 行发展，则 会失去市场。嵌入式处理器的功耗、体积、成本、可靠性、速度、 处理能力、电磁兼 容性等方面均受到应用要求的 制约16 1 。和通用计算机不同，嵌入式系统的 硬件和软件 都必须高效率地设计， 量体裁衣、去除冗余。 力争在同样的硅片面积上实现更高的性 能， 对芯片配置进行裁剪和添加才能达到理想的性能， 这样才能在具体应用对处理器 的选择面前更具有竞争力， 】 . 嵌入式系统的未来将向多媒体化和网络化方向 发展，特别是与i n t e r n e t 和无线网 络的结合。由于国外厂商都是以开发实时内核为主的，因此所开发的嵌入式 t c p / i p ( t r a n s m i s s io n c o n t r o l p r o t o c o l/ i n t e m e t p r o to c o l ) 网 络组 件 往 往都 是以自 己 以 前 所 开 发 的实时 操作系统为平台， 其网 络产品属于一种增值的开发8 1 。 为适应嵌入式分布处理 和上网需求， 面向二十一世纪的嵌入式系统要求配备标准的一种或多种网络通信接口 9 ,1 0 。 针对外部联网 要求， 嵌入式设备必须配备以 太网网口 ， 相应需要t c p / i p 协议软 件支持。 可以预言，嵌入式设备与i n t e r n e t 的结合代表着嵌入式系统和网络技术的真 正 未 来 11 ,12 1 华 中 科 技 大 学 硕 士 学 位 论 文 传统的t c p / i p协议在实时性方面做得不够好，而是把大量的精力花在保证数据 传送的可靠性以 及数据流量的控制上。 而在实时性要求比较高的嵌入式领域， 传统的 t c p / i p 并 不能 满足 其实时 要 求1 3 - 1 5 1 。 另外 传统t c p j i p 的实 现 过于复杂， 需占 用大量 系统资源，而嵌入式应用的系统资源往往都很有限。因此，需要把传统t c p / i p在不 违背协议标准的前提下加以改进实现， 使其实时性得到提高，占用的存储空间尽可能 少，从而满足嵌入式应用的要求。 1 .2 国内外发展现状 以信息家电为代表的互联网时代嵌入式产品，不仅为嵌入式市场展现了美好前 景， 注入了 新的生命。同时也对嵌入式系统技术， 特别是软件技术提出新的挑战。 这 主要包括:实时操作系统的发展， 支持日 趋增长的功能密度、灵活的网络联接， 轻便 的 移动应用和多媒体的信息处理【 1 6 ,1 7 1 1 . 2 . 1 实时操作系统发展概况 在嵌入式微处理器的应用开发中，嵌入式实时操作系统或 r t o s ( r e a l t i m e o p e r a t i o n s y s t e m ) 是核心软件。 就像日 常所用计算机的桌面系统中， 微软公司的视窗 操作系统一样重要。 从 一九 八 一 年r e a l s y s te m发 展了 世 界 上 第 一 个 商 业 嵌 入式 实时 内 核， 到 今 天已 经已 有二十多年的历史【 1 8 1 。 二十世纪八十年代的产品 还只支持一些1 6 位的 微处理器， 如6 8 k , 8 0 8 6 等2 9 ,2 0 。 这时 候的r t o s 还只有内 核，以 销售二进制 代码为 主。 产品 主 要用于军事和电信设备。 进入二十世纪九十年代， 微内 核设计技术和模块化设计思想 开 始渗 入r t o s 领域2 1 - 2 3 1 。 二十 世纪 九十年代中 期， 互联网 之 风在北 美日 渐风行。 网 络设备制造商、终端产品制造商都要求r t o s 有网络和图形界面的功能。 这个时期代 表 性 的 产 品 有v x w o r k , q n x , l y n x 和w i n c e 等 2 4 ,2 5 1 进入二十世纪九十年代后期， 开放源码之风己 波及r t o s 厂家， 并且新的处理器 越来越多，r t o s自 身结构的设计更易于移植，r t o s在嵌入式系统设计中的主导地 位已 经 确定 2 2 8 1 。 后p c ( p e r s o n a l c o m p u t e r ) 时 代 更 多 的 产品 使 用r t o s ， 它 们 对 实 时性要求并不高，如手持设备等。 微软公司的w i n c e , p l a m o s , j a v a o s 等r t o s 产品 就是顺应这些应用而开发出 来的 ! 2 9 ,3 0 1嵌入式l i n u x 已 经在消费电 子设 备中 得到 华 中 科 技 大 学 硕 士 学 位 论 文 应用， 韩国 和日 本的一些企业都推出了基于嵌入式l i n u x的手持设备。嵌入式l i n u x 也 得到了 相当 广 泛的 半导 体 厂 商的 支 持 和 投资 ， 如i n t e l 和m o t o r o la 3 1 ,3 2 1 . 目 前，国外商品化的嵌入式实时操作系统己进入我国市场的有 win d r iv e r . m ic r o s o ft . q n x 和n u c le a r 等 产品 13 3 ,3 4 1 。 在 过 去的 几 年中 ， 中 国 的 一 些国 家 研究 机构 和企业已 经在开发自 有知识产权的r t o s ，或在开放源码的l i n u x 基础上发展自己的 嵌入l i n u x 版本。国产r t o s 的市场主要集中在消费电子方面，因为这里有许多国 外 r t o s不能适应的部分，如中文处理。目 前主要产品有:中 科院系统的。 女娟， ，英文 是 ”o p e n :中 科院 红 旗l i n u x ; 深 圳蓝点l in u x 13 s 。目 前 这 些r t o s 市 场占 有率 还 很 低。 1 .2 . 2 嵌入式设备联网方式研究状况 近年来，国际上学术界已 意识到互联网不能停留在信息管理这种单一层面， 而必 须 深入 到 控 制 领域 及家 庭之中 ， 所以 美国 著 名的网 络 公司 埃 施朗公 司 提出 了 “ b r in g i n g t h e i n t e r n e t t o li f e ，即“ 把互联网带入生活中”的口 号13 6 1 。 九十年代中 后期，美国、 欧洲、日 本、 加拿大等国家和地区己对信息家电上网都进行了 各种研究和开发，并已 形成热潮，但尚未成熟。国内也有少数家电厂家对信息家电上网进行了研究和开发， 还仅仅处于起步阶段。 当今国际上一些著名的嵌入式操作系统供应商， 都在自己 的嵌入式系统产品中集 成了t c p / i p网络组件，以便自己的实时系统具备网络通讯功能。由于是面向嵌入式 应用， 因此这些产品在实时性、 占用存储空间、 可移植性方面都做了各具特色的改进。 ( 1 ) v r t x s a 中的s n x v r t x s a 是m r i ( m i c r o t e c r e s e a r c h i n c .) 开 发的 实 时 操作 系统， s n x是 其中 的 t c p / i p 13 t e s n x不仅体现了 一般网 络的特性， 而且也体现了 其作为实时 操作系统网 络组件的特性。 s n x利用了v r t x s a 超微内核的特性， 在响应速度、 吞吐量上体现了 其实时性。 还采用了 静态分配技术、 非暂停网络通讯方 式、 紧急消息优先处理机制等 措施来保证其实时性13 8 1 ( 2 ) n u c l e u s 中的n e t n u c l e u s 是a c c e l e r a t e d t e c h n o lo g y公司开 发的 实时 操 作系 统， n e t是 其中的 t c p / i p 网 络 组 件 13 9 1 。 它 最大 的 特 点 是引 入了 一 种o d h o p t im iz e d d a t a h a n d l in g ) 机 制， 华 中 科 技 大 学 硕 士 学 位 论 文 去 掉了 传统t c p / i p 协 议栈中 各 层间 不必要的 数 据拷贝， 使 得代 码的 效 率更高 14 0 7 ( 3 ) p s o s 中 的p n a + p s o s 是i s i ( i n t e g r a t e d s y s t e m s , i n c .) 开 发 的 实 时 操 作 系 统 ， p n a + 是 其中 的t c p / i p网 络组件。 它支持用于管理参与多目 传送的计算机群的i g m p ( i n t e r n e t g r o u p m a n a g e m e n t p r o to c o l) 14 1 ,4z 1 o 上述t c p a p网 络组件的 应用主要是嵌 入式领域，因 此对系统的实时性能要求比 较高。这就要求协议栈在实现时对系统响应时间等一系列实时性能指标加以着重考 虑。 都对协议栈内部的数据处理采用了更加高效的 策略。 同时嵌入式网络系统的可剪 裁性方面都具有各自 的 特色， 都向 用户提供系统的剪裁功能14 3 1 1 .3 课题主要研究工作 本文的 研究重点将以一个源码公开的实时嵌入式操作系统u c / o s - i i 为基础， 根据 其内核优先权分配的特点， 对其任务调度算法的函数进行一定的改进， 将任务优先权 调度和时间片轮转在一定程度上作适当的结合。并根据标准 t c p / i p协议，结合实际 系统的大小和应用情况进行适当的裁剪， 嵌入一个基于u c / o s - i i 的网络协议栈。 同时 利用操作系统的进程间通信方法， 设置一些信号量对系统的资源作一定的控制， 在一 定程度上避免 死锁发生的可能。 本课题将主要完成如下工作: ( 1 ) 主要介绍实时嵌入式系统的内核分类以 及任务调度算法。 ( 2 )以u c / o s - 11嵌入式操作系统内 核作为基础， 简要分析操作系统的任务控制 块、 事件控制块结构、 任务调度算法、时钟控制等方面的 系统函数。 ( 3 ) 对实时嵌入式操作系统任务调度算法函 数进行改进，提出 优先权调度算法 和时间片轮转调度算法相互配合的任务调度算法，实现局部进程之间的时间片轮转. ( 4 ) 利用操作系统的进程间通信方法， 在分配存储器缓存的函数中加入了一定 的信号量控制，对全局统一的n b u f 资源进行统一调配，在一定程度上避免死锁发生 的可能。 ( 5 ) 针对u c o s - i i 操作系统的特点， 对标准t c p / i p协议进行裁剪， 给u c o s - i i 增加网络服务功能。 并列出主要的数据结构和数据报处理流程，以及相关的主要系统 函 数，以实现t c p / i p 协议的基 本功能。 华 中 科 技 大 学 硕 士 学 位 论 文 2 实时嵌入式操作系统 实时操作系统中最关键的部分是实时多任务内 核， 它的 基本功能包括任务管理、 定时器管理、 存储器管理、 资源管理、 事件管理、 系统管理、 消息管理、 队列管理等。 这些管理功能是通过内核服务函数形式交给用户调用的， 也就是实时操作系统的a 月。 使用可占先性内核时，所有时间要求苛刻的事件都得到了尽可能快捷、有效的处理。 实时操作系统通过有效的服务， 如信号量、邮箱、消息队列、延时、超时等使资源得 到更好的利用。 2 . 1 特点 实时系统的特点是， 如果逻辑和时序出现偏差将会引起严重的后果。 有两种类型 的实时系统: 软实时和硬实时系统。 硬实时和软实时的区别就在于对外界的事件做出 反应的时间。 硬实时系统必须及时对事件做出反应，绝对不能错过事件处理的最后时 限。 软实时系统是指，如果在系统负荷较重的时候，允许错过事件处理的最后时限而 且不会造成太大的危害。 硬实时系统和软实时系统的区别主要在于选择调度算法的不同。 对软实时系统而 言， 选择基于优先权的调度算法足以 满足系统的需求， 可以实现快速响应和具有更大 的系统吞吐率;而对硬实时系统来说， 通常采用调度方式简单、反应速度快的实时调 度算法。 大多数实时系统是二者的结合， 实时系统的应用涵盖的领域十分广泛，而多 数实时系统又是嵌入式的。为了实现实时系统，就需要引入实时内核的概念。 实时内核也称为实时操作系统。 它的使用使得实时应用程序的设计和扩展变得很 容易， 不需要大的改动就可以 增加新的 功能。 随着嵌入式系统中软件比 重不断上升， 应用程序越来越大， 对开发人员、 应用程序接口、 程序档案的 组织管理成为一个大的 课题。 实时内核的引入相当于引入了 一种新的管理模式， 解决了嵌入式软件开发标准 化的难题， 提高了 开发单位或开发人员对项目 开发的管理水平。 通过将应用程序分割 成若干独立的任务，实时内核使得应用程序的设计过程大为简化。 目 前嵌入式应用领域的一个发展倾向是采用实时多任务操作系统。 随着应用的复 杂化， 一个嵌入式控制器系统可能要处理很多实时任务， 同 时各个任务之间也可能有 - - 一 - - 一 一 - 一 - 一 - 华 中 科 技 大 学 硕 士 学 位 论 文 多种信息传递。 如果仍采用原来的程序设计方法将存在两个问 题: 一是中断可能得不 到及时响应， 处理时间过长， 这对于一些控制场合是不允许的; 二是系统任务多， 要 考虑的 各种可能也多，各种资源如调度不当就会发生死锁，降低软件可靠性。 从性能上讲，实时内核和普通的操作系统的区别主要在于对实时性的要求不一 样。 在实时计算中， 系统的正确性不仅仅依赖于计算的逻辑结果而且依赖于结果产生 的时间。从这个角 度上看， 可以 把实时系统定义成“ 一个能够在指定或者确定的时间 内完成系统功能和对外部或内部、同步或异步时间做出响应的系统，a 嵌入式系统是开发信息电 器在软件系统方面的关键技术。 信息电 器是网 络时代的 产物， 那么对于用来开发信息电器的嵌入式系统来说， 嵌入一个网络协议栈是开发嵌 入式系统必须考虑的问题。 在实时操作系统核心界面上实现网 络协议栈， 通过网 络协议栈提供对嵌入式系统 网络应用程序的接口。因此需要能够处理标准的协议，如 t c p / i p协议以及相应的应 用服务。网络设备也需要有提供安全检测、授权验证的功能。 这些在网络协议栈里面 都需要实现。当然，也增加了嵌入式系统的开发复杂度，提高了开发成本。 如果应用项日 对额外的需求可以承受， 应该考虑使用实时内 核。 这些额外的需求 是:内 核的价格，额外的r o m j r a m开销，以及2 %到4 %的c p u额外负荷。但是实 时内 核通常价格较高，在一些低成本的应用中， 就无法使用实时内核。在网络协议栈 的开发过程中， 通常利用现成的代码， 选用高性能、低价格、稳定的软件平台， 提高 开发效率，尽量降低开发成本。 2 . 2 内核 在多任务系统中，内 核负责管理各个任务，或者说为每个任务分配 c p u时间， 并且负责任务之间的通信。 内核提供的基本服务是任务切换。 之所以使用实时内核可 以 大大简化应用系统的设计， 是因为实时内 核允许将应用分成若干个任务，由实时内 核来管理它们。 内核本身也增加了应用程序的额外负荷， 代码空间增加r o m的用量， 内 核本身的数据结构增加了r a m的用量。 而且更加主要的是， 每个任务要有自己的 栈空间， 这是相当 可观的容量。内 核本身对c p u的占 用时间一般在2 % 到5 % 之间。 实时内 核按c p u控制权的分配方法的不同， 通常分为非抢占 式内 核和抢占 式内 核。 华 中 科 技 大 学 硕 士 学 位 论 文 2 .2 . 1 非抢占 式内 核 非 抢占 式内 核要求每个任务自 我放弃 c p u的 所有权。 非抢占 式调度法也称作合 作型多任务， 各个任务彼此合作共享一个c p u 。 异步事件还是由中断服务来处理， 中 断 服务可以 使一个高 优先级的 任务由 挂起状态变为 就绪状态。 但中断服务完成以 后， 控制权还是回到原来被中断了的 那个任务， 直到该任务主动放弃 c p u的使用权。此 时那个高优先级的任务才能获得c p u的使用权。 非 抢占 式内 核的一个优点是， 几乎不需要使用信号 量来保护共享数据。 运行着的 任务占 有c p u . 而不必担心被别的任务抢占。 但这也不是绝对的， 在某种情况下， 信 号 量还 是 用得到， 如 在处 理共享i / 0 ( i n p u t / o u tp u t ) 设备时 仍 需 要使用 互斥型 信号 量。 非抢占 式内 核如图2 . 1 所示。 非抢占式内核的最大缺陷在于其响应时间。高优先级的任务已经进入就绪态，但 还不能运行，也许要等很长时间， 直到当前运行着的任务释放c p u . 非抢占式内核的 任务级响应时间是不确定的，不知道最高优先级的任务何时能够拿到 c p u控制权， 其 完全取决于 应用程序什么时 候释放c p u 。目 前商业软件中 几乎没有非抢占 式内 核。 低优先级任务 间 !1刁*时 图2 . i 非抢占 式内 核 2 . 2 . 2 抢占 式内核 如果系统对响应时间要求很高，需要使用抢占式内核。 因此， u c l o s - i i 以及绝大 多 数商业上销售的 实时内 核都是抢占 式内 核。 最高 优先级的任务一旦就绪， 总能得到 c p u的 控制权。 当 一个运行着的 任务使一个比它优先级高的任务进入了 就绪态， 当 前 任务的c p u使用权就被剥夺了 ，或者说被挂起了， 那个高 优先级的任务立刻得到了 华 中 科 技 大 学 硕 士 学 位 论 文 c p u的控制权。 如果是中断服务子程序使一个高 优先级的任务进入就绪态， 中断完成 时，中断了的 任务被挂起， 优先级最高的 那个任务开始运行。 抢占 式内 核如图2 . 2 为 所示。 低优先级任务 中断服务子程序 ( 使高优先级任务就绪) 、. . 高 优 先 级 任 务 -时间 图2 . 2 抢占 式内 核 使用抢占式内 核，最高优先级的任务何时可以得到 c p u的控制权是可预知的。 使用抢占式内核使得任务级响应时间得以最优化。 抢占式内核总是让就绪态的高优先级任务先运行，中断服务程序可以抢占c p u , 到中断服务完成时，内核让此时优先级最高的任务运行 ( 不一定是那个被中断了的任 务) 。任务级系统响应时间得到了最优化，而且是可知的。 2 .3 调度 调度是内核的主要职责之一， 它决定该轮到哪个任务运行了。多数实时内核是基 于优先级调度算法的。 每个任务根据其重要程度的不同被赋予一定的优先级。 基于优 先级的调度算法是指， c p u总是让处在就绪态的优先级最高的任务先运行。 然而究竟 在何时让优先级最高的任务掌握 c p u 的使用权，有两种不同的情况，这要看用的是 什么类型的内核，是非抢占式内核还是抢占式内核。 一个良 好的 任务调度算法应该主要体现在以下 几个方面: ( 1 )公平:保证每个进程得到合理的c p u时间; ( 2 )高效:使c p u保持忙碌状态，即在c p u上总有进程在运行; ( 3 )响应时间:使用户交互的响应时间尽可能短; ( 4 ) 周转时间: 使批处理用户等待输出的时间 尽可能短; ( 5 )吞吐量:使单位时间内处理的进程尽可能多。 华 中 科 技 大 学 硕 士 学 位 论 文 很显然， 在任何操作系统中， 这几个目 标不可能同时达到。 不同的 操作系统会在 这几个方面中 做出相应的 取舍，从而确定自己的 调度算法。 常用的任务调度算法有: 先来先服务、短作业优先、优先级、时间片轮转法、多级队列法、多级反馈队列法。 2 .2 . 1 时间片轮转调度算法 当两个或两个以上任务有相同优先级，内核允许一个任务运行事先确定的一段时 间， 然后切换给另一个任务， 这就叫时间片轮转调度算法。内核在满足以 下条件时， 把c p u控制权交给下一个任务就绪态的任务。 c 1 )当前任务已 无事可做; ( 2 )当前任务在时间片还没结束时己 经完成了。 时间片轮转调度算法主要是为分时系统设计的。其中时间片是一个重要的参数， 不能取的过大或过小，通常为1 0 至 l o o m s 数量级。就绪队列可以看成是一个环形队 列， c p u调度程序轮流地把c p u分给就绪队 列中的每个进程，时间长 度为一 个时间 片。l in u x 操作系统就是采用时间片轮转的调度算法。 2 . 2 .2 实时操作系统的任务优先级分配 因为实时系统相当复杂，所以给任务定优先级是不容易的。许多系统中，并非所 有的任务都至关重要， 不重要的任务自 然优先级可以低一些。 实时系统大多综合了软 实时和硬实时这两种需求。软实时系统只是要求任务执行得尽量快， 并不要求在某一 特定时间内完成。硬实时系统中，任务不但要执行无误，还要准时完成。 一 项 有意 思的 技 术 称 之为 单 调 执 行率 调 度 法r m s ( r a te m o n o to n ic s c h e d u l in g ) , 用于分配任务 优先级。 这种方法基于哪个任务执行的次数最频繁， 执行最频繁的任务 优先级最高。 r m s 做了一系列假设: ( 1 ) 所有的任务都是周期性的; c 2 ) 任务间 不需要同步， 没有共享资 源，没有任务间数据交换等问 题: ( 3 ) c p u必须总是执行那个优先级最高且处于就绪态的 任务。 换句话说， 要使 用抢占式调度法。 华 中 科 技 大 学 硕 士 学 位 论 文 给出一系列n 值表示系统中的不同任务数，要使所有的任务满足硬实时条件，必 须使以下不等式成立，这就是r ms 定理。 s n ( 2 1 - 1 ) 尽一不 ，v同 这 里 瓦 是 任 务 i 最 长 执 行 时 间 ， 军 是 任 务 i 的 执 行 周 期 。 换 句 话 说 ， 双 / 不 是 任 务 i 所 需 的c p u 时 间 。 表2 .1 中 给 出 n ( 2 rr - 1 ) 的 值 ， n 是 系 统 中 的 任 务 数 。 对 于 无 穷 多 个任务， 极限 值是1 n 2 或0 .6 9 3 。 这就意味着， 基于r m s , 要任务都满足硬实时 条件， 所有有时间条件要求的 任务i 总的c p u时间 应小于7 0 %! 注意， 这里是指有时间条件 要求的任务，系统中当然还可以有对时间没有什么要求的任务，使得 c p u的利用率 达到1 0 0 % 。使c p u利用率达到1 0 0 % 并不好，因为那样的话程序就没有了 修改的余 地，也没法增加新功能了。作为系统设计的一条原则，c p u利用率应小于7 0 %. 表2 . 1 基于任务的c p u最高允许使用率 任务数 n ( 2 一 1 ) 1 1 . 0 0 0 2 0 . 8 2 8 3 0 . 7 7 9 4 0 . 7 5 6 5 0 . 7 4 3 a s 0 . 6 9 3 2 .4 本章小结 本章主要介绍了 实时嵌入式操作系统的特点， 以 及一些常见的进程调度算法和进 程的优先级分配方法等内 容。这些是本文的理论基础，为后文作了一定的铺垫。 华 中 科 技 大 学 硕 士 学 位 论 文 3 u c / o s - ii嵌入式操作系统 u c / o s - n是一个源代码公开的抢占式内 核的实时嵌入式操作系统， 它提供了实时 系统所需的基本功能。其包含全部功能的核心部分代码只占 用 8 .3 k字节，而且由 于 u c / o s - ii是可裁剪的，所以用户系统中实际的代码最少可达2 . 7 k字节，非常短小精 悍。 u c / o s - ii 实际上是一个实时操作系统内 核， 只包含了任务调度、 任务管 理、时间 管理、内 存管理和任务间的通信与同步等基本功能。 没有提供输入输出管理、 文件系 统、 网 络之类的额外服务。 但是由于u 。o s - ii的可移植性和开源性， 用户可以自己 添 加所需的各种服务。 3 . 1 任务控制块基本结构 在 操 作系 统中， 一 旦 建 立 任务， 任务 控 制 块o s jc b ( t a s k c o n tr o l b lo c k ) 将 被 赋值。任务控制块是一个数据结构，当任务的c p u使用权被剥夺时，u c / o s - 1 1 用它 来保存该任务的状态。当任务重新得到 c p u使用权时， 任务控制块会确保任务从中 断的那一点丝毫不差地执行下去。任务控制块驻留在系统的r a m中，任务建立的时 候，任务控制块就被初始化。以下为u c / o s - ii任务控制块中的主要成员变量: ( 1 ) o s t c b s t k p t r 是指向当前任务栈顶的指针。 u c / o s - ii允许每个任务有自己 的栈， 并且每个任务的栈的容量可以是任意的。 有些商业内核要求所有任务栈的容量 都一样，除非用户写一个复杂的接口函数改变它。这种限制浪费了r a m，当 各任务 需要的栈空间不同时，也必须按任务中预计的最大栈空间来分配栈空间。 ( 2 ) o s t c b s t k b o t t o m时指向 任务栈底的指针。 如果微处理器的栈指针是 递减的， 即 栈存储器从高 地址向 低地址方向 分配， 则o s t c b s t k b o t t o m指向 任务使用的 栈空间 的最低地址。类似地，如果微处理器的栈是从低地址向高地址递增型的，则 o s t c b s t k b o t t o m指向任务可以使用的栈空间的最高地址。 ( 3 ) o s t c b s t k s i z e 存有 栈中 可 容纳的 指针 元数日 而不 是 用字节 表示的 栈容 量总 数， 也就是说， 如果栈中 可以 保存1 0 0 0 个入口 地址， 每个地址的宽度是3 2 位的， 则 实际容量是4 0 0 0 字节。同样是 1 0 0 0个入口 地址，如果每个地址宽度是 1 6位的，则 总栈容量有2 0 0 0 字节。 华 中 科 技 大 学 硕 士 学 位 论 文 ( 4 ) o s t c b n e x t 和o s t c b p r e v 用于任务控制块o s t c b s 的双重链接， 该链表 在时 钟 节 拍函 数中 使 用， 用 于 刷新 各 个 任务的 任务 延 迟 变量o s t c b d l y ， 每 个 任 务的 任务 控 制 块o s se t c b 在 任务 建 立的 时 候 被 链 接到 链 表中， 在 任 务 删除 的 时 候 从 链 表中 被删除。双重链接的链表使得任一成员都能被快速插入或者删除。 ( 5 ) o s t c b e v e n t p t r 是指向事件控制块的指针. ( 6 ) o s t c b m s g 是 指向 传 给 任务 的 消 息的 指 针 ( 7 ) o s t c b d l y当需要 把任务延时若干时钟节拍时要用到这个变量， 或者需要 把任务挂起一段时间以 等待某事件的发生， 这种等待是有超时限制的。 在这种情况下， 这个变量保存的是任务在等待时间发生过程中允许挂起的最多时钟节拍数。 如果这个 变量为0 ， 表示任务不延时， 或者表示等待事件发生的时间没有限制。 ( 8 ) o s t c b s t a t 是任务的 状态字。当o s t c b s t a t 为0 ， 任务进入就绪态。 可以 给o s t c b s t a t 赋其它的值以 表示任务的其它状态。 ( 9 ) o s t c b p r i o 是任务优先级。高优先级任务的o s t c b p r i 。 值小。也就是说， 这个值越小，任务的优先级越高。 ( 1 0 ) o s t c b x , o s t c b y , o s t c b b i t x , o s t c b b i t y用于加速任务进入就绪 态的过程或进入等待事件发生状态的过程。 u c / o s - i i 最多可以 管理6 4 个任务， 这个数也是u c / o s - i i 分配给用户程序的任务 控 制 块o s 份 t c b s 的 最 大数目 。 所 有的 任 务 控制 块 都 是 放 在 一 个任 务 控 制块 列 表 数 组 o s t c b t h l 日 中 的。 在u c / o s - i i 初 始 化的 时 候， 如图3 .1 所 示， 所 有 任务 控 制 块o s t c b s 被链接成空任务控制块的单向链表。当任务一旦建立，空任务控制块指针 o s t c b f r e e l i s t 指向的 任务控制块便赋给了该任务，然后o s t c b f r e e l i s t 的值调整为 指向下链表中下一个空的任务控制块， 一旦任务被删除， 它的任务控制块就会回到空 任务控制块链表中。 图3 . 1 空 任务链表 华 中 科 技 大 学 硕 士 学 位 论 文 3 .2 优先权调度管理方法 u