李菲[1]2003年在《截止时间单调技术研究与实时调度模型的实现》文中指出实时系统是那些不仅要求计算结果在逻辑上正确，而且要求结果在给定的时间范围内给出的系统。实时任务调度就是研究如何合理安排任务的执行，以保证所有的任务或者尽可能多的任务能满足其时间的要求[Stankovic 92]。实时任务调度算法是实时系统设计和实现的关键。 在诸多的实时调度策略中，截止时间单调调度策略以其静态最优调度的性质和容易实现，应用前景广泛等优点成为了实时系统开发的支柱性技术。本文详细讨论和研究了截止时间单调技术，并提出和实现了一个以之为基础的实时调度模型(文中称为实时任务调度器)，为真实系统的设计提供了一个参考调度模型。本文的主要内容如下： ● 介绍了实时调度理论的发展现状，分析了当前流行的各种调度算法的优缺点，其中包括静态调度算法，比如速率单调调度(RMS)、截至时间单调调度(DMS)；和动态调度算法，比如最早截止时间优先调度(EDF)、最小空闲时间优先调度(LLF)等。 ● 从理论发展历史、可调度性测试方法、优先级倒置的处理、非周期任务的处理等几个方面对截止时间单调算法进行了研究。并对算法的两个重要结论：静态最优性和可调度性测试方法分别进行了证明和推导。为实时任务调度器的设计和实现提供了理论基础。 ● 详细讨论了实时任务调度器的设计考虑和实现中的关键算法。在实时任务调度器中将实时任务划分为可调度性能够保证的ScheduableTasks和可调度性不能保证的ManageableTasks两个集合，分别采用不同的调度策略。并且将实时任务按照到达模式(周期性任务，非周期任务等)和截止时间类型(硬截止时间单调技术研究与实时调度模型的实现实时任务，固定截至时间任务等)两个维度进行了分类，讨论了如何利用截至时间单调算法处理不同类型的实时任务。其中将任务集划分为SeheduableTasks和ManageableTasks的思想，最大化SeheduableTaskS算法，硬实时任务的调度优化算法为笔者自行研发。而对于可调度性不能预测的ManageableTasks的处理方法借鉴了StarBase实时数据库系统〔Kim97〕中的实时交易调度策略。 讨论了如何将实时任务调度器应用于真实的实时系统上，并指出了实时任务调度器进一步改进的方向。 本文组织如下:第一章为研究背景介绍;第二章为实时调度综述和对截止时间调度理论的研究;第叁章介绍了实时调度器的设计考虑和设计目标以及试验平台QNX实时操作系统:第四章详细阐述了实时任务调度器设计和实现细节和关键算法:第五章为全文总结和对实时任务调度器在真实系统中的应用和进一步改进的讨论。
冯艳红[2]2005年在《实时多任务集成调度算法的研究》文中认为本文通过研究在一个实时系统中会有多类型任务的出现,将实时任务按照到达模式和截止时间类型两个纬度进行分类。并且在分析了诸多的调度算法中,对截止时间单调调度算法进行了详细的研究,它已被证明是最优的静态调度算法,比起动态调度算法的复杂性更易于在实际的操作系统中实现,所以成为了实时系统的支柱性技术。此基础上,本文提出并实现了一个实时调度模型(文中称之为SM模型) ,在SM模型中将实时任务划分为可调度性能够保证的ScheduableTasks和可调度性不能够保证的ManageableTasks两个任务集合,对它们分别采用不同的调度策略。本文研究的重点为:将任务集划分为ScheduableTasks和ManageableTasks两个集合的思想,最大化ScheduableTaks的算法,硬实时任务的调度优化算法,ManageableTasks的处理方法。最后本文对于SM模型提出了进一步改进的方向。
谢建平[3]2008年在《单处理器环境下实时混合任务的调度算法研究》文中进行了进一步梳理随着计算机与自动控制技术的发展,实时系统广泛地应用于航空、航天、航海等领域。实时调度是实时系统核心问题之一,因而成为现代工业、军事等领域的研究热点。调度算法是实时调度的核心所在,本文首先分析了实时混合任务调度算法的研究现状,将实时任务按照到达模式和截止期限类型两个纬度进行分类。然后针对以前调度算法的不足,对两类混合任务调度做了一定的研究并提出了改进性能的算法:1)当任务按照截止期限类型进行分类时可以分为硬截止期任务、固截止期任务和软截止期任务。针对传统的最高价值优先(HVF)和截止期/价值优先(EDV)等算法致使某些硬截止期任务的截止期得不到满足的缺点,提出了一种新的基于动态优先级的混合任务调度算法。该算法特别针对硬截止期任务的执行时机,融合了基于阈值的调度算法和任务的执行价值等多种元素。鉴于硬截止期、固截止期和软截止期任务的不同特征,对它们采用不同的优先级计算方法。经过仿真试验表明,该算法能保证硬截止期任务的满足截止期,并且能提高固截止期任务完成数量占总数量的比例。2)当任务按照到达模式进行分类时可以分为周期任务和非周期任务。文章提出了结合总带宽服务器算法(TBS)算法和时限单调算法(DMS)算法的实时混合任务的调度算法,基于TBS服务器思想将非周期任务临时转换成有时限要求的硬实时任务,然后基于DMS调度周期任务和非周期任务。由于是使用静态的DMS算法,不仅可以减小任务的切换开销,而且对系统的瞬时过载有一定的适应性。该方法能保证周期任务满足时限的要求,还能缩短非周期任务的响应时间。
赵明阳[4]2011年在《基于嵌入式实时操作系统的软总线技术研究》文中研究指明随着新一代航空电子系统的发展,担负着多种航空使命的机载软件变得日益复杂,为了保证它们在不同机载系统中的可移植性、可维护性、可靠性和互操作性,实时中间件技术被引入到新一代航空电子的软件系统设计中。在具有协同作战能力的C4ISR体系结构中,飞机之间、飞机与地面控制中心之间构成了一个有大量信息交互的分布式实时嵌入式系统。该系统运行在一个动态变化的环境中,而传统的实时中间件在该环境下存在着不能提供动态QoS确保和动态资源管理等问题,因此本文主要研究中间件关键技术中的动态调度服务。本文首先分析了中间件技术在解决异构平台互操作问题上的相关理论,针对传统实时中间件TAO在航空领域中的应用,分析了它在动态环境下存在的不足。接着对实时中间件中的调度服务进行了研究,分析了现有调度模型的缺陷,提出了一种能够进行资源再分配的两层调度服务模型。本文的主要工作是在TAO调度服务的基础上,基于两层调度服务模型设计了一个顶层调度服务框架。首先针对分布式实时系统中的QoS需求,给出了一种动态QoS机制的实现方案。然后将该方案引入到顶层调度服务框架中,通过对TAO源码的分析,按照软件工程中的构件思想,将其实现为一个CORBA服务。该调度服务能够根据不同的实时应用配置相应的QoS需求,并且能够在动态环境下确保关键任务实时性的同时,调整非关键任务的QoS级别和系统资源。论文最后阐述了调度服务的设计和实现,并对测试结果进行了分析,初步验证了提出的动态QoS机制的有效性。
毛磊[5]2007年在《基于嵌入式实时操作系统的任务调度研究与应用》文中研究表明嵌入式系统有一个共同的特性，即对系统的响应时间有严格要求。随着实时嵌入式系统结构的日益复杂，运行环境的不确定因素增多，操作系统中任务调度受到广泛关注。本文首先介绍RTOS中经典的调度策略，分析其各种任务调度算法的局限性。然后从实时系统的不确定性、不可预测性角度入手，针对实时系统中硬实时任务与软实时任务并存情况，分析混合任务并介绍混合任务调度算法，提出了混合任务调度模型框架。在对任务反馈调度研究中，根据Chenyang Lu和John A．Stankovic提出的反馈控制实时调度算法，对PI控制器详细分析并介绍利用率、丢失率、利用率丢失率反馈调度算法，总结了各调度算法优劣。对于控制与调度协同设计问题，提出以Qoc作为评价基础，给出基于Qoc的调度策略，并构建基于实时控制与调度协同设计模型，使用弹簧算法灵活处理扰动到来对被控系统的影响。最后在反馈混合任务调度研究中，以反馈控制混合任务调度框架为基础，可调软硬实时任务负载带宽为出发点，准入与Qos调节器为软实时任务负载调节手段，提出了反馈调度的水箱模型以及控制器的控制算法，仿真结果验证了该算法的可行性。通过研究μC／OS-Ⅱ的任务管理、内核调度方面的内容，移植μC／OS-Ⅱ于TMS320LF2407A硬件平台上。在μC／OS-Ⅱ实时内核调度的可扩展性研究基础上，修改内核，设计实时任务和软件结构，并引入基于反馈控制混合任务调度算法。实践验证该调度算法有效提高系统的鲁棒性。
王立刚[6]2006年在《开放式混合实时系统中的调度方法研究》文中研究指明实时系统主要面向现实世界中与时间因素相关的应用需求，在工业控制、航空航天和军事设备等众多领域里有着广泛的应用。它所关注的不仅是计算结果在逻辑上的正确性，而且还有输出结果时间上的及时性。随着实时系统应用的不断深入发展，多类型的硬实时、软实时与非实时任务共存于同一系统中的情况越来越普遍，致使其复杂性不断提高。开放式混合实时系统即是针对这种实际情况被提出的。 本文在对开放式混合实时系统的调度问题进行了深入分析的基础上，对调度问题进行了系统的研究，提出了一种新的集成调度框架——RPDS(Rigorously Proportional Dispatching Server)。针对广泛存在的不确定实时环境，提出了一种反馈控制实时调度算法NF-QoS(Normalized Fair QoS)。结合具体的操作系统平台(MiniCore)讨论了集成上述两种调度算法的设计与实现方案，构建了一个原型操作系统RT-MiniCore。 在混合实时系统中，调度器必须既保证所有硬实时任务严格按照其时间约束在截止期内完成，又要尽可能提高软实时任务和非实时任务的服务质量。RPDS算法就是为解决这个问题而提出的，并以此为基础构建了一种层次式调度框架。该算法将不同类型实时任务分开，由不同调度器调度，由RPDS统一派发时间片。在保证硬实时任务不受其他类型任务影响的基础上，RPDS将处理器时间流分成连续的小段，并在每一小段中强制为非硬实时任务分配一个时间片，使软实时任务的截止期错失率达到了最小化。对于在系统中同时运行的各类应用程序，可单独进行开发和验证，并可以选择不同的局部调度器。 任务间的QoS公平性是多QoS级别的可调节动态实时调度系统中的一个重要问题。本文引入了标准化QoS公平的概念，在公平性中加入了任务的重要性因素，并构造了具有PID反馈控制环节的实时调度算法NF-QoS，以达到系统的标准化QoS公平。利用NF-QoS对系统截止期错失率进行实时采样，定期反馈给PID控制器，根据PID控制器计算的结果对各任务QoS级别进行动态调整，以保证各任务公平地得到处理器资源。 调度方法要在实际中得到应用，需要与具体的操作系统相结合。本文介绍了一种我们提出的基于服务体／执行流模型(Servant／Exe-Flow Model，SEF)的
张嵎桐[7]2011年在《基于反馈机制的软实时系统任务调度算法研究》文中研究表明随着嵌入式系统及其相关技术的快速发展与普及，一种运行于开放和不可预测环境的软实时系统正在迅速崛起，为实时系统的研究提出了新的挑战。传统的实时调度算法大多都是开环调度的，此类算法在静态或者特定动态系统中均具有较好的性能，但是在不可预测的动态系统中其性能会急剧下降。因此，将反馈机制应用到软实时系统调度算法中已经成为调度算法研究的一个热点。系统过载问题一直是调度研究的主题，任务过载率对于软实时系统的有效性和可靠性至关重要；任务间的公平性是软实时系统中的又一个重要问题，不同的任务有着不同的重要性，如何公平的给它们分配资源还有待进一步研究。针对上述需求，本文在国家自然科学基金《异构多核片上系统自适应实时任务调度机制及算法研究》的资助下，对基于反馈控制的软实时任务调度中的部分问题进行了完善和改进。本文的主要工作如下：针对系统运行过载问题，目前的研究基本都是针对系统发生过载后，如何通过反馈来及时有效的制止，没有从跟本上解决过载发生的必然性。本文利用回归模型与非精确计算设计了一种提前预防系统过载的策略，该策略面向多任务实时系统，对每个任务进行跟踪，并在所有任务利用率之和大于系统最大利用率时提前进行调整，从而避免过载现象的发生。针对任务公平性调度问题，已有的研究或者没有考虑任务之间的公平性，随着系统根据反馈信息对所有任务服务等级进行调整，就会出现某些任务持续运行在很高或者很低的服务等级；或者考虑了任务间的公平性问题，但未进一步考虑不同任务的权重差异，将所有任务等同对待。本文利用反馈控制描述了一种任务权重公平化的策略。该策略加入了任务的权重因素，根据各个任务的相对权重对其服务等级进行及时调整，以保证任务之间公平地得到处理器资源。为了验证本文算法的有效性，基于现有的非精确计算任务调度模型实现了一个模拟系统，对本文提出的算法和现有的相关经典算法进行模拟比较。实验数据表明：过载避免算法在系统负载存在突发的情况下，算法不仅很好地体现了任务的实时性，而且有效地增强了系统的容错能力；任务公平性算法在合理保证系统利用率和错失率的同时，有效地提高了系统任务之间的公平性。
陈克力[8]2006年在《嵌入式组件及其实时调度策略研究》文中研究说明嵌入式系统的应用开发已经成为计算机工业最热门的领域,嵌入式系统在汽车电子领域内也获得了越来越广泛的应用。针对特定行业应用的软件开发平台是支持嵌入式软件开发的一种快速、高效的工具,对于提高嵌入式软件的开发效率和开发质量具有重要意义。但是如何构造嵌入式软件开发平台来满足汽车电子领域软件发展的需要,支持各种厂商提供的种类繁多的硬件平台,满足各种不同信息产品的应用开发,与现有成熟的辅助开发工具和软件集成,一直是个难题。本文正是基于这个目标,以组件模型为中心展开了深入的理论研究和实践探索。软件总线是当前一种前沿的软件体系结构设计方式。正如硬件系统的复杂化使工业生产不堪重负从而导致了总线结构的兴起,软件开发也迎来了“总线时代”。论文论述了软总线的原理,分析和探讨了基于软总线的组件软件工程。分析了组件的概念,基于组件的软件开发过程及组件软件工程对嵌入式软件开发的要求。在对通用组件模型和嵌入式组件模型的深入研究的基础上,论文研究和设计了一种基于进程间通信的嵌入式组件模型,为商品化组件的复用和环境移动提供了可行的途径,为软件系统的“即插即用”给出一种解决方案。论文阐述了进程间通信组件模型的设计原理,分析了该组件模型的优缺点。论文分析了嵌入式系统的实时性需求,并讨论了几种典型的实时调度策略和经典的实时调度算法,进一步提出了基于组件的嵌入式系统开发中组件实时调度的意义。在分析了操作系统中集成调度算法的基础上,分析了组件调度中采用集成调度的意义,提出了一种通用组件调度框架。该框架应用到嵌入式组件集成开发的设计中,有利于满足不同应用系统对组件系统的实时性要求。论文给出了通用调度框架的实现原型。在面向汽车电子领域的嵌入式软件开发平台中对进程间通信组件模型的设计和实现证明,在实际系统的设计中基于进程间通信组件模型的通用组件调度框架是具有可行性和实用性的。论文的研究成果对于嵌入式软件开发平台进一步的研究工作有一定的参考价值。
刘勇[9]2007年在《基于DNA-GA的最早截止期限优先调度算法优化》文中进行了进一步梳理实时调度算法是嵌入式实时系统设计和实现的关键问题之一，也是保障实时系统两个必备特性(时限性和可靠性)的重要方法，是实时系统中重要而活跃的研究领域。在众多的实时调度算法中，速率单调(Rate Monotonic，RM)和最早截止期限优先(Earliest Deadline First，EDF)分别是静态调度和动态调度领域中经典的调度算法。RM算法属于静态调度算法，在系统运行前决定任务的调度，实现简单，在满足前提条件的情况下可以保证实时任务集的成功调度。EDF算法属于动态调度算法，在系统运行时决定任务的调度，CPU利用率可以达到100％(理想情况下)。虽然RM和EDF算法以其各自所具备的优良性能在嵌入式实时系统中得到了广泛应用，但是我们也不能忽视它们本身存在的实时性问题。本文是在考虑“任务调度开销时间”的情况下，通过优化EDF调度算法中各个任务的启动时间来提高EDF调度算法的实时性能的。首先介绍实时调度算法的应用背景：实时系统、嵌入式系统、实时操作系统和嵌入式实时操作系统。接着对现有的实时调度模型、实时调度基本理论、调度策略和实时调度算法进行了分析和研究。对RM和EDF实时调度算法进行了详细分析，并举例说明了它们的调度过程。然后介绍了本文用到的优化算法—DNA遗传算法(Deoxyribonucleic acid Genetic Algorithm，DNA-GA)，及其基本理论和操作方法，并说明了DNA(Deoxyribonucleic acid)算法的生物学基础和遗传算法的基本理论。最后，通过使用DNA-GA对EDF调度算法中各个任务的启动时间进行离线优化，离线计算各实时任务的启动时间，运用这些优化的启动时间作为在线实时系统使用EDF调度算法的参数进行实时任务调度，以此来提高实时系统的实时性能。本文模拟了基于DNA-GA的最早截止期限优先调度算法的优化调度，并比较了优化前后因抢占引起的调度开销。实验结果表明：使用DNA遗传算法可以对实时任务的启动时间进行优化，可以减少实时任务因抢占引起的调度开销。说明了使用DNA遗传算法对EDF调度算法进行优化的可行性和有效性。该结论对实时调度算法的研究和使用有一定的理论和实践意义。本文的创新之处在于使用DNA遗传算法对EDF调度算法中各个任务的启动时间进行优化，实现了DNA遗传算法在嵌入式实时调度算法领域的运用。
柴华[10]2008年在《一种反馈控制机制在EDF算法上的应用》文中指出实时调度算法是嵌入式实时系统设计和实现的关键问题之一,也是保障实时系统两个必备特性(时限性和可靠性)的重要方法,是实时系统中重要而活跃的研究领域。在众多的实时调度算法中,速率单调(Rate Monotonic,RM)和最早截止期限优先(Eartiest Deadline First,EDF)分别是静态调度和动态调度领域中经典的调度算法。RM算法属于静态调度算法,在系统运行前决定任务的调度,实现简单,在满足前提条件的情况下可以保证实时任务集的成功调度。EDF算法属于动态调度算法,在系统运行时决定任务的调度,CPU利用率可以达到100%(理想情况下)。虽然RM和EDF算法以其各自所具备的优良性能在嵌入式实时系统中得到了广泛应用,但是我们也不能忽视它们本身存在的实时性问题。虽然一些改进后的算法能支持更复杂的任务集特性,但这些算法都是开环的调度算法。开环就意味着一旦调度器被创建,它们就不能基于持续的反馈进行调整了。尽管开环调度算法在负载精确建模的静态或动态系统中执行良好,但是该类算法在不可预测的动态系统环境下性能却较差。本文是在考虑“系统过载”的情况下,通过在EDF调度算法中引入反馈控制机制来提高EDF调度算法的实时性及稳定性。首先介绍实时调度算法的应用背景:实时系统、嵌入式系统、实时操作系统和嵌入式实时操作系统。接着对现有的实时调度模型、实时调度基本理论、调度策略和实时调度算法进行了分析和研究。对RM和EDF实时调度算法进行了详细分析,并举例说明了它们的调度过程。然后介绍了本文提出的反馈控制机制用到的相关理论—比例-积分-微分(Proportional-Integral-Derivative,PID)自动控制理论和操作方法,并说明了单神经元智能控制的基本理论。最后,通过使用自适应单神经元PID算法对EDF调度算法进行动态反馈控制,动态调整过载时系统中的任务数量,运用每次运行获得的截止期错失率作为下一次运行的输入参数进行实时任务调度,以此来提高实时系统的实时性和稳定性,达到有效改善过载的目的。本文模拟了基于PID反馈控制机制的最早截止期限优先调度算法,并比较了引入反馈控制机制前后的实验情况。实验结果表明:引入自适应单神经元PID反馈调度算法可以快速稳定并积极改善实时系统达到过载时的情况,可以优化系统降级时的性能。说明了使用PID反馈控制对改善EDF调度算法执行情况的可行性和有效性。该结论对实时调度算法的研究和使用有一定的理论和实践意义。本文的创新之处在于引入了单神经元PID反馈控制机制,使反馈控制更具智能型,实现了自适应单神经元PID控制算法在嵌入式实时调度算法领域的运用。
参考文献：
[1]. 截止时间单调技术研究与实时调度模型的实现[D]. 李菲. 四川大学. 2003
[2]. 实时多任务集成调度算法的研究[D]. 冯艳红. 华北电力大学（河北）. 2005
[3]. 单处理器环境下实时混合任务的调度算法研究[D]. 谢建平. 武汉理工大学. 2008
[4]. 基于嵌入式实时操作系统的软总线技术研究[D]. 赵明阳. 南京航空航天大学. 2011
[5]. 基于嵌入式实时操作系统的任务调度研究与应用[D]. 毛磊. 同济大学. 2007
[6]. 开放式混合实时系统中的调度方法研究[D]. 王立刚. 中国科学技术大学. 2006
[7]. 基于反馈机制的软实时系统任务调度算法研究[D]. 张嵎桐. 湖南大学. 2011
[8]. 嵌入式组件及其实时调度策略研究[D]. 陈克力. 电子科技大学. 2006
[9]. 基于DNA-GA的最早截止期限优先调度算法优化[D]. 刘勇. 太原理工大学. 2007
[10]. 一种反馈控制机制在EDF算法上的应用[D]. 柴华. 太原理工大学. 2008
标签：计算机软件及计算机应用论文; 实时系统论文; 反馈控制论文; 优化策略论文; 动态模型论文; 任务调度论文; 嵌入式论文; qos论文; 算法论文;