单调时限调度算法的可调度分析

单调时限调度通过定义Di≤Ti放宽了单调比率调度对被调度任务集的限制,使之更加近似于工程实际,但现有的单调时限调度的可调度分析的充分条件十分复杂。文章提出并证明了基于最小处理器利用率上限的单调时限调度的充分可调度条件,大大简化了单调时限调度的调度分析。     

改进的单调速率调度算法

实时系统中调度算法起着重要的作用.单调速率调度算法(rate monotonic algorithm,RM)是一种被 广泛使用的调度算法,并且已被证明是一种最佳的静态优先级算法.传统的RM算法忽略上下文切换需要消耗的时间,针对此问题,提出了一种延迟抢占的改进方法.该方法考虑了上下文切换消耗时间对调度算法的影响,可以减少...     

一种基于非抢占RM算法的可行性判决算法及应用

为中断服务例程建立了任务模型，在该模型的基础上给出了中断服务例程集使用非抢占RM调度的可行性的充分必要条件，并且基于该条件提出了一种新的非抢占RM算法的可行性判决算法。进一步地，给出了如何改进不可调度例程集的方法，并且将该方法应用到一个具体工程项目中，取得较好的效果。     

提高软非周期任务响应性能的调度算法

实时环境中常常既包含硬周期任务,又包含软非周期任务,引入一种改进软非周期实时任务响应时间的算法.已有的解决混合任务调度问题的方法都是基于速率单调（Rate Monotonic）策略的,其中从周期任务“挪用时间”的算法被证明优于其他所有算法.但是,速率单调算法限制了处理器的使用率,从而使周期任务的可“挪用”时间受到限制.最后期限驱动（Deadline Driven）策略DD可使潜在的处理器利用率达到100%.新算法正是在周期任务的调度中适当加入了DD策略,从而使非周期任务的响应时间得以缩短.仿真实验的结果表明,这种算法的性能优于已有的所有算法,而由它所带来的额外开销却不算很高.     

单调比率调度算法研究及改进

本文对经典实时调度算法单调比率算法进行了分析研究,并提出了一种基于弹性优先级的改进方法减少了空闲任务的数量,使该算法更加适合流媒体应用环境。     

The Non-Optimality of the Monotonic Priority Assignments for Hard Real-Time Offset Free Systems

In this paper, we study the problem of scheduling hard real-time periodic tasks with static priority pre-emptive algorithms. We consider tasks which are characterized by a period, a hard deadline, a computation time and an offset (the time of the first request), where the offsets may be chosen by the scheduling algorithm, hence the denomination offset free systems.We study the rate monotonic and the deadline monotonic priority assignments for this kind of system and we compare the offset free systems and the asynchronous systems in terms of priority assignment. Hence, we show that the rate and the deadline monotonic priority assignments are not optimal for offset free systems.     

基于命题投影时序逻辑的单调速率调度算法模型检测

提出了基于命题投影时序逻辑(propositional projection temporal logic,简称PPTL)的单调速率调度(rate monotonic scheduling,简称RMS)模型检测方法.该方法使用SPIN模型检测器的系统建模语言PROMELA为任务调度系统建模,使用PPTL描述系统期望的性质,通过SPIN验证系统模型是否满足性质,从而得知一个任务组在RMS下是否可调度.同时,RMS算法控制下的任务调度系统的其他性质也可以得到验证.     

Multicycle Polling Scheduling Algorithms for FieldBus Networks

The paper deals with the scheduling of periodic information flow in a FieldBus environment. The scheduling problem is defined from an analytical point of view, giving a brief survey of the most well-known solutions. One of these is called multicycle polling scheduling, which is based on the hypothesis that all the production periods of the periodic processes to be scheduled are harmonic. Although in some process control or manufacturing scenarios, this hypothesis may be acceptable, there are many real industrial processes to which it cannot be applied. The aim of the paper is to make a contribution towards solving the scheduling problem. It essentially concerns extension of the theory on which multicycle polling scheduling is based to a much more realistic and general scenario, where the periods of all the processes to be scheduled have arbitrary values. The authors present a new formulation of multicycle polling scheduling, called extended multicycle polling scheduling, and demonstrate that it comprises the scenario currently considered in the literature. Two algorithmic solutions for extended multicycle polling scheduling are then proposed, giving a computational complexity analysis which will highlight the capability of the algorithmic scheduling solutions to be performed on-line. The paper concludes by comparing the multicycle polling scheduling approach known in literature and the one presented in the paper. Comparison is performed by evaluating the use of available bandwidth to serve both periodic and asynchronous traffic in the two approaches.     

Scheduling of Offset Free Systems

In this paper, we study the problem of scheduling hard real-time periodic tasks. We consider independent tasks which are characterized by a period, a hard deadline and a computation time, but where the offsets may be chosen by the scheduling algorithm. We first show that we can restrict the problem by considering non-equivalent offset assignments. More precisely, we show that there are finitely many non-equivalent offset assignments and we propose a method to reduce significantly this number and consider only the minimal number of non-equivalent offset assignments. We then propose an optimal offset assignment rule which considers only the non-equivalent offset assignments. However the number of combinations remains exponential; for this reason, we also propose a nearly optimal algorithm with a more reasonable time complexity.     

基于截止时间满意度的网格工作流调度算法

动态网格环境中用户截止时间保障是工作流调度问题的一个挑战.利用随机服务模型来描述网格资源的动态处理能力及其动态负载压力,提出了截止时间满意度的概念和工作流截止时间满意度的计算方法.将以DAG图形式表示的任务执行关系转换为以数值表示的任务执行优先级,并根据最大截止时间满意度优先的思想,确定执行工作流子任务的候选资源;将工作流全局截止时间划分问题描述为一个约束下的非线性规划问题并通过已有方法求解该问题,提出了一种截止时间满意度增强的工作流调度算法(DSESAW).仿真实验采用实际网格应用和系统数据来验证所提出算法的性能表现,实验结果表明新算法在网格环境的自适应性和用户截止时间保障方面优于其他两种实际网格系统中的调度算法.     

多特征协调的实时调度算法

目前大多数实时调度算法都依据单一的特征参数确定任务优先级,本文提出一种基于多特征协调的实时调度算法,对特定高优先级任务优先处理,并且对其他任务的调度不产生任何影响。同时,在系统超载的时候,有效避免了EDF算法性能的急剧下降。实验结果表明,该算法有效地保证了特定任务的调度优先级,相对于EDF算法性能有明显改进。     

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

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

一种考虑截止期的METCD业务组合调度方法

海洋设备检定、校准和检测（Marine Equipment Testing, Calibrate & Detection, METCD）业务规模大、紧急情况多,如何对业务进行合理的调配是海洋计量检定行业亟待解决的问题。本文提出了一种考虑截止期的任务组合METCD业务调度方法。在建立业务调度问题数学模型的基础上,采用最早截止时间优先-蚁群算法(EDF-PACO)对模型求解,在最早截止日期的约束条件下对任务组合处理的最优调度方案,达到降低任务总完成时间和减少执行空间浪费双重优化目标。为了验证方法的可行性,以国家海洋局东海标准技术中心的业务为实例,将EDF-PACO算法与传统的最早截止时间优先算法和蚁群算法进行比较,结果表明本文所提出的调度方法在满足截止期的约束条件下能高效地对海洋设备的计量检定业务进行组合调度。     

基于优先级表的实时调度算法及其实现

讨论了综合考虑任务的截止期和价值两个特征参数的优先级表设计方法,提出了EDV(earliest deadline value)与VED(value earliest deadline)两种不同的基于优先级表的实时任务调度算法,并且利用多重链表给出了这两种算法的实现,包括任务接收策略与任务完成/夭折策略的算法实现.这种优先级表设计方法及其基于多重链表的实现方法也适用于对任务的其他两种甚至3种不同特征参数之间的综合.基于累积实现价值率、加权截止期保证率与差分截止期保证率3个方面,分析了VED算法与EDV算法的性能,实验结果表明,在所有负载条件下VED算法与EDV算法相对于EDF(earliest deadline first)算法与HVF(highest value first)算法都有很大的性能改进.     

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

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

一种基于决策森林的单调分类方法

单调分类问题是特征与类别之间带有单调性约束的有序分类问题.对于符号数据的单调分类问题已有较好的方法,但对于数值数据,现有的方法分类精度和运行效率有限.提出一种基于决策森林的单调分类方法(monotonic classification method based on decision forest, MCDF),设计采样策略来构造决策树,可以保持数据子集与原数据集分布一致,并通过样本权重避免非单调数据的影响,在保持较高分类精度的同时有效提高了运行效率,同时这种策略可以自动确定决策森林中决策树的个数.在决策森林进行分类时,给出了决策冲突时的解决方法.提出的方法既可以处理符号数据,也可以处理数值数据.在人造数据集、UCI及真实数据集上的实验数据表明:该方法可以提高单调分类性能和运行效率,缩短分类规则的长度,解决数据集规模较大的单调分类问题.     

有预算和截止期约束的网格作业调度算法

在商业网格计算环境中,作业有预算和截止期限制。如何向消费者提供有质量保障的服务,同时考虑服务提供者的利益,是一个关键问题。现有的作业调度算法只从消费者的角度出发对作业完成的时间和成本进行优化。同时从消费者和服务者的角度,利用作业的属性定义了作业的价值密度,在此基础上提出了高价值密度优先的网格作业调度算法HVDF。仿真结果表明,HVDF算法在实现价值率和按时完成作业数两个性能指标上优于现有算法。     

混合实时事务的延期单调速率调度算法及其可调度性分析

对于含有实时和非实时两部分的混合实时应用,传统的单调速率调度算法(RM)已不再适用.为此,该文引入“混合实时事务”的概念,并针对这类事务提出一种延期单调速率调度算法(DRM);着重分析了DRM算法对混合实时事务的可调度性;进行了实验测试与性能分析比较．结果表明,事务集中混合实时事务占的比例越高,混合事务中非实时子事务占的比例越大,该算法的CPU使用率阈值就越高,且在各种情况下,DRM算法与RM算法相比性能都更优,最低情况也与之一样．     

基于(m,k)-firm约束规范的混合任务调度算法研究

讨论了在准实时环境下,包括准实时周期任务和准实时非周期任务在内的混合任务调度算法HTSF.HTSF算法是在满足周期任务(m,k)-firm 约束规范的前提下提高非周期任务可调度性,同时合理利用可用空闲时间,提高整个系统的服务质量.HTSF算法给出了非周期任务的可调度性分析方法,同时采用静态调度与动态调度相结合的方法调度周期任务和非周期任务.模拟测试结果显示,系统对非周期任务的接收率比同类相关算法的接收率高.     

DAG任务图的一种调度算法

并行程序的调度技术是开发并行计算机系统的计算潜能的关键问题。本文讨论了4种典型的调度算法的缺陷，提出了一种新的调度算法CPFMBF，它采用的策略是：优先调度关键路径节点，其次调度b-level值大的节点，再次调度节点的关键路径影响度大的节点。对照分析及在几种具代表性的工程应用任务图上的实验结果证明CPFMBF算法的调度性能普遍好于其它算法。