控制工程专业毕业论文设计-周期性互换的实时多任务调度方法研究.docx

分类号_ 密级_U D C_硕士学位论文周期性互换的实时多任务调度方法研究 研 究 生 姓 名 王 聪 指导教师姓名、职称 王 彬（副教授） 学 科 专 业 控制工程 研 究 方 向 实时系统多任务调度算法 论 文 工 作 起 止 日 期 2012年3月至2013年3月 论 文 提 交 日 期 2013年3月26日 Error! No text of specified style in document.昆明理工大学学位论文原创性声明本人郑重声明：所呈交的学位论文，是本人在导师的指导下或我个人进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不含任何其他个人或集体已经发表或撰写过的研究成果。对本文的研究做出重要贡献的个人和集体，均已在论文中作了明确的说明并表示了谢意。本声明的法律结果由本人承担。 学位论文作者签名： 日 期： 年 月 日关于论文使用授权的说明本人完全了解昆明理工大学有关保留、使用学位论文的规定，即：学校有权保留、送交论文的复印件，允许论文被查阅，学校可以公布论文的全部或部分内容，可以采用影印或其他复制手段保存论文。（保密论文在解密后应遵守）导 师 签 名： 论文作者签名： 日 期： 年 月 日57周期性互换的实时多任务调度方法研究摘要近年来，随着数字化和智能化程度的提高，微处理器被引进到电子领域的各个行业。一般来讲，凡是带有微处理器的电子系统，都可以统称为嵌入式系统。由于一个系统中集成的功能越来越多，因而需要微处理器处理的任务也随之增加。这就引进了单个微处理器对多任务的调度问题。多任务调度问题不仅在嵌入式行业，在通用处理平台上也存在，并且更早。多任务调度从实时性上划分，分为实时调度和非实时调度；从调度算法上划分为动态调度和静态调度。实时调度一般是基于抢占式优先级来调度任务，不同的任务分配不同的优先级，从而实现高优先级任务优先执行。非实时调度一般是按照时间片轮转法进行多任务调度，每个任务的执行几率是相同的。动态调度算法是通过预先设定的某一指标对所有就绪任务进行衡量，满足条件的任务优先执行。由于该指标所依赖的参数是不断变化的，所以满足条件的任务也是不断变更的。这样就实现了对任务的动态调度。静态调度算法也是通过预先设定的某一指标对当前所有就绪任务进行衡量，满足条件的任务优先执行。但是和动态调度算法不同的是该指标所依赖的参数是固定的或者人为的设定的，不会在任务执行过程中发生变化，所以是静态调度。本文研究实时系统多任务调度中低优先级任务的延迟问题。由于低优先级任务总是要等到高优先级任务的执行间隙才能得到执行，所以研究低优先级任务的延迟问题很有必要。这关系到底优先级任务的实时性。通过研究，本文的重点放在实时系统采用静态调度算法进行多任务调度时的低优先级任务的实时性研究。本文提出了一种优先级周期性互换的任务调度算法，来解决低优先级任务的实时性问题。通过Ptolemy II仿真软件对优先级周期性互换任务调度算法进行仿真，得出仿真结果并进行分析。最后，以实际控制系统的响应曲线图来验证优先级周期性互换算法对低优先级任务的实时性的提高有很大的改进。关键字：多任务调度；优先级周期性互换；实时系统；Ptolemy IIAbstractIn recent years, with the improvement in the level of digital and intelligent, microprocessor was introduced to various industries in the field of electronics. In general, any electronic system with a microprocessor, can be collectively referred to as embedded systems. As more and more integrated in a system increases, thus the need for a microprocessor to handle the task. This is the introduction of a single microprocessor to multi-task scheduling problem.Multi-task scheduling problem, not only in the embedded industry, there are also general purpose processing platform and earlier. Multi-task scheduling from the real-time performance on a divided, divided into real-time scheduling and non-real-time scheduling; scheduling algorithm is divided into dynamic scheduling and static scheduling. The real-time scheduling preemptive priority-based scheduling tasks, different tasks assigned different priority, in order to achieve a high-priority task execution priority. The non-real-time scheduling rotation method according to the time slice of the multi-task scheduling, the probability of each execution of the task is the same. The dynamic scheduling algorithm is all ready tasks through a pre-set indicators to measure to meet the conditions of the task execution priority. Since the indicator depends on the parameters are constantly changing, so that satisfy the condition task is constantly changed. This dynamic scheduling of tasks. Static scheduling algorithm is also through a pre-set indicators to measure the current all ready tasks to meet the conditions of task execution priority. And dynamic scheduling algorithm is different indicators dependent parameters are fixed or artificially set, will not change in the task execution process, and so is static scheduling.In this paper, real-time multi-task scheduling low priority task latency issues. As a low-priority task is always to wait until the implementation of high-priority task execution gap to get, so study the low-priority task latency issues is necessary. This relationship in the end the real-time nature of the priority tasks. Through research, the article focuses on real-time systems using static scheduling algorithm for multi-task scheduling, real-time low-priority task. This paper proposes a priority periodic swap task scheduling algorithm, to solve real-time problems of low-priority tasks. The theoretical analysis of the algorithm and demonstration priority periodic exchange of task scheduling algorithm, and by Ptolemy II simulation software simulation, simulation results derived algorithm. A great improvement verify priority cyclical interchangeable algorithm response curves of the actual control system to improve real-time low-priority task.Keyword目录摘要IABSTRACTII第一章绪论11引言11.1嵌入式实时系统11.2国内外研究现状及分析51.3课题来源71.4本文组织结构7第二章嵌入式实时系统任务调度机制92.1嵌入式实时操作系统92.1.1实时操作系统相关术语92.1.2嵌入式实时操作系统特点112.1.3实时任务及其特性122.1.4实时任务间的相关性132.2多任务调度算法策略研究132.2.1时间片轮转法142.2.2先来先服务调度算法152.2.3单调速率任务调度算法152.2.4期限最近者优先调度算法182.2.5经典调度策略的局限性18第三章 基于角色的PTOLEMY II实时仿真平台研究213.1 Ptolemy II域的研究分析213.1.1离散事件域223.1.2连续时间域233.1.3时间多任务域243.1.4其它计算域253.2常用角色（actor）分析介绍283.3 Ptolemy II使用简介31第四章优先级周期性互换调度算法的验证374.1优先级周期性互换任务调度算法374.1.1优先级周期性互换任务调度算法分析374.1.2使用Ptolemy II软件仿真384.2 优先级周期性互换任务调度算法应用级仿真414.3实验总结44第五章总结与展望475.1 总结475.2 进一步的研究48致谢51参考文献53附录A（攻读硕士期间发表的论文）57第一章 绪论1引言随着信息时代发展和进步，特别是进入二十世纪以来，大量的电子产品纷纷涌现出来，充斥在每个人生活的方方面面。目前这些电子产品与过去有个明显的区别就是有内嵌微处理器，也就是常说的嵌入式系统。嵌入式系统给人们生活带来了很大的方便，小到手机、智能电视、机顶盒等，大到汽车、飞机、火车、导弹、火箭等等，都嵌入了微处理器来实现智能控制或者调节。在以上列举出来的系统中像手机、智能电视、机顶盒之类的嵌入式系统，它们在使用过程中，对于任务触发的响应没有严格的时限要求，因而它们们属于嵌入式非实时系统；而对于导弹、火箭之类的嵌入式系统就对于任务触发的响应有严格的时限要求，它们则属于嵌入式实时系统。例如在汽车的安全气囊防护系统1 (Supplemental Inflatable Restraint System，简称SRS)。当车速50公里/时进行正面撞车时，其发生时间只有十分之一秒左右。由于作用时间太短，它对嵌入式实时系统的实时性要求就更为明显。据计算，正规的安全气囊必须在发生汽车碰撞后的0.01秒内微处理器开始工作，0.03秒内点火装置启动，0.05秒内高压气体进入气囊，0.08秒内气囊向外膨胀，0.11秒内气囊完全胀大，此刻之后，驾车者才会撞上气囊。由此例可见，“0.01秒”就是嵌入式实时系统对任务触发时的响应时间；“0.03秒”就是该任务的执行时间。这两个任务的时限特别重要，一旦时限错失将会带来灾难性后果。1.1嵌入式实时系统实时系统更注重“实时”概念，实质上就是将提交到系统内部的信息及时进行处理并迅速输出结果2-5。至于“及时”如何界定，这就取决于外部任务对系统的要求，是实时系统中一项最重要的衡量系统实时性的指标。目前对实时系统的定义可以描述为：系统在响应任务请求后，其结果的正确取决于如下两个方面：第一、一般概念下处理任务逻辑的正确；第二、产生任务结果的时效6-10。实时系统的特点要求也适用于嵌入式实时系统。实时概念自提出以来，实时技术随着嵌入式实时系统向安防系统、工业控制系统、机器人控制系统等方向的发展，其自身的研究和应用取得很大的突破和发展。主要是体现在实时系统的核心问题上：多任务调度算法。许多专家和学者都在探索多任务调度算法方面研究出了一批经典算法，提出了很多行之有效的调度方法11-17。嵌入式实时系统并非局限的就认为是一个嵌入式实时操作系统的内核，当然嵌入式实时操作系统在实时系统中占据着极其重要的地位。作为一个具有完整功能的系统来看，一般分为软件和硬件两部分（见图1.1）。软件部分的核心是实时操作系统（主要是内核）和服务于实时任务的应用程序；硬件包括微处理器、存储器及I/O端口和外设器件等。高速运行的外围设备是信号采集和传输的重要保障；实时操作系统则是在多任务的运行环境中按照特定的调度算法找出当前最需要执行的任务运行并将结果通过硬件接口输出。应用程序实时操作系统中央处理器应用程序接口硬件接口通用I/O存储器图1.1 嵌入式实时系统构架嵌入式系统的软件核心是实时操作系统(RTOS：Real Time Operation System)。通常情况下，实时系统中的任务数总是大于硬件处理器的数目。这就需要一种机制将系统中的多个任务按照既定的调度方法来占有处理器资源，使得在有限的资源条件下尽可能多的及时处理多个任务。这就需要实时操作系统来参与调度多个任务进行执行，一方面能使得各个任务自动的及时有序的执行；另一方面也充分利用了处理器等资源。当前市面上出现了一批应用广泛的专注于嵌入式行业的实时操作系统，主要有uC/OS-III，VxWorks，WinCE，QNX和RT-Linux五类主流嵌入式操作系统。需要注意的是，以上这五类主流嵌入式实时操作系统都需要付费才可以投入到产品中进行应用开发。虽然需要收费，但是可以获得全面专业的技术支持，这在产品开发中至关重要。提高产品研发工作效率，加快新产品的上市和更新换代。与之相反，开源Linux实时操作系统可以随意获得，但是它对开发者要求很高，需要开发人员自己解决所有问题。如果需要专家的协助，同样是要花费巨额资金。作为学习人员，可以免费在uC/OS官网上获得当前最新uC/OS-III源码，并有针对多个平台的一致用例供学习参考。几种流行实时操作系统的简介如下：VxWorks实时操作系统：该实时操作系统是美国风河公司在上世纪八十年代出品的。风河公司专门定制了一套Tornado开发环境，便于用户对VxWorks的开发。有一点需要指出的是，美国在1996年12月4日发射升空，于1997年7月4日登陆到火星表面的“索杰纳”机器人车辆的多任务调度系统使用的就是VxWorks操作系统18-19。VxWorks最显著的特点：生成代码容量小，内核易裁剪，实时性强，特别适合嵌入式多任务系统的要求。它在出现短短几年内，由于开发环境友好，支持平台多，性能出众等特点，在嵌入式行业就成了首选的操作系统。QNX实时操作系统QNX名称来源于Quick UNIX，缩写为QNX。由加拿大Quantum Software Systems（QNX）公司的创始人Gordon Bell和Dan Dodge在上世纪八十年代编写的，主要市场就是嵌入式行业。QNX是一种遵从POSIX规范的类UNIX操作系统。QNX的应用从民用的汽车多媒体、平板电脑到军用的核反应堆、无人驾驶控制系统。QNX实时操作系统只提供进程调度、进程间通信、网络通信和中断处理等最基本的系统服务，所以它的代码只有12Kb左右。这个特点也被称之为微内核操作系统。QNX嵌入式实时操作系统应用最为成功的地方在于车载多媒体和网络通信行业的高端路由。RT-Linux实时操作系统RT-Linux是real time linux的简称。由Fsmlabs公司对现有Linux操作系统的的少量改动20而成的一种兼容性很强的实时操作系统。显然，RT-Linux操作系统可以充分利用当下普通Linux平台上的资源。该特点决定了RT-Linux的开发方法简单易学，并有大量的现有开发经验可供借鉴。RTLinux已经成功应用于航天飞机的空间数据采集、科学仪器测控到电影特技图像处理等领域。目前，RTLinux有一个由社区支持的免费版本，称为RTLinux Free，以及一个来自FSMLabs的商业版本，称作RTLinux Pro。uC/OS-III实时操作系统uC/OS-III是uC/OS操作系统的第三版，它是由Jean J.Labrosse开发编写的。他将开发出来的uC/OS源码公开，揭开了实时操作系统的内核运作机制。让更多的人了解到实时操作系统的内核，并出现了一批专门研究研究人员对uC/OS现有调度策略的基础上进行算法改进。由此而引起了巨大的轰动。它的大部分源码遵守ANSIC标准，并且针对不同行业的C代码编写规范也在兼容部分行业标准，如汽车行业MISRA C针对C代码的编写规范。uC/OS在平台间移植有很明显的优势，只需将与处理器有关的汇编代码进行改写，就基本完成移植工作21-22。操作系统中的各个模块，如消息队列、信号量、邮箱和事件等，都可以依据具体情况通过宏定义进行裁剪。WinCE实时操作系统WindowsCE是精简的Windows 95。微软公司专门为智能嵌入式设备而开发的一款实时操作系统23，是微软在嵌入式平台的基础。为了适应嵌入式环境，WinCE的内部结构也是模块化设计，可以根据实际情况进行裁剪。WinCE来源于大家最熟知的Windows操作系统，目前内部已经集成了大约五百个Win32 API函数，并且提供和PC机环境相当的桌面环境。所以它的使用和开发基本和通用Windows环境下开发流程类似。嵌入式实时系统的关键在于多任务调度算法，因为不同的调度算法会对实时性造成一定影响。目前在嵌入式实时系统中主要采用优先级驱动调度算法，这类算法分为静态优先级调度算法和动态优先级调度算法。嵌入式系统硬件部分的核心是嵌入式微处理器。嵌入式微处理器一般具备以下特点：一、 为了实现及时响应和处理，内核对多任务的调度算法和任务间切换时间以及对应于处理实时任务的应用程序的时间降到最低程度，需要处理器有较高的运行频率和很短的中断响应时间，以提高对实时多任务的支持能力。二、 便于嵌入式系统对实时操作系统的裁剪，实时操作系统已将软件构成特别是驱动和进程间通信机制高度模块化。该特点需要硬件有较强的存储区保护功能，便于软件模块之间正常工作、互不干扰，也利于软件本身的测试。三、 同嵌入式实时操作系统的模块化构成一样，硬件处理器也需要可裁剪功能，以便功能的升级和产品的换代。对硬件的这一需求，市场上流行的FPGA就可以完全满足这一特点要求。四、 微控制器的最大特点是单片化，高度集成了外设模块，提高了系统的可靠性。另一方面，特别在便携式电子设备中使用的移动电源，所以要求微处理器功耗极低。功耗在W到mW之间。1.2国内外研究现状及分析任务调度在操作系统中的地位尤为重要，所以目前针对任务调度所采用的算法已经取得的很多成果。下面主要介绍对于周期任务调度算法：时间片轮转法是分时系统中一种常用任务调度策略，它将系统时间划分成等长多个时间片段，给每个任务分配一小片系统时间逐一执行。这种算法在表面上看起来是最公平的算法，可是它不利于重要任务的优先执行。单调速率调度算法24是针对周期任务进行调度的基于优先级调度算法。任务的优先级取决于周期任务的周期，周期越短，优先级就越高。如果采用单调速率多任务调度算法，需要根据任务集的特性判定可调度性。截止期单调调度算法是在单调速率调度算法的基础上发展起来的基于优先级多任务调度算法。该算法分配给任务的优先级是按照任务的截止时间来进行分配的。截止时间越短的任务优先级就越高，反之任务的优先级就越低。和单调速率调度算法一样，它也对被调度任务进行可调度分析。最早截止期优先调度算法是一种截止期驱动的动态可抢占优先级实时调度算法。该算法是通过确定操作系统不断地判断任务的截止期而进行动态优先级分配，即任务的时限与当前时刻的距离越近，优先级就越高，反则优先级越低。最小空闲时间优先调度算法是通过计算任务的截止时间和剩余执行时间之差对任务的优先级进行动态分配。其差值越小，系统分配给任务的优先级就越高，反则优先级就越低25。主流静态优先级调度算法有单调速率任务调度算法，截止期单调调度算法等，截止期单调算法已被证明是静态最优算法。动态优先级调度算法有最早截止期优先算法，最小空闲时间优先，其中期限最近者优先调度算法是一种最优的单处理器动态调度算法。主流实时系统中任务调度算法的优缺点如下：表1 静态优先级和动态优先级之间优缺点比较算法类别优点缺点静态优先级调度算法系统开销小低优先级别的任务延迟大动态优先级调度算法调度灵活系统开销大，易出现调度颠簸现象针对上述两类算法存在的问题提出一种调度策略优先级周期性互换，以满足系统开销小，任务调度相对灵活。其详细情况将在第二章介绍。由于本文对于优先级周期性互换尚处在研究阶段，其可行性采用Ptolemy II仿真验证的方法。一方面减少研究时间，加快项目进度；另一方面通过仿真可以快速发现优先级周期性互换调度算法的可行性，存在的问题等。仿真工具是一种采用某种（软件或者硬件）替代手段来模拟真实环境。仿真软件是从上世纪五十年代随着计算机技术的发展而出现的。仿真软件可以模拟真实环境，使得使用者在不具备真实环境或者不可能具备真实环境的条件下在模拟软件上进行试验。模拟软件的优势是显而易见的，它有成本低，不受地域和时空的限制和灵活性大等特点，从而在当前的数字化领域应用广泛。由于本论文所研究的对象的特点和项目所处的阶段，对于提出的理论需要进行仿真验证，以加快项目研发进度和节约时间成本。本文提出的理论是基于单处理器多任务环境下的任务调度算法。所以需要一个能够模拟单处理器多任务环境的仿真软件，以便对所提出的任务调度算法进行仿真验证。主流仿真软件有Matlab中自带的Simulink26模块、NI（美国国家仪器公司）开发的LabView26、Synopsys的Cocentric Studio27以及Ptolemy28软件等。通过分析和了解，Ptolemy软件在仿真单处理器多任务环境具有明显优势。Ptolemy软件是由Berkeley大学开发的采用面向角色的设计方法进行设计。嵌入式领域的硬件信号特点是多种结构共同，如频域信号、时域信号、模拟信号和离散信号等等；软件特点则是通过划分层次来进行设计，下层给上层提供标准信号，对上层屏蔽底层操作。这种复杂结构在仿真环境中一般比较难以模拟层次间、异构间的信号进行交互，而Ptolemy采用角色设计方法很好的解决了不同结构之间的信号交互，实现了异构系统的模拟仿真。Ptolemy内部自带有单处理器多任务调度模块，直接可以进行任务调度的算法级仿真。本次选择Ptolemy软件进行仿真单处理器多任务调度环境，在此基础上只实现多任务的调度算法。但是本项目是一个标准的嵌入式系统，具有异构性和层次性29，因此上它更适合于整个项目的仿真。优先级周期性互换实时系统任务调度算法的仿真对仿真软件的要求：需要一个基于优先级抢占式的单处理器任务调度模型；该任务调度模型可以和连续时间域的传递函数联合仿真。Ptolemy II的时间多任务可以实现基于优先级抢占式的单处理器任务调度模型，由于Ptolemy II的本身特性，它完全可以支持不同模型之间的异构。1.3课题来源一、国家自然科学基金项目“实时领域交互行为模型转换方法及非功能语义规约研究”（项目编号61263017）二、云南省自然科学基金项目“基于实时语义模型的模型转换及语义一致性研究”（项目编号2011FZ060）1.4本文组织结构本文研究嵌入式实时系统多任务调度策略。本文的重点是学习Ptolemy II仿真软件，分析当前实时系统多任务调度算法，提出一种改进的多任务调度方法优先级周期性互换，以及该方法的使用条件，并用仿真软件Ptolemy II对该方法进行仿真验证。第一章 介绍实时系统的应用范围、实时操作系统种类；常用任务调度算法；并简要介绍Ptolemy II仿真软件在任务调度方面的仿真优势。第二章 对当前多任务实时系统的任务调度方法进行分析，并通过仿真软件Ptolemy II进行实例分析，总结优缺点。第三章 研究Ptolemy II仿真软件异构仿真原理和组件功能，重点分析任务调度方面的优势及使用方法。第四章 提出周期性任务优先级转化调度算法的适用条件，并通过仿真来验证周期性任务优先级转化的可行性。使用Ptolemy II软件将周期性任务优先级转化调度算法融合到实际系统中进行仿真验证。第五章 总结优先级周期性互换调度算法，针对存在的问题，提出下一阶段的工作任务。第二章 嵌入式实时系统任务调度机制2.1嵌入式实时操作系统嵌入式实时操作系统是针对于嵌入式系统而专门“定制”的一类实时操作系统的统称。按照嵌入式系统对时效性的要求，分为嵌入式实时操作系统和嵌入式非实时操作系统。嵌入式实时操作系统就比如第一章举例的汽车上的安全气囊，它要求安全气囊在规定的时间内打开。这里就包括了两个要素：规定时间内和安全气囊打开。这里的“规定时间内”就是系统对时效性的要求；安全气囊打开就是一般意义上的逻辑结果正确。这两个要素必须同时满足，缺一不可，才能成为“结果”正确。试想，一旦超过这个“规定时间”，即便是安全气囊成功打开，也已经丧失了安全气囊存在的必要性。而对于通常情况下的时效性要求则并非实时系统中的时效性。例如目前最为常见的智能手机，它的内部就有Android操作系统（非实时操作系统），该系统来自于Linux系统的改进。用户经常反映手机反应快慢的问题，看起来好似实时系统中的时效性问题，实则不然。手机中某个程序响应慢，甚至会出现“该应用程序无响应”的提示。出现这种结果，用户最多是不耐烦，但不会出现其他意外。但实时系统对外部激励做出响应一旦错失时间，那就会导致致命性错误。从以上两个例子，可以感性的了解到实时系统和非实时系统的区别。接下来给出实时系统中涉及到的概念，便于后续工作的介绍和论证。2.1.1实时操作系统相关术语同一般操作系统一样，实时操作系统的主要工作仍然是对系统内多任务的调度和对资源的管理。为了详细描述任务在各个时刻所处的状态，下面给出实时系统中所涉及到的概念30。任务：是系统中能够完成某种功能的软件实体，它是系统可以调度的基本单位。为了便于描述任务调度基本单位，下文将用任务来表征调度基本单位。不再使用其他文献中作业的概念。周期任务：指任务按照某个时间段间隔性的出现在系统中的任务。与之对应的是非周期任务。非周期任务出现时间是随机的，不确定的。虽然通常情况下任务大多都是非周期性任务，但由于非周期任务调度算法比较复杂，需要专门对其进行分析。为了便于验证新提出的任务调度算法，本文选取的任务均为周期性任务。以下凡是没有特别说明，所提到的任务均为周期性任务。任务创建：将任务以可执行二进制代码实体加载到内存中。就绪态：任务已具备运行条件，等待CPU空闲。处于就绪态的任务可以是多个。运行态：任务获取CPU资源进行执行。处于运行态的任务只能有一个（在单处理器）。释放时间：任务由其他状态转变为就绪态的那个时刻称为它的释放时间。响应时间：从任务的释放时间，到任务所有功能都完成的时刻，这段时间是任务的相应时间。当任务在执行过程中，由于等待资源而被挂起，从任务的释放时间到任务被挂起这段时间只是响应时间的一部分，因为任务并未完成所有的任务而放弃了CPU。剩余执行时间：响应时间减去任务已经执行了的时间。截止期：任务必须在此时刻之前完成它应该执行的所有功能。若任务的的截止期没有限制，称该任务没有截止期。截止期是一个时间点。空闲时间：就是任务的绝对截止期减去任务的剩余执行时间再减去当前时间。任务的空闲时间是一个时间段概念。相对截止期：作业的响应时间所允许的最大值称为该作业的相对截止期。绝对截止期：它等于作业的释放时间加上其相对截止期。在实时系统中，所有的作业都应该在各自的绝对截止期内完成。最坏执行时间：指任务在执行期间由于各种因素的影响，在最坏的条件（时间延迟）下完成所有功能所耗费的最大执行时间值。该参数主要用于硬实时任务调度系统中的一个重要衡量指标。截止期错失率：是由系统中所有任务在一段时间内未在截止期完成的总数和系统任务总数之间的一种比率。该指标主要用在衡量一种调度算法的优良性。很明显，截止期错失率越低，系统对任务的调度成功率越高，调度算法性能越优良。处理器利用率：就是CPU被任务占用执行时间与总时间的比值。具体的衡量办法是：系统中所有任务的最坏执行时间与对应任务周期的比值之和就是处理器利用率。系统中所采用的任务调度算法应使得处理器的利用率必须小于100%，否则，截止期错失率很高。处理器的利用率越高，所能处理的数据量就越大，效率也越高。2.1.2嵌入式实时操作系统特点由于实时系统的结果取决于运算结果逻辑的正确性和产生结果的时间，这就与一般系统有了如下的显著区别：一、 时间约束性实时系统最明显的特点就是添加了时间的概念，只有在规定时间内产生正确的逻辑才算作最终结果的正确。按照截止时间，实时系统被分为“软实时”系统和“硬实时”系统。“软实时”系统，虽然对结果的时效性有一定的要求，但是如果在某种特殊环境中导致了系统中的实时任务在执行过程中超过了截止时间，却不至于引起严重的后果（涉及到人身财产的损失）。比如监控系统、信息采集系统均属于“软实时”系统。“硬实时”系统对时效性的要求是最为苛刻的，所有的实时任务必须在截止时间以内完成，以免发生关系到人身伤害的致命性后果。比如汽车的安全气囊、航天工业中的对接技术和核控制等领域均属于“硬实时”系统。“软实时”和“硬实时”两类实时操作系统因对实效性的要求不同，所以“软实时”系统的设计要比“硬实时”系统的设计相对简单。若不涉及到人身财产等重大安全事故，一般的实时任务被设计为“软实时”系统便足够。二、 可预测性实时系统中任务必须在截止时间内完成，这就确定了任务的执行是可预测的。实时系统应该对任务的进行时限要求的判断，确定是否可以满足时限要求。实时系统包括软硬件两部分，在软件层面主要涉及到中断响应时间、系统任务切换时间和任务调度时间；在硬件层面主要涉及到I/O口响应时间、存储区的读写和保护相应时间等。只有整个系统的各个环节响应时间是有界的，才可能设计出实时系统。三、 可靠性实时系统的可靠性是显而易见的，整个系统的各个部分都有时间的限制要求，以确保系统的可靠性。但是除了时间上的可靠，因受外界复杂环境的影响（温度、强电磁环境等）需要系统的各个部分都要有较强的健壮性。一个小环节出现问题，都可对整个系统造成不可估量的错误。实时系统为了避免类似情况的发生，一般在系统中都设计了采用静态分析和冗余配置，让系统能在最恶劣的复杂环境中都能正常工作。四、 与外部环境的交互作用性实时系统都是在一定的环境下运行的，外部环境是实时系统的组成部分。比如数据采集系统、各种外部环境的传感器等。外部环境通常是被控子系统，实时系统和外部环境相互作用构成完整的实时系统。实时系统必须在规定时间内对外部请求或异常作出反应，才能保证外部环境和整个系统的正常工作。以上四点特性，属于早期简单实时系统的特点。早期的实时系统主要组成结构如单板机和简单的嵌入式实时系统。这些系统的特点是调度过程相对简单。但是随着系统复杂性的提高和应用范围的扩大，目前实时系统还具有如下新特性：多任务类型包括非周期任务、偶发任务、周期性任务以及非实时任务等多种类型任务混合。短暂的超载特点尽管设计人员在实时系统的设计初期尽可能的满足各项实时指标，但由于总有一些实际环境的不确定性因素会造成超载。比如系统环境的动态变化、应用规模的扩大以及系统元件出现老化等均会造成系统的短暂超载。2.1.3实时任务及其特性任务是系统中能够完成某种功能的软件实体，它是系统可以调度的基本单位。实时任务相较于一般任务多了一个时效性限制，必须在截止期内完成。以下所称任务，除特殊说明外均指实时任务。在实时系统中，按照任务的触发时间特点将任务划分为如下：非周期任务随机到达系统的任务称之为非周期任务。它没有规律可循，触发时间不确定。在仿真环节，非周期任务的触发时间可以通过仿真软件提供的随机数发生器来产生非周期任务的触发时间进行模拟仿真。周期任务按照一个固定的时间间隔重复到达系统的任务称之为周期任务。周期任务的每一次到达系统就称为任务的一个任务实例。在仿真环节，可以通过仿真软件提供的定时器来周期性的产生周期任务的触发时间进行模拟仿真。偶发任务相对于非周期任务，它的触发时间有一个最小时间间隔，但是没有周期性。在仿真环节，可以通过仿真软件提供的随机数发生器和定时器产生最小间隔联合产生偶发任务的触发时间。按照任务在截止时间是否严格完成（超时完成），可以将任务分为：软实时任务允许任务在截止时间内未完成，但超时完成的任务。超时任务产生的结果会随着超时时间的延长有效性逐步下降。准实时任务允许任务在截止时间内为完成，通过超时完成的任务产生的结果将不再有效。软-强实时任务该类型任务一般是周期性任务才可以具备的。软-强实时任务要求周期任务的每次执行实例按照某种规则可以超时运行，这种规则被称为超时分布约束31。如不满足该约束，就会使得系统不稳定。强实时任务在截止时间内必须完成，是实时任务中要求最为严格的一类任务，超时完成就会导致致命性错误。针对于强实时任务的截止时间应该在最坏的条件下所产生的最大相应时间为依据来确定，避免由于特殊情况而导致的系统失效。2.1.4实时任务间的相关性当前环境下的嵌入式实时系统都是多任务系统，有的功能需要多个任务协作才能完成，有的功能只需要单个任务就可完成。实时任务间的相关性对于实时系统的设计至关重要。独立性任务实时系统中某个功能只需要一个实时任务就可完成，不需要和其他任务之间进行交互。这类实时任务在实时系统的设计中最为容易，不要考虑任务间的通信问题。本文在仿真阶段所涉及到的任务均为独立任务，在验证多任务调度算法的时候，只调度独立性任务能直观的显现出调度算法的优劣性。顺序性任务实时系统中一个功能的实现往往需要多个任务的协作才能实现，这多个任务类似于流水线上的工序逐个顺序执行。互斥性任务由于任务间使用的资源具有互斥性而造成的，资源被一个任务占用后其他需要使用该资源的任务均不能获取该资源进行操作，必须等到被目前占用资源的任务释放该资源后其他任务才可获取资源并操作。非抢占式任务实时系统中的任务调度大多都是基于优先级进行调度的，非抢占式任务就是低优先级任务在执行过程中不得被高优先级任务中断，直到低优先级任务执行完或者被挂起释放处理器后其他任务才能占有处理器。抢占式任务低优先级任务在执行过程中允许随时被高优先级任务中断而挂起。实时系统为了实现硬实时任务的严格时限要求，实时操作系统一般采用抢占式优先级调度算法，给硬实时任务赋予高优先级来实现最快的任务响应。2.2多任务调度算法策略研究一般处理器系统中只有单个处理器时，如何在有限的资源下较好地进行系统中多任务的调度，是一个系统性能好坏的重要指标之一。而在多处理器系统中有多个处理器时，如何简单且高效地把系统中的多任务合理的分配给各个处理器，从而发挥多处理器资源丰富、处理速度快的特点。调度策略就是一种解决在任务多，资源少的情况下合理利用资源并有效完成任务的一种方法。放在操作系统中就是定义了如何选择将处于就绪状态的任务提升为执行状态。操作系统就是用来实现在有限资源下调度多任务的功能，每个多任务操作系统都使用了一定的调度策略。而调度策略的好坏直接影响系统的实时性以及CPU的功耗。调度策略的主要指标有CPU利用率以及截至期限丢失率等。一个有效的任务调度应满足如下几个条件：一、每个处理器在任意时刻只分配最多一个任务。二、每个任务在任意时刻最多被分配给一个处理器。三、任务只有被释放后才能被调度。四、基于所用的调度算法，分配给每个任务的处理器时间总和等于其最大或者实际处理器执行时间。五、所有的优先权和资源使用限制得到满足。为了更好的实现嵌入式多任务的控制性能，保证更好的控制效果，本文对目前常用的操作系统中所采用的主流多任务调度策略进行了研究与分析，在此基础上提出了优先级周期性互换的多任务调度算法。2.2.1时间片轮转法时间片轮转法是一种主要用于分时系统中的多任务调度算法，常见于服务器中的多任务调度算法。该算法是最公平、最简单容易实现的调度算法。它的工作原理是将系统处理任务的时间分成等长时间片，并且维护一个任务就绪队列表，按照任务的释放时间进行排队。进入队列最早的任务首先分配时间片执行，如果在给定时间片内任务未执行完，任务就被释放，排列到任务就绪队列表的最后一个位置，原先的第二个任务开始执行，如此往复。如果给定时间内任务已经执行完毕，处理器马上进行切换下个任务进行执行。时间片是分时系统中的一个重要的参数，该参数的确定一般依据系统的处理能力、系统对相应时间的要求和就绪队列中进程数目三个方面进行参考。通常为几十毫秒到几百毫秒数量级，不能取的过大或过小。对于时间片轮转法，很明显一个问题：假定时间片大小为t，某个任务执行完成所需要的执行时间是T。当T/t等于整数时，任务执行及时；当T/t大于t/2时，任务执行也算及时；当T/t小于t/2时，此时任务要完成就必须等到下个执行周期分到的时间片进行执行，显然对于任务有效执行很不利。针对上述问题，显而易见的解决方法就是：当任务的一个时间片用完后，就对该任务的剩余执行时间和时间片进行比较，若任务剩余执行时间大于等于t/2时，就调用下个任务执行；若任务剩余执行时间小于t/2时，就在该时间片后添加和任务剩余执行时间等长的时间段将剩余的任务执行完毕。这样一来就大大减小了任务执行周期，提高了任务执行效率32。2.2.2先来先服务调度算法先来先服务调度算法和通常意义上的排队是一样的。处理器按照任务的释放时间进行排队，建立一个就绪队列表。最先到达的任务最先占用处理器进行执行，不论该任务的执行时间有多长，直到该任务执行完毕或者挂起才释放处理器。处理器加载下个任务进行处理，如此一直执行完所有任务。先来先服务调度算法只需要依赖任务的释放时间进行调度，所以实现比较容易。先来先服务任务调度算法存在以下问题：从形式上看，它的调度策略符合一般的排队模型，比较公平。但是，假如最先到的任务是一个需要长响应时间的任务，后面的任务均是响应时间很短的任务。先来先服务调度算法为了执行一个长响应时间的任务而造成了后面所有短响应时间任务的很大延迟。在这个意义上讲，先来先服务任务调度算法又是不公平的。所以，先来先服务任务调度算法在实际系统中很少单独用，通常的做法都是将先来先服务任务调度算法和其他算法相结合。比如基于优先级任务调度算法中，在相同优先级之间采用先来先服务调度算法。2.2.3单调速率任务调度算法单调速率调度算法被证明是最优静态实时调度算法。所谓静态是指实时操作系统为所有任务分配的优先级是根据某种算法得出，在运行过程中任务的优先级不再发生变化。其后有很多研究人员基于单调速率调度为基础进行算法的改进和优化。单调速率调度算法是由Liu和Layland在“Scheduling Algorithm for Multiprogramming in a Hard Real Time Environment”提出的。实时操作系统中所处理的任务优先级是根据任务的周期决定的，任务的周期越短优先级越高。另外，单调速率调度算法是基于优先级抢占式任务调度算法，低优先级任务在执行过程中允许随时被高优先级任务中断。单调速率调度算法是在如下条件下提出的：一、在单个处理器中，所有的任务都是周期性运行的。二、忽略上下文切换时间。三、任务的执行时间是恒定的。四、任务之间相互独立，没有数据交换或者资源互斥。五、任务截止期限都在它们周期的结束点上。六、抢占式调度算法，优先级最高的就绪任务一定会被