一种基于阈值的嵌入式实时系统调度算法

基于阈值的双优先级调度算法结合了抢占式与非抢占式调度算法的优点,可以提高任务集的调度成功率,并减少由于任务切换引起的系统开销。对阈值的分配是调度算法的核心。在基本优先级已知的条件下,基于回溯技术的阈值分配算法利用低端任务阈值单向影响高端任务最大响应时间的特性,可以在有限的时间内为任务集找出一组具有极大值特征的阈值。该组阈值可以将任务切换次数降至最低。     

低复杂度的阈值优化实时调度算法

嵌入式实时系统在其CPU及内存资源相对稀缺时,必须采用复杂度低,系统开销小的调度算法.基于阈值的调度算法可以提高任务的调度性,减少任务间的切换,以此减少内存需求和系统开销.提出了基于抢占差值的阈值分配优化算法.算法在最小阈值分配法基础上,从高优先级向低优先级方向设置任务的阈值,为任务集找出一组满足最大抢占差值的阈值分配方案.经过理论分析及实例验证,算法可以显著降低任务的切换次数,并且算法的复杂度优于传统的优化算法.     

多处理器硬实时系统的抢占阈值调度研究

在实时系统中,抢占在提高系统灵活性的同时带来额外的系统开销,特别在多处理器平台上抢占导致的作业迁移会造成相当大的性能下降,减少不必要的抢占是硬实时系统研究的重要方向.抢占阈值调度是处于抢占调度和不可抢占调度之间的一种混合调度方法,在保持调度能力的基础上限制抢占.基于截止期分析建立了多处理器硬实时系统抢占阈值调度的可调度性判定条件,针对抢占阈值调度提出一种改进的优先级分配算法OPA-MLL,并建立了抢占阈值分配(preemption threshold assignment,PTA)算法.仿真结果表明,采用OPA-MLL算法和PTA算法分别给任务集分配优先级和抢占阈值时,可调度任务集比率明显提高,同时能最大程度限制抢占次数.     

信息物理系统中基于保护阈值的实时调度算法研究

信息物理融合系统CPS是一种融合计算、通信与控制的新型复杂实时分布式系统,系统中计算过程和物理过程在开放环境下持续交互、深度融合。为了对物理世界的信息作出实时反馈,系统一般会采用抢占式调度的方法,保障关键任务能够在截止期前完成。但是,分布式环境中抢占式调度方式容易导致频繁的任务切换,影响系统的实时性。提出了基于保护阈值的调度算法,通过建立保护阈值模型,最大化低优先级任务的执行时间,减少任务切换次数。通过实验验证,算法有效地减少了任务切换次数,提高了CPS系统的实时性能。     

面向对象实时多任务系统的优化实现模型

论文提出了一种基于抢占门限的实时多任务系统的优化实现模型,它同时具有低开销与高可调度性。该模型扩展了固定优先级调度模型,同时通过实现模型中线程数的减少实现了运行时的低开销。文中同时也讨论了互不抢占分组的实现算法及每个任务最大抢占门限的分配算法。     

一种新型实时调度算法研究

在许多片上特定应用系统中，任务多且切换频繁，任务切换开销大，有时甚至严重影响系统的可调度性．研究了动态可抢占门限调度算法，它通过初始门限值、动态门限值的计算和优化线程分配，实现了在处理器高利用率下，有效降低任务切换开销的目的，并相应地减少了对内存的需求．动态可抢占门限调度算法是将静态抢占门限算法与动态调度算法有机地结合在一起。完成了由静态到动态无缝转换．     

改进的最小空闲时间优先调度算法

最小空闲时间优先(least slack first,简称LSF)算法结合任务执行的缓急程度来给任务分配优先级.任务所剩的空闲时间越少,就越需要尽快执行.然而,LSF算法造成任务之间的频繁切换或严重的颠簸现象,增大了系统开销,并限制了其应用.在调度策略中设置抢占阈值可以减少任务之间的切换,但现有的抢占阈值设置方法因受到固定优先级的限制而不适用于LSF算法.为了减轻LSF算法的颠簸现象,基于抢占阈值的思想,提出适用于LSF算法的抢占阈值分配方法,动态地给每个任务配置抢占阈值.任务的抢占阈值是随着任务执行的缓急程度不同而动态地变化的,而且不受任务个数的限制.仿真结果表明,通过对LSF算法的改进,任务之间的切换大大减少,同时降低了任务截止期错失率.该改进型算法对设计和实现实时操作系统具有一定的参考价值.     

Hadoop集群环境下集成抢占式调度策略的本地性调度算法设计

在Hadoop集群环境下本地性调度算法是提高数据本地性的算法。本地性调度算法的调度策略的本质是提高数据本地性,减少网络传输开销,避免阻塞。但是由于Map任务的完成时间不同,Reduce任务存在的等待现象影响了作业的平均完成时间,使得作业的完成时间增加,进而引起系统的性能参数不佳。因此提出在保留原算法数据本地性要求的基础上集成可抢占式的调度方法。在Reduce任务等待时,挂起该任务并释放资源给其他Map任务,当Map任务完成到一定程度后,重新调度Reduce任务。基于上述调度策略设计了集成抢占式策略的本地性调度。为了对改进的算法进行验证,通过实验对本地性调度算法和集成抢占式本地性调度算法进行比较。实验结果表明,在相同数据上,集成抢占式本地性调度算法的平均完成时间有明显的降低。     

定时器驱动的RM调度机制建模及其性能优化

在Katcher等人对定时器驱动的RM(Rate Monotonic)调度机制研究的基础上,通过对该机制下实时任务抢占行为的分析,建立了周期性任务的抢占模型,给出了直接抢占发生的充分必要条件,据此确定了任务间的抢占关系,进而精确了可调性的判定条件,然后讨论了系统的平均响应时间．依据此抢占模型,受生物界寄生现象的启发,提出了一个改善嵌入式系统实时性能的方法,将获取机制和利用机制分离,屏蔽了复杂优化计算对目标嵌入式系统性能的负面影响．最后,通过实验验证了该方法在改善抢占关系、减少抢占开销和增强系统可调度性方面的有效性,结果表明可调度利用率可以提高0．25％～6．64％。     

基于动态抢占阈值的LSF调度算法

在最小空闲时间优先(LSF)调度算法中,当任务集中有多个任务的优先级相同或相近时,过多的上下文切换会产生“颠簸”现象,从而大幅增加系统开销。为此,结合LSF算法的特点,通过设计合理的动态抢占阈值,提出一种改进的调度算法DPTLSF。仿真结果表明,改进的算法能够大幅减少“颠簸”现象的发生,降低任务集的截止期错失率。     

DS-TE网络环境中新的LSP抢占策略

针对DS-TE的网络环境提出一种新LSP抢占策略,其基本思想是将避免级联抢占、减少受到影响的业务数量,以及避免因抢占带来的带宽浪费3个标准进行重要性排序,并依序优化抢占目标。其中,在避免带宽浪费方面,新策略使用一种层次逼近的规则,明显提高了对带宽抢占的约束程度。仿真实验的结果也表明对新策略的使用可以有效改善发生抢占时的网络性能。     

Bounding cache-related preemption delay for real-time systems

Cache memory is used in almost all computer systems today to bridge the ever increasing speed gap between the processor and main memory. However, its use in multitasking computer systems introduces additional preemption delay due to the reloading of memory blocks that are replaced during preemption. This cache-related preemption delay poses a serious problem in realtime computing systems where predictability is of utmost importance. We propose an enhanced technique for analyzing and thus bounding the cache-related preemption delay in fixed-priority preemptive scheduling focusing on instruction caching. The proposed technique improves upon previous techniques in two important ways. First, the technique takes into account the relationship between a preempted task and the set of tasks that execute during the preemption when calculating the cache-related preemption delay. Second, the technique considers the phasing of tasks to eliminate many infeasible task interactions. These two features are expressed as constraints of a linear programming problem whose solution gives a guaranteed upper bound on the cache-related preemption delay. This paper also compares the proposed technique with previous techniques using randomly generated task sets. The results show that the improvement on the worst-case response time prediction by the proposed technique over previous techniques ranges between 5 percent and 18 percent depending on the cache refill time when the task set utilization is 0.6. The results also show that as the cache refill time increases, the improvement increases, which indicates that accurate prediction of cache-related preemption delay by the proposed technique becomes increasingly important if the current trend of widening speed gap between the processor and main memory continues     

改进的抢占阈值调度任务响应时间分析方法

现有的基于抢占阈值调度的任务响应时间分析方法对实时任务系统进行可调度性判定时,对任务响应时间估计过低,造成任务错过期限的现象。针对上述缺点不足,该文提出改进的基于抢占阈值调度的任务响应时间分析方法,考虑了任务释放抖动和时钟嘀嗒调度的影响,使用改进的任务参数计算系统任务时间需求函数。仿真对比结果表明,改进后的方法较单纯固定优先级抢占阈值调度下的任务响应时间分析方法得到更加精确可调度性分析结果。     

Minimizing preemption cost for path selection in Diffserv-ware MPLS networks

Preemption is becoming an attractive strategy for bandwidth reservation and management in DiffServ-aware Traffic Engineering. In this paper, we propose an improved heuristic algorithm for the well-known optimization formulation based on versatile preemption policy, which can minimize the preemption cost with high accuracy and less computational intractability. Simulation results show that the proposed algorithm significantly outperforms well-known algorithms recently proposed in the literature. Moreover, we present a new path selection scheme to minimize preemption. Due to preemption of those LSPs that share more links with the selected path, the proposed scheme obviously minimize rerouting in DS-TE environments.     

改进的基于抢占阈值调度的任务响应时间分析方法

基于抢占阈值调度的任务响应时间分析方法是一种新型实时系统任务可调度性判定技术。然而已有的研究工作,有时对以前的任务请求检查过少,可能导致对响应时间估计过低。同时对任务响应时间的分析忽略了任务释放抖动和时钟嘀嗒调度对任务响应时间的影响,造成任务错过期限的现象,系统任务可调度性判定存在潜在的不精确因素。针对上述缺点不足,本文提出改进的基于抢占阈值调度的任务响应时间分析方法,在修正已有方法缺陷的同时,考虑任务释放抖动和时钟嘀嗒调度的影响,引入额外的时间需求,使用改进的任务参数计算系统任务时间需求函数。仿真对比结果表明,改进后的方法较单纯固定优先级抢占阈值调度下的任务响应时间分析方法得到更加精确可调度性分析结果。     

Minimizing Total Completion Time Subject to Job Release Dates and Preemption Penalties

Extensive research has been devoted to preemptive scheduling. However, little attention has been paid to problems where a certain time penalty must be incurred if preemption is allowed. In this paper, we consider the single-machine scheduling problem of minimizing the total completion time subject to job release dates and preemption penalties, where each time a job is started, whether initially or after being preempted, a job-independent setup must take place. The problem is proved to be strongly NP-hard even if the setup time is one unit. We also study a natural extension of a greedy algorithm, which is optimal in the absence of preemption penalty. It is proved that the algorithm has a worst-case performance bound of 25/16, even when the maximum completion time, i.e., makespan, criterion is considered simultaneously.     

Online deadline scheduling with preemption penalties

This paper presents a study of the problem of online deadline scheduling under the preemption penalty model of Zheng, Xu, and Zhang (2007). In that model, each preemption incurs a penalty of ρ times the weight of the preempted job, where ρ ? 0 is the preemption penalty parameter. The objective is to maximise the total weight of jobs completed on time minus the total penalty.     

Scheduling with job release dates, delivery times and preemption penalties

We consider in this paper the single-machine preemptive scheduling problem with job release dates, delivery times and preemption penalties, where each time a job is started, whether initially or after preemption, a job-dependent setup must take place. First, we prove that the problem is strongly NP-hard. Then, we present a dynamic programming algorithm and a polynomial time approximation scheme.     

Cache-Conscious Limited Preemptive Scheduling

In multi-tasking real-time systems, inter-task cache interference due to preemptions degrades schedulability as well as performance. To address this problem, we propose a novel scheduling scheme, called limited preemptive scheduling (LPS), that limits preemptions to execution points with small cache-related preemption costs. Limiting preemptions decreases the cache-related preemption costs of tasks but increases blocking delay of higher priority tasks. The proposed scheme makes an optimal trade-off between these two factors to maximize the schedulability of a given task set while minimizing cache-related preemption delay of tasks. Experimental results show that the LPS scheme improves the maximum schedulable utilization by up to 40\% compared with the traditional fully preemptive scheduling (FPS) scheme. The results also show that up to 20\% of processor time is saved by the LPS scheme due to reduction in the cache-related preemption costs. Finally, the results show that both the improvement of schedulability and the saving of processor time by the LPS scheme increase as the speed gap between the processor and main memory widens.