基于模型的窗口限制实时系统的分析与研究

在研究基于（m，k）模型的窗口限制实时系统的基础上，提出了一种受（m，k）限制的窗口限制实时系统．首先对该实时系统的调度性进行了分析与研究，得出了一些结论．然后提出了一种新的动态窗口调度算法，该算法充分利用了（m，k）限制的特点来提高实时任务的可调度性，减少窗口限制违例．同时，还进行了大量的模拟研究，这些模拟以传统的动态窗口调度算法为基准，将其应用于受（m，k）限制的窗口限制实时系统时的窗口限制违例情况并与新算法进行比较．模拟结果表明，新算法的表现优于传统的动态窗口限制的调度算法．最后进行了总结与展望．     

一种帧间相关的弱硬实时系统的分析与研究

随着嵌入式系统的发展，实时操作系统越来越受到人们的重视，实时操作系统的一个关键问题是实时调度问题，在研究弱硬实时系统的基础上提出了一种受弱硬实时限制的帧间相关周期模型．首先对该模型的调度性进行了分析与研究，得出了一些结论，然后提出了相应的基于双距离的优先级调度算法，该算法充分利用了帧间相关的特点来提高实时任务的可调度性，最后进行了总结与展望．     

组合窗口约束(m,k)＾的实时系统分析与研究

在研究基于窗口约束(m,k)模型的实时系统的基础上,提出一种基于非重叠组合窗口约束的实时系统.通过对该实时系统的可调度性条件的研究,提出一种新的组合窗口约束(m,k)＾的调度算法,该算法充分利用组合约束的特点,考虑本次调度对该窗口的可调度的影响来确定任务的优先级,并以此来提高任务的可调度性、减少组合窗口限制违例.仿真试验表明该算法在组合窗口约束的调度上,优于传统的独立比较两个约束确定优先级的调度算法.     

组合窗口约束（m，k）^∧〈h，k〉的实时系统分析与研究

在研究基于窗口约束（m,k）模型的实时系统的基础上,提出一种基于非重叠组合窗口约束的实时系统.通过对该实时系统的可调度性条件的研究,提出一种新的组合窗口约束（m,k）^∧〈h,k〉的调度算法,该算法充分利用组合约束的特点,考虑本次调度对该窗口的可调度的影响来确定任务的优先级,并以此来提高任务的可调度性、减少组合窗口限制违例.仿真试验表明该算法在组合窗口约束的调度上,优于传统的独立比较两个约束确定优先级的调度算法.     

一种实时异构系统的集成动态调度算法

提出了一种实时异构系统的集成动态调度算法.该算法通过一个新的任务分配策略以及软实时任务的服务质量QoS(quality of service)降级策略,不仅以统一方式完成了对实时异构系统中硬、软实时任务的集成动态调度,而且提高了算法的调度成功率.同时,还进行了大量的模拟研究.这些模拟以传统的近视算法为基准,将其应用在实时异构系统集成动态调度时的调度成功率与新算法进行比较,模拟结果表明,在多种任务参数取值下,新算法的调度成功率均高于传统的近视算法.     

混合型实时容错调度算法的设计和性能分析

以往文献中研究的实时容错调度算法都只能调度单一的具有容错需求的任务.该文建立了一个混合型实时容错调度模型,提出一种静态实时容错调度算法.该算法能同时调度具有容错需求的实时任务和无容错需求的实时任务.该文还提出了一个求解最小处理机个数的算法,用于对静态实时容错调度算法的性能进行模拟分析.为了提高静态调度算法的调度性能,提出了一种动态调度算法.最后,通过模拟实验分析了静态和动态调度算法的性能.实验表明,调度算法的性能与实时任务的个数、任务的计算时间、周期和处理机个数等系统参数相关.     

基于IP-SAN的拟序备份调度算法的研究

随着企业信息爆炸性增长,海量信息存储成为目前存储行业研究的热点。先分析了传统的拟序备份AOE模型的缺陷和依赖该模型的调度算法的不足,然后针对网络状况不确定的因素,提出了一种改进的拟序备份AOV模型和调度算法。该调度算法依赖图的深度搜索与动态剪枝算法,能够根据任务的完成状况动态地调度,达到最大化地并发处理任务的目的。模拟仿真实验结果表明该调度算法能很好地弥补传统算法的不足。     

基于距离挖掘的多变量原子性违例检测

针对并发程序错误中涉及到的多变量原子性违例检测问题,提出一种动态检测算法。通过计算共享变量间的距离,推测变量之间的相关性,利用相关联的变量关系检测原子性违例错误,确定原子区域的挖掘方法。实验结果表明,该算法能有效挖掘程序中的相关变量,并检测程序中涉及到的多变量原子性违例错误。     

基于禁忌搜索算法测地卫星任务调度研究

研究测地卫星调度问题,它是一个复杂的组合优化问题,涉及多个卫星,大量的任务与约束限制,何时和如何执行每项任务。分析了问题的主要约束,在合理的假设基础上建立了带有时间窗口多资源调度问题模型,提出一种改进的禁忌搜索算法求解该模型。用实例对模型和算法进行了验证,并将结果与动态规划方法求解结果比较分析,结果表明模型和算法是有效的。     

基于DVS技术的性能感知反馈调度算法

传统DVS算法在能量管理方面没有考虑实际系统性能的需求,这在一定意义上限制了其节能效果．针对这一问题,提出一种基于DVS技术的性能感知反馈调度算法．在反馈调度器中,分别采用DVS技术和模糊控制技术设计CPU电压调节模块和控制任务周期调节模块,实现对系统CPU速率和控制任务采样周期的动态调节．通过与基于固定采样周期的DVS反馈调度算法进行对比,结果表明该算法在保证系统控制性能的同时进一步降低了系统能耗．     

应用于实时系统的DMS算法可调度性分析

固定优先级任务的可调度性判定是实时系统调度理论研究的核心问题之一。本文提出了一种可行的DMS可调度性判定方法——确切性判定方法（precised schedulability test algorithln,简称PSTA）,利用DMS调度的充要条件,保证任何任务集均可被判定,并且判定结果是确切的。首先给出了DMS调度模型,介绍了可调度性判定的基本思想,然后进一步通过实验提出并证明了PSTA相关的定理。     

不可抢占式EDF调度算法的可调度性分析

现有的不可抢占式EDF调度算法的可调度性分析判定条件限定实时任务的截止期必须等于其周期,限制了它的使用范围。论文突破这一限制,提出了更具一般性的可调度性分析判定充要条件。通过对可调度性判定充要条件的分析,提出了基于不可抢占式EDF调度算法的周期性实时系统可调度性分析算法。     

一种改进的RM可调度性判定算法

固定优先级任务可调度性判定是实时系统调度理论研究的核心问题之一.目前已有的各种判定方法可归结为两大类:多项式时间调度判定和确切性判定.多项式时间调度判定通常采用调度充分条件来进行,为此,许多理想条件下基于RM(rate monotonic)调度算法的CPU利用率最小上界被提了出来.确切性判定利用RM调度的充要条件,保证任何任务集均可被判定,并且判定结果是确切的.但是由于时间复杂度较差,确切性判定方法难以实现在线分析.提出了一种改进的RM可调度性判定方法(improved schedulability test algorithm,简称ISTA).首先介绍了任务调度空间这一概念,并提出了二叉树表示,然后进一步提出了相关的剪枝理论.在此基础上,研究了任务之间可调度性的相关性及其对判定任务集可调度性的影响,提出并证明了相关的定理.最后基于提出的定理,给出了一种改进的伪多项式时间可调度性判定算法,并与已有的判定方法进行了比较.仿真结果表明,该算法平均性能作为任务集内任务个数的函数具有显著提高.     

长释放时间间隔优先的混合任务调度算法

针对混合任务实时调度的需求和MUF算法的局限性,提出了一种长释放时间间隔优先的混合任务实时调度算法LRIF,该算法除了可对周期性硬实时任务提供调度保证外,同时还可确保非周期性软实时任务的可调度率。论文还提出了LRIF调度算法的可调度性分析方法,并讨论了LRIF调度算法的实现方法。     

Scheduling and Priority Mapping for Static Real-Time Middleware

This paperpresents a middleware real-time scheduling technique for static,distributed, real-time applications. The technique uses globaldeadline monotonic priority assignment to clients and the DistributedPriority Ceiling protocol to provide concurrency control andpriorities for server execution. The paper presents a new algorithmfor mapping the potentially large number of unique global prioritiesrequired by this scheduling technique to the restricted set ofpriorities provided by commercial real-time operating systems.This algorithm is called Lowest Overlap First Priority Mapping;we prove that it is optimal among direct priority mapping algorithms.This paper also presents the implementation of these real-timemiddleware scheduling techniques in a Scheduling Service thatmeets the interface proposed for such a service in the Real-TimeCORBA 1.0 standard. Our prototype Scheduling Service is integratedwith the commercial PERTS tool that provides schedulability analysisand automated generation of global and local priorities for clientsand servers.     

实时调度EDZL算法的可调度性判定

针对多处理器实时调度中的EDZL调度算法,利用多任务之间的相互干涉关系,找出与多处理器之间的时间约束条件,提出了一种可调度性判定的方法,并对给出的判定方法进行了证明。给出了一种判定多处理器实时EDZL可调度性的算法,这种方法可在设计多处理器实时系统时使用。     

云环境下周期和非周期混合实时任务双容错调度算法

云环境中的处理机故障已成为云计算不可忽视的问题,容错成为设计和发展云计算系统的关键需求。针对一些容错调度算法在任务调度过程中调度效率低下以及任务类型单一的问题,提出一种处理机和任务主副版本分组的容错调度方法;并给出了副版本可重叠执行的判定方法,以及任务最坏响应时间的计算公式。通过实验和分析表明,和以前算法相比,将处理机分成两组分别执行任务主版本和任务副版本,减少了任务调度所需进行可调度测试的时间,增加了副版本重叠执行的机会,减少了所需的处理机个数,对提高系统处理机的利用率和容错调度的效率具有重要的意义。     

An Analysis of Totally Clairvoyant Scheduling

Traditional scheduling models assume that the execution time of a job in a periodic job-set is constant in every instance of its execution. This assumption does not hold in real-time systems wherein job execution time is known to vary. A second feature of traditional models is their lack of expressiveness, in that constraints more complex than precedence constraints (for instance, relative timing constraints) cannot be modeled. Thirdly, the schedulability of a real-time system depends upon the degree of clairvoyance afforded to the dispatcher. In this paper, we shall discuss Totally Clairvoyant Scheduling, as modeled within the E-T-C scheduling framework (Subramani, 2002). We show that this instantiation of the scheduling framework captures the central issues in a real-time flow-shop scheduling problem and devise a polynomial time sequential algorithm for the same. The design of the polynomial time algorithm involves the development of a new technique, which we term Mutable Dynamic Programming. We expect that this technique will find applications in other areas of system design, such as Validation and Software Verification. We also introduce an error-minimizing performance metric called Violation Degree and establish that optimizing this metric in a Totally Clairvoyant Scheduling System is NP-Hard.This research is supported in part by the Air Force Office of Scientific Research under Grant F49620-02-1-0043.     

异构分布式系统混合型实时容错调度算法

基/副版本技术是实现实时分布式系统容错的一个重要手段。提出了一种异构分布式混合型容错模型,该模型与传统的异构分布式实时调度模型相比同时考虑了周期和非周期调度任务。在此基础上给出3种容错调度算法:以可调度性为目的SSA算法、以可靠性为目的RSA算法、以负载均衡性为目的BSA算法。算法能够在异构系统中同时调度具有周期和非周期容错需求的实时任务,且能够保证在异构系统中某节点机失效情况下,实时任务仍然能在截止时间内完成。最后从可调度性、可靠性代价、负载均衡性、周期与非周期任务数及任务周期与粒度J个方面对算法进行了分析。模拟实验结果显示算法各有优缺点,所以在选择调度算法时应该根据异构系统的特点来选择。