（计算机软件与理论专业论文）osek操作系统调度机制研究.pdf

摘要 摘要 o s e k 操作系统标准是针对汽车电子领域嵌入式系统制定的工业标准，在汽 车工业界有着广泛的应用。 调度是多任务系统正确运行的保证，而o s e k 操作系统作为硬实时系统， 其调度有着特殊的需求，因此研究o s e k 操作系统的调度是o s e k 操作系统设 计中最为核心的部分。 本文主要针对o s e k 操作系统调度机制进行研究。主要包括以下两个方面： 1 ) 0 s e k 操作系统调度机制分析及实现 本文深入分析o s e k 操作系统标准，给出满足0 s e k 操作系统支持优先级 天花板协议的固定优先级任务调度机制的实现方法。 ( 1 ) 将o s e k 任务调度分为三个部分：判断何时发生调度、查找最高优先 级就绪任务以及任务切换机制； ( 2 ) 通过分析o s e k 操作系统的重调度点j 解决了o s e k 操作系统何时才 会发生重调度的问题； ( 3 ) 根据0 s e k 操作系统就绪队列的特性，提出了0 s e k 操作系统中优就 绪任务优先级队列的实现方法： ( 4 ) 通过分析o s e k 操作系统任务特征以及任务切换机制，提出了针对 o s e k 操作系统的任务堆栈优化方法。 2 ) o s e k 应用任务集可调度性分析 实时系统调度分析理论中，需要考虑每个任务的最坏情况响应时间是否满 足其时间约束，本文通过对o s e k 操作系统中的任务调度简化抽象，首先给出 了不考虑系统开销的任务最坏情况响应时间计算方法以及任务集可行性条件， 分析给出0 s e k 操作系统任务调度的一些本质特性。 本文根据0 s e k 应用，提出了o s e k 操作系统调度相关的六种系统开销： 激活任务、终止任务、时钟滴答、切换开销、获取资源以及释放资源。在不考 虑系统开销的调度分析基础上，加入了对这些系统开销的分析，进一步精确了 考虑系统开销的0 s e k 应用任务集中任务的最坏情况响应时间的计算方法，并 提出了考虑系统开销的情况下，o s e k 应用任务集调度可行性的充分条件，最 后通过实验对比了不考虑系统开销的任务最坏情况响应时间、考虑系统开销的 任务最坏情况响应时间二者理论值以及实际系统运行的任务响应时间。 关键词：o s e k 操作系统实时系统调度算法调度分析理论 i a b s t r a c t a b s t r a c t o s e k o p e r a t i n gs y s t e ms t a i l d a r di sa ni n d u s t r i a ls t a l l d a r df o ra u t o m o t i v e e m b e d d e ds y s t e m ，a n dt h e r ea r em a n ya p p l i c a t i o n sf o ro s e ks t a l l d a r d s s c h e d u i i n gi st h ev e r ) ri m p o r t a n tp a r i i lm u l t i t a s ks y s t e m s o s e ko p e r a t i n g s y s t e m sa r eh a r dr e a l t i m es y s t e m s ；也es c h e d u l i n gm e c h a n i s mh a ss p e c i a ld e m a n d f o ro s e k o p e r a t i n gs y s t e m s s ot h er e s e a r c ho fo s e ko p e r a t i n gs y s t e ms c h e d u l i n g i sk e yp a r t0 fo s e ko p e r a t i n gs y s t e md e s i g n 1 1 1 i sp a p e ri sf o c u so n 也er e s e a r c ho fo s e ko p e r a t i n gs y s t e ms c h e d m i n g m e c h a n i s m t h e r ea r em a i n l ya b o u tt 、op a r t s ： 1 ) o s e ko p e r a t i n gs y s t e ms c h e d u l i n gm e c h a n i s ma n a l y z ea n di m p l e m e n t t h i sp a p e r ，d e e p l ya n a l y z e st h eo s e ko p e r a t i n gs y s t e ms t a ：n d a r d s ，p r e s e n t st h e e s s e n c eo fo s e ko p e r a t i n gs y s t e ms c h e d u l i n gm e c h a n i s m 一一丘x e dp r i o r i t y s c h e d u l i n g w i t ho s e k p r i o r i t yc e i l i n gp r o t o c 0 1s u p p o r t ， a n d g i v e t h e i m p l e m e n t a t i o no fo s e ko p e r a t i n gs y s t e ms c h e d u l i n gm e c h a n i s m ( 1 ) t h i sp a p e r d i v i d eo s e kt a s ks c h e d u l i n gi n t ot h r e ep a n ：d e t e 肌i n e 、v h e nt o s c h e d u l e 、f i n d 也er e a d yt a s kw i t hh i 幽e s tp r i o r i t ya n dt h et a s ks w i t c h m e c h a n i s m ： ( 2 ) t 1 1 i sp a p e rs 0 1 v e sd e t e n n i n i n gw h e nm es y s t e m s w i l lr e s c h e d u l eb y a n a l y z i n gt h er e s c h e d u l i n gp o i n to fo s e ko p e r a t i n gs y s t e m ； ( 3 ) t h i sp a p e rp r e s e n t sah i g h l yo p t i m i z a t i o ni m p l e m e n t a t i o nm e t h o do fr e a d y t a s kq u e u eb a s e do nt h ei i e a d yt a s ks p e c i 矗c a t j o ni no s e ko p e r a t j n g s y s t e m s ； ( 4 ) f i n a l l yt h i sp a p e rg i v e sa no p t i m i z a t i o nm e t h o df o ro s e ko p e r a t i n gs y s t e m t a s ks t a c k 1 a s ks t a c ks h a r i n g 2 ) s c h e d u l i n ga n a l y z eo fo s e k 印p l i c a t i q nt a s ks e t b a s e do nt h em o d e ms c h e d u l i n ga n a l y z et h e o r y ，t h i sp a p e rp r e s e n t st h e s c h e d u l i n ga n a l y z em e t h o d sf o ro s e ka p p l i c a t i o nt a s ks e t w i t ho s e ko p e r a t i n g s y s t e mc h a r a c t e r i z e w 色g i v et h eo s e ka p p l i c a c i o nt a s km o d e la n dh y p o t h e s i su n d e r o u rm o d e l ；p r e s e n tt h ec a l c u l a t i n gm e t l l o do fw o r s tc a s er e s p o n s et i m ef o rt a s k si n o s e ka p p l i c a t i o nt a s ks e ti g n o r i n gt h es y s t e mo v e r h e a d s ；f i n a l l yp r o v et h ef e a s i b l e s c h e d u l i n gc o n d i t i o nf o ro s e ka p p l i c a t i o nt a s k a c c o r d i n gt ot h eo s e ka p p l i c a t i o n s ，w ep r e s e n ts i xs y s t e mo v e r h e a d sr e l a t e dt o o s e k o p e r a t i n gs y s t e ms c h e d u l i n g ：a c t i v et a s ko v e r h e a d 、t e n n i n a t et a s ko v e r h e a d 、 t t 摘要 t i c kt i m eo v e r h e a d 、s w i t c h i n go v e r h e a d 、g e ta n dr e l e a s er e s o u r c eo v e r h e a d w ba d d t h ec o n s i d e m t i o no ft h e s es y s t e mo v e r h e a d su n d e rt 1 1 ef b n n e rs c h e d u l i n ga n a l y z e m e m o d m o r e o v e r 、v eg i v et h ec a l c u l a t i n gm e m o do fw o r s tc a s er e s p o n s et i m ef o r t a s k si no s e k 印p l i c a t i o nt a s ks e tw i t ht h e s es y s t e mo v e r h e a d s ，a l s op r e s e n tt h e f e a s i b l es c h e d u l i n gc o n d i t i o nf o r0 s e ka p p l i c a t i o nt a s ks e t f i n a l l yw ec o m p a r et h e w o r s tc a s er e s p o n s et i m ei g n o r i n gs y s t e mo v e r h e a d s 、w o r s tc a s er e s p o n s et i m ew i t h s y s t e mo v e r h e a d sa n dt h ea c t u a lr e s p o n s et i m ei nt r 锄p o l i n es y s t e ma 1 1 dg i v et h e c o n c h l s i o n k e y w o r d s ：o s e ko p e r a t i n gs y s t e m ，r e a lt i m es y s t e m s ，s c h e d u l i n ga l g o r i t h m ，s c h e d u l n g a n a l y z et h e 0 拶 。i i i 插图目录 插图目录 图2 1t r a m p o l i n e 原优先级队列结构图2 4 图3 1 扩展任务状态转换图2 6 图3 2 基本任务状态转换图2 6 图3 3 优先级反转示意图2 7 图3 4 优先级天花板协议示意图2 8 图3 5 空就绪任务队列：3 0 图3 6 多次激活就绪任务队列3 0 图3 7 资源优先级就绪任务队列31 图3 8 实时系统任务结构图3 3 v i i 表格目录 表格目录 表1 1o s e k 操作系统一致类1 0 表3 1 扩展任务状态及其转换2 6 表3 2 扩展任务状态及其转换2 7 表3 3t r 锄p o l i n e 原调度算法下a c t i v e 协k 的执行时间3 6 表3 4 新调度算法下a c t i v e t a s k 的执行时间3 6 表4 1 测试任务集数据5 2 表4 2 系统开销最坏情况运行时间 5 2 表4 3 任务最坏情况响应时间理论与实验值对比。5 2 v i i i 中国科学技术大学学位论文原创性和授权使用声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工 作所取得的成果。除已特别加以标注和致谢的地方外，论文中不包 含任何他人已经发表或撰写过的研究成果。与我一同工作的同志对 本研究所做的贡献均已在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权，即： 学校有权按有关规定向国家有关部门或机构送交论文的复印件和电 子版，允许论文被查阅和借阅，可以将学位论文编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 文。 保密的学位论文在解密后也遵守此规定。 作者签名：2 塾! ：叁 7 而年 月1 日 绪论 1 1 背景介绍 1 1 1o s e k 标准简介 第1 章绪论 随着汽车安全、环保、舒适和经济等性能要求的不断提高，汽车电控单元 ( e l e c t r o n i cc o n t r o lu n i t ，e c u ) 的数量越来越多，其复杂性也急剧上升。大量e c u 的使用和复杂的控制程序给汽车制造商带来了巨大的成本压力，因此，开发经 济、高效的e c u 内存和处理器资源的操作系统已变得十分迫切。传统的实时操 作系统太大，功能过多，己难以适应e c u 数量大而内存小的现代汽车控制系统。 为满足日益庞大复杂的汽车电子控制软件的开发需要，实现应用软件的可 移植性和不同厂商的控制模块间的可兼容性，德国汽车工业协会于1 9 9 3 年提出 0 s e k 标准( 德语“汽车电子设备开放式构架及其接口规范”的简称) ，旨在建立一 个用于汽车电子分布式控制系统的开放式结构体系，1 9 9 4 年法国汽车电子规范 v d x ( v e h i c l ed i s t r i b u t e de x e c u t i v e ) 并入o s e k 标准。o s e k 标准更名为 o s e k d x ( 本文简称o s e k ) ，并在1 9 9 5 年发布了它的第一个正式版本。目 前o s e k 标准已经加入i s o 国际标准。 o s e k 标准包含o s ( o s e k 操作系统标准) 1 ，2 ，3 】、c o m ( o s e k 通信服务标 准) 【4 】、n m ( o s e k 网络管理标准) 5 】以及0 i l ( o s e k 实现语言标准) 6 等部分， 对汽车电子控制软件的开发平台作了较为全面的定义与规定。 o s e k 标准发布至今，国外著名汽车制造商如：宝马、博世、戴姆勒一奔驰、 欧宝、西门子、大众、标致和雷诺等，其产品中使用的嵌入式操作系统均支持 o s e k 标准。 1 1 1o s e k 操作系统标准 o s e k 操作系统标准 1 ，2 ，3 】旨在为汽车控制单元的应用程序提供一个高效 利用资源的统一平台。o s e k 操作系统是一种单处理器的操作系统，用于分布 式e c u ( 电子控制单元) 。o s e k 应用中所有对象均是静态的，它们在应用程序 启动之前就已经创建，并且启动后不会被删除。 o s e k 操作系统具有可配置性、可移植性、标准化接口、实时性以及可靠性 等特点。0 s e k 操作系统标准要求操作系统具有任务管理、资源管理、时钟管 9 绪论 理、中断管理和错误处理等功能，并且操作系统给处理器带来的负担不应超过 5 ，操作系统的代码应高度优化以减少内存消耗量。 1 1 1 1 任务管理 o s e k 操作系统标准提供了两种不同的任务类型：基本任务和扩展任务。一 方面，基本任务是不会被阻塞的顺序代码。其同步点只在任务的开始和结束时， 基本任务只在任务终止、内核切换到更高优先级的任务时或中断时释放处理器； 另一方面，扩展任务可以看作是由可导致等待状态的操作系统服务分隔开的若 干代码段。扩展任务与基本任务相比，引入了等待状态，扩展任务可以阻塞自 身进入等待状态，直到某个事件发生再进入就绪状态。而事件的触发可以通过 任务或者中断来设置，等待事件并不会超时，也就是说，扩展任务可以无限期 的阻塞自己。任务执行结束后进入挂起状态，处于该状态的任务可以被再次激 活。o s e k 操作系统中，管理扩展任务比管理基本任务开销更大。o s e k 操作 系统中的任务在系统生成时静态创建。 1 1 1 2 一致类 o s e k 操作系统标准中的一致类定义了四种实时内核的版本，用来满足不同 的应用需求。它们由三种主要属性来区别：任务类型、对基本任务的多次激活 请求的记录以及每个优先级对应的任务数。这四个一致类分别是b c c l 、b c c 2 、 e c c l 和e c c 2 ，如表1 1 所示 表1 1o s e k 操作系统一致类 一致类 b c c lb c c 2e c c le c c 2 基本任务的多次不支持支持 不支持 支持 激活请求 任务类型基本基本扩展基本扩展基本 每个优先级是否否是否是 对应多个任务 非挂起状态任务 881 61 6 数 每个任务事件数无 无88 任务优先级数 881 61 6 资源数调度器 888 显然，b c c 2 和e c c 2 一致类中，需要支持对基本任务的多次激活，每个优 先级可能与多个任务对应，调度行为更为复杂。而e c c l 和e c c 2 一致类中， 需要对扩展任务以及事件机制提供支持。 l o 绪论 1 1 1 3 调度策略 任务的优先级由用户通过o i l 文件静态指定，采用“最高优先级就绪任务 最先运行 的策略，而在b c c 2 和e c c 2 中，由于每个优先级可能有多个任务， 相同优先级的任务需要按照f i f o 原则来进行调度。 o s e k 操作系统中支持四种调度策略： 1 ) 完全可抢占调度 ， 该调度策略下，在任务的任何位置都可能发生重调度，只要有更高优先 级的任务就绪，就会抢占当前任务运行。完全可抢占调度策略下系统用于 保存任务上下文的开销最大，任务需同步访问共享资源，系统复杂度最大。 2 ) 无抢占调度 无抢占调度策略下，通过用户通过系统服务设置重调度点，基本任务一 旦运行就会一直运行直到其运行结束，而扩展任务可能进入等待状态。 3 ) 混合抢占调度 可抢占任务和非抢占任务共存于一个系统中时，使用混合抢占调度策 略，系统调度依赖于正在运行的任务的抢占特性。如果当前运行的任务是 非抢占的，其它任务只有在该任务结束或者进入等待状态时才能运行；如 果当前运行的任务是可抢占的，执行可抢占调度策略。 如果应用中包含较长运行时间的并行任务，选择可抢占调度更为合适： 而应用中包含较多短执行时间的任务时，无抢占调度更适合，为了实现性 能和效率的折衷，可以使用混合抢占调度策略。 4 ) 任务组 通过任务组，o s e k 操作系统能使多个任务同时具有可抢占和无抢占调 度特性。如果任务的优先级等于或者小于某组中优先级最高的任务，那么 该任务对于组中的任务是不可抢占的。反之，组中的任务是可抢占的。 o s e k 应用开发者，通过配置任务优先级以及抢占属性来定义任务执行顺 序，o s e k 操作系统的任务类型独立于调度策略。 1 1 1 4 任务同步 任务同步( 扩展任务) 是基于私有事件机制：只有事件的拥有者才能等待该事 件的发生。设置事件可以通过任务或者i s r ( 中断处理例程) 完成，等待事件不会 超时。 事件只用于扩展任务，传递二进制信息，其具体含义通过应用决定。事件 是扩展任务从等待状态进入就绪状态的标志。o s e k 操作系统不允许拥有资源 的扩展任务进入等待状态。 绪论 1 1 1 5 资源管理 资源管理用于协调优先级不同的任务和中断服务例程对资源进行并发访 问。共享资源包括：调度程序、程序代码、内存或硬件资源等。所谓资源，就 是临界区，o s e k 操作系统禁止访问共享资源时进入等待状态，同时也禁止对 同一资源的嵌套访问。协调任务和中断时，o s e k 操作系统需确保所有需要的 资源均释放后，才执行中断服务例程。 o s e k 操作系统标准规定了对共享资源的并发访问机制o s e k p c p ( 优 先级天花板) 协议，也称作i p c p ( 立即优先级天花板协议) 。当一个任务获取一个 资源后，该任务的优先级立即提升到资源的优先级，资源的优先级等于共享该 资源的任务中的最高优先级。这样，就可以避免优先级反转的问题。 由于资源共享允许发生在任务和中断服务例程之间或者中断服务例程之 间，需要为每个中断分配一个虚拟的优先级来实现扩展到中断级的o s e k p c p 协议。在系统初始化阶段，根据来自o i l 配置的先验知识，为每一资源静态分 配天花板优先级。 1 1 1 6 中断管理 o s e k 操作系统中，将中断服务例程分为两类：第一类中断，不使用0 s e k 系统调用的中断服务例程。中断结束后，处理器从被中断的指令处继续运行， 即第一类中断对任务调度没有影响。此类中断系统开销最小。而第二类中断， 操作系统需要提供中断服务例程处理框架，为其提供运行环境，系统初始化时， 需要将第二类中断处理例程注册到相应中断。 o s e k 操作系统不允许第二类中断执行中进入调度内核。即使在第二类中断 中激活了某任务，也要在退出中断后，再去执行调度。 1 1 1 7 警报和计数器 警报和计数器管理周期性任务以及看门狗定时器，用来监测各种情况( 等待 事件发生、发送接收消息等) 。警报用于处理周期性事件，这些事件可以来自定 期提供中断的定时器，也可以来自其它定期感应的传感器。 计数器用一个计数值表示，按系统滴答频率计数，警报需要与具体的计数 器相关联。当警报相关计数器达到了警报预设的值时，警报可以有三种行为： 激活相关任务、设置相关任务的事件或者执行回调函数。警报可以设置成一次 性或者周期性的以满足不同应用要求，多个警报可以依附于同一计数器。 1 1 1 8 通信 o s e k 操作系统中，任务之间通过消息实现通信。消息是应用数据的容器， 1 2 绪论 只是一个发送者，但可以有多个接收者。消息类型在系统创建时定义，不能在 运行时增加和删除消息。 o s e k 操作系统中有两类消息：可排队消息和不可排队消息。前者是静态长 度消息，可以被消息接收程序移走，实现时使用f i f o 队列来管理；不可排队 消息类似黑板模式，即消息不断刷新，不能被消息接收程序移走。 1 1 1 9 错误处理 o s e k 操作系统提供了系统专用钩子程序，以便在操作系统内部操作时执行 用户定义的函数。特点是：依赖于操作系统实现，在特定现场被操作系统调用； 比所有任务的优先级都高；不能被第二类中断服务例程中断；是操作系统的一 部分；接口被标准化，但功能( 包括执行环境和处理程序的行为) 没有被标准 化。钩子程序通常是不可移植的，为了减小系统复杂性，只允许使用系统服务 例程的一个子集。 钩子程序可用于：系统启动，相应钩子程序在操作系统启动后，进入调度 程序之前执行；系统关闭，相应钩子程序在应用或操作系统( 此时发生严重错 误) 请求系统停止运行时执行；跟踪，调试应用以及现场切换时调用用户定义 的扩展程序；错误处理。 1 1 1 1 0o s e k 执行语言 o s e k 执行语言( o i l ) 2 ，3 ，6 】主要是配置在特定处理器上的o s e k 应用程 序。所有的o s e k 系统对象都在o i l 文件中定义，包括任务优先级、资源优先 级等信息。通过用户定义o i l 文件，整个o s e k 操作系统是完全静态配置的。 1 1 2o s e k 操作系统任务调度 o s e k 操作系统标准只定义了调度策略，并且规定了o s e k 操作系统中的 调度选择当前优先级最高的任务运行，任务的当前优先级通过任务的基本优先 级以及此刻用户的资源优先级共同决定。该标准并未提出如何实现o s e k 操作 系统的调度机制，因此实现o s e k 操作系统调度机制是本文的研究目标之一。 o s e k 操作系统标准中规定了任务的基本优先级由用户静态指定，用户可能 为不同的应用设计不同的任务集，用户需要关注自己设计的任务集能否满足应 用的时间限制，而在实际应用中验证需时较长、成本要求较高，因此通过对 o s e k 操作系统调度机制进行理论分析，计算每个任务的最坏情况响应时间， 判断该时间是否满足最终期限要求，是本文的另一研究目标。 1 3 绪论 1 2 现有o s e k 操作系统 o s e k 操作系统主要应用于汽车电子领域，目前己知的支持o s e k 操作系 统的标准大多是商业系统。德国3 s o r 公司从1 9 9 6 开始开发o s e k 操作系统， 1 9 9 7 年发布了第一个商业化的o s e k 操作系统p r 0 0 s e k l 。0 ，已经为b m w 提 供了基于0 s e k 的软件开发平台，为v w a u d i 开发了o s e k 软件开发平台， 同时为d a i m l e r c l y s l e r 提供了首个基于o s e k 项目的软件平台，此外提供了各 种硬件平台的b 0 0 t l o a d e r 、h i s 实现 7 】。f r e e s c a l e 公司开发的o s e k t u r b o 是目 前市场上使用最为广泛的o s e k 操作系统之一【8 】。德国v e c t o r 公司开发了具有 c a n o p e n 协议栈的o s e k 操作系统o s c a n ，支持多处理器以及不同的c a n 通 信协议。此外德国的e t a s 公司、英国的l i v e d e v i c e s 公司开发了支持o s e k 标 准的嵌入式产品r 1 队o s e k 【9 ，1 0 】。美国w i n d 黜v e r 公司也在其产品v x w 6 r k s 的基础上扩展开发了0 s e k w b r k s 以支持o s e k 标准【1 1 】。 目前国内也有许多基于o s e k 标准的嵌入式操作系统。北京西曼公司与清 华大学智能技术与系统实验室合作，自主研发了支持o s e k 标准的嵌入式操作 系统p o w e r o s e k 1 0 】。浙江大学嵌入式系统工程中心也自主研发了面向汽车电 控领域的嵌入式软件开发平台s m a n q s e k 【1 3 ，1 4 ，1 5 】。 相关的研究论文中，大多是对已有的嵌入式操作系统例如m i c u m 、l i n u x 等进行扩展，以支持0 s e k 标准 1 6 ，1 7 ，1 8 ，1 9 ，2 0 ，2 1 ，2 2 】。 而在开源嵌入式操作系统领域，o p e n o s e k 2 3 】和t r a m p o l i n e 【2 4 】均为基于 o s e k 标准的嵌入式操作系统。其中o p e n o s e k 并未发布成熟运行版本， t r 锄p o l i n e 已经可以在多个平台上运行。 t r 锄p o l i n e 嵌入式操作系统的设计出发点是良好的平台移植性以及低内存 消耗，整体可分为三个部分： 1 ) g o i l ：o i l 解析器。以o i l 文件为输入文件，生成系统配置相关的头文 件( 与平台相关) 。目前支持i n f i n e o nc 1 6 7 、p o w e r p c 以及x 8 6 平台。 2 ) p e r ：虚拟处理器仿真器( n u a lp r o c e s s o re r n u l a t o r ) 。用于在类u n i x 平台之上对目标平台进行仿真，p e r 监控定时器、中断以及警报，通 过共享内存以及异步p o s i x 信号与o s e k 进程通信。 3 ) k e m e l ：o s e k 内核。支持e c c 2 和b c c 2 一致类中的标准中规定的系 统调用。 在已有系统上对o s e l d x 进行扩展的系统仅仅是部分支持0 s e k 标准， 并且其调度算法并非针对o s e k 操作系统专门设计，可能带来不必要的开销。 而t r 锄p o l i n e 是专门针对o s e k 标准设计的嵌入式实时操作系统，平台移植性 好、内存消耗较低，但是其调度开销可能随着任务增多而加剧。 1 4 绪论 1 3 论文的主要工作 本文主要针对o s e k 操作系统调度机制进行研究。主要包括以下两个方面： 1 ) o s e k 操作系统调度机制分析及实现 本文在深入分析o s e k 操作系统标准的基础上，结合实时系统调度机制现 有研究，分析了o s e k 操作系统调度机制的实质支持优先级天花板协议的 固定优先级调度，进而提出了满足o s e k 特殊需求的调度机制的实现方法。将 o s e k 任务调度分为三个部分：判断何时发生调度、查找最高优先级就绪任务 以及任务切换机制。通过分析o s e k 操作系统的重调度点，解决了o s e k 操作 系统何时才会发生重调度的问题；根据o s e k 操作系统就绪队列的特性，提出 了针对o s e k 操作系统的高度优化的就绪任务队列的实现方法；通过分析o s e k 操作系统任务特征以及任务切换机制，提出了针对o s e k 操作系统的任务堆栈 优化方法。在t r 锄p o l i n e 原有算法的基础上实现了本文提出的算法，对二者运 行时间进行对比分析。 2 ) o s e k 应用任务集可调度性分析 本文在实时现有调度分析理论的基础上，结合o s e k 操作系统特征，提出 了针对o s e k 应用任务集的调度分析方法，给出了0 s e k 应用任务模型，并在 该模型基础上做出相关假定，给出了不考虑系统开销情况下o s e k 应用任务集 中任务的最坏情况响应时间的计算方法，进一步提出了o s e k 应用任务集调度 可行性的充分条件。 根据o s e k 应用，提出了o s e k 操作系统调度相关的六种系统开销：激活 任务、终止任务、时钟滴答、切换开销、获取资源以及释放资源。在不考虑系 统开销的调度分析基础上，加入了对这些系统开销的分析，进一步给出了考虑 系统开销的o s e k 应用任务集中任务的最坏情况响应时间的计算方法，并提出 了考虑系统开销的情况下，o s e k 应用任务集调度可行性的充分条件，最后通 过实验对比了不考虑系统开销的任务最坏情况响应时间、考虑系统开销的任务 最坏情况响应时间二者理论值以及实际系统运行的任务响应时间。 本文工作的创新点在于： 1 ) 目前已有的o s e k 操作系统绝大多数均为商业系统，本文在深入分析 o s e k 操作系统的调度机制基础上，给出一种更适合o s e k 操作系统的 调度实现方案。 2 ) 已有的调度分析理论主要针对通用的调度策略，本文在此基础上，提出 了针对0 s e k 应用任务集的调度分析方法。 1 5 绪论 1 4 论文组织结构 本文绪论主要对o s e k 相关标准进行介绍，并针对o s e k 操作系统中任务 调度的问题加以分析，提出了本文需要解决的问题。 本文第二章介绍了多任务系统的分类，分析不同类别多任务系统的调度需 求，介绍了相关调度算法，着重介绍了实时系统中调度所受的约束，以及实时 系统中的常用调度方法。 本文第三章是o s e k 操作系统任务调度机制，首先介绍了o s e k 操作系统 中的任务概念，在此基础上分析了o s e k 操作系统中的任务调度机制，给出适 合0 s e k 操作系统的调度算法及其实现，从调度角度分析并给出了对任务堆栈 的优化方法。在第三章结尾，通过实验验证本文提出的调度算法。 本文第四章对o s e k 应用进行调度分析，首先提出了o s e k 操作系统中的 任务模型以及相关概念假设，在此基础上对o s e k 应用任务集进行调度分析， 进而在分析基础上加入对系统开销的考虑，最后通过实验对比了不考虑系统开 销的任务最坏情况响应时间、考虑系统开销的任务最坏情况响应时间二者理论 值以及实际系统运行的任务响应时间。 文章最后总结全文，并对进一步工作进行展望。 1 6 操作系统中的任务调度 第2 。章操作系统中的任务调度 通常操作系统中的调度可以分为交互式操作系统调度、多处理器调度以及 实时调度三类。调度算法需要考虑系统多个方面的需求，不可能使这些需求都 达到最优，例如，提供较好的响应时间可能需要调度算法在任务间频繁的切换， 增加了系统开销，降低了吞吐量。因此，设计一个调度算法需要在互相竞争的 各个条件之间进行折衷，根据系统的本质和使用情况，给各种要求设定相对权 值。 2 1 背景介绍 操作系统中必须为多个任务可能有竞争的请求分配计算机资源。对处理器 而言，可分配的资源是在处理器上的执行时间，分配的途径是任务调度。调度 功能必须设计成可以满足多个目标，包括公平、任何进程都不会饿死、有效的 使用处理器时间和低开销。此外，调度功能可能需要为某些进程的启动或者结 束考虑不同优先级和实时最终期限。 近年来，调度已经成为深入研究的焦点，并且已经实现了许多不同的算法。 选择函数确定在就绪进程中选择哪一个在下一次运行，该函数可以是基于优先 级、资源需求或者任务的执行特性。调度模式通常可分为：可抢占与不可抢占 的 6 】。 不可抢占型内核要求每个任务自我放弃处理器的所有权。不可抢占型调度 法也称作合作型多任务，各个任务彼此合作共享一个处理器。异步事件还是由 中断服务来处理。中断服务可以使一个高优先级的任务由挂起状态变为就绪状 态。但中断服务以后控制权还是回到原来被中断了的那个任务，直到该任务主 动放弃处理器的使用权时不可剥夺型内核的最大缺陷在于其响应时间。高优先 级的任务已经进入就绪态，但还不能运行，要等，也许要等很长时间，直到当 前运行着的任务释放处理器。不可抢占型内核的优点是响应中断快、几乎不需 要使用信号量保护共享数据。不可抢占型内核的任务响应时间是不确定的，不 知道什么时候最高优先级的任务才能拿到处理器的控制权，完全取决于应用程 序什么时候释放处理器。，那个高优先级的任务才能获得处理器的使用权。 当系统响应时间很重要时，要使用可抢占型内核。因此，绝大多数商业上 销售的实时内核都是可抢占型内核。最高优先级的任务一旦就绪，总能得到处 理器的控制权。当一个运行着的任务使一个比它优先级高的任务进入了就绪态， 】7 操作系统中的任务调度 当前任务的处理器使用权就被剥夺了，或者说被挂起了，那个高优先级的任务 立刻得到了处理器的控制权。如果是中断服务子程序使一个高优先级的任务进 入就绪态，中断完成时，中断了的任务被挂起，优先级高的那个任务开始运行。 使用可剥夺型内核，最高优先级的任务什么时候可以执行，可以得到处理器的 控制权是可知的。使用可抢占型内核使得任务响应时间得以最优化。使用可抢 占型内核时，应用程序不应直接使用不可重入型函数。调用不可重入型函数时， 要满足互斥条件，这一点可以用互斥型信号量来实现。如果调用不可重入型函 数时，低优先级的任务处理器的使用权被高优先级任务抢占，不可重入型函数 中的数据有可能被破坏。综上所述，可抢占型内核总是让就绪态的高优先级的 任务先运行，中断服务程序可以抢占处理器，到中断服务完成时，内核选择此 时优先级最高的任务运行( 不一定是那个被中断了的任务) 。任务系统响应时间 得到了最优化，且是可知的。 2 1 1 交互式操作系统中的调度 交互式操作系统中，通常为单处理器，任务之间共享一个处理器，处理器 通过执行某个任务而保持忙状态，而此时其它任务处于等待状态。交互式操作 系统中，由于需要与用户进行交互，需要为用户提供适当的响应时间，考虑用 户使用的需求。常见的交互式操作系统中的调度算法有以下几类 2 5 】： 1 ) 先来先服务( f c f s ) 也称作先进先出( f i f o ) ，当每个任务就绪后，加入就绪队列，当前任务 停止运行时，选择就绪队列中最早的任务运行。 2 ) 时间片 以固定的时间间隔周期性产生时钟中断，当中断发生时，当前任务被置 于就绪状态，然后基于f i f 0 选择下一个就绪任务运行。 3 ) 最短任务优先 最短任务优先属于不可抢占调度，其原则是选择所需时间最短的任务， 可能导致长任务被饿死的情况。 4 ) 最短剩余时间 调度程序总是选择预期剩余时间最短的任务，可能导致长任务被饿死的 情况。 5 ) 反馈队列 当一个任务第一次进入系统中时，将其放在最高优先级的队列中，在随 后时间，每当它被抢占时，就被降级到下一个低优先级的队列中。队列内 使用f i f o 来选择任务。 1 8 操作系统中的任务调度 可以看出，交互式系统需要考虑用户与系统之间的交互，需要平衡各个任 务的公平执行，对运行时间要求不是很高。 2 1 2 多处理器调度 当一个计算机系统中包含多个处理器时，在设计调度功能时就会产生一些 新的问题，主要包括以下两个方面 2 5 】： 1 ) 任务分配到处理器 通常系统维护一个公共队列，任务就绪时加入该队列，然后调度选 择到可用的处理器上运行。 2 】任务的实际分派 任务被分配到具体的处理器后，问题就变成了该任务在单处理器系 统中的调度。 多处理器调度中，通常将任务划分为一组线程，这些线程可以在同一地址 空间内协作和并发的执行，线程调度常用的几种方法有： 1 ) 负载分配 任务不是分配到一个特定的处理器，而是维护一个就绪任务的全局 队列，每个处理器只要空闲就从队列中选择一个任务。 2 ) 成组调度 一组相关的线程基于一对一的原则，同时调度到一组处理器上运 行。 3 ) 专用处理器分配 与负载分配方法相反，它通过把线程指定到处理器来定义隐式的调 度。在任务执行过程中，每个任务被分配给一组处理器，处理器的数目 与任务中线程数目相等。当任务终止时，处理器返回到总的处理器池中， 可供分配给另一个任务。 4 ) 动态调度 在执行过程中，任务内线程数目可变。 显然，多处理器系统中，会对多个处理器间的协同工作以及负载平衡予以 较多考虑。 2 1 3 实时调度 实时系统中的调度根据实时性要求分为硬实时调度和软实时调度。其中硬 实时调度是所有的任务必须在其最终期限内完成，而软实时调度允许有部分延 1 9 操作系统中的任务调度 迟。任务调度算法设计的好坏直接决定了实时系统能否成功运行，实时系统中 的任务调度算法必须是高度优化、高效、对资源占用尽可能少的。实时系统中 任务的另一个特征就可以是周期的也可以是非周期的。实时系统的设计目标是 尽可能快速的启动实时任务，因此强调快速中断处理和任务分派。通常，实时 系统中的任务调度可以分为三个部分：离线配置、运行时分派以及优先级分析 【2 6 】。 离线配置主要用来为系统运行生成静态配置信息。在某些调度方法中，配 置信息由表组成，这些表指示了哪个任务将被运行以及何时运行。而在另一类 调度算法中，这些离线配置信息非常少，甚至没有，调度器使用实时信息( 如最 终期限) 来选择哪个任务将被运行。 运行时分派用来处理计算系统运行中不同事务所发生的切换。绝大多数的 调度方法都是基于处理器上的任务系统。实时调度算法通过当前系统信息( 例如 当前系统时间) 以及离线配置信息( 例如任务优先级) 来确定何时发生任务切换。 任务切换有两种策略：可抢占的和不可抢占的。可抢占切换需要停止当前正在 运行的任务，切换到另外的任务，后面需要再切换回被中止的任务继续执行。 而不可抢占中断中，任务一旦开始运行，就需要等待其运行结束才能继续运行 其它任务。 运行时的调度算法并不能保证所有的任务都能在其最终期限内完成，而优 先级分析主要是在系统运行前分析是否能满足时间要求。分析需要清楚的知道 离线配置信息以及运行时调度算法的具体行为。当优先级分析得出调度可行的 结论时，所有最终期限条件都满足，此时称该分析是必要的。而当优先级分析 得出调度不可行时，必定有某个任务的最终期限不会被满足，称该分析是充分 的。同时满足充分和必要的分析称为严格的。近三十年来，调度分析理论不断 发展，针对固